我哭了......什么鬼题我怎么都不会...果然教育场是教我做人的...
打的虚拟赛，286名...太菜了。EF都是可做题我都没写出来...G题大水题我居然没看...
B：设g(i) = i的各位数字之和，f(i) = g(i) < 10 ? g(i) : f(g(i))
多组询问，每次求g(i) = x的第k大的i。k <= 1e12
解：这题一开始把我看得一愣一愣的，啥玩意？数位DP？怎么放在第二题？
然后冷静下来打了一波表，发现是个SB找规律......从1开始每个数的g()值一定是12345....912...912...9.....
这就很OK了，输出9(k-1)+x即可。
C：给定字符串，每个位置都有一个权值。
你要选出一个子序列，使得这些位置上的权值和最大，且没有哪个字符连续出现超过k次。
权值非负。
解：稍加思索......直接堆啊！每连续的一段贪心选最大的k个即可。
(如果权值可以为负怎么办？首先肯定可以暴力DP，f[i][j][k]表示前i个选j个，第i个必须选，末尾有连续k个s[i]的最大权值。DP优化...不会...复杂度更优的做法......不会...)
D：给定n x n的01矩阵，你要尝试把它压缩，每a x a个字符压缩成一个字符，要求这a2个字符全部一样。
显然a必须是n的约数。求最大的a。
解：稍加思索...好像直接n2gcd就行啊？这么简单？
a必须是每行/列所有连续段的长度的约数。
感觉没错就写了。为了加速把gcd记忆化了，还加了个剪枝。然后就A了...
E：给定长为n的01序列与数组a。
你每次可以选择其中连续的一段0或1消掉，如果长度为x则能够得到a[x]的收益。求最大收益。
a[x]非负，n <= 100。
解：我是SB系列......
看到题就想到了区间DP，比如啥神题ZUMA......尝试一下。
f[i][j][k]表示[i, j]这一段后面接长为k的0/1时完全消除的最大收益，发现完全不行...弃疗了。
看题解，发现是f[i][j][k][0/1]表示把[i，j]这一段消成k个0/1的最大收益，这样就可行了......
答案是f[1][n][0][0]或f[1][n][0][1]。
转移就是枚举这k个0/1其中第一个在哪里。f[l][r][0][0/1]的转移是f[l][r][k][0/1] + a[k]
#include <cstdio>
#include <cstring> typedef long long LL;
const int N = ;
const LL INF = 0x3f3f3f3f3f3f3f3f; LL f[N][N][N][], a[N];
char s[N]; inline void exmax(LL &a, const LL &b) {
a < b ? a = b : false;
return;
} int main() {
memset(f, ~0x3f, sizeof(f));
int n;
scanf("%d%s", &n, s + );
for(int i = ; i <= n; i++) {
scanf("%lld", &a[i]);
s[i] -= '';
f[i][i][][] = f[i][i][][] = a[];
f[i][i - ][][] = f[i][i - ][][] = f[i][i][][s[i]] = ;
}
f[n + ][n][][] = f[n + ][n][][] = ;
for(int len = ; len <= n; len++) {
for(int l = ; l + len - <= n; l++) {
int r = l + len - ;
for(int k = len; k >= ; k--) {
// f[l][r][k][0] f[l][r][k][1]
for(int p = l; p + k - <= r; p++) {
exmax(f[l][r][k][s[p]], f[l][p - ][][] + f[p + ][r][k - ][s[p]]);
}
exmax(f[l][r][][], f[l][r][k][] + a[k]);
exmax(f[l][r][][], f[l][r][k][] + a[k]);
}
}
} printf("%lld", f[][n][][]);
return ;
}
AC代码
F：有n个贷款，你可以在每个月初选择第i个贷款，得到ai，之后的ki个月就要每个月底还款bi(包括本月)。
你会在某个月中间携巨款潜逃，求你最多能带走多少钱。
每个月只能贷一笔款，每笔贷款也只能被贷一次。n <= 500
解：回想起修车的套路，我们可以计算在潜逃前i个月贷j的收益是a[j] - b[j] * min(i - 1, k[j])
然后想到一个类似背包的DP，可以设f[i][j]表示潜逃前j个月只贷前i笔款时的最大收益。
然后发现我凉了。。。原因是贷款的顺序跟背包不一样，背包无序，这个有序。
然后发现可以费用流，兴冲冲打了一波，TLE...
结束后发现是KM，赶快去现场学一波...DFSTLE...BFSKM就是大毒瘤至今不会...
我疯了。看别人的提交，TM是DP......
还是之前那个状态，但是多了个排序，按bi排序！我是大SB...
我的理解是这样的，对于每个贷款你显然有三种选择，要么老实还钱，要么畏罪潜逃，要么不去选。
现在考虑两个畏罪潜逃的贷款的先后顺序。
两个的ai都选了，所以就只跟bi有关了，所以bi大的应该越晚越好。
这样就可以DP了......
具体的转移：f[i][j] = max(f[i - 1][j], f[i][j - 1], //不选i/第j天不选
f[i - 1][j - 1] + a[i] - b[i] * (j - 1), //第j天选i，畏罪潜逃
f[i - 1][j] + a[i] - b[i] * k[i]) //很久以前的某一天选了i
有一个要注意的地方是，你f[i][0]的地方也要转移，否则f[i][1]的值会出错......
#include <cstdio>
#include <algorithm>
#include <cstring> typedef long long LL;
const int N = ; struct Node {
LL a, b, k;
inline bool operator <(const Node &w) const {
return b > w.b;
}
}node[N]; LL f[N][N]; int main() {
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%lld%lld%lld", &node[i].a, &node[i].b, &node[i].k);
}
std::sort(node + , node + n + );
for(int i = ; i <= n; i++) { // use i-th credit
LL a = node[i].a, b = node[i].b, k = node[i].k;
f[i][] = std::max(f[i - ][], f[i - ][] + a - b * k);
for(int j = ; j <= n; j++) { // j days before
// f[i][j]
f[i][j] = std::max(f[i - ][j], f[i][j - ]);
// today use i
f[i][j] = std::max(f[i][j], f[i - ][j - ] + a - b * (j - ));
f[i][j] = std::max(f[i][j], f[i - ][j] + a - b * k);
}
}
printf("%lld", f[n][n]);
return ;
}
AC代码
G：给定数组c和d。你要选出一段子区间，得到的收益是a * len - ∑ci - max(di+1 - di)2
保证di递增，求最大收益。
解：发现di递增好像没用......
首先考虑枚举右端点，发现不行，然后考虑枚举哪个△d作为max，这就很OK了，在左右各取前缀和max/min即可。
这道题比前面两题友善多了，我居然没看......太SB了。
#include <cstdio>
#include <algorithm> typedef long long LL;
const int N = ;
const LL INF = 0x3f3f3f3f3f3f3f3f; int n, pw[N], p[N], top, left[N], right[N];
LL A, d[N], val[N], sum[N], b[N];
LL STmax[N][], STmin[N][]; inline LL getMax(int l, int r) {
int t = pw[r - l + ];
return std::max(STmax[l][t], STmax[r - ( << t) + ][t]);
} inline LL getMin(int l, int r) {
int t = pw[r - l + ];
return std::min(STmin[l][t], STmin[r - ( << t) + ][t]);
} int main() {
scanf("%d%lld", &n, &A);
LL ans = ;
for(int i = ; i <= n; i++) {
scanf("%lld%lld", &b[i], &val[i]);
d[i] = b[i] - b[i - ];
val[i] = A - val[i];
sum[i] = sum[i - ] + val[i];
STmax[i][] = STmin[i][] = sum[i];
ans = std::max(ans, val[i]);
}
for(int i = ; i <= n; i++) {
pw[i] = pw[i >> ] + ;
}
for(int j = ; j <= pw[n]; j++) {
for(int i = ; i + ( << j) - <= n; i++) {
STmax[i][j] = std::max(STmax[i][j - ], STmax[i + ( << (j - ))][j - ]);
STmin[i][j] = std::min(STmin[i][j - ], STmin[i + ( << (j - ))][j - ]);
}
} d[] = INF;
p[++top] = ;
for(int i = ; i <= n; i++) {
while(top && d[p[top]] <= d[i]) {
top--;
}
left[i] = p[top];
p[++top] = i;
}
top = ;
d[n + ] = INF;
for(int i = ; i <= n + ; i++) {
while(top && d[p[top]] < d[i]) {
right[p[top]] = i;
top--;
}
p[++top] = i;
} for(int i = ; i <= n; i++) {
LL t = getMax(i, right[i] - ) - getMin(left[i] - , i - ) - d[i] * d[i];
ans = std::max(ans, t);
} printf("%lld", ans);
return ;
}
AC代码
太菜了...