CF1928 题解

· · 题解

\rm A.\ Rectangle\ Cutting

纸片按照某一条边切成两份，拼接肯定按照另一条边拼。因此 x,y 都是奇数必然无解，都是偶数必然有解。否则我们切开偶数的一边，然后拼起来奇数的另一边，这种情况仍然无解的条件是偶数一侧恰好是奇数一侧长度的 2 倍。

\rm B.\ Equalize

重复的元素必然不可能变得相同，先排序去重。

现在数组是有序的，记最的最终方案中，出现次数最多的数最靠左出现在 l，最靠右出现在 r，可以通过调整法证明存在一种方式使得 [l,r] 内都为这个数。于是双指针找到一个最长的极差 <n 的区间即可。

\rm C.\ Physical\ Education\ Lesson

考虑 k 合法的条件。题目里告诉我们循环节长度为 2k-2，我们就直接用。

如果 (n-1)\bmod(2k-2)<k，说明 x 这个数在第一个循环节中出现在前半段，此时若 (n-1)\bmod(2k-2)=x-1 则合法。

如果 (n-1)\bmod(2k-2)\geq k，说明 x 这个数在第一个循环节中出现在后半段，此时若 (n-1)\bmod(2k-2)=2k-1-x 则合法。

换个视角。第一种情况，一个 k 合法的条件是 \exists t\in Z,t(2k-2)=n-x 且 k\geq x。暴力枚举 n-x 的因数判断即可。

第二种情况，一个 k 合法的条件是 \exists t\in Z,(t+1)(2k-2)=n+x-2 且 k\geq x+1。暴力枚举 n+x-2 的因数判断即可。注意去重。

\rm D.Lonely\ Mountain\ Dungeons

每类人的贡献是独立的。假设我们知道总共分了 x 组，那么我们可以枚举每类人计算其贡献。将 S 个同类人分在 x 组内的贡献是组内人数两两乘积和的 b 倍，平方公式拆一下可知我们要最小化平方和，也即平均分，具体来说，有 \displaystyle x-S\bmod x 组有 \displaystyle\lfloor\frac{S}{x}\rfloor 人，\displaystyle S\bmod x 组有 \displaystyle\lfloor\frac{S}{x}\rfloor+1 人，贡献可以 O(1) 计算。

问题在于要枚举两维。我们发现 x 这一维省不掉，因为要减去 (x-1)X；但是注意到人数总和不超过 V=2\times 10^5，由根号结论可知本质不同的 S 只有 O(\sqrt V) 种，于是暴力枚举即可。

\rm E.\ Modular\ Sequence

见上一篇博客。