ICPC2020模拟测试赛总结
A
求满足 0 ≤ x ≤ a , 0 ≤ y ≤ b , 0 ≤ z ≤ c , 0 ≤ k ≤ d 0\le x\le a, 0\le y\le b, 0\le z\le c, 0\le k\le d 0≤x≤a,0≤y≤b,0≤z≤c,0≤k≤d的整数 x , y , z , k x,y,z,k x,y,z,k有多少组。
答案即：
∑ i = 0 d [ x i ] 1 − x a + 1 1 − x 1 − x b + 1 1 − x 1 − x c + 1 1 − x = ∑ i = 0 d [ x i ] ( 1 − x a + 1 ) ( 1 − x b + 1 ) ( 1 − x c + 1 ) ( 1 − x ) − 3 = ∑ i = 0 d [ x i ] ∑ j = 0 d ( 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 ) \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}) i=0∑d[xi]1−x1−xa+11−x1−xb+11−x1−xc+1=i=0∑d[xi](1−xa+1)(1−xb+1)(1−xc+1)(1−x)−3=i=0∑d[xi]j=0∑d2(j+1)(j+2)xj(1−xa+1−xb+1−xc+1+xa+b+2+xb+c+2+xc+a+2−xa+b+c+3)
枚举 j j j，计算不超过 d d d的项的系数和即可。
B
在 n × m ( 满 足 g c d ( n − 1 , m − 1 ) = 1 ) n\times m(满足gcd(n-1,m-1)=1) n×m(满足gcd(n−1,m−1)=1)的棋盘上沿 45 ° 45\degree 45°方向滚动一个球，直到球滚回原处，求经过奇数次的格子有多少个。
可以发现一定回经过角落原路返回，答案为2。
D
两个pokemon，血量分别为 h p 1 hp_1 hp1和 h p 2 hp_2 hp2，每回合有 p p p概率对1号造成 w w w伤害， 1 − p 1-p 1−p概率对2号造成 w w w伤害，求击杀一个的期望次数。
概率dp
E
一个序列，每次删一个数，代价为它和两边两个数之和的平方。求删到只剩端点两个数的最小代价。
（一开始以为要用四边形不等式优化，试了一发WA了（大概不满足单调性的条件？））
后来发现直接 n 3 n^3 n3区间dp就能过了。
H
队友写的 O ( n H ) O(nH) O(nH)DP。
I
队友写的，纯模拟
J
求 n × m n\times m n×m的棋盘从左上角到右下角一条长度为 k k k的路径。
大致想法是构建一条最长路径，然后根据需求裁弯取直。
最后没调出来。
投递京东等公司10个岗位 >
