Contest Info

practice link

Solutions

A. SelfDescFind

暴搜。

B. LollipopHoney

题目大意：有 \(n\) 种食物，每种有一个口味和一个美味度。现在要你选出 \(k\) 对食物，使得每对食物的口味都不相同，同时使美味度之和最大。同时还需要你求出选出最大值的方案数。

题解：选 \(k\) 对食物互不相同是一个经典结论。只要最多的口味也不超过总数的一半即可。如果不满足这个条件显然无法满足要求；如果满足这个要求，最大值任意和另一种口味配对，仍然满足要求。

在本题中，这个条件就等价于每种食物最多选 \(k\) 个，总共要选 \(2k\) 个。我们对每种食物保留最美味的 \(k\) 个，即可任意选择，那么我们肯定选前 \(2k\) 大的。

注意在统计方案时，我们就不能只保留前 \(k\) 个了，因为存在后面的和第 \(k\) 个一样大的可能。设 \(\min\) 表示 \(2k\) 个中最小的那个。如果第 \(k\) 个大于 \(\min\)，那么这种口味肯定是前 \(k\) 个全取了，只要乘一个组合数即可。否则的话需要对取 \(\min\) 的 \(dp\) 一下。

C. PrettyLiar

题目大意：两个人玩游戏，每人有一个长为 \(n\) 的队列，另外还有一个两人共用的数 \(S\le2\times10^{4}\)。每次当前的人把 \(S\) 减去队首，并把队首弹掉。如果 \(S\le0\)，那么这个人就输了。现在两个人的队列都可以重新排列，问 \((n!)^{2}\) 种可能中，先手获胜的有多少种。\(S\le\sum\text{All Elements}\)，\(n\le100\)，每个元素 \(\le100\)。

题解：容斥，恰好在第 \(i\) 回合结束的方案数即为前 \(i\) 回合结束的方案数减去前 \(i-1\) 回合结束的方案数。前 \(i\) 回合结束，即为要在两边分别选出一些元素使得它们的和大于等于 \(S\)。这可以用背包来解决。两边 merge 的时候可以通过前缀和线性完成。