CodeForces 628E Zbazi in Zeydabad
这个树状数组很巧妙。
将$O(n^3)$降到$O(n^2logn)$。
每个对角线的加和相等，建在一棵树上。
#include <bits/stdc++.h> using namespace std; const int maxn = 3005; int c[maxn << 1][maxn]; int l[maxn][maxn]; int dig[maxn][maxn]; int r[maxn][maxn]; char s[maxn][maxn]; int n, m; typedef long long ll; void add(int id, int x) { while(x <= n) { c[id][x] += 1; x += (x & -x); } } int sum(int id, int x) { int res = 0; while(x > 0) { res += c[id][x]; x -= (x & -x); } return res; } int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%s", s[i] + 1); } /// O(nm)预处理出向左的最长，向左下的最长，还有是不是水平线段的最右点 for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(s[i][j] == '.') { l[i][j] = 0; } else if(s[i][j] == 'z') { l[i][j] = l[i][j - 1] + 1; } if(s[i][j + 1] != 'z') { r[i][j] = 0; } else r[i][j] = 1; } } for(int i = n; i >= 1; i--) { for(int j = 1; j <= m; j++) { if(s[i][j] == '.') { dig[i][j] = 0; } else { dig[i][j] = dig[i + 1][j - 1] + 1; } } } ll ans = 0; for(int j = m; j >= 1; j--) { for(int i = 1; i <= n; i++) { if(s[i][j] == 'z' && r[i][j] == 0) { int pos = j; while(s[i][pos] == 'z') { add(i + pos, i); pos--; } } } for(int i = 1; i <= n; i++) { if(s[i][j] == 'z') ///枚举右上端点 { ans += sum(i + j, i + min(l[i][j], dig[i][j]) - 1) - sum(i + j, i - 1); } } } printf("%lld ", ans); return 0; }
写的傻逼样，明天再改吧。
傻逼代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; int dp1[33][33][3]; int dp2[33][33][3]; char s[33][33]; int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%s", s[i] + 1); } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(s[i][j] == 'B') { for(int p = 1; p <= i; p++) { for(int q = 1; q <= j; q++) { if(s[p][q] == '.') { s[p][q] = 'B'; } } } } } } for(int i = n; i >= 1; i--) { for(int j = m; j >= 1; j--) { if(s[i][j] == 'R') { for(int p = n; p >= i; p--) { for(int q = m; q >= j; q--) { if(s[p][q] == '.') { s[p][q] = 'R'; } } } } } } for(int i = 1; i <= n; i++) printf("%s ", s[i] + 1); if(s[1][1] == 'B' || s[1][1] == '.') dp1[1][1][0] = 1; if(s[n][m] == 'R' || s[n][m] == '.') dp2[n][m][1] = 1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++)= { if(i == 1 && j == 1) continue; if(s[i][j] == 'B') { ///那我就检查是否合法 int flag = 0; if(j > 1 && dp1[i][j - 1][0] == 0) flag = 1; if(i > 1 && dp1[i - 1][j][0] == 0) flag = 1; if(!flag) dp1[i][j][0] = 1; else dp1[i][j][0] = 0; } } } for(int i = n; i >= 1; i--) { for(int j = m; j >= 1; j--) { if(i == n && j == m) continue; if(s[i][j] == 'R' || s[i][j] == '.') { int flag = 0; if(i < n && dp2[i + 1][j][1] == 0) flag = 1; if(j < m && dp2[i][j + 1][1] == 0) flag = 1; if(!flag) dp2[i][j][0] = 1; else dp2[i][j][0] = 0; } } } int ans = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { } } printf("%d ", ans); return 0; } /* 7 6 ...... .....B .B..R. ...... ...B.. ...... .R.R.. */
学习了一份优秀的代码，$l$数组和$r$数组加的非常好，这样就把区间缩小到可变化的范围内。
转移从上一行右边转移过来，$dp[i][j]=sum_{k=max(l[i-1],j)}^{r[i]}dp[i-1][k]$。
之前没想好转移方程。
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll dp[33][33]; char s[33][33]; int l[33], r[33]; int main() { int n, m; scanf("%d %d", &n, &m); int flag = 0; for(int i = 1; i <= n; i++) { scanf("%s", s[i] + 1); l[i] = 0, r[i] = m; for(int j = 1; j <= m; j++) { if(s[i][j] == 'B') l[i] = max(l[i], j); if(s[i][j] == 'R') r[i] = min(r[i], j - 1); } if(l[i] > r[i]) flag = 1; } if(flag) { printf("0 "); return 0; } memset(dp, 0, sizeof(dp)); for(int i = l[1]; i <= r[1]; i++) { dp[1][i] = 1; } for(int i = 2; i <= n; i++) { for(int j = l[i]; j <= r[i]; j++) { for(int k = max(l[i - 1], j); k <= r[i - 1]; k++) { dp[i][j] += dp[i - 1][k]; } } } ll sum = 0; for(int i = l[n]; i <= r[n]; i++) sum += dp[n][i]; printf("%lld ", sum); }