解题报告以及数据

data.zip

A

B

C

dp[i]表示以i为终点递增的最重的一系列书的重量之和。

dp[i] = max(dp[i], dp[k] + weight[i]) (1 <= k <= i && weight[i] >= weight[k])

找到最大的dp[i]，那么需要移动的书的重量为所有书的重量sums - dp[i]。

D

两个人如果不会争吵的话连一条边，形成一个图，取这个图的反图。这个反图之间存在边则

说明这两个人不能在同一个team。首先二分染色看是否能够将反图变成一个二分图。

如果能染成二分图，记录每个二分图颜色人数。在某个联通分量里白色/黑色可以交换。

接下来用dp[i][j] = 1表示前i个联通分量能够形成一个人数为j的team.

然后在dp[num][s]里面遍历找到相差最小的team分法，输出答案，num为联通分量数。

E

点分治+启发式合并+可持久化线段树，出题人去非洲挖矿了，更详细的题解并没有...欢迎提出更高效做法

F

LIS 变形

G

签到题，按题意直接做就好了

H

N个球，M层，考虑在第K层扔下，如果碎了，则还有N-1个球，K-1层，如果没碎，则是N个球，M-K层，所以dp方程就是dp[n][m]=min{max(dp[n-1][k-1],dp[n][m-k])},1<=k<=m

I

J

K

考虑两个数列A[0]=1,A[1]=0,A[i]=A[i-1]+A[i-2]以及B[0]=0,B[1]=1,B[i]=B[i-1]+B[i-2],那么对于数列C[0]=x,C[1]=y,C[i]=C[i-1]+C[i-2],有C[i]=x*A[i]+y*B[i],所以预处理A，B数组与其前缀和（其实B数组也可以直接由A得出）就可以直接求出任意C数组，至此，线段树做法就比较明显了，每段记录SUM值，lazy标记记录的是add的x,y此时就和CF446C几乎没有区别了