UESTC 2440
题目
和UESTC-2430完全一致,数据量增大。
题解
我觉得没写啥的必要了,和UESTC-2430完全一致,加上二进制优化就行。
代码
AC代码
这是debug之后了的,注意到打开了OPTIMIZE
宏。
1 | // @author: hzy |
测试例生成(Python)
1 | def G(n, m, c, max=1e3, filename='/Volumes/RD/in'): |
UESTC 2431
题目
给任意一个字符串,求最少插入多少字符可以得到回文串。
题解
求该字符串与它的反序的最长公共子序列(LCS)长度,然后用字符串长度减去这个长度,输出答案完事,时间复杂度为字符串长度的平方。签到题。
代码
因为一发入魂,就没写测试例生成和暴力验证。
AC代码
1 | // @author: hzy |
UESTC 2430
题目
有$n$种普通物品,第$i$种物品的体积为$V_i$,价值$W_i$,数量$D_i$,有$m$件神奇物品,神奇物品的价值由分配的体积$V_i$决定,计算公式为
$$
W_i=x_iV_i^2+y_iV_i+z_i
$$
给一个体积为$C$的背包,求最大价值。
题解
多重背包+泛化物品。
先说多重背包的部分。
其实背包问题没啥好讲的,考虑0-1背包,$dp[i][j]$表示前$i$个物品在容量为$j$的背包下的最大价值,有状态转移方程
$$
dp[i][j]=\max(dp[i-1][j],dp[i-1][j-V_i]+W_i)
$$
这题数据量比较小,直接朴素做法就行,把多重背包考虑为多个相同重量和价值的物品,就可以转变为0-1背包,时间复杂度$O(nCD)$(讲道理这已经达到1e9了,居然没超时)。
再来说一下泛化物品。
参照背包九讲中关于泛化物品的部分。计算完多重背包的部分之后,我们得到了一个在没有神奇物品情况下,任意容量背包能装的最大价值。背包九讲中对于多个泛化物品的操作是两两合并,这样就只有一个泛化物品了,但是我觉得太麻烦,其实泛化物品就相当于有$C$个一般物品,并且将它们放到一个组(也就是只能拿一个,因为泛化物品只有一个),这样就转变为分组背包,遍历容量然后求最大值就行,同样考虑$dp[i][j]$为前$i$个神奇物品在容量为$j$的背包下的最大价值,转移方程为
$$
dp[i][j]=\max{dp[i-1][j-v]+x_iv^2+y_iv^2+z_i|v\in[1,j]}
$$
注意到$j$是两重循环,所以是这部分复杂度是$O(mC^2)$。
代码
暴力测试的程序代码找不到了,嘤嘤嘤。
AC代码
OPTIMIZE
是二进制优化,在写这题的时候没有并没有完成这一部分,朴素暴过去的。
1 | // @author: hzy |
测试例生成(Python)
1 | def G(n, m, c, max=1e3, filename='/Volumes/RD/in'): |
UESTC 2429
题目
和UESTC-2428基本相同,区别在于只能相邻的两个进行交换,询问最少交换次数。
题解
有一说一,这题我没怎么搞懂,基本上全靠出题人的PPT。
这题比较直白了,直接就是$1\sim 20$的数字。继续使用状态压缩,变量$s$二进制表示状态,$dp[s]$表示状态$s$需要的最少交换次数,$w[i][j]$表示原排列i在j前面的对数,状态转移方程
$$
dp[s]=\min{dp[s-(1<<i)]+\sum_{j\in s &j\ne i}w[i][j]}
$$
显然$dp[0]=0$。
$w$直接暴力就行,题解上给的做法也是暴力。(学姐真是太良心了)
代码
虽然没有一发入魂(某个循环的边界写错了),但是调了几下就过了,所以也没有写测试例生成和暴力验证……
AC代码
1 | // @author: hzy |
UESTC 2428
题目
给一段长度为$n$的序列,包含$1\sim m$的数字,可以任意交换两个数字的位置,目标是让所有相同的数字相邻,问最多可以有几个数字的位置不被交换。
题解
参照出题人的PPT。
把“已经排列好的数字种类的集合”视为状态,不考虑集合中数字的顺序,他们的总数是固定的,记状态为$s$,已经排列的人数为$f[s]$,这个可以在输入的时候直接求出来。$m$最大只有20,直接位运算来实现集合。$dp[s]$表示状态$s$最多能固定的数字数量。
枚举$s$,在每次枚举的时候枚举数字$i$,考虑
- $i$不在$s$中,则$dp[s|(1<<i)]=\max{dp[s]+sum[r][i]-sum[l-1][i]|i\in[0,m-1]}$
- $i$在$s$中,则$dp[s]=\max{dp[s\oplus(1<<i)]+sum[r][i]-sum[l-1][i]|i\in[0,m-1]}$
注意我为了方便位运算将输入序列全部减去1。
最后输出$dp[(1<<m)-1]$即可。
代码
因为一发入魂,所以没有写测试例生成和暴力验证。
AC代码
1 | // @author: hzy |
UESTC 2427
题目
给一组长度为$n$序列,相邻的数字可以合并为一个数字,合并后的数字等于合并前的数字+1,问合并后的数字最少是多少个。
题解
参照出题人PPT,是区间DP没错了。
$dp[l][r]$表示区间$[l,r]$在合并过之后有多少个数,$ag[l][r]$表示区间$[l,r]$合并成一个(如果可以)的数。
不好解释,直接看代码吧。。。
1 | for (int mid = l; mid <= r; mid++) { |
对于区间$[l,r]$,将其分为$[l,mid]$和$[mid+1,r]$,看能否合并,然后最小值。
然后枚举长度和$l$即可,复杂度$O(n^3)$。
代码
因为一发入魂,就没写测试例生成和暴力程序了。
AC代码
1 | // @author: hzy |
UESTC 2404
题目
给一颗$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$的子节点。
考虑到不一定1为根节点($dp[1][p]$)才是最优,所以我们可以遍历每一个节点作为根节点的情况。注意到除了根节点之外,其他节点为根节点的话需要断开自己与父节点的边,所以遍历的时候+1即可。
还有一个坑是输入。每行输入的是$u$和$v$表示$u$和$v$之间有一条边,然而并不知道哪个是父节点,所以得专门做一次处理,我懒得搞骚操作直接暴力了,速度还行吧。
代码
AC代码
1 | // @author: hzy |
测试例生成(Python)
1 | def N(n, p, filename='in'): |
UESTC 2398
题目
给定$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$,所以无法用单调队列优化,我们考虑斜率优化。
设$k_1<k_2$且$k_2$比$k_1$更优,即
$$
(dp[i-1][k_2]+s[k_2])-k_2\cdot a[j]+(j\cdot a[j]-s[j])<
(dp[i-1][k_1]+s[k_1])-k_1\cdot a[j]+(j\cdot a[j]-s[j])
$$
$$
(dp[i-1][k_2]+s[k_2])-k_2\cdot a[j]<
(dp[i-1][k_1]+s[k_1])-k_1\cdot a[j]
$$
$$
\frac{(dp[i-1][k_2]+s[k_2])-(dp[i-1][k_1]+s[k_1])}{k_2-k_1}<a[j]
$$
(虽然我不知道变换出这个式子之后有什么用,总之就放这吧)
其实对于斜率优化,我的理解是对于不同的自变量(这里是$k$),取到的值不同,而当$k_1<k_2$且从$k_1$到$k_2$的斜率小于这里的$a[j]$(注意$a[j]$单调不减)时,则后续的状态转移一定不会有$k_1$,因为$k_2$一定比$k_1$更优,同时能取到的点集会有斜率单调不减的特征,也就是一个下凸包,同时那个最优的点就是凸包上第一个斜率大于等于$a[j]$的点,由于$a[j]$单调不减,所以在取了这点之后可以直接将这个点以前的点全部移除。
之后就是代码实现了,我用一个数组来维护下凸包,准确说是一个双向队列(两个变量head
和tail
,但是STL的deque
效率不得行,所以是手写的。
代码
AC代码
这题int
会溢出,我吐了。
1 | // @author: hzy |
测试例生成(Python)
为了方便直接将位置都设为0了。
1 | def e(m, p, max=1e9, filename='in'): |
暴力验证
只是没有斜率优化,其他一样。
1 | // @author: hzy |