SenseTime Ace Coder Challenge 暨商汤在线编程挑战赛*

预处理四个角，枚举重叠段，发现可以前缀max

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int INF = 1e9;
  4 int G[1111][1111], lu[1111][1111], ru[1111][1111], ld[1111][1111], rd[1111][1111];
  5 
  6 int main(){
  7     int T;
  8     scanf("%d", &T);
  9     for(int kase = 1; kase <= T; kase++){
 10         int n, m;
 11         scanf("%d %d", &n, &m);
 12         for(int i = 1; i <= n; ++i)
 13             for(int j = 1; j <= m; ++j)
 14                 scanf("%d", &G[i][j]);
 15         // lu
 16         lu[1][1] = G[1][1];
 17         for(int i = 1; i <= n; ++i){
 18             for(int j = 1; j <= m; ++j){
 19                 if(i == 1 && j == 1) continue;
 20                 if(i == 1) lu[i][j] = lu[i][j-1] + G[i][j];
 21                 else if(j == 1) lu[i][j] = lu[i-1][j] + G[i][j];
 22                 else lu[i][j] = max(lu[i-1][j], lu[i][j-1]) + G[i][j];
 23             }
 24         }
 25         // ru
 26         ru[1][m] = G[1][m];
 27         for(int i = 1; i <= n; ++i){
 28             for(int j = m; j >= 1; --j){
 29                 if(i == 1 && j == m) continue;
 30                 if(i == 1) ru[i][j] = ru[i][j+1] + G[i][j];
 31                 else if(j == m) ru[i][j] = ru[i-1][j] + G[i][j];
 32                 else ru[i][j] = max(ru[i-1][j], ru[i][j+1]) + G[i][j];
 33             }
 34         }
 35         // ld
 36         ld[n][1] = G[n][1];
 37         for(int i = n; i >= 1; --i){
 38             for(int j = 1; j <= m; ++j){
 39                 if(i == n && j == 1) continue;
 40                 if(i == n) ld[i][j] = ld[i][j-1] + G[i][j];
 41                 else if(j == 1) ld[i][j] = ld[i+1][j] + G[i][j];
 42                 else ld[i][j] = max(ld[i+1][j], ld[i][j-1]) + G[i][j];
 43             }
 44         }
 45         // rd
 46         rd[n][m] = G[n][m];
 47         for(int i = n; i >= 1; --i){
 48             for(int j = m; j >= 1; --j){
 49                 if(i == n && j == m) continue;
 50                 if(i == n) rd[i][j] = rd[i][j+1] + G[i][j];
 51                 else if(j == m) rd[i][j] = rd[i+1][j] + G[i][j];
 52                 else rd[i][j] = max(rd[i+1][j], rd[i][j+1]) + G[i][j];
 53             }
 54         }
 55 
 56         int ans = -INF;
 57         for(int i = 1; i <= n; ++i){
 58             int sum = 0, M = -INF;
 59             for(int j = 1; j <= m; ++j){
 60                 int t1, t2;
 61                 if(i == 1 && j == 1) t1 = ld[i+1][j];
 62                 else if(i == n && j == 1) t1 = lu[i-1][j];
 63                 else if(i == 1) t1 = lu[i][j-1] + ld[i+1][j];
 64                 else if(i == n) t1 = lu[i-1][j] + ld[i][j-1];
 65                 else if(j == 1) t1 = lu[i-1][j] + ld[i+1][j];
 66                 else t1 = max(lu[i-1][j] + ld[i+1][j], max(lu[i-1][j] + ld[i][j-1], lu[i][j-1] + ld[i+1][j]));
 67                 if(i == 1 && j == m) t2 = rd[i+1][j];
 68                 else if(i == n && j == m) t2 = ru[i-1][j];
 69                 else if(i == 1) t2 = ru[i][j+1] + rd[i+1][j];
 70                 else if(i == n) t2 = ru[i-1][j] + rd[i][j+1];
 71                 else if(j == m) t2 = ru[i-1][j] + rd[i+1][j];
 72                 else t2 = max(ru[i-1][j] + rd[i+1][j], max(ru[i-1][j] + rd[i][j+1], ru[i][j+1] + rd[i+1][j]));
 73                 ans = max(ans, sum + G[i][j] + t2 + M);
 74                 M = max(M, t1 - sum);
 75                 sum += G[i][j];
 76             }
 77         }
 78         for(int j = 1; j <= m; ++j){
 79             int sum = 0, M = -INF;
 80             for(int i = 1; i <= n; ++i){
 81                 int t1, t2;
 82                 if(i == 1 && j == 1) t1 = ru[i][j+1];
 83                 else if(i == 1 && j == m) t1 = lu[i][j-1];
 84                 else if(j == 1) t1 = lu[i-1][j] + ru[i][j+1];
 85                 else if(j == m) t1 = lu[i][j-1] + ru[i-1][j];
 86                 else if(i == 1) t1 = lu[i][j-1] + ru[i][j+1];
 87                 else t1 = max(lu[i][j-1] + ru[i][j+1], max(lu[i][j-1] + ru[i-1][j], lu[i-1][j] + ru[i][j+1]));
 88                 if(i == n && j == 1) t2 = rd[i][j+1];
 89                 else if(i == n && j == m) t2 = ld[i][j-1];
 90                 else if(j == 1) t2 = ld[i+1][j] + rd[i][j+1];
 91                 else if(j == m) t2 = ld[i][j-1] + rd[i+1][j];
 92                 else if(i == n) t2 = ld[i][j-1] + rd[i][j+1];
 93                 else t2 = max(ld[i][j-1] + rd[i][j+1], max(ld[i][j-1] + rd[i+1][j], ld[i+1][j] + rd[i][j+1]));
 94                 ans = max(ans, sum + G[i][j] + t2 + M);
 95                 M = max(M, t1 - sum);
 96                 sum += G[i][j];
 97             }
 98         }
 99         for(int i = 2; i < n; i++)
100             for(int j = 2; j < m; ++j)
101                 ans = max(ans, G[i][j] + max(lu[i-1][j] + rd[i+1][j] + ru[i][j+1] + ld[i][j-1], lu[i][j-1] + rd[i][j+1] + ru[i-1][j] + ld[i+1][j]));
102         printf("Case #%d: %d
", kase, ans);
103     }
104     return 0;
105 }

Aguin

1 #include <bits/stdc++.h> 2 using namespace std; 3 int G1[222][222], G2[222][222]; 4 5 int main(){ 6 int T; 7 scanf("%d", &T); 8 for(int kase = 1; kase <= T; ++kase){ 9 int N; 10 scanf("%d", &N); 11 for(int i = 1; i <= N; ++i){ 12 char s[222]; 13 scanf("%s", s + 1); 14 for(int j = 1; j <= N; ++j) 15 G1[i][j] = (s[j] == '1' ? 1 : 0), G2[i][j] = 0; 16 } 17 for(int i = 1; i <= N; ++i){ 18 for(int j = 1; j <= N; ++j){ 19 if(!G1[i][j]) continue; 20 for(int k = 1; k <= N; ++k) G2[i][k] += G1[j][k]; 21 } 22 } 23 int ans = 0; 24 for(int i = 1; i <= N; ++i){ 25 for(int k = 1; k <= N; ++k){ 26 if(i == k) continue; 27 int c = 0; 28 for(int p = 1; p <= N; ++p){ 29 if(p == i || p == k) continue; 30 if(G2[i][p] && G1[k][p]) c++; 31 } 32 for(int j = 1; j <= N; ++j){ 33 if(j == i || j == k) continue; 34 if(!G1[i][j] || !G1[k][j]) continue; 35 int b = G2[i][j] && G1[k][j] ? 1 : 0; 36 ans += c - b; 37 } 38 } 39 } 40 for(int j = 1; j <= N; ++j){ 41 for(int p = 1; p <= N; ++p){ 42 if(!G1[j][p]) continue; 43 int c = 0; 44 for(int k = 1; k <= N; ++k) c += G1[j][k] && G1[p][k] ? 1 : 0; 45 for(int i = 1; i <= N; ++i){ 46 if(i == j || i == p) continue; 47 if(!G1[i][j]) continue; 48 if(G2[i][p] != 1) continue; 49 int b = G1[j][i] && G1[p][i] ? 1 : 0; 50 ans -= c - b + c - b; 51 } 52 } 53 } 54 for(int i = 1; i <= N; ++i){ 55 for(int p = 1; p <= N; ++p){ 56 if(i == p) continue; 57 if(G2[i][p] != 2) continue; 58 vector<int> v; 59 for(int k = 1; k <= N; ++k) 60 if(G1[i][k] && G1[p][k]) v.push_back(k); 61 if(G1[v[0]][v[1]]) ans -= 2; 62 } 63 } 64 printf("Case #%d: %s ", kase, ans > 0 ? "Starfish!" : "Walk Walk"); 65 } 66 return 0; 67 }

1 #include <bits/stdc++.h> 2 using namespace std; 3 4 void FWT_Xor(int *A, int len) { 5 if (len == 1) return; 6 int len2 = len >> 1; 7 FWT_Xor(A, len2); 8 FWT_Xor(A + len2, len2); 9 for (int i = 0; i < len2; ++i) { 10 int x = A[i], y = A[i + len2]; 11 A[i] = x + y; 12 A[i + len2] = x - y; 13 } 14 } 15 16 void IFWT_Xor(int *A, int len) { 17 if (len == 1) return; 18 int len2 = len >> 1; 19 for (int i = 0; i < len2; ++i) { 20 int x = A[i], y = A[i + len2]; 21 A[i] = (x + y) >> 1; 22 A[i + len2] = (x - y) >> 1; 23 } 24 IFWT_Xor(A, len2); 25 IFWT_Xor(A + len2, len2); 26 } 27 28 int a[66]; 29 int main(){ 30 int T; 31 scanf("%d", &T); 32 for(int kase = 1; kase <= T; ++kase){ 33 int n, ok = 1, sum = 0; 34 scanf("%d", &n); 35 for(int i = 0; i < 64; ++i) scanf("%d", a + i), sum += a[i]; 36 if(sum != n * n * n) ok = 0; 37 FWT_Xor(a, 64); 38 for(int i = 0; i < 64; ++i){ 39 int flag = 0; 40 for(int j = 0; j * j * j <= abs(a[i]); ++j) 41 if(j * j * j == a[i]) {a[i] = j; flag = 1; break;} 42 else if(j * j * j == -a[i]) {a[i] = -j; flag = 1; break;} 43 if(!flag) ok = 0; 44 } 45 IFWT_Xor(a, 64); 46 vector<int> ans; 47 for(int i = 0; i < 64; ++i) 48 if(a[i] < 0) ok = 0; 49 else for(int j = 0; j < a[i]; ++j) 50 ans.push_back(i); 51 printf("Case #%d:", kase); 52 if(!ok || ans.size() != n) puts(" -1"); 53 else{ 54 for(int i = 0; i < ans.size(); ++i) printf(" %d", ans[i]); 55 puts(""); 56 } 57 } 58 return 0; 59 }

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 6e5 + 10; 4 typedef long long LL; 5 typedef pair<LL, LL> pii; 6 vector<pii> vec; 7 int u[maxn], v[maxn]; 8 vector<int> G[maxn]; 9 LL tag[maxn], sum[maxn]; 10 11 int fa[maxn]; 12 int Find(int x){ 13 return fa[x] == x ? x : fa[x] = Find(fa[x]); 14 } 15 void Union(int x, int y){ 16 x = Find(x), y = Find(y); 17 if(x == y) return; 18 fa[y] = x; 19 } 20 21 int n, sz[maxn]; 22 void dfs1(int x){ 23 sz[x] = x <= n ? 1 : 0; 24 for(int i = 0; i < G[x].size(); ++i) dfs1(G[x][i]), sz[x] += sz[G[x][i]]; 25 } 26 void dfs2(int x, LL o){ 27 sum[x] = o; 28 for(int i = 0; i < G[x].size(); ++i) dfs2(G[x][i], o + tag[x] * (sz[x] - sz[G[x][i]])); 29 } 30 31 int main(){ 32 int T; 33 scanf("%d", &T); 34 for(int kase = 1; kase <= T; ++kase){ 35 int m; 36 scanf("%d %d", &n, &m); 37 int id = n; 38 for(int i = 1; i <= n + n; ++i) fa[i] = i, G[i].clear(), tag[i] = 0; 39 vec.clear(); 40 for(int i = 1; i <= m; ++i){ 41 LL w; 42 scanf("%d %d %lld", u + i, v + i, &w), 43 vec.push_back(pii(w, i)); 44 } 45 sort(vec.begin(), vec.end()); 46 for(int i = 0; i < m; ++i){ 47 int x = vec[i].second; 48 if(Find(u[x]) == Find(v[x])) continue; 49 LL w = vec[i].first; 50 tag[++id] = w; 51 G[id].push_back(Find(u[x])); 52 G[id].push_back(Find(v[x])); 53 Union(id, Find(u[x])); 54 Union(id, Find(v[x])); 55 } 56 dfs1(id); 57 dfs2(id, 0); 58 LL ans = 0; 59 for(int i = 1; i <= n; ++i) ans ^= sum[i] * i; 60 printf("Case #%d: %lld ", kase, ans); 61 } 62 return 0; 63 }

SenseTime Ace Coder Challenge 暨 商汤在线编程挑战赛*

相关推荐

SenseTime Ace Coder Challenge 暨商汤在线编程挑战赛*