A. Keanu Reeves

题意

要将一个仅包含 \(01\) 的字符串分割成尽可能少的段，使得每一段中的 \(0\) 和 \(1\) 数量不同。

分析

做一个简单的分类讨论即可：

• 如果原串中 \(0\) 和 \(1\) 数量不同，直接输出；
• 如果相同的话，我们只需要取出任意一个字符，即将第一个字符分割出，显然这样就不同了。

B. Number Circle

题意

要求将给定的数构造成一个环数列，满足任意一个数都要小于其两边数的和。

分析

考虑最大的数，一定会用次大的和第三大的数来围起来。

于是我们将最大的数放在第一位，次大的放在第二位，第三大的放在最后。

接下来，可以发现，将剩下的数倒序的填入从第三位到倒数第二位的位置即可，因为每一个数都显然满足小于下一个数，而因为每个数都是正的，所以显然满足任意一个数都要小于其两边数的和。

C. Candies!

题意

将给定的一个区间数列，每次两两合并，大于等于 \(10\) 的计数 \(+1\) 后取模，不断进行这样的合并，直到只剩下一个数，求计数次数。

分析

我们可以考虑合并的过程：

• 如果两个数相加 \(\le 9\) ，显然数字和不变；
• 如果两个数相加 \(\ge 10\) ，计数依次，数字和减小了 \(10\) 。

而合并后的最后结果其实就是所有数的数字和，那么显然计数个数也就是本来数字和除以 \(10\) 取整的结果。

D1. Add on a Tree

题意

给出一棵树，每次可以选择任意的两个不同的叶子结点，将两个叶子结点路径上的所有边都加上任意的权值 \(x\) ，\(x\) 是实数，询问这棵树的边权是否可以是任意的。

分析

先给出结论：边权可以是任意的，当且仅当不存在度数为 \(2\) 的结点。

证明：

必要性：显然，如果存在度数为 \(2\) 的结点，那么这个结点所连接的两条边的权值在任何时刻都必须是一样的，无法达到边权任意。

充分性：我们要尝试说明在度数均不为 \(2\) 的情况下，一定存在一种方式能够完成。

我们考虑对于任意的两个结点 \(x,y\) 所构成的边 \((x,y)\) ，需要使他的边权变成 \(z\) 。假设当前的根为 \(root\) ，且结点 \(root\) 是一个叶子结点（为了方便，后面的构造方式会有所体现），于是 \(x,y\) 必为父子关系，假设 \(x\) 是 \(y\) 的父结点。

对于将边 \((x,y)\) 变成 \(z\) ，我们分成两步：路径 \(root\)->\(y\) 加上 \(z\) ， 路径 \(root\)->\(x\) 加上 \(-z\) 。

而对于任意的路径 \(root\)->\(x\) 加上 \(z\) ，我们可以通过 \(x\) 结点不同子树中的叶子结点 \(u,v\) 达到 （\(u,v\) 是 \(x\) 为根的不同子树中的叶子结点，显然需要满足 \(x\) 的度数至少为 \(3\)）：

• 路径 \(root\)->\(u\) 加上 \(\frac{z}{2}\) ；
• 路径 \(root\)->\(v\) 加上 \(\frac{z}{2}\) ；

• 路径 \(v\)->\(u\) 加上 \(-\frac{z}{2}\) 。

显然这样就完成了路径 \(root\)->\(x\) 加上 \(z\) 的操作。

于是可以证明充分性是成立的。

D2. Add on a Tree: Revolution

题意

给出一棵树，每次可以选择任意的两个不同的叶子结点，将两个叶子结点路径上的所有边都加上任意的权值 \(x\) ，\(x\) 是整数，构造一种方案使得变成给定的树。

分析

给定树的边权一定是偶数，于是不需要考虑 \(\frac{z}{2}\) 的情况。

于是直接借用 D1 中充分性证明中的构造方式构造即可。

最多只需要 \(6(n-1)\) 次操作，而显然由于某些叶子结点的关系，实际操作次数是不到这个数的。

E. Count Pairs

题意

给出一个数列，求其中满足 \((a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p\) 的数对数量。

分析

这个式子如果在高中数学中，还是算非常明显的了。

\((a_i + a_j)(a_i^2 + a_j^2) \equiv k \Leftrightarrow (a_i + a_j)(a_i – a_j)(a_i^2 + a_j^2) \equiv k\cdot (a_i – a_j) \Leftrightarrow a_i^4-a_j^4\equiv ka_i – ka_j \Leftrightarrow a_i^4-ka_i\equiv a_j^4-ka_j\)

于是我们只需要算每一个数 \((a_i^4-ka_i)\; mod \; p\) 的结果，用 map 维护相同的数，计算贡献即可。

F. Array Beauty

题意

一个数列的 beauty 值是任意两个数绝对值的最小值。

给出一个数列，求其所有子数列的 beauty 值。

分析

很经典的套路。

对于求所有子数列的 beauty 值，可以转换成求所有 \(\ge beauty (beauty\ge 1)\) 的子数列数量。

考虑枚举 beauty 值，设状态 \(f[i][j]\) 表示当前子数列的长度为 \(i\) ，以 \(j\) 结尾的 beauty 值 \(\ge beauty\) 的数量。

转移方程是显然的，\(f[i][j]=\sum f[i-1][k] (|a_j-a_k|\ge beauty)\) 。

于是我们考虑将数列排序（因为是子数列，排序显然不会影响答案），然后就可以用前缀和来优化方程的转移了。

这样的时间复杂度是 \(O(nk\cdot beauty)\) ，而显然 \(beauty=\left \lfloor \frac{max\{a_i\}}{k-1}\right \rfloor\) ，于是复杂度是近似 \(O(n\cdot max\{a_i\})\) 。