CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

[[https://atcoder.jp/contests/abc178/tasks|Task Link]]

=====D题=====
枚举容器数 $i$，削去 $3*i$，剩余 $m$ 球装入 $i$ 个容器的方案。\\

解法一：视作 $i$ 种体积为 $1$、数量无限的物品装入容积为 $m$ 的完全背包

解法二：插板法 $C(i+m-1,i-1)$

=====F题=====
存在 $f[i]+g[i]>n$ 则无解（鸽巢原理）。\\

解法一：反序，设重叠部分值为 $i$，用两端均不等于 $i$ 的部分替换，可证 $n-a-b + a\cap b=n-f[i]-g[i]+a\cap b>= a\cap b$，故满足所有 $i$ 使得 $f[i]+g[i]<n$ 则有解。[[https://atcoder.jp/contests/abc178/submissions/16736765|code]]\\

解法二：按 $f[i]+g[i]$ 大小顺序匹配，选择一个 $i={\max\arg}_{i} f[i]+g[i]$，将之与任意 $j$ 匹配，问题规模化为 $n-1$，当存在 $j$ 使得 $f[i]+g[i]==f[j]+g[j]$ 均为最大值时，只剩两种元素，互相匹配即可。**待实现**

吐槽：比赛时候第一眼想到了无解证明以及反序，但是不会证有解、也不会解决反序的重叠问题，随即开始贪心匹配，各种贪，3个点死活被卡过不去。

CVBB ACM Team

用户工具

站点工具

页面工具