Codeforces Round #638 (Div. 2)

一个细菌，初始大小为$1$，每个周期内可选择分裂与否，周期结束时所有细菌大小$+1$，$T$组数据,给出$n$求最快多少周期可达到，输出每个周期分裂的数量

$1 \le t \le 1000,2\le n \le 1e9$

很容易想到每次全部分裂增长最快，但并不一定能满足准确到达$n$，记$S=\Sigma 2^k$，$S_t$为小于$n$中最大的数，只需要将$n-S_k$也插入序列即可，对于操作序列$1,2,4,···,n-S_k,···，2^{t-1},2^t$求差分数组记为所求，可以证得此方案下最优

$n$棵树每棵树上$a_i$个红果，$b_i$个蓝果，每个篮子容量为$k$，可以装同一棵树上的果实（条件一）或者颜色相同的果实（条件二），问最多使多少篮子恰好填满

$1 \le n,k \le 500,1\le a_i,b_i\le 1e9$

考虑到对于一棵树如果装在$t$个篮子中，一定可以使大于等于$t-1$个篮子满足条件一，因而所有最优解中存在一种方案使得每棵树最多提供一个满足条件二的篮子

因而记$f(i,j)$表示前$i$棵树装完剩余$j$个红果的最大篮子数,$S_i$表示前$i$棵树果子总和,可以推得剩余蓝果数量为$S_i-f(i,j)*k-j$

下面只简述存在条件二篮子的转移

枚举该篮子中红果数量$num_1$，蓝果为$k-num_1$；令$t_1=j-num_1+a_i,t_2=S_i-f(i,j)*k-j-k+num_1+b_i$

转移方程$f(i+1,t_1\%k)=max(f(i+1,t_1\%k),f(i,j)+1+t_1/k+t_2/k)$