四 倍 役 满
传送门勇者比太郎看懂题后可以发现,我们要求每个 J 右边的 O 的数量乘下面的 I 的数量之和。预处理前缀和后枚举每个 J 计算即可。代码画展先以 $V_i$ 为第一关键字、$S_i$ 为第二关键字对所有画排个序,以 $C_i$ 为关键字对所有画框排序。然后从后往前扫,如果当前的画能装进没有装画的 $C$ 最大的画框里,就把它装进去。正确性比较显然?反正我不会证代码有趣的家庭菜园 3设 $d...
CodeForcesLuogu翻译分析考虑一个$O(n^2)$的DP。设$f[i][j]$表示以$i$为根的子树内到$i$的距离为$j$的点的个数。$\large f[i][j]=\sum f[son][j-1]$发现这个方程极其眼熟(雾)。还是假设只有一个儿子,方程变为$\large f[i][j]=f[son][j-1]$写成指针形式:$f[i]=f[son]-1$然后就可以上长链剖分了...
BZOJ分析长链剖分入门题。接着原题推。之前那样子是$O(n^2)$的,考虑继续优化。注意转移时的式子:$\large f[i][j]=\sum f[son][j-1]$$\large g[i][j]=\sum \Big(g[son][j+1]+f[i][j]\times f[son][i-1]\Big)$如果只有一个儿子,就变成了$\large f[i][j]=f[son][j-1]$$\...