比赛:Codeforces Round #429 (Div. 2)
时间:2017.8.1晚
这次感觉状态不好,就去打div2了
A:有\(26\)种颜色的气球,每种的数量不一样,你要把这些气球分给\(k\)个人,使得每个人拿到的气球中没有两个颜色相同的。
直接判断每种颜色的气球是否大于\(k\)个。
B:有一个序列,两个人轮流决策(第一个人先):第一个人可以删掉一个元素和为奇数的子串,第二个人可以删掉一个元素和为偶数的子串。无法选的人输。问你谁能获胜。
可以证明,如果这个序列有至少一个奇数,那么先手获胜。否则后手获胜。证明:如果有奇数个奇数,先手可以直接选完,如果有偶数个奇数(大于\(1\)个),先手可以随便选,后手无法一次选完,先手第二次决策时可以选完。如果没有奇数,先手第一次决策时无法选择满足要求的子串。
C:有两个序列\(a,b\),你要把\(b\)重新调整顺序,使得\(\sum_{i=1}^nF(a_i,b_i)\)最小。\(F(n,k)\)是$1\ldots n \(中选\)k$个数中最小元素的期望。
我们先推一下看看这个式子是什么:
\[F(n,k)=\frac{1\times\binom{n-1}{k-1}+2\times\binom{n-2}{k-1}+\cdots+(n-k+1)\times\binom{k-1}{k-1}}{\binom{n}{k}}\]
好像我推不出来啊。。。(结果是\(\frac{n+1}{k+1}\))那我就直接说结论了(可以通过观察样例猜出来):把\(a\)中最小的数与\(b\)中最小的数对齐,把\(a\)中第二小的数与\(b\)中第二小的数对齐。。。
D:有一个连通图,你要选出一些边使得有一些点的度数为奇数,有一些点的度数为偶数,有一些点的度数没有限制。
先找出这个图的一棵生成树,然后会发现非树边是没有影响的。你可以选出非树边,然后把路径上的树边反向。然后就是一个简单的树形DP了。
E:有一个序列,你要统计有多少个排列满足相邻两个数的积不是完全平方数。
我们先把每个数的完全平方的因子删掉,这样两个数的积是完全平方数就等价于两个数相同。然后DP:\(f_{i,j}\)表示前\(i\)种数放完后有\(j\)组相邻且相同的数。转移时枚举下一种数分成几块(\(k\))和这\(k\)块中有几块插到前面的\(j\)块中(\(l\))。转移:
\[f_{i+1,j+a_{i+1}-k-l}=f_{i,j}\times\binom{a_{i+1}-1}{k-1}\times\binom{j}{l}\times\binom{(\sum_{o=1}^{i-1}a_o)-j+1}{k-l}\]
你没看错,时间复杂度是\(O(n^4)\)的,但是能跑过去。