很高兴给大家出题，本次难度低于上一场，新生的六个题都可以直接裸递归式或者裸递推式解决，对于老生的汉诺塔3，需要找出一般式，后两题分别为裸ST算法（或线段树）/线性DP。

正确的难度顺序为

一、种花

本题很容易能推出递推式或者一般式，对于第一快地，有3种种植方法，对于后面的每一快地有不同于前一块地的两种种植方法。

a₁ = 3；
a_n = 2*（a_n-1）；

代码：

 #include <bits/stdc++.h>

 using namespace std;

 int a[];

 void init(){

     a[] = ;

     for(int i = ; i <= ; i++){

         a[i] = a[i-]*;

     }

 }

 int main(){

     freopen("test.out","w",stdout);

     int n;

     init();

     while(cin>>n){

         cout << a[n] << endl;

     }

     return ;

 }

二、角谷定律

本题按照给出的式子操作即可，用另外一个变量记录操作次数。

代码：

 #include <bits/stdc++.h>

 using namespace std;

 int cnt = ;

 void fun(long long n){

     if(n == )

         return ;

     if(n&)

         cnt++,fun(*n+);

     else

         cnt++,fun(n/);

 }

 int main(){

     int n;

     freopen("test.in","r",stdin);

     freopen("test.out","w",stdout);

     while(cin>>n){

         cnt = ;

         fun(n);

         cout << cnt << endl;

     }

     return ;

 }

三、猴子和椰子

可能你们也在其他地方看见过本题，设初始椰子为A，最后一次分给每个人的椰子为n，很容易推得一个A关于n得常数式子，因为要保证能够按照题目分下去，所以要保证每次分椰子都为正整数，已得答案为15621（5^6 - 4）。算是个小学数学题。

输出15621即可。

四、汉诺塔1

这是一个汉诺塔的基本变式，其实用汉诺塔的思想去想也不难，要移动n根木根从A至C，可划分为下面几个步骤。

先移动n-1根木根到C
移动第n根木棍到B
移动C上的n-1根木棍到A
移动B上的第n根木棍到C
移动A上的n-1根木棍到C

至此，完成这个汉诺塔的移动，我们把移动n根木棍从A到C计为F(n)。

则F(n） = F(n-1) + 1 + F(n-1) + 1 + F(n-1) = 3*F(n-1) + 2；且F(1) = 2;

按照这个步骤写出递归函数即可。代码：

 #include <bits/stdc++.h>

 using namespace std;

 long long fun(int n){

     if(n == )

         return ;

     return *fun(n-)+;

 }

 int main(){

     freopen("test.in","r",stdin);

     freopen("test.out","w",stdout);

     int n;

     while(cin>>n){

         cout << fun(n) << endl;

     }

     return ;

 }

五、汉诺塔2

在汉诺塔1的基础上多了可以把最长的木棍放在最上面，还是按照上面的步骤，移动n根木棍从A到C可划分为

移动n-1根木棍从A到B
移动第n根木棍到B上
移动第n根木棍到C上
移动n-1根木棍从B到C

至此，完成汉诺塔的移动，我们把移动n根木根从A到C计为F(n)，移动n根木棍到邻柱子计为T(n)，关于T(n)的公式这里就不推了，演变方式一样。

所以有F(n) = T(n-1)+1+1+T(n-1) = 2*T(n-1)+2；且F(1) = 2;

代码：

 #include <bits/stdc++.h>

 using namespace std;

 int fc(int n){

     if(n == )

         return ;

     return *fc(n-)+;

 }

 int fun(int n){

     if(n == )

         return ;

     return *fc(n-)+;

 }

 int main(){

     freopen("test.in","r",stdin);

     freopen("test.out","w",stdout);

     int n;

     while(cin>>n){

         cout << fun(n) << endl;

     }

     return ;

 }

六、整数划分

其实这个题题面以及给出了一点提示，把n分成m个正整数的和，要直接求n的划分个数比较难，但是我们可以求n-1、n-2,,,的划分，设n = ΣD_i，且max(D_i) <= k，

即Di为n的一种划分方案，最大数字不超过k，把它计为F(n,k)，那么本题也就是求F(n,n)；根据 n，k的不同大小关系，可得下列递归式

F(n, k) = 1; (n =1 or k = 1)
F(n, k) = F(n, n); (n < k)
F(n, k) = F(n, k-1) + 1; (n = k)
F(n, k) = F(n-k, k) + F(n, k-1); (n > k)

所以可以写出代码：

 #include <bits/stdc++.h>

 using namespace std;

 int fun(int n,int m){

     if(n ==  || m == )

         return ;

     else if(n < m)

         return fun(n,n);

     else if(n == m)

         return fun(n,n-)+;

     else if(n > m)

         return fun(n,m-)+fun(n-m,m);

 }

 int main(){

     freopen("test.in","r",stdin);

     freopen("test.out","w",stdout);

     int n;

     while(cin>>n){

         cout << fun(n,n) << endl;

     }

     cerr << clock() << endl;

     return ;

 }

七、跳台阶

其实很容易推出对于n阶台阶的方案有

F(n) = Σ(F(n-P_i)); (P1 = 1，Pi = 质数集合)

边界条件F(1) = F(0) = 1;

所以代码显而易见了，其实本题还想卡一下数据范围，因为34好像就会爆int，还是算了，就只给你们弄到30，而且本题开了4s，其实我STD只跑了1.7s，奈何只能取整，干脆就4s得了。

代码：

 #include <bits/stdc++.h>

 using namespace std;

 int prime[],primesize,phi[];

 bool isprime[];

 int n;

 void getlist(int listsize){

     memset(isprime,,sizeof(isprime));

     isprime[]=false;

     for(int i=;i<=listsize;i++)

     {

         if(isprime[i])prime[++primesize]=i;

          for(int j=;j<=primesize&&i*prime[j]<=listsize;j++)

          {

             isprime[i*prime[j]]=false;

             if(i%prime[j]==)break;

         }

     }

     prime[] = ;

 }

 int fun(int n){

     int sum = ;

     if(n ==  || n == )

         return ;

     for(int i = ; i <= primesize; i++){

         if(n < prime[i])

             break;

         sum += fun(n-prime[i]);

     }

     return sum;

 }

 int main(){

     freopen("test.in","r",stdin);

     freopen("test.out","w",stdout);

     ios_base::sync_with_stdio(false);

     getlist();

     int n;

     while(cin>>n){

         cout << fun(n) << endl;

     }

     cerr << clock() <<endl;

 }

八、汉诺塔3

四柱汉诺塔问题，我都懒得写如何推了，易得下面递归式

F(n) = min(2*F(n-r)+2^r-1)，1 <= r <= n；

但是直接用上面式子写递归式肯定会时间爆炸，不信你试试。

最大n不超过100，所以其实你先递推出任意一项就可以了= =，这样的话预处理时间为O(n²)，查询时间为O(1)。为了你们好= =所以我没有卡这种算法。

但其实也可以得出一般式，根据Frame-Stewart算法可得出当r = floor((sqrt(8*n+1)-1)/2)时，有最小值，且最小值F(n) = (n - (r²-r+2)/2)*2^r+1；

即可以在O(1)时间内得出任意n根木棍需要的最小转移次数。

代码：

 #include <bits/stdc++.h>

 using namespace std;

 int a[] = {};

 int init(){

     fill(a,a+,0x3f3f3f3f);

     a[] = ,a[] = ,a[] = ;

     for(int i = ; i <= ; i++){

         for(int j = ; j < 32; j++){

             temp = *a[j]+pow(2LL,(long long)j)-;

             a[i] = min(a[i],temp);

         }

     }

 }

 int main(){

     freopen("test.in","r",stdin);

     freopen("test.out","w",stdout);

     int n;

     while(cin>>n){

         int r = floor((sqrt(*n+)-1.0)/2.0);

         int ans = (n-(r*r-r+)/2.0)*pow(2.0,r)+;

         cout << ans << endl;

     }

     cerr << clock() << endl;

     return ;

 }

九、夏目友人帐（一）

经典RMQ问题，ST/线段树都可以。

本来想卡线段树做法，想了一下不卡算了= =。

代码：

 #include <bits/stdc++.h>

 using namespace std;

 //线段树

 #define lson l,m,p<<1

 #define rson m+1,r,p<<1|1

 #define Max(a,b) (a<b?b:a)

 #define Min(a,b) (a<b?a:b)

 #define INF 999999999

 int N,M;

 int MaxP[*+];

 int maxT;

 void Update(int val,int K,int l,int r,int p){

     int m=(l+r)>>;

     if(l==r){

         MaxP[p]=val;

         return;

     }

     if(K<=m)

         Update(val,K,lson);

     else

         Update(val,K,rson);

     MaxP[p]=Max(MaxP[p<<],MaxP[p<<|]);

 }

 void Query(int L,int R,int l,int r,int p){

     int m=(l+r)>>;

     if(L<=l&&r<=R){

         maxT=Max(maxT,MaxP[p]);

         return;

     }

     if(L<=m)

         Query(L,R,lson);

     if(R>=m+)

         Query(L,R,rson);

 }

 int main(){

     freopen("test2.in","r",stdin);

     freopen("test2.out","w",stdout);

     int i,val,a,b;

     scanf("%d %d",&N,&M);

     for(i=;i<=N;i++){

         scanf("%d",&val);

         Update(val,i,,N,);

     }

     for(i=;i<=M;i++){

         scanf("%d %d",&a,&b);

         maxT=;

         Query(a,b,,N,);

         printf("%d\n",maxT);

     }

     cerr << clock() << endl;

     return ;

 }

 //ST算法

 int N,M;

 int A[];

 int FMax[][];

 void Init(){

     int i,j;

     for(i=;i<=N;i++)

         FMax[i][]=A[i];

     for(i=;(<<i)<=N;i++){

         for(j=;j+(<<i)-<=N;j++){

             FMax[j][i]=max(FMax[j][i-],FMax[j+(<<(i-))][i-]);

         }

     }

 }

 int Query(int l,int r){

     int k=(int)(log(r-l+)/log());

     return max(FMax[l][k],FMax[r-(<<k)+][k]);

 }

 int main(){

     freopen("test1.in","r",stdin);

     freopen("test1.out","w",stdout);

     int i,a,b;

     scanf("%d %d",&N,&M);

     for(i=;i<=N;i++)

         scanf("%d",&A[i]);

     Init();

     for(i=;i<=M;i++){

         scanf("%d %d",&a,&b);

         printf("%d\n",Query(a,b));

     }

     cerr << clock() << endl;

     return ;

 }

十、夏目友人帐（二）

这里就不说怎么推的了，到时候认真听我黑板上讲23333。

代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N = ;

 const int Q = ;

 int f[Q][N][N];

 int p[Q];

 int c[N][N];

 int main(){

     freopen("test3.in","r",stdin);

     freopen("test3.out","w",stdout);

     ios_base::sync_with_stdio(false);

     cin.tie();

     cout.tie();

     int n,q;cin>>n>>q;

     for(int i = ; i <= n; i++){

         for(int j = ; j <= n; j++){

             cin>>c[i][j];

         }

     }

     for(int i = ; i <= q; i++){

         cin>>p[i];

     }

     memset(f,0x3f,sizeof(f));

     int INF = f[][][];

     p[] = ;

     f[][][] = ;

     for(int i = ; i <= q; i++){

         for(int x = ; x <= n; x++){

             for(int y = ; y <= n; y++){

                 if(x != p[i] && y != p[i])

                     f[i][x][y] = min(f[i][x][y],f[i-][x][y]+c[p[i-]][p[i]]);

                 if(p[i] != y && p[i] != p[i-])

                     f[i][p[i-]][y] = min(f[i][p[i-]][y],f[i-][x][y]+c[x][p[i]]);

                 if(p[i] != x && p[i] != p[i-])

                     f[i][x][p[i-]] = min(f[i][x][p[i-]],f[i-][x][y]+c[y][p[i]]);

             }

         }

     }

     int ans = INF;

     for(int i = ; i<= n; i++){

         for(int j = ; j<= n; j++){

             ans = min(ans,f[q][i][j]);

         }

     }

     cout << ans << endl;

     cerr << clock() << endl;

     return ;

 }

P.S. 其实很多题目都可以卡你们算法，不卡不卡，怕被打= =，后面给你们出卡常数233333

第二场周赛（递归递推个人Rank赛）——题解

一、种花

二、角谷定律

三、猴子和椰子

四、汉诺塔1

五、汉诺塔2

六、整数划分

七、跳台阶

八、汉诺塔3

九、夏目友人帐（一）

十、夏目友人帐（二）

第二场周赛（递归递推个人Rank赛）——题解的相关教程结束。

相关推荐

AcWing 4798. 打怪兽题解

AcWing 4797. 移动棋子题解

P1941 [NOIP2014 提高组] 飞扬的小鸟题解

P1880 [NOI1995] 石子合并题解

P5020 [NOIP2018 提高组] 货币系统题解

【青少年CTF】Crypto-easy 题解小集合

AcWing 4799. 最远距离题解

第十三届蓝桥杯c++b组国赛题解（还在持续更新中...）

第二场周赛（递归递推个人Rank赛）——题解

一、种花

二、角谷定律

三、猴子和椰子

四、汉诺塔1

五、汉诺塔2

六、整数划分

七、跳台阶

八、汉诺塔3

九、夏目友人帐（一）

十、夏目友人帐（二）

第二场周赛（递归递推个人Rank赛）——题解的相关教程结束。

相关推荐

AcWing 4798. 打怪兽题解

AcWing 4797. 移动棋子题解

P1941 [NOIP2014 提高组] 飞扬的小鸟 题解

P1880 [NOI1995] 石子合并 题解

P5020 [NOIP2018 提高组] 货币系统 题解

【青少年CTF】Crypto-easy 题解小集合

AcWing 4799. 最远距离题解

第十三届蓝桥杯c++b组国赛题解（还在持续更新中...）

P1941 [NOIP2014 提高组] 飞扬的小鸟题解

P1880 [NOI1995] 石子合并题解

P5020 [NOIP2018 提高组] 货币系统题解