ICPC2020模拟测试赛总结

A

求满足$0\le x\le a,0\le y\le b,0\le z\le c,0\le k\le d$的整数$x,y,z,k$有多少组。

答案即：
$$\begin{gathered} \sum _{i=0}^d[x^i]\frac{1-x^{a+1}}{1-x}\frac{1-x^{b+1}}{1-x}\frac{1-x^{c+1}}{1-x} \\ =\sum _{i=0}^d[x^i](1-x^{a+1})(1-x^{b+1})(1-x^{c+1})(1-x{)}^{-3} \\ =\sum _{i=0}^d[x^i]\sum _{j=0}^d\frac{(j+1)(j+2)}{2}{x}^j(1-x^{a+1}-x^{b+1}-x^{c+1}+x^{a+b+2}+x^{b+c+2}+x^{c+a+2}-x^{a+b+c+3}) \end{gathered}$$
枚举$j$，计算不超过$d$的项的系数和即可。

B

在$n\times m(满足gcd(n-1,m-1)=1)$的棋盘上沿$45°$方向滚动一个球，直到球滚回原处，求经过奇数次的格子有多少个。

可以发现一定回经过角落原路返回，答案为2。

D

两个pokemon，血量分别为$h{p}_1$和$h{p}_2$，每回合有$p$概率对1号造成$w$伤害，$1-p$概率对2号造成$w$伤害，求击杀一个的期望次数。
概率dp

E

一个序列，每次删一个数，代价为它和两边两个数之和的平方。求删到只剩端点两个数的最小代价。

（一开始以为要用四边形不等式优化，试了一发WA了（大概不满足单调性的条件？））
后来发现直接$n^3$区间dp就能过了。

H

队友写的$O(nH)$DP。

I

队友写的，纯模拟

J

求$n\times m$的棋盘从左上角到右下角一条长度为$k$的路径。

大致想法是构建一条最长路径，然后根据需求裁弯取直。
最后没调出来。