题目

给一段长度为\(n\)的序列，包含\(1\sim m\)的数字，可以任意交换两个数字的位置，目标是让所有相同的数字相邻，问最多可以有几个数字的位置不被交换。

题解

参照出题人的PPT。

把“已经排列好的数字种类的集合”视为状态，不考虑集合中数字的顺序，他们的总数是固定的，记状态为\(s\)，已经排列的人数为\(f[s]\)，这个可以在输入的时候直接求出来。\(m\)最大只有20，直接位运算来实现集合。\(dp[s]\)表示状态\(s\)最多能固定的数字数量。

题目

给一组长度为\(n\)序列，相邻的数字可以合并为一个数字，合并后的数字等于合并前的数字+1，问合并后的数字最少是多少个。

题解

参照出题人PPT，是区间DP没错了。

\(dp[l][r]\)表示区间\([l,r]\)在合并过之后有多少个数，\(ag[l][r]\)表示区间\([l,r]\)合并成一个（如果可以）的数。

题目

给一颗\(n\)节点的树，1节点为根节点，求最少减去多少条边可以得到一颗\(p\)节点的树。

题解

参照洛谷P1272。

基本上是原题了。

\(dp[i][j]\)表示以\(i\)为根节点时获得节点数为\(p\)的树最少需要的修建次数。状态转移方程 \[ dp[i][j]=\min\{dp[i][j-k]+dp[son][k]-1|k\in[1,j]\} \] \(son\)是\(i\)的子节点。

题目

给定\(m\)个牛头人和\(p\)个老哥，老哥向一个方向移动，遇到牛头人时牛头人停止活动，现在给出牛头人出现的时间距离，让所有牛头人加起来的活动时间最短，安排老哥的出发时间。

题解

参照出题人PPT的状态转移方程。

首先简化问题，假设所有牛头人都出现在起始位置，直接用时间减去距离即可，为了方便后面的操作再排序一下，设为\(a[]\)，\(dp[i][j]\)表示第\(i\)个老哥在\(a[j]\)时刻出发前\(j\)牛头人的最少活动时间，于是有状态转移方程 \[ dp[i][j]=\min\{dp[i-1][k]+\sum_{x=k+1}^{j}(a[j]-a[x])|k\in[1,j]\} \] 考虑用前缀和，令 \[ s[j]=\sum_{x=1}^ja[x] \] 方程可以变为 \[ dp[i][j]=\min\{(dp[i-1][k]+s[k])-k\cdot a[j]+(j\cdot a[j]-s[j])|k\in[1,j]\} \] 考虑\(i\in[1,p]\)，\(j\in[1,m]\)，直接DP的话复杂度依然高达\(O(pm^2)\)，因为式子中有一项同时包含\(k\)和\(j\)，所以无法用单调队列优化，我们考虑斜率优化。

题目

这次在每一轮游戏中，綾波需要使用鱼雷把一个区间[l,r]内的所有点的数值变为c，每改变一个点的数值需要消耗一枚特制鱼雷。

尽管如此，在知道了墙面上各点初始数值和每轮的任务后，綾波还是希望指挥官能帮她计算她各轮需要的鱼雷数量的说。呐，快来帮帮綾波吧。

题解

参照出题人题解PPT。

出题人告诉我们这题可以分块也可以用珂朵莉树。

题目

在与拉菲、标枪等人相遇几次之后，綾波心里有些烦恼。一天，她独自在港区玩一个既有趣又能提升自己的能力的游戏，在这个游戏中，她面对一面长墙，墙上排列着 n个点（编号 1∼n），每个点都带有一个数值（可能为负数），同时，还有一个一定要记住的数值 k。

在每一轮游戏中，綾波需要使用鱼雷击中在一个区间（[l,r]）内的所有对 k取模（取非负最小剩余）后数值与 c对 k取模（同样取非负最小剩余）相等的点，每次击中每个点需要一枚鱼雷。

题目

利姆露现在想知道一个奇怪魔法序列的含义，于是她把这个任务交给了大贤者。

这个魔法序列由 nn 个字符组成，仅包含 L，R，小写拉丁字母和括号（即 ‘(’ 和 ‘)’），表达对一个空白字符串的操作（因为是空白字符串，所以最初操作位置在哪里都一样），其中

1. L 表示当前操作位置左移一位。
2. R 表示当前操作位置右移一位。
3. 其余任何小写拉丁字母或括号表示将当前操作位置修改为该字符。

题目

你带着大量佣兵回到城市，看到了大量的新赏金任务。你无视其他等级的任务，拿过最高等级的任务列表，发现其任务数量刚好和你的佣兵数量相同，便把它们都接到了自己手上。

每个佣兵都有自己的能力值，每个任务都有能力值要求，能力值大于要求即可完成任务。

你让佣兵们自行选择任务（每人一个），然而，一旦脱离你的命令，他们就无法做出恰当的决策：你看完他们的选择后，发现他们选择的任务既有重复，也有缺漏，还有不少佣兵选择了自己能力不够、无法完成的任务。但你既然已经下令，朝令夕改会影响你的威信。

题目

给一个\(n\)行\(m\)列的数据，找出其中

• 尽可能大
• 边长为奇数
• 中心元素能被其他元素整除

的正方形。

题解

出题人的PPT题解上写的挺清楚了，上述条件成立的情况下，则中心元素一定是正方形内所有元素中最小的，而且正方形内所有元素的最大公约数也是中心元素。

暴力枚举每个点就行。我们可以用二维ST表来实现复杂度\(O(1)\)求最小值，\(O(\log_2 n)\)求区域内的最大公约数（GCD）。下标从\(0\)开始的话，只需要从\((1,1)\)枚举到\((n-1,m-1)\)即可，因为边缘上的数不会有正方形。

题目

一个环，环上有点，查询从\(s\)点到最近的大于等于\(t\)的点的正向距离，没有则输出\(-1\)。每个点在被查询过后会消失，没消失的点的值每次查询都增加1。

题解

基本上还是用线段树。

首先用一个grow变量标记过了多少个晚上，长了多少，然后就是用线段树查找出距离\(s\)最近的大于等于\(t-\mathrm{grow}\)的点，输出距离完事。