Solution
据说正解DP30行？？？
然后写了100行的状压DP？？
疯狂特判，一算极限时间复杂度过不了aaa！！
然而还是过了....QAQ
所以我定的状态是待转移的位置的前三位，用6位二进制位表示，每2位表示一个位置的状态。然后特判转移就可以了QAQ
Code
#include<bits/stdc++.h> #define LL long long #define mod 1000000007 #define RG register using namespace std; char fi[1000005]; int a[1000005]; LL dp[2][123]; int len; int change(char x) { if(x == '?') return 4; if(x == '*') return 3; if(x == '0') return 0; if(x == '1') return 1; if(x == '2') return 2; } bool check(int s, int i) { int pre = s & (3 << 4); int s1 = s >> 4, s2 = (s ^ pre) >> 2, s3 = s & 3; if(~a[i] && a[i] != 4 && s3 != a[i]) return 0; if(i - 1 > 0 && a[i - 1] != 4 && s2 != a[i - 1]) return 0; if(i - 2 > 0 && a[i - 2] != 4 && s1 != a[i - 2]) return 0; if(i == len) { if(s3 == 1 && s2 != 3) return 0; if(s3 == 2) return 0; if(s3 == 3 && s2 == 0) return 0; } if(i == 1) { if(s1 || s2) return 0; if(s3 == 2) return 0; return 1; } else if(i == 2) { if(s1) return 0; if(s2 == 0 && s3 == 3) return 0; if(s2 == 1 && s3 != 3) return 0; if(s2 == 2) return 0; if(s2 == 3 && s3 == 0) return 0; if(s3 == 2 && s2 != 3) return 0; return 1; } if(s1 == 0 && s2 == 3) return 0; if(s1 == 1 && s2 == 2) return 0; if(s1 == 2 && s2 != 3) return 0; if(s1 == 3 && s2 == 0) return 0; if(s2 == 0 && (s1 == 3 || s3 == 3)) return 0; if(s2 == 1 && s1 == 3 && s3 == 3) return 0; if(s2 == 1 && (s1 != 3 && s3 != 3)) return 0; if(s2 == 2 && (s1 != 3 || s3 != 3)) return 0; if(s2 == 3 && (s1 == 0 || s3 == 0)) return 0; if(s3 == 0 && s2 == 3) return 0; if(s3 == 1 && s2 == 2) return 0; if(s3 == 2 && s2 != 3) return 0; if(s3 == 3 && s2 == 0) return 0; return 1; } int main() { freopen("mine.in", "r", stdin); freopen("mine.out", "w", stdout); scanf("%s", fi + 1); len = strlen(fi + 1); if(len == 1) { if(fi[1] == '0' || fi[1] == '?') puts("1"); else puts("0"); return 0; } memset(a, -1, sizeof(a)); for(int i = 1; i <= len; i ++) a[i] = change(fi[i]); int now = 0; if(a[1] != 4) { dp[now][a[1]] = 1; } else dp[now][0] = dp[now][1] = dp[now][2] = dp[now][3] = 1; for(RG int i = 2; i <= len; i ++) { now ^= 1; memset(dp[now], 0, sizeof(dp[now])); for(RG int s = 0; s < (1 << 6); s ++) { int pre = s & (3 << 4); if(!check(s, i - 1)) continue; if(a[i] != 4) { int ss = (s ^ pre) << 2 | a[i]; if(!check(ss, i)) continue; dp[now][ss] = (dp[now ^ 1][s] + dp[now][ss]) % mod; } else { for(RG int k = 0; k <= 3; k ++) { int ss = (s ^ pre) << 2 | k; if(!check(ss, i)) continue; dp[now][ss] = (dp[now ^ 1][s] + dp[now][ss]) % mod; } } } } LL ans = 0; for(int s = 0; s < (1 << 6); s ++) if(check(s, len)) ans = (ans + dp[now][s]) % mod; printf("%lld", ans); return 0; }
Solution
完全把题意理解错了QAQ
以为从每一个点开始一直就只能向上下左右四个方向走了QAQ
结果一波暴力还得了20pts？？
正解不懂QAQ然而$zyl$dalao爆搜轻松过！
其实也不是很暴力的搜辣，加上记忆化剪枝，大大的好！
先预处理出可以流出去的位置们，然后对于每一个位置暴力bfs它们的所有路径QAQ，记忆化剪枝效果非常好了QAQ
很有道理的样子呢QAQ
我们要找的实际上就是每个点出去的每条路径上最大值的最小值，而想到最小生成树就是满足这个性质，最大边最小。
所以按边权排序加边，两个联通块中如果一个已经有出去的节点，另一个没有，那么更新没有的那个联通块的答案就是这条新加的边权。
吼麻烦啊QAQ
#include<bits/stdc++.h> using namespace std; int h[305][305], n, m; int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}; inline void read(int &x) { x = 0; int t = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') t = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } x *= t; } bool check(int x, int y) { return x >= 0 && y >= 0 && x <= n + 1 && y <= m + 1; } int vis[305][305], vis1[305][305], ans[305][305]; int idc, tmp; void dfr(int x, int y) { if(vis[x][y]) return ; vis[x][y] = 1; for(int k = 0; k < 4; k ++) { int xx = x + dx[k], yy = y + dy[k]; if(!check(xx, yy)) ans[x][y] = 0; else if(h[xx][yy] <= h[x][y]) { dfr(xx, yy); if(ans[xx][yy] == 0) ans[x][y] = 0; } } } bool dfs(int x, int y, int u) { if(vis1[x][y] == idc) return 1; if(h[x][y] > u) { tmp = min(tmp, h[x][y] + ans[x][y]); return 1; } if(ans[x][y] == 0) return 0; vis1[x][y] = idc; for(int k = 0; k < 4; k ++) { int xx = x + dx[k], yy = y + dy[k]; if(!dfs(xx, yy, u)) return 0; } return 1; } struct Point { int x, y, h; bool operator < (const Point &t) const { return h > t.h; } } points[305 * 305]; int main() { freopen("water.in", "r", stdin); freopen("water.out", "w", stdout); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) { read(h[i][j]); points[(i - 1) * m + j] = (Point) {i, j, h[i][j]}; } sort(points + 1, points + 1 + n * m); memset(ans, -1, sizeof(ans)); for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) dfr(i, j); for(int i = 1; i <= n * m; i ++) { idc ++; tmp = 0x3f3f3f3f; if(!dfs(points[i].x, points[i].y, points[i].h)) ans[points[i].x][points[i].y] = 0; else ans[points[i].x][points[i].y] = tmp - points[i].h; } for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) printf("%d ", ans[i][j]); printf(" "); } return 0; }