题目链接：https://codeforces.com/contest/841
签到题，用一下鸽巢原理。
题意：有一个n个元素的正整数序列，两个玩家轮流操作，玩家A先操作。玩家A每次可以选连续的一段元素，满足：他们的和为奇数，然后删除选择的元素，玩家B每次可以选连续的一段元素，满足：他们的和为偶数，然后删除选择的元素。每次删除完元素过后，剩余的部分会重新连接在一起。谁无法操作谁就输。问最优策略下谁会赢。
题解：显然假如全部元素的和为奇数，就是A赢。否则假如全部元素都是偶数，那么就是B赢。会不会有B赢的其他情况呢？既然是B赢，那么必然是B操作最后一步，也就是最后一步必定全部元素的和为偶数，由于是A先操作，假如一开始全部元素的和为偶数，且至少有一个奇数，已知就是至少有两个奇数，那么A肯定取走奇数的一部分，剩下的一部分和也是奇数，也就是只有当A起手不能操作的时候B才能赢。然后马上就能发现必胜策略：把最后一个奇数左边的一段在第一步都拿走。
题意：定义一个函数 \(F(n,k)\) 表示在 \([1,n]\) 中选 \(k\) 个元素形成的子集，然后取每个子集的最小值的数学期望。给两个长度都是 \(m\) 的正整数数组 \(A\) 和 \(B\) ，满足 \(min(A)\geq max(B)\) ，重新排列 \(A\) ，使得 \(\sum\limits_{i=1}^{m}F(A'_i,B_i)\) 最大，这里的 \(A'\) 表示重新排列之后的数组 \(A\) 。
题解：看了一下样例貌似是大的配小的这样排序，但是不知道会不会有坑。用微扰法观察：设 \(A_1\leq A_2\) 且 \(B_1\leq B_2\) ，则 \(F(A_1,B_1)+F(A_2,B_2)\leq F(A_1,B_2)+F(A_2,B_1)\) 是否成立？先考虑 \(F(n,k)\) 本身有什么性质，首先当 \(k\) 不变且 \(n\) 变大，答案显然变大；当 \(n\) 不变 且 \(k\) 变大，就感觉不是特别明显。考虑
\(F(6,1)=\frac{1}{6}(1+2+3+4+5+6)=\frac{7}{2}\)
\(F(6,2)=\frac{1}{15}(1*5+2*4+3*3+4*2+5*1+6*0)=\frac{1}{15}(5+8+9+8+5+0)=\frac{7}{3}\)
\(F(6,3)=\frac{1}{C_6^3}(1*C_5^2+2*C_4^2+3*C_3^2+4*C_2^2+5*C_1^2+6*C_0^2)=\frac{7}{4}\)
\(F(6,4)=\frac{1}{C_6^4}(1*C_5^3+2*C_4^3+3*C_3^3+4*C_2^3+5*C_1^3+6*C_0^3)=\frac{7}{5}\)
\(F(6,5)=\frac{1}{C_6^5}(1*C_5^4+2*C_4^4+3*C_3^4+4*C_2^4+5*C_1^4+6*C_0^4)=\frac{7}{6}\)
\(F(6,6)=\frac{1}{C_6^6}(1*C_5^5+2*C_4^5+3*C_3^5+4*C_2^5+5*C_1^5+6*C_0^5)=\frac{7}{7}\)
貌似 \(F(n,k)=\frac{n+1}{k+1}\) ，假如这个式子成立，就能够说明 \(F(A_1-1,B_1-1)+F(A_2-1,B_2-1)=\frac{A_1B_2+A_2B_1}{B_1B_2}\leq F(A_1-1,B_2-1)+F(A_2-1,B_1-1)=\frac{A_1B_1+A_2B_2}{B_1B_2}\) 。所以贪心的策略确实就是上述的大数配小数。不过这个期望是怎么准确计算呢？
由上面的算法可知： \(F(n,k)=\sum\limits_{i=1}^{n}i*C_{n-i}^{k-1}\frac{n+1}{k+1}\)
Codeforces Round #429 (Div. 2)
原文：https://www.cnblogs.com/KisekiPurin2019/p/12327248.html