Codeforces Round #572


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\})\) 。

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 123,359

Categories

Archive

Comments