昨天的校赛时彻底脑残, 只在前44分钟做了三题大水, 后面再也没A过题, 更要命的是我真的不会做, 那道最大m子段和我就是不会, 而对模板的依赖也使得我的B在编译错误之后变得无从下手, G完全没想法, H也是一样, 最要命的就是E(求a到b之间所有数的约数的个数和), 校赛一模一样的题目啊, 那天晚上我还画了图给同学解释为什么可以将连续函数y=1/x用在这题, 今天看到这题竟然完全没印象了, 一直到结束之后队友在我的草稿纸上又把那幅图画出来的时候我才意识到自己的愚蠢. 还是题目做的太少, 不能再这样下去了.
关于最大M子段和的状态压缩, 做这题的时候我已经没想法了, 很无耻地跑到google搜索了一番, 结果搜到三篇代码竟然都是错的, 崩溃了我, 比赛以后静下心来想想, 其实是很简单的DP, 不论压缩哪一维的状态都是可以过的, 最终经过几番优化, 间复杂度变为O(nm), 空间复杂度变为O(m).
[Ecust ACM 2009 Summer Practice Contest 3][D][Max Partial Sums]
2009-07-22
最大M子段和: 给出一个整数序列, 包含负数, 求M个不相交子段, 使它们中的元素和最大, 每段长度至少为1.
很容易想到O(m*n^2)的算法, 状态转移如下:
f[m][n]表示m个子段正好覆盖到n个元素.
f[m][n] = max{f[m][n-1], f[m-1][t]} + a[n]
注意到只依赖m-1, 所以可以把第一维压缩, 又f[m-1][t]需要前一轮状态的最大值, 所以需要长度n的数组来记录, 又f[m][n]另外只依赖n-1, 所以在使用后就就无用了, 利用它来存储最大值.
f[n][1] = max{f[n-1][0], f[n-1][1]} + a[i]
f[n][0] = max{f[n-1][0], f[n][1]}
1表示当前正好到n, 0表示前一轮在n及其之前的最大值, 迭代的时候需要开临时变量.
代码如下:
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000000, M = 30;
int _dp[N][2], _a[N];
int max(int a, int b) { return a > b ? a : b; }
int DP(int n, int m) {
memset(_dp, 0, sizeof(_dp));
int i, j;
_dp[0][1] = _dp[0][0] = _a[0];
for (i = 1; i < n; ++i) {
_dp[i][1] = max(0, _dp[i - 1][1]) + _a[i];
_dp[i][0] = max(_dp[i - 1][0], _dp[i][1]);
}
for (i = 1; i < m; ++i) {
int pmx = _dp[i][0];
_dp[i][1] = _dp[i - 1][1] + _a[i];
_dp[i][0] = _dp[i][1];
for (j = i + 1; j < n; ++j) {
pmx = _dp[j][0];
_dp[j][1] = max(pmx, _dp[j - 1][1]) + _a[j];
_dp[j][0] = max(_dp[j - 1][0], _dp[j][1]);
}
}
int res = _dp[m - 1][1];
for (i = m; i < n; ++i) {
res = max(res, _dp[i][1]);
}
return res;
}
int main() {
int n, m, i;
while (EOF != scanf("%d%d", &m, &n)) {
for (i = 0; i < n; ++i) {
scanf("%d", _a + i);
}
printf("%d\n", DP(n, m));
}
return 0;
}
稍微修改一下, 就可以压缩成一维数组:
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000000, M = 30;
int _dp[N], _a[N];
int max(int a, int b) { return a > b ? a : b; }
int DP(int n, int m) {
memset(_dp, 0, sizeof(_dp));
int i, j;
_dp[0] = _a[0];
for (i = 1; i < n; ++i) {
_dp[i] = max(0, _dp[i - 1]) + _a[i];
}
for (i = 1; i < n; ++i) {
_dp[i] = max(_dp[i - 1], _dp[i]);
}
for (i = 1; i < m; ++i) {
int pmx = _dp[i];
_dp[i] = _dp[i - 1] + _a[i];
for (j = i + 1; j < n; ++j) {
int tpmx = _dp[j];
_dp[j] = max(pmx, _dp[j - 1]) + _a[j];
pmx = tpmx;
}
for (j = i + 1; j < n; ++j) {
_dp[j] = max(_dp[j - 1], _dp[j]);
}
}
return _dp[n - 1];
}
int main() {
int n, m, i;
while (EOF != scanf("%d%d", &m, &n)) {
for (i = 0; i < n; ++i) {
scanf("%d", _a + i);
}
printf("%d\n", DP(n, m));
}
return 0;
}
再又注意到m<n, 可以将第二维压缩:
f[m][i][j], i=0,1,表示滚动状态, j=0表示正好到m, j=1表示m及其之前的最大值.
f[m][1 - k][0] = max(f[m][k][0], f[m - 1][k][1]) + a[i];
f[m][1 - k][1] = max(f[m][k][1], f[m][1 - k][0]);
注意初始状态置负无穷, f[0][0][0] = f[0][0][1] = a[0];
最终代码如下:
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000000, M = 30, INF = 1147483647;
int _a[N];
typedef int T;
T _dp[M][2][2];
T MMaxSum(int n, int m, T a[]) {
// cannot be this:
// fill_n(_dp[0][0], sizeof(_dp), -INF);
fill_n(_dp[0][0], M * 2 * 2, -INF);
int i, j, k, jend;
_dp[0][0][0] = _dp[0][0][1] = a[0];
for (i = 1, k = 0; i < n; ++i, k = 1 - k) {
_dp[0][1 - k][0] = max(0, _dp[0][k][0]) + a[i];
_dp[0][1 - k][1] = max(_dp[0][k][1], _dp[0][1 - k][0]);
for (j = 1, jend = min(i + 1, m); j < jend; ++j) {
_dp[j][1 - k][0] = max(_dp[j][k][0], _dp[j - 1][k][1]) + a[i];
_dp[j][1 - k][1] = max(_dp[j][k][1], _dp[j][1 - k][0]);
}
}
return _dp[m - 1][k][1];
}
int main() {
int n, m, i;
while (EOF != scanf("%d%d", &m, &n)) {
for (i = 0; i < n; ++i) {
scanf("%d", _a + i);
}
printf("%d\n", MMaxSum(n, m, _a));
}
return 0;
}
[Ecust ACM 2009 Summer Practice Contest 3][E][Divistors]
2009-07-22
求a到b之间(inclusive)所有数字约数的总数(总数目).
画出y=n/x的曲线图, 容易发现y=x这条线两边被曲线圈住的点是对称的, 所以只要求出上限为sqrt(n)的约数数目, 乘2, 再减去中间重复的正方形那块中的整点数目(即(floor(sqrt(n)))^2).
注意若n太大不则能用i^2<=n来做循环条件, 除非用64位, 否则会溢出. 还有记得a-1.
这题是上次去东华之前校赛的最后一题, 竟然完全忘了.
#include <cmath>
#include <cstdio>
typedef __int64 I;
I Sol(int n) {
int i, sq = int(sqrt(double(n)));
I res = 0;
for (i = 1; i <= sq; ++i) {
res += n / i;
}
res += res - sq * sq;
return res;
}
int main() {
int a, b;
while (scanf("%d%d", &a, &b), a) {
// note "a - 1"
printf("%I64d\n", Sol(b) - Sol(a - 1));
}
return 0;
}