记一次LVM误操作引发的事故
总之是闯了大祸,好在最后数据都没事。主要问题是我对LVM操作不熟练,以及对文件系统和磁盘没有比较清晰的认识,具体来说就是我以为LVM在进行lvresize时会自动处理文件系统,这当然是错误的,文件系统应该使用resize2fs命令来调整,LVM管理的是块设备,不会处理文件系统上的问题。
总之是闯了大祸,好在最后数据都没事。主要问题是我对LVM操作不熟练,以及对文件系统和磁盘没有比较清晰的认识,具体来说就是我以为LVM在进行lvresize时会自动处理文件系统,这当然是错误的,文件系统应该使用resize2fs命令来调整,LVM管理的是块设备,不会处理文件系统上的问题。
和UESTC-2430完全一致,数据量增大。
我觉得没写啥的必要了,和UESTC-2430完全一致,加上二进制优化就行。
这是debug之后了的,注意到打开了OPTIMIZE
宏。
1 | // @author: hzy |
测试例生成(Python)
1 | def G(n, m, c, max=1e3, filename='/Volumes/RD/in'): |
给任意一个字符串,求最少插入多少字符可以得到回文串。
求该字符串与它的反序的最长公共子序列(LCS)长度,然后用字符串长度减去这个长度,输出答案完事,时间复杂度为字符串长度的平方。签到题。
因为一发入魂,就没写测试例生成和暴力验证。
1 | // @author: hzy |
有$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)$。
暴力测试的程序代码找不到了,嘤嘤嘤。
OPTIMIZE
是二进制优化,在写这题的时候没有并没有完成这一部分,朴素暴过去的。
1 | // @author: hzy |
1 | def G(n, m, c, max=1e3, filename='/Volumes/RD/in'): |