[关闭]
@2368860385 2018-12-20T11:19:06.000000Z 字数 6101 阅读 206

北京八十中集训——day4

比赛总结

预计：100+100+0
实际：100+100+0
第三题最后1分钟交的，一交就测了（按提交时间逆序评测），不用预计了，直接返回了成绩。

考试过程

T1
感觉比较可做，写了三个小时，有点慢了，最后由于一个bug调了很长时间，和暴力拍上就交了（一直担心暴力也是错的。。）
T2
读完题感觉是树形背包，写完T1，写了半小时，过了样例，就交了。试了几组小样例，发现了一个bug！！！，然后改，改完过了就交了；又试了一组小样例，又发现一个bug，改过又交了；又试了一组小样例，又发现一个bug，改过又叫了....（重复几次）；由于不知道怎么拍，只能靠造几组小样例检验，最后又改了几个地方，使代码更安全，就交了。

幸亏多试了几组，前面的交的全0分。。
T3
写完前两道，看的第三道，（T1花了3个小时，T2半小时，此时还有半小时），读完好像是网络流，感觉不能这么简单吧。。仔细想了会，好像就是网络流。好像有点不敢写（想到noip day1 T3），不过这次还好，坚信，就是简单题！
于是就写了，不过时间紧，思绪混乱，没调出。
混乱到什么程度？开始想二分最大值，写着写着忘了。用费用流判断是否满流。。

总结：
时间分配，T1花的时间有点长。
T3比较好，这次敢写了，其实就是网络流。

T1

n^3：枚举一条水平线，枚举一个高度，计算以这个高度，底是这条线的矩形的贡献。居然可以有70分。
n^2：枚举一条水平线，计算所有以这条水平线为底的矩形的贡献。

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<cmath>
  6. #include<cctype>
  7. #include<set>
  8. #include<map>
  9. #include<queue>
  10. #include<vector>
  11. using namespace std;
  12. typedef long long LL;
  14. inline int read() {
  15.     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  16.     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  17. }
  19. const int N = 2005;
  20. LL tot[N][N], sum2[N], h[N][N], sumh[N][N];
  21. char s[N][N];
  23. inline LL Calc(LL m) { // xigema i=0 to m i * (n - i + 1)
  24.     return m * (m + 1) / 2 * m - sum2[m] + (m * (m + 1)) / 2;
  25. }
  26. void init(int n,int m) {
  27.     int mx = max(n, m);
  28.     for (int i = 1; i <= mx; ++i) sum2[i] = sum2[i - 1] + i * i;
  29.     for (int i = 1; i <= n; ++i) 
  30.         for (int j = 1; j <= m; ++j) 
  31.             tot[i][j] = Calc(i) * Calc(j), h[i][j] = Calc(j) * i;
  32.     for (int j = 1; j <= m; ++j)
  33.         for (int i = 1; i <= n; ++i) 
  34.             sumh[i][j] += sumh[i - 1][j] + h[i][j];
  35. }
  36. /*
  37. namespace BF1{
  38.     int sum[N][N];
  39. //  int tmp[N];
  40.     void solve2(int n,int m) {
  41.         LL Ans = 0;
  42.         for (int i = 1; i <= n; ++i) 
  43.             for (int j = 1; j <= m; ++j) 
  44.                 sum[i][j] = sum[i - 1][j] + (s[i][j] == '#');
  45.         for (int i = 1; i <= n; ++i) {
  46.             for (int j = i; j <= n; ++j) {
  47.                 int last = 0;
  48.                 for (int k = 1; k <= m; ++k) 
  49.                     if (sum[j][k] - sum[i - 1][k]) 
  50. //                      Ans += h[j - i + 1][k - 1 - last], last = k;
  51. //                      tmp[j] += 1ll * Calc(k - 1 - last) * (j - i + 1), 
  52.                         Ans += 1ll * Calc(k - 1 - last) * (j - i + 1), last = k;
  53. //              if (last != m) Ans += h[j - i + 1][m - last];
  54.                 if (last != m) Ans += 1ll * Calc(m - last) * (j - i + 1);
  55. //                  tmp[j] += 1ll * Calc(m - last) * (j - i + 1);
  56.             }
  57.         }
  58. //      for (int i = 1; i <= n; ++i) cout << tmp[i] << " "; puts("");
  59.         cout << Ans;
  60.     }
  61. }
  62. */
  63. int sk[N], u[N][N];
  64. inline LL Calc2(int i,int j,int x,int y) {
  65.     if (x == y) return 0;
  66.     return sumh[y][j - i] - sumh[x][j - i];
  67. }
  68. void solve(int n,int m) {
  69.     for (int i = 1; i <= n; ++i) 
  70.         for (int j = 1; j <= m; ++j) 
  71.             u[i][j] = (s[i][j] == '.' ? u[i - 1][j] + 1 : 0);
  72.     LL Ans = 0;
  73.     for (int top, i = 1; i <= n; ++i) {
  74. //      LL tmp = 0;
  75.         top = 0; sk[++top] = 0;
  76.         for (int j = 1; j <= m; ++j) {
  77.             while (top && u[i][j] < u[i][sk[top]]) {
  78.                 Ans += Calc2(sk[top - 1], j - 1, max(u[i][j], u[i][sk[top - 1]]), u[i][sk[top]]);
  79. //              tmp += Calc2(sk[top - 1], j - 1, max(u[i][j], u[i][sk[top - 1]]), u[i][sk[top]]);
  80.                 top --;
  81.             }
  82.             while (top && u[i][j] == u[i][sk[top]]) top--;
  83.             sk[++top] = j;
  84.         }
  85.         while (top >= 2) {
  86. //          tmp += Calc2(sk[top - 1], m, u[i][sk[top - 1]], u[i][sk[top]]);
  87.             Ans += Calc2(sk[top - 1], m, u[i][sk[top - 1]], u[i][sk[top]]); top --;
  89. //          Ans += Calc2(sk[top - 1], sk[top], u[i][sk[top - 1]], u[i][sk[top]]);top --;
  90.         }
  91. //      cout << tmp << " ";
  92.     }
  93. //  puts("");
  94.     cout << Ans;
  95. }
  97. int main() {
  98. //  freopen("1.txt", "r", stdin);
  99.     int n = read(), m = read();
  100.     for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
  101.     init(n, m);
  102. //  if (n <= 300 && m <= 300) { BF1::solve2(n, m); return 0; }
  103.     solve(n, m);
  104.     return 0;
  105. }
  106. /*
  107. 4 5
  108. #.##.
  109. .#...
  110. #.#..
  111. ..#..
  114. 5 6
  115. ..#..#
  116. #.####
  117. #.#.##
  118. .##..#
  119. ##.###
  121. */

T2

树形dp，有一种情况是进去又不回来了，还有进去后回来。分别转移。

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<cmath>
  6. #include<cctype>
  7. #include<set>
  8. #include<map>
  9. #include<queue>
  10. #include<vector>
  11. using namespace std;
  12. typedef long long LL;
  14. inline int read() {
  15.     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  16.     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  17. }
  19. const int N = 505;
  20. int f[N][N][2], w[N], siz[N];
  21. vector<int> T[N];
  22. int n, m;
  24. void dfs(int u,int fa) {
  25.     f[u][1][0] = f[u][1][1] = w[u]; siz[u] = 1;
  26.     for (int sz = T[u].size(), i = 0; i < sz; ++i) {
  27.         int v = T[u][i];
  28.         if (v == fa) continue;
  29.         dfs(v, u);
  30.         siz[u] += siz[v];
  31.         for (int j = min(siz[u] * 3, m); j >= 1; --j) {
  32.             for (int k = 0, lim = min(j, min(siz[v] * 3, m)); k <= lim; ++k) {
  33.                 if (j - k - 1 >= 0) f[u][j][0] = max(f[u][j][0], f[v][k][0] + f[u][j - k - 1][1]);
  34.                 if (j - k - 2 >= 0) f[u][j][0] = max(f[u][j][0], f[v][k][1] + f[u][j - k - 2][0]);
  35.                 if (j - k - 2 >= 0) f[u][j][1] = max(f[u][j][1], f[v][k][1] + f[u][j - k - 2][1]);
  36.             }
  37.         }
  38.     }
  39. }
  41. int main() {
  42. //  freopen("1.txt", "r", stdin);
  43.     n = read(), m = read();
  44.     for (int i = 1; i <= n; ++i) w[i] = read();
  45.     for (int i = 1; i < n; ++i) {
  46.         int u =read(),v = read(); T[u].push_back(v); T[v].push_back(u);
  47.     }
  48.     dfs(1, 0);
  49.     int ans = 0;
  50.     for (int i = 0; i <= m; ++i) ans = max(ans, max(f[1][i][0], f[1][i][1]));
  51.     cout << ans;
  52.     return 0;
  53. }
  54. /*
  55. 2 1
  56. 8 9
  57. 1 2
  60. 2 2
  61. 8 9
  62. 1 2
  65. 2 3
  66. 8 9
  67. 1 2
  69. 3 5
  70. 9 2 5
  71. 1 2
  72. 1 3
  74. 5 8
  75. 3 2 3 4 1
  76. 1 2
  77. 1 3
  78. 2 4
  79. 2 5
  81. */

T3

二分最大值，建图，网络流判断是否满流。

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<cmath>
  6. #include<cctype>
  7. #include<set>
  8. #include<map>
  9. #include<queue>
  10. #include<vector>
  11. using namespace std;
  12. typedef long long LL;
  14. inline int read() {
  15.     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  16.     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  17. }
  19. const int N = 105 * 5;
  20. struct Edge{
  21.     int to, nxt, c;
  22.     Edge() {}
  23.     Edge(int x,int y,int z) { to = x, nxt = y, c = z; }
  24. }e[1000005];
  25. struct Node{
  26.     int x, y;
  27. }A[N], B[N];
  28. int head[N], q[N], dis[N], D[N][N], cur[N];
  29. vector<int> C[N];
  30. int En = 1, S, T, n, m, c, k;
  32. inline void add_edge(int u,int v,int w) {
  33.     ++En; e[En] = Edge(v, head[u], w); head[u] = En;
  34.     ++En; e[En] = Edge(u, head[v], 0); head[v] = En;    
  35. }
  36. inline int sqr(int x) { return x * x; }
  37. inline int dist(const Node &A,const Node &B) { return sqr(A.x - B.x) + sqr(A.y - B.y); }
  39. bool bfs() {
  40.     for (int i = 0; i <= T; ++i) dis[i] = -1, cur[i] = head[i];
  41.     int L = 1, R = 0; q[++R] = S, dis[S] = 0;
  42.     while (L <= R) {
  43.         int u = q[L ++];
  44.         for (int i = head[u]; i; i = e[i].nxt) {
  45.             int v = e[i].to;
  46.             if (dis[v] == -1 && e[i].c > 0) {
  47.                 dis[v] = dis[u] + 1; q[++R] = v;
  48.                 if (v == T) return 1;
  49.             }
  50.         }
  51.     }
  52.     return 0;
  53. }
  54. int dfs(int u,int flow) {
  55.     if (u == T) return flow;
  56.     int used = 0;
  57.     for (int &i = cur[u]; i; i = e[i].nxt) {
  58.         int v = e[i].to;
  59.         if (dis[v] == dis[u] + 1 && e[i].c > 0) {
  60.             int t = dfs(v, min(flow - used, e[i].c));
  61.             if (t > 0) {
  62.                 e[i].c -= t, e[i ^ 1].c += t;
  63.                 used += t;
  64.                 if (used == flow) break;
  65.             }
  66.         }
  67.     }
  68.     if (flow != used) dis[u] = -1;
  69.     return used;
  70. }
  71. int Dinic() {
  72.     int ans = 0;
  73.     while (bfs()) ans += dfs(S, 1e9);
  74.     return ans;
  75. }
  76. bool check(int x) {
  77.     En = 1;
  78.     for (int i = 0; i <= T; ++i) head[i] = 0;  // T!!! not n
  79.     for (int i = 1; i <= n; ++i) add_edge(S, i, 1);
  80.     for (int i = 1; i<= n; ++i) 
  81.         for (int j = 1; j <= m; ++j) 
  82.             if (D[i][j] <= x) add_edge(i, j + n, 1);
  83.     for (int i = 1; i <=k; ++i) 
  84.         for (int sz = C[i].size(), j = 0; j < sz; ++j) 
  85.             add_edge(C[i][j] + n, i + n + m, 1e9);
  86.     for (int i = 1; i <= k; ++i) add_edge(i + n + m, T, c);
  87.     return Dinic() == n;
  88. }
  89. int main() {
  90.     n = read(), m =read(), c = read(), k = read();
  91.     for (int i = 1; i <= n; ++i) A[i].x = read(), A[i].y = read();
  92.     for (int i = 1; i <= m; ++i) B[i].x = read(), B[i].y = read();
  93.     for (int i = 1; i <= k; ++i) 
  94.         for (int T = read(); T--; ) C[i].push_back(read());
  95.     S = 0, T = n + m + k + 1; // T = n + n + k !!!
  96.     int L = 0, R = 0, ans = 0;
  97.     for (int i = 1; i <= n; ++i) 
  98.         for (int j = 1; j <= m; ++j) 
  99.             R = max(R, D[i][j] = dist(A[i], B[j]));
  100.     while (L <= R) {
  101.         int mid = (L + R) >> 1;
  102.         if (check(mid)) ans = mid, R = mid - 1;
  103.         else L = mid + 1;
  104.     }
  105.     cout << ans;
  106.     return 0;
  107. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注