期望100-实际100
老师说是结论题。
其实可以直接打表，t[i]表示0-63中有t[i]对数与起来等于i，然后乘法原理即可。
（没什么难度。
#include <cstdio> #include <cstring> using namespace std; const int MAXN = 100005; const int mod = 1e9 + 7; char s[MAXN]; int a[MAXN], t[64]; int main() { scanf ("%s", s + 1); int n = strlen(s + 1); for(int i = 1; i <= n; i++) { if('0' <= s[i] && s[i] <= '9') a[i] = s[i] - '0'; else if('A' <= s[i] && s[i] <= 'Z') a[i] = 10 + (s[i] - 'A'); else if('a' <= s[i] && s[i] <= 'z') a[i] = 36 + (s[i] - 'a'); else if(s[i] == '-') a[i] = 62; else if(s[i] == '_') a[i] = 63; } // for(int i = 1; i <= n; i++) // printf("%d ", a[i]); t[0] = 729; t[1] = 243; t[2] = 243; t[3] = 81; t[4] = 243; t[5] = 81; t[6] = 81; t[7] = 27; t[8] = 243; t[9] = 81; t[10] = 81; t[11] = 27; t[12] = 81; t[13] = 27; t[14] = 27; t[15] = 9; t[16] = 243; t[17] = 81; t[18] = 81; t[19] = 27; t[20] = 81; t[21] = 27; t[22] = 27; t[23] = 9; t[24] = 81; t[25] = 27; t[26] = 27; t[27] = 9; t[28] = 27; t[29] = 9; t[30] = 9; t[31] = 3; t[32] = 243; t[33] = 81; t[34] = 81; t[35] = 27; t[36] = 81; t[37] = 27; t[38] = 27; t[39] = 9; t[40] = 81; t[41] = 27; t[42] = 27; t[43] = 9; t[44] = 27; t[45] = 9; t[46] = 9; t[47] = 3; t[48] = 81; t[49] = 27; t[50] = 27; t[51] = 9;t[52] = 27; t[53] = 9; t[54] = 9; t[55] = 3; t[56] = 27; t[57] = 9; t[58] = 9; t[59] = 3; t[60] = 9; t[61] = 3; t[62] = 3; t[63] = 1; long long ans = 1; for(int i = 1; i <= n; i++) { ans *= t[a[i]]; ans %= mod; } printf("%lld\n", ans % mod); return 0; }打表代码：
#include <cstdio> int t[64]; int main() { for(int i = 0; i <= 63; i++) for(int j = 0; j <= 63; j++) { int k = (i & j); printf("%d = %d & %d\n", k, i, j); t[k]++; } for(int i = 0; i <= 63; i++) printf("t[%d] = %d;\n", i, t[i]); return 0; }期望100-实际9
老师说是最短路。
其实可以BFS-DFS，不过需要记忆化提速。每次在BFS里存储下一个点的坐标、到下一个点是上一次休息后过的第几条街、从起点到下一个点的距离。
可以在这里执行最优解剪枝。
#include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 105; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { 1, 0, -1, 0 }; int map[MAXN][MAXN], n, T; void read(int &a) { a = 0; int k = 1; char s = getchar(); while (s < '0' || s > '9') { if (s == '-') k = -1; s = getchar(); } while (s >= '0' && s <= '9') { a = (a << 3) + (a << 1) + s - '0'; s = getchar(); } a *= k; return; } struct node { int x, y, step, dis; node(int X, int Y, int S, int D) { x = X; y = Y; step = S; dis = D; } }; int ans[3][MAXN][MAXN]; void bfs(int sx, int sy) { memset(ans, 0x3f, sizeof ans); queue<node> q; ans[0][sx][sy] = 0; q.push(node(sx, sy, 0, 0)); while (!q.empty()) { node t = q.front(); q.pop(); int x = t.x, y = t.y, di = t.dis, va = t.step; if (ans[va][x][y] < t.dis) // 剪枝 1（如果走过的总路径都比之前存的答案长了，直接判断不是最优解 for(int i = 0; i < 4; i++) { continue; for (int i = 0; i < 4; i++) { int cx = x + dx[i]; int cy = y + dy[i]; int val = va + 1; int dis = di + T; if (val == 3) { val = 0; dis += map[cx][cy]; } if (cx < 1 || cx > n) continue; if (cy < 1 || cy > n) continue; if (ans[val][cx][cy] <= dis) // 剪枝 2（同剪枝 1 continue; ans[val][cx][cy] = dis; q.push(node(cx, cy, val, dis)); } } return; } int main() { read(n); read(T); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) read(map[i][j]); bfs(1, 1); printf("%d\n", min(ans[1][n][n], min(ans[0][n][n], ans[2][n][n]))); return 0; }期望100-实际77
一道完全背包，我记得我们之前做过类似题目的。
可以把这道题改写一下。对于第i天，第j件物品的价值就是它下一天的价格，第j件物品的重量就是它当天的价格，而背包容量就是上一天获得的最大价值。
所以做k-1次完全背包即可。
但有一个细节需要考虑：每一次背包不一定装满，而未装满的部分还能拿到下一次去用，所以每次跑完完全背包后，还要再遍历一遍。
#include <cstdio> typedef long long LL; const int MAXN = 55; const int MAXD = 15; const int MAXM = 1000005; int v[MAXN][MAXD]; LL dp[MAXM], add[MAXM]; int Max(int x, int y) { return x > y ? x : y; } int main() { int n, d, m; scanf("%d %d %d", &n, &d, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= d; j++) scanf("%d", &v[i][j]); LL t = m; for (int k = 2; k <= d; k++) { for (int i = 1; i <= t; i++) dp[i] = 0; for (int i = 1; i <= n; i++) for (int j = v[i][k - 1]; j <= t; j++) if (dp[j] < dp[j - v[i][k - 1]] + v[i][k]) dp[j] = dp[j - v[i][k - 1]] + v[i][k]; int ma = 0; for (int i = 0; i <= t; i++) ma = Max(ma, dp[i] + t - i); // dp[i] 表示背包容量为 i 的最大价值，再加上 t - i 也就是没装完的部分 t = Max(ma, t); } printf("%lld\n", t); return 0; }期望0-实际30？？？？
当我们求到前缀和之后，就需要把所有的满足条件的超级音符选出最大的k个超级音符来。
又很显然，暴力排序跑是不可能的，因此，我们就需要换个方法。因为对于一个确定的起点i而言，找到以i为起点，往后数[l,r]这个区间的子段的最大值，是可求的。因为我们已经计算出来了前缀和，那么，[l,r]这个范围内的最大值减去i-1这个位置的前缀和就是我当前这个段能取得的最大值。
那么，对于我的答案而言，每次都选取这样的最优值，最后得到的是不是就是最优解？因此，我们可以用一个堆来存储这样的一些数据，存储对于每一个起点i而言，取出[i+l,i+r]这个范围内的最大值存入我们的优先队列。
当我们取走一个当前的局部最优解之后，又由于我这个区间范围内的次优解还可能比其他地方的最优解优，因此，假设t就是我们得到最优解得位置，我们在取走它之后，还需要再放进从i开始，[i+l,i+t-1]的最优解以及[i+t+1,i+r]的最优解，当然，如果t=l或者t=r时，需要特判。（思路来自LHY
#include <bits/stdc++.h> using namespace std; const int MAXN = 500005; long long a[MAXN], sum[MAXN]; long long n, m, L, R; struct RMQ { int v, index; } st[MAXN][25]; struct data { int l, r, l_, r_, t; friend bool operator<(data x, data y) { return sum[x.r_] - x.t < sum[y.r_] - y.t; } }; priority_queue<data> q; void RMQ() { for (int j = 1; (1 << j) <= n; j++) for (int i = 0; i + (1 << j) - 1 <= n; i++) if (st[i][j - 1].v < st[i + (1 << (j - 1))][j - 1].v) { st[i][j].v = st[i][j - 1].v; st[i][j].index = st[i][j - 1].index; } else { st[i][j].v = st[i + (1 << (j - 1))][j - 1].v; st[i][j].index = st[i + (1 << (j - 1))][j - 1].index; } return; } int work_v(int l, int r) { int k = log2(r - l + 1); return min(st[l][k].v, st[r - (1 << k) + 1][k].v); } int work_index(int l, int r) { int k = log2(r - l + 1); return st[l][k].v < st[r - (1 << k) + 1][k].v ? st[l][k].index : st[r - (1 << k) + 1][k].index; } int main() { long long ans = 0; scanf("%lld %lld %lld %lld", &n, &m, &L, &R); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); sum[i] = sum[i - 1] + a[i]; st[i][0].v = sum[i]; st[i][0].index = i; } RMQ(); for (int i = 1; i <= n; i++) { int sl = max(0, int(i - R)), sr = i - L; if (sl > sr || sr < 0) continue; data cnt; cnt.r = sr; cnt.l = sl; cnt.r_ = i; cnt.l_ = work_index(cnt.l, cnt.r); cnt.t = work_v(cnt.l, cnt.r); q.push(cnt); } while (m-- && !q.empty()) { data cnt = q.top(); q.pop(); ans += sum[cnt.r_] - cnt.t; data cnt2; cnt2 = cnt; cnt2.l = cnt.l; cnt2.r = cnt.l_ - 1; if (cnt2.l <= cnt2.r) { cnt2.t = work_v(cnt2.l, cnt2.r); cnt2.l_ = work_index(cnt2.l, cnt2.r); q.push(cnt2); } cnt2 = cnt; cnt2.l = cnt.l_ + 1; cnt2.r = cnt.r; if (cnt2.l <= cnt2.r) { cnt2.t = work_v(cnt2.l, cnt2.r); cnt2.l_ = work_index(cnt2.l, cnt2.r); q.push(cnt2); } } printf("%lld", ans); return 0; }