建议开题顺序：A,B1,B2,C,E,F,D1,D2。
A. Polycarp and Coins
记 \(k=\min(c1,c2)\)，则 \((c1-k)\times 1 +(c2-k)\times 2+k\times 3=n\)。注意到 \(n \mod 3\) 为 \(0,1,2\)。所以我们 \(|c1-c2|\) 最多为 \(1\)，只需要将 \(n \mod 3\) 给 \(1\) 或 \(2\) 即可。
B1. Wonderful Coloring - 1
记 \(cnt_i\) 表示 \(s_j=i\) 的数量。那么当 \(cnt_i \ge 2\) 时，我们能在里面随便拿两个，一个染成红色，一个染成绿色。当 \(cnt_i=1\) 时，记一共有 \(x\) 个。那么我们将其中 \(\lfloor \frac{x}{2} \rfloor\) 个染成红色，另外 \(\lfloor \frac{x}{2} \rfloor\) 个染成绿色。很显然剩下的点只能不染色。模拟即可。
B2. Wonderful Coloring - 2
模仿 B1 的思路。当 \(cnt_i \ge k\) 时，选其中 \(k\) 个染成 \(k\) 种颜色。当 \(1\le cnt_i <k\) 时我们将总数记录出来，然后均匀地染色即可。时间复杂度 \(O(n)\)。
代码
il void solve(){
n=rd,k=rd;
for(re int i=0;i<=n;++i) cnt[i]=0,v[i].clear();
for(re int i=1;i<=n;++i) ans[i]=0,s[i]=rd,++cnt[s[i]],v[s[i]].push_back(i);
int c1=0,c2=0;
for(re int i=1;i<=n;++i)
if(cnt[i]>=1&&cnt[i]<k){
c1+=cnt[i];
}
for(re int i=n;i>=1;--i)
if(cnt[i]>=1&&cnt[i]<k){
if(c1%k!=0) c1-=min(cnt[i],(c1%k));
}
int U=1,c_=0;
for(re int i=1;i<=n;++i)
if(cnt[i]>=k){
int cc=0;
for(auto x:v[i]){
ans[x]=++cc;
if(cc==k) break;
}
}
else{
for(auto x:v[i]){
if(c_>=c1) break;
++c_,U++,U%=k;
if(!U) U=k;
ans[x]=U;
}
}
for(re int i=1;i<=n;++i) cout<<ans[i]<<" ";
cout<<"\n";
return ;
}
C. Interesting Story
记 \(f_{i,j}\) 为第 \(i\) 个字符串中 \(s_{k}=j\) 的数量与 \(s_k \ne j\) 的差。那么对于一个字符 \(x\)，记我们选择的字符串下标为 \(p_1 \dots p_m\)，则：\(\sum\limits_{i=1}^{m} f_{p_i,x} >0\)。暴力枚举最多的字符是哪个，则每次贪心地选 \(f_{i,j}\) 大的，只要和不小于 \(1\) 即可。
D1. Domino (easy version)
暴力分类讨论题。这里我们令 \(m\) 为偶数。如果读入的 \(m\) 为奇数，旋转矩阵即可。如果 \(k=0\)，当 \(n\) 为偶数时有解（全构造竖的），否则无解。如果 \(k \ne 0\)，我们考虑将前面的若干行填满（因为 \(m\) 为偶数，所以只要数量足够多就可以），记填满了 \(x\) 行，最后剩下 \(y\) 个。当 \(n-x\) 为偶数时，如果 \(y\) 也为偶数，则我们可以构造将 \(\frac{y}{2}\) 个放在第 \(x+1\) 行的前面，其它的放第 \(x+2\) 行的前面，就能保证每一列后面还没填的空为偶数个（每两个放一个竖的就行了）；否则无解。当 \(n-x\) 为奇数时，此时我们将第 \(x\) 行的一半放下来，到第 \(x+1\) 行就能保住合法了；否则无解。这里需要注意我们 \(x\ge 1\)。
然后就判断完了。
D2. Domino (hard version)
将 D1 的所有合法情况分别构造即可，但是有点麻烦。
E. Fixed Points
考虑 DP。定义状态函数 \(f_{i,j}\) 表示前 \(i\) 个数，删了 \(j\) 个位置时的最大匹配价值。然后 \(O(n^2)\) 就做完了。
F. Equidistant Vertices
注意到当 \(k>2\) 时我们选出来的点满足：任意两个点的 \(\operatorname{LCA}\) 相同，且距离 \(\operatorname{LCA}\) 的距离相等。然后暴力做背包就行了，时间复杂度 \(O(n^4)\)。
标签：cnt,cc,题解,染成,偶数,ge,734,Div,c1 From： https://www.cnblogs.com/harmisyz/p/18667106