CF846.Div2 A~C

A. Hayato and School

题意：从序列中选 $3$ 个数使其和为奇数。

和为奇数只有两种情况，两偶一奇和全奇。

于是分别存储奇数偶数，然后分类讨论即可。

---

B. GCD Partition

题意：将序列划分为 $k$ 段，使得每段之和的最大公因数最大。

一开始想到了一个 DP 的思路。

设 $dp[i]$ 表示目前处理到第 $i$ 个数的最大答案。

显然有

$$dp[i]=\max\{\gcd(dp[j],sum[i]-sum[j]\}$$

由于 $k>1$ ，所以 $dp[n]$ 需要单独考虑。

这样可以写出一个 $O(n^2)$ 的 DP，但是会 TLE 。

将状态转移方程中的 $dp[j]$ 全部换掉，发现 是这样的一个形式：

$$\gcd(sum[i_1],sum[i_2]-sum[i_1],\dots,sum[i_k]-sum[i_{k-1}])$$

由辗转相除法，不难发现其实就是

$$\gcd(sum[i_1],sum[i_2],\dots,sum[i_k])$$

而 $sum[i_k]=sum[n]$ 。

且，$\gcd(x,y)\le \max(x,y)$ ，所以数越多，只可能变得越小。

所以答案就是

$$\max\Big(\gcd(sum[n],sum[i])\Big),i\in[1,n)$$

于是便可以 $O(n)$ 解决本题。

因为

---

C. Bon appetit!

题意：$n$ 个客人， $m$ 张桌子，每个客人有自己的口味，每个桌子只能上一种口味的菜。将所有客人分配到桌子上，并决定桌子的口味，使得被满足口味的客人最多。

这题好像出锅了，因此本场 unrated 了。

我用优先队列把每个口味的人数存了起来，然后贪心地从大到小分配到桌子，多出的人重新加入优先队列，这样也过了 pretests 。

因为没清空优先队列查了半天。

复杂度不会算。

---

unrated 了，也困了，不打了，睡觉了。