复制粘贴 3

支持三种操作，三种操作如下：

在末尾添加一个字符

将当前字符串剪贴到剪贴板中

将当前剪贴板粘贴到字符串末尾
三种操作有对应代价，

tag：动态规划，字符串匹配

如果你像我一样想线性 dp，那估计是想不出来的。

由于剪贴板只有一个，这实际上可以视为分层操作，层的不同取决于剪贴板的内容。

层与层之间靠添加操作连接，于是想到用区间 dp，连接区间即为添加操作。

传统的区间 \(dp\) 是 \(O(n^3)\) 的，但是可以发现一个贪心：如果一次剪切粘贴更优，我们会尝试把所有可以再次粘贴的地方粘贴完。于是状态数就降至 \(O(n^2)\) 了。

所以说，见到有关合并的操作，要往区间 dp 上想。

团队竞技

每个人有智力，力量，幸运三个属性，现需要组成一个三人小队，三个人分别要求智力严格高于其他两人，力量严格高于其他两人，幸运严格高于其他两人。问在此要求基础上，三人中智力最高值，力量最高值，幸运最高值之和。

tag：贪心，基础数据结构

简单题。考虑如果有一个人，在两个方面都是最高值，那么这个人肯定不能选，得删掉。那么在剩下的人里贪心分别选择智力最高，力量最高，幸运最高的人即可。实现上可以用三个 set。

给你一棵树，点有权值，还有一个开始会输入的整数 \(L\)，支持以下两种操作

单点查询

给你一个点 \(u\)，对于所有距离 \(u\) 不超过 \(d\) 的点，将权值 \(\times w \bmod L\)。
特殊限制：\(d\le 40\)

tag：面向数据编程

鉴定为点分树。然后发现 \(d\le 40\)，于是发现了更简单的做法。

建立数组 \(f_{i,j}\) 表示距离 \(i\) 距离为 \(j\) 的儿子需要乘几，我们对于 \(u\)，暴力往上跳，每次将 \(f_{i,d}\) 与 \(f_{i-1,d}\) 全部 \(\times w\)，往上跳时将 \(d\) 变为 \(d-1\)。

查询时类似。由于将 \(f_{i-1,d}\) 也更新了，所以所有奇偶点都会被更新。不重不漏。

将 \(n\) 个点在保证每段长度不大于 \(k\) 的限制下分成最少的串 \(\lceil \frac{n}{k} \rceil\)。定义一种分段方式的权值为分出各段最大值之和，求满足上面要求的分段方式的最大的权值。

tag：动态规划及其优化

第一次碰到这种优化状态设计的题，有点棘手，但是第二次就不会这样了。

容易想到简单动态规划：设 \(f_{i,j}\) 为当前到 \(i\)，且已经分了 \(j\) 段。那么容易转移。但是这是 \(O(n^3)\) 的。

枚举方式已经很优了，我们尝试优化状态设计。发现只有 \(f_{i,\lceil \frac{i}{k} \rceil}\) 会对之后产生贡献。原因如下：

若 \(j < \lceil \frac{i}{k} \rceil\)，则 \(j \times k <i\)，必定有一段大于 \(k\)。
若 \(j > \lceil \frac{i}{k} \rceil\)，则 \(j + \lceil \frac{n - i}{k} \rceil > \lceil \frac{i}{k} \rceil + \lceil \frac{n-i}{k} \rceil \ge \lceil \frac{n}{k} \rceil\)，之后必有一段大于 \(k\)。

那么我们新设状态 \(g_i = f_{i,\lceil \frac{i}{k} \rceil}\)，\(g_i\) 能从 \(g_j\) 转移当且仅当 \(\lceil \frac{j}{k} \rceil + 1 = \lceil \frac{i}{k} \rceil\)。转移方程式为：

\[g_i = \max\{g_j + \max[j+1,i]\} \]

这是一个经典的单调栈加数据结构转最值为加减的技巧，我们线段树维护 \(g_j + \max[j+1,i]\) 的最值，每一次增加 \(a_i\) 从单调栈中一层一层调出需要更新的区间，用区间加更新即可。