细胞分裂 题解

看图：

统计，找规律：

易得：每一个时间对应的红球排列都应被分成两部分（即红线处分割） 上半部分的每一排都是上一个小时的*2 ，下半部分直接把上个小时的移过来。

先预处理k小时后总共有多少个红球（总数！一大块里的“总”红球数！），每个小时一个红球变三个，所以共3^k个 把上面分析时两部分翻译一下：

定义一个函数dfs(nn,kk)，表示第k/小时，1~nn红球的总数 1.上半部分（即nn<=2^(k-1)） 返回dfs(nn,kk-1)*2

2.下半部分 返回dfs(nn-2^(k-1),k-1)

注意！边界！

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,k,a,b,cnt,sum_red[50];
int dfs(int nn,int kk){
	if(nn<=0)return 0;
    if(kk<=0)return 1;
    if(nn<=(1<<kk-1))return dfs(nn,kk-1)<<1;
    return dfs(nn-(1<<(kk-1)),kk-1)+(sum_red[kk]<<1);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>t;
	sum_red[1]=1;
	for(int i = 2;i<=31;i++)sum_red[i]=sum_red[i-1]*3;
	while(t--){
	 	cin>>k>>a>>b;
	 	cnt++;
	 	cout<<(dfs(b,k)-dfs(a-1,k))<<'\n';
	 }
	return 0;
}

1、不难想到递归

2、不难想到区间统计利用前缀和相减

设 f(k, x) 表示经过 k 个时间后，前 x 行的红细胞总数

则第 x 行 ~ 第 y 行的红细胞数量 = f(k,y)-f(k,x-1)

递归函数 f(k,x)

1、递归边界？

k=0 时 f(0,i)=1

i=0 时 f(k,0)=0

2、递归式？

f(k,i) 与 f(k-1, ?) 的关系？