小技巧（1）

DP瓶颈解决思路

有些时候我们可能会遇到在dp中状态开不下的问题，可以考虑把状态和存储内容互换，尽可能使状态简洁，同时不要过快否决转换的思想，正确性的证明？ ~（打完比赛再说，说不定试出来是对的呢）~ 除了知识储备还是要对自己有一点信心。

例：
接下来$n(1\le n\le 2000)$天，每天有$a_i(1\le a_i\le 5*10^5)$场比赛。

如果截止到第$i-1$天的胜率小于第$i$天的胜率，乐乐就会在第$i$天心情变得更好。否则，他的心情会变得更糟。其中，第$i$天的胜率指的是，当$i=0$时为$0$，否则指的是第$i$天之前玩游戏赢的次数总和除以第$i$天之前玩游戏的次数总和所得的值。

已知这$n$天，总共赢了$K(0 \le K\le \sum a_i)$次。求乐乐最多能开心多少天。

正常这题我们能想到开二维：第一维表示当前天数，第二维表示使用胜利数，存储的是最多快乐天数。

那这复杂度显然没法接受，其实我在赛时就想到了把存的最多快乐天数变成第二维“快乐天数”，之前的第二维变成存储的“达成最少使用的胜利数”，但我很快就意识到了他的正确性问题——他不一定是单调的（即有时候用的胜利数多了可能反而快乐天数少了），因此赛时我就陷入了瓶颈，最终没能切掉。

其实最后再观察观察，用不等式的一些变换就可以得到“真分数分子分母同加值会变大”这一结论，那只要他达不到1，如果拥有的胜利数多于最少需要的，我们尽可能把他往后堆，一旦先填满后面的几天，他的值就绝对是单增的，因此特判1的情况后他的正确性就可以保证了，至于1的情况那就只会快乐1天因为一直相等。

数量级小结论

把一个数划分成若干数的不同方案数我们称之为划分数，30的划分数在2000左右，50的划分数在$2*10^6$左右

图上小结论

有些时候我们可能需要求一棵树上的一个连着某些点的这么一个连通分量的大小，那我们可以考虑按随意顺序但是单环状求一遍两点之间路径（注意并非两两之间路径），即求包含$a_1,a_2,a_3...a_n$的连通分量的边数，我们可以求$a_1a_2,a_2a_3,a_3a_4...a_{n-1}a_n,a_na_1$之间的的路径数之和再除2（因为每条边刚好被算两遍），点数则为边数+1。

例：

给定一棵树，节点有编号，给最大边数，求连续编号在同一边数不超过最大边数的联通块的最多连续编号数量。

考虑尺取法，即一个一个点加入联通块，记录$ans=总边数*2$的值，加入时选新加点$u$在树上DFN序的前驱和后继（最后与最前互为前驱和后继），$ans+=Dis_{pre,u}+Dis_{u,nxt}-Dis_{pre,nxt}$，除去点时同理只需把符号反转，ans为总边数*2的性质依然成立。

正确性？

dfs时它走的顺序都是“前-x-后”，那它自然不会重复加一段已经加两遍且没被删一次的边（图为错误示范，即从已有红点选中绿点的并非黄点DFN序的前驱和后继，红边为原有加入的边，紫边为删掉的边，灰边为新加的边，棕边为重复加的边）