今天是我调代码最久的y一天
题解:
第一题：
check的时候记录c字符从左区间向右第一次出现cmin, 和最后一次出现cmax;
如果这个区间合法，就有cmax(c -1) < cmin(c);
这道题的细节很多，比如其中一个字符没有出现怎么办（数据中每组都有这种情况，还有边界的取舍）；
我调了一下午，最后又是请zjj同学帮我看的， 结果多组数据初值没有搞好
#include<bits/stdc++.h> using namespace std; const int M = 100005; int T, C, cmin[5], cmax[5], L; int m, a[5], t[5], p[M][5][2], pos[M]; void check(int len){ for(int c = 0; c < C; c++)cmax[c] = 0, cmin[c] = len; for(int lf = 1; lf <= L; ){ int rg = min(lf + len - 1, L); for(int c = 0; c < C; c++){ if(p[rg][c][0] >= lf)cmax[c] = max(cmax[c], p[rg][c][0] - lf + 1); if(p[lf][c][1] <= rg)cmin[c] = min(cmin[c], p[lf][c][1] - lf ); } lf += len; } for(int c = 0; c < C; c++){ if(cmax[c] == 0) cmin[c] = c ? cmax[c - 1] : 0, cmax[c] = cmin[c] + 1; else if(cmin[c] > (c ? cmax[c - 1] : 0)) cmin[c] = c ? cmax[c - 1] : 0; else if(c && cmin[c] < cmax[c - 1])return ; } if(cmax[C - 1] > len)return; cmax[C - 1] = len; for(int c = 0; c < C; c++){ t[c] = cmax[c] - cmin[c]; if(t[c] > a[c])return; } for(int c = 0; c < C; c++)a[c] = t[c]; } int fg = 0; int main(){ freopen("char.in","r",stdin); freopen("char.out","w",stdout); scanf("%d%d", &T, &C); while(T--){ scanf("%d", &m); L = 0; fg++; memset(pos, 0, sizeof(pos)); for(int i = 1; i <= m; i++){ int t, z; scanf("%d%d", &t, &z); L = max(L, t); pos[t] = z + 1; } for(int c = 0; c < C; c++)a[c] = L + C + 1; for(int i = 1; i <= L; i++){ for(int c = 0; c < C; c++) p[i][c][0] = p[i - 1][c][0]; if(pos[i]) p[i][pos[i] - 1][0] = i; } for(int c = 0; c < C; c++)p[L + 1][c][1] = L + 1; for(int i = L; i; i--){ for(int c = 0; c < C; c++) p[i][c][1] = p[i + 1][c][1]; if(pos[i]) p[i][pos[i] - 1][1] = i; } for(int len = C; len < C + L; len++) check(len); if(a[0] == L + C + 1)puts("NO"); else { for(int c = 0; c < C; c++)printf("%d ", a[c]); puts(""); } } }
第二题：
老师说这道题没做出来，根基不牢，我就只能呵呵了
#include<bits/stdc++.h> using namespace std; const int M = 2005; #define ll long long ll dp[2][M], a[M << 1]; int n; const ll inf = 1e15; inline int moc(int i){return i ? i : n;} int main(){ freopen("cake.in","r",stdin); freopen("cake.out","w",stdout); scanf("%d", &n); for(int i = 1; i <= n; i++)scanf("%I64d", a + i), a[n + i] = a[i], dp[0][i] = a[i]; ll ans = 0; a[0] = a[n]; int l, o; for( l = 1, o = 0; l < n; l++, o ^= 1){ for(int i = 1; i <= n; i++)dp[o ^ 1][i] = -inf; if(o) for(int i = 1; i <= n; i++){ dp[0][moc(i - 1)] = max(dp[0][moc(i - 1)], dp[1][i] + a[i - 1]); dp[0][i] = max(dp[0][i], dp[1][i] + a[i + l]); } else for(int i = 1; i <= n; i++){ if(a[i - 1] >= a[i + l])dp[1][moc(i - 1)] = max(dp[1][moc(i - 1)], dp[0][i]); if(a[i - 1] <= a[i + l])dp[1][i] = max(dp[1][i], dp[0][i]); } //for(int i = 1; i <= n; i++)printf("%I64d ", dp[o ^ 1][i]);puts(""); } for(int i = 1; i <= n; i++) ans = max(ans, dp[o][i]); printf("%I64d\n",ans); }
第三题：
多个方向移动，拆点多状态的思想；但是建边复杂度很高，只能边跑边建边，用dijistra第一次跑到最优，就可以少建边了
#include<bits/stdc++.h> using namespace std; #define For(a, b, c) for(int a = b; a <= c; a++) const int M = 2 * 1e6; #define ll long long const ll inf = 1e18; ll dis[505][505][3], dir[505][505]; int q[M >> 1]; int zl[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; struct sta{ int k, x, y; ll dis; bool operator < (const sta & rhs) const{ return dis > rhs.dis; } }; priority_queue <sta> Q; int main(){ freopen("game.in","r",stdin); freopen("game.out","w",stdout); int X, Y, N, sx, sy, tx, ty; ll A, B, C; scanf("%d%d%I64d%I64d%I64d%d", &X, &Y, &A, &B, &C, &N); memset(dir, -1, sizeof(dir)); For(i, 1, N){ int x, y; scanf("%d%d", &x, &y); dir[x][y] = 0; if(i == 1)sx = x, sy = y; if(i == N)tx = x, ty = y; } int lf = 0, rg = 0; For(x, 0, X) For(y, 0, Y) if(!dir[x][y]) q[++rg] = x, q[++rg] = y; while(lf != rg){ int x = q[++lf], y = q[++lf]; for(int k = 0; k < 4; k++){ int u = x + zl[k][0], v = y + zl[k][1]; if((u >= 0 && u <= X && v <= Y && v >= 0) && dir[u][v] == -1){ dir[u][v] = dir[x][y] + C; q[++rg] = u, q[++rg] = v; } } } For(x, 0, X) For(y, 0, Y) For(k, 0, 3)dis[x][y][k] = inf + 1; Q.push((sta) { 2, sx, sy, 0 }); while(!Q.empty()){ sta u = Q.top(); Q.pop(); if(dis[u.x][u.y][u.k] < inf)continue; dis[u.x][u.y][u.k] = u.dis; //printf("%d %d %d %I64d\n",u.x,u.y,u.k,u.dis); if(u.x == tx && u.y == ty)break; switch(u.k){ case 2:{ if(dis[u.x][u.y][0] > inf)Q.push((sta){0, u.x, u.y, u.dis + B}); if(dis[u.x][u.y][1] > inf)Q.push((sta){1, u.x, u.y, u.dis + B}); for(int k = 0; k < 4; k++){ int vx = u.x + zl[k][0], vy = u.y + zl[k][1]; if(vx >= 0 && vx <= X && vy >= 0 && vy <= Y && dis[vx][vy][2] > inf) Q.push((sta){2, vx, vy, u.dis + C}); } break; } default:{ if(dis[u.x][u.y][2] > inf) Q.push((sta){2, u.x, u.y, u.dis + dir[u.x][u.y]}); for(int k = u.k; k < 4; k += 2){ int vx = u.x + zl[k][0], vy = u.y + zl[k][1]; if(vx >= 0 && vx <= X && vy >= 0 && vy <= Y && dis[vx][vy][u.k] > inf) Q.push((sta){u.k, vx, vy, u.dis + A}); } } } } printf("%I64d\n", min(dis[tx][ty][1], min(dis[tx][ty][0], dis[tx][ty][2]))); }
最后在说一句，林荫的大佬太强啦，完全吊打我们这边的