题目

给一段长度为\(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}\)的点,输出距离完事。

阅读全文 »