<span>CF1348D. Phoenix and Science</span>
题目地址：http://codeforces.com/contest/1348/problem/D
大意：第一天有一个细胞质量为1，每一天白天细胞可以发生分裂（任意个发生分裂，前后质量守恒），晚上细胞质量增加（每个细胞质量增加1）。给定一个n，问至少要多少天，细胞总质量恰好达到为n（2≤n≤1e9）。
分析：
先考虑分裂，分裂不会对细胞的总质量带来任何影响，只是会影响晚上细胞质量增加的值。若当前细胞数量为x，那么晚上细胞可以增加的质量dm满足x≤dm≤2x。
我们可以确定的是细胞增加最快的情况是：每一天白天所有细胞都发生分裂。但是这样不能保证最后细胞总质量恰好达到n。
计算x为满足的最大值n≥20+21+...+2x，令sum=20+21+...+2x,若sum==n,那么每天全部分裂即可。否则将n-sum插入增加的队列。排序。可以证明这样天数最少。
证明过程：
设最少经过d天细胞总质量m可以满足m≥n。要让m尽可能块的增加，那么每一天白天所有细胞都应该进行分裂，d应该等于x或x+1（当n=20+21+...+2x时d=x，否则d=x+1）,可以发现上面算法所求出来的天数恰好等于让m满足m≥n的最小的天数。说明这样求出来的天数最少。
上面我们已经得到了一个结论若当前细胞数量为x，那么晚上细胞可以增加的质量dm满足x≤dm≤2x。可以发现将n-sum插入并排序后，是可以让细胞数量和增加数量是满足这样的关系的。所以这样的增加是可行的。
而每天细胞分裂的数量应该书细胞增加数量的增量。所以最后差分就是答案了。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,int> P; const int INF=0x3f3f3f3f; const LL LINF=0x3f3f3f3f3f3f; const int MAX_N=1e5+20; const LL MOD=1e9+7; LL n; int t; int main(){ //freopen("1.txt", "r", stdin); //ios::sync_with_stdio(false); //cin.tie(0),cout.tie(0); scanf("%d",&t); while(t--){ scanf("%I64d",&n); vector<LL> V; LL sum=0; for(LL i=1;sum+i<=n;i*=2){ sum+=i; V.push_back(i); // cout<<i<<endl; //cout<<sum<<endl; } if(sum<n){ V.push_back(n-sum); } sort(V.begin(),V.end()); int len=V.size(); printf("%d\n",len-1); for(int i=1;i<len;i++){ printf("%I64d ",V[i]-V[i-1]); } printf("\n"); } }
