[关闭]
@qq290637843 2021-03-22T10:14:46.000000Z 字数 27331 阅读 315

2019上海

题目见https://ac.nowcoder.com/acm/contest/4370

A、Mr. Panda and Dominoes

首先预处理出每个块上下左右四个方向分别有多少个块。
考虑型的数法，将块按照的值分类，那么自然地，以的形作为插入，以的形作为查询点，就变成插入一些区间，以及查询一些区间，当且仅当时插入区间和查询区间耦合，此问题考虑按照区间右端点从大到小排列，于是对每一个查询区间只需要考虑其内有多少个插入区间的左端点。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. ul n;
  12. const ul maxn = 1e6;
  14. class data {
  15. public:
  16.     ul xp = 0;
  17.     ul yp = 0;
  18.     ul xm = 0;
  19.     ul ym = 0;
  20. };
  22. data map[maxn + 1];
  24. ul tot1;
  25. ull stack1[maxn + 1];
  27. ul calcxp(ul x, ul y)
  28. {
  29.     ull v = ull(x) << 32 | y;
  30.     auto it = std::lower_bound(stack1 + 1, stack1 + tot1 + 1, v) - stack1;
  31.     if (it == tot1 + 1 || stack1[it] != v) {
  32.         return 0;
  33.     } else if (map[it].xp) {
  34.         return map[it].xp;
  35.     } else {
  36.         return map[it].xp = calcxp(x + 1, y) + 1;
  37.     }
  38. }
  40. ul calcyp(ul x, ul y)
  41. {
  42.     ull v = ull(x) << 32 | y;
  43.     auto it = std::lower_bound(stack1 + 1, stack1 + tot1 + 1, v) - stack1;
  44.     if (it == tot1 + 1 || stack1[it] != v) {
  45.         return 0;
  46.     } else if (map[it].yp) {
  47.         return map[it].yp;
  48.     } else {
  49.         return map[it].yp = calcyp(x, y + 1) + 1;
  50.     }
  51. }
  53. ul calcxm(ul x, ul y)
  54. {
  55.     ull v = ull(x) << 32 | y;
  56.     auto it = std::lower_bound(stack1 + 1, stack1 + tot1 + 1, v) - stack1;
  57.     if (it == tot1 + 1 || stack1[it] != v) {
  58.         return 0;
  59.     } else if (map[it].xm) {
  60.         return map[it].xm;
  61.     } else {
  62.         return map[it].xm = calcxm(x - 1, y) + 1;
  63.     }
  64. }
  66. ul calcym(ul x, ul y)
  67. {
  68.     ull v = ull(x) << 32 | y;
  69.     auto it = std::lower_bound(stack1 + 1, stack1 + tot1 + 1, v) - stack1;
  70.     if (it == tot1 + 1 || stack1[it] != v) {
  71.         return 0;
  72.     } else if (map[it].ym) {
  73.         return map[it].ym;
  74.     } else {
  75.         return map[it].ym = calcym(x, y - 1) + 1;
  76.     }
  77. }
  79. ul tree[1 << 22];
  81. ul sz;
  83. ul query(ul l, ul r)
  84. {
  85.     ul ret = 0;
  86.     for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
  87.         if (~l & 1) {
  88.             ret += tree[l ^ 1];
  89.         }
  90.         if (r & 1) {
  91.             ret += tree[r ^ 1];
  92.         }
  93.     }
  94.     return ret;
  95. }
  97. void change(ul pos, ul v)
  98. {
  99.     for (pos |= sz; pos; pos >>= 1) {
  100.         tree[pos] += v;
  101.     }
  102. }
  104. class seg {
  105. public:
  106.     ul f = 0;
  107.     ul b = 0;
  108.     bool insert = false;
  109.     seg()=default;
  110.     seg(ul x, ul y, bool z): f(x), b(y), insert(z) {}
  111. };
  113. ul datas[maxn + maxn + 1];
  114. ul tot;
  116. ul stack2[maxn + maxn + 1];
  117. ul tot2;
  119. std::vector<seg> blobs[maxn + maxn + 1];
  121. std::vector<seg>& at(ul v)
  122. {
  123.     return blobs[std::lower_bound(stack2 + 1, stack2 + tot2 + 1, v) - stack2];
  124. }
  126. int main()
  127. {
  128.     std::scanf("%u", &T);
  129.     for (ul Case = 1; Case <= T; ++Case) {
  130.         std::scanf("%u", &n);
  131.         tot1 = 0;
  132.         tot2 = 0;
  133.         for (ul i = 1; i <= n; ++i) {
  134.             ul x, y;
  135.             std::scanf("%u%u", &x, &y);
  136.             ++tot1;
  137.             stack1[tot1] = ull(x) << 32 | y;
  138.             map[tot1] = data();
  139.         }
  140.         std::sort(stack1 + 1, stack1 + tot1 + 1);
  141.         for (ul it = 1; it <= tot1; ++it) {
  142.             ull tmp = stack1[it];
  143.             calcxp(tmp >> 32, tmp);
  144.             calcyp(tmp >> 32, tmp);
  145.             calcxm(tmp >> 32, tmp);
  146.             calcym(tmp >> 32, tmp);
  147.         }
  148.         ul ans = 0;
  149.         tot2 = 0;
  150.         for (ul it = 1; it <= tot1; ++it) {
  151.             ul x = stack1[it] >> 32;
  152.             ul y = stack1[it];
  153.             ++tot2;
  154.             stack2[tot2] = x + x + y;
  155.             ++tot2;
  156.             stack2[tot2] = x + x + y + 1;
  157.         }
  158.         std::sort(stack2 + 1, stack2 + tot2 + 1);
  159.         tot2 = std::unique(stack2 + 1, stack2 + tot2 + 1) - stack2 - 1;
  160.         for (ul i = 1; i <= tot2; ++i) {
  161.             blobs[i].resize(0);
  162.         }
  163.         for (ul it = 1; it <= tot1; ++it) {
  164.             ul x = stack1[it] >> 32;
  165.             ul y = stack1[it];
  166.             at(x + x + y).push_back(seg(x, x + std::min(map[it].xp, map[it].ym >> 1) - 1, true));
  167.             at(x + x + y + 1).push_back(seg(x - std::min(map[it].xm, map[it].yp >> 1) + 1, x, false));
  168.         }
  169.         for (ul it = 1; it <= tot2; ++it) {
  170.             std::sort(blobs[it].begin(), blobs[it].end(), [](const seg& a, const seg& b){return a.b != b.b ? a.b > b.b : a.insert > b.insert;});
  171.             tot = 0;
  172.             for (const auto& s : blobs[it]) {
  173.                 ++tot;
  174.                 datas[tot] = s.f;
  175.                 datas[tot] = s.b;
  176.             }
  177.             std::sort(datas + 1, datas + tot + 1);
  178.             tot = std::unique(datas + 1, datas + tot + 1) - datas - 1;
  179.             sz = 1;
  180.             while (sz < tot + 2) {
  181.                 sz <<= 1;
  182.             }
  183.             std::memset(tree, 0, sizeof(ul) * (sz << 1));
  184.             for (const auto& s : blobs[it]) {
  185.                 ul f = std::lower_bound(datas + 1, datas + tot + 1, s.f) - datas;
  186.                 ul b = std::lower_bound(datas + 1, datas + tot + 1, s.b) - datas;
  187.                 if (s.insert) {
  188.                     change(f, 1);
  189.                 } else {
  190.                     ans += query(f, b);
  191.                 }
  192.             }
  193.         }
  194.         tot2 = 0;
  195.         for (ul it = 1; it <= tot1; ++it) {
  196.             ul x = stack1[it] >> 32;
  197.             ul y = stack1[it];
  198.             ++tot2;
  199.             stack2[tot2] = x + y + y;
  200.             ++tot2;
  201.             stack2[tot2] = x + y + y + 1;
  202.         }
  203.         std::sort(stack2 + 1, stack2 + tot2 + 1);
  204.         tot2 = std::unique(stack2 + 1, stack2 + tot2 + 1) - stack2 - 1;
  205.         for (ul i = 1; i <= tot2; ++i) {
  206.             blobs[i].resize(0);
  207.         }
  208.         for (ul it = 1; it <= tot1; ++it) {
  209.             ul x = stack1[it] >> 32;
  210.             ul y = stack1[it];
  211.             at(x + y + y).push_back(seg(y, y + std::min(map[it].yp, map[it].xm >> 1) - 1, true));
  212.             at(x + y + y + 1).push_back(seg(y - std::min(map[it].ym, map[it].xp >> 1) + 1, y, false));
  213.         }
  214.         for (ul it = 1; it <= tot2; ++it) {
  215.             std::sort(blobs[it].begin(), blobs[it].end(), [](const seg& a, const seg& b){return a.b != b.b ? a.b > b.b : a.insert > b.insert;});
  216.             tot = 0;
  217.             for (const auto& s : blobs[it]) {
  218.                 ++tot;
  219.                 datas[tot] = s.f;
  220.                 datas[tot] = s.b;
  221.             }
  222.             std::sort(datas + 1, datas + tot + 1);
  223.             tot = std::unique(datas + 1, datas + tot + 1) - datas - 1;
  224.             sz = 1;
  225.             while (sz < tot + 2) {
  226.                 sz <<= 1;
  227.             }
  228.             std::memset(tree, 0, sizeof(ul) * (sz << 1));
  229.             for (const auto& s : blobs[it]) {
  230.                 ul f = std::lower_bound(datas + 1, datas + tot + 1, s.f) - datas;
  231.                 ul b = std::lower_bound(datas + 1, datas + tot + 1, s.b) - datas;
  232.                 if (s.insert) {
  233.                     change(f, 1);
  234.                 } else {
  235.                     ans += query(f, b);
  236.                 }
  237.             }
  238.         }
  239.         std::printf("Case #%u: %u\n", Case, ans);
  240.     }
  241.     return 0;
  242. }

B、Prefix Code

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. ul n;
  12. const ul maxn = 1e4;
  14. std::unordered_set<ull> set;
  16. ull data[maxn + 1];
  18. char str[12];
  20. int main()
  21. {
  22.     std::scanf("%u", &T);
  23.     for (ul Case = 1; Case <= T; ++Case) {
  24.         std::scanf("%u", &n);
  25.         for (ul i = 1; i <= n; ++i) {
  26.             std::scanf("%s", str + 1);
  27.             data[i] = 1;
  28.             for (ul j = 1; str[j]; ++j) {
  29.                 data[i] *= 10;
  30.                 data[i] += str[j] - '0';
  31.             }
  32.         }
  33.         bool flag = true;
  34.         set.clear();
  35.         for (ul i = 1; i <= n; ++i) {
  36.             if (set.find(data[i]) != set.end()) {
  37.                 flag = false;
  38.                 break;
  39.             }
  40.             ull tmp = data[i];
  41.             while (tmp) {
  42.                 set.insert(tmp);
  43.                 tmp /= 10;
  44.             }
  45.         }
  46.         if (flag) {
  47.             set.clear();
  48.             for (ul i = n; i >= 1; --i) {
  49.                 if (set.find(data[i]) != set.end()) {
  50.                     flag = false;
  51.                     break;
  52.                 }
  53.                 ull tmp = data[i];
  54.                 while (tmp) {
  55.                     set.insert(tmp);
  56.                     tmp /= 10;
  57.                 }
  58.             }
  59.         }
  60.         std::printf("Case #%u: %s\n", Case, flag ? "Yes" : "No");
  61.     }
  62.     return 0;
  63. }

C、Maze

先解决一个子问题：从出发，到，满足在过程中且的路径数量。考虑容斥，将两条直线叫做和，那么所有违法路径一定有接触两条直线的顺序。现在考虑其接触过，这意味着，其最后一次接触之后的路径全都依对称，正好和从出发到的路线一一对应，而这样的路线一定以或者的顺序收尾。同理，以或者的顺序收尾的路线和从出发到的路线一一对应。直接减掉这两部分之后，还需要将以或以收尾的路线加回来，因为重复减掉了。而继续迭代，以或以收尾的路线，先将最后一次接触之后的路线依对称，再将最后一次接触之后的路线依对称，就和从出发到的路线一一对应了。于是一直这样迭代并乘上容斥系数就能刚好只减去以或结尾的路线。
关于必须经过以及必不经过的点再容斥就是了。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul mod = 1e9 + 7;
  10. ul plus(ul a, ul b)
  11. {
  12.     return a + b < mod ? a + b : a + b - mod;
  13. }
  15. ul minus(ul a, ul b)
  16. {
  17.     return a < b ? a + mod - b : a - b;
  18. }
  20. ul mul(ul a, ul b)
  21. {
  22.     return ull(a) * ull(b) % mod;
  23. }
  25. void exgcd(li a, li b, li& x, li& y)
  26. {
  27.     if (b) {
  28.         exgcd(b, a % b, y, x);
  29.         y -= a / b * x;
  30.     } else {
  31.         x = 1;
  32.         y = 0;
  33.     }
  34. }
  36. ul inverse(ul a)
  37. {
  38.     li x, y;
  39.     exgcd(a, mod, x, y);
  40.     return x < 0 ? x + li(mod) : x;
  41. }
  43. ul T;
  45. ul n, m, s, k;
  47. const ul maxn = 1e5;
  48. const ul maxm = 1e5;
  50. const ul maxs = 10;
  51. const ul maxk = 20;
  53. std::pair<ul, ul> c[maxs + maxk + 2 + 1];
  55. ul tot;
  57. ul fac[maxn + maxm + 1];
  58. ul fiv[maxn + maxm + 1];
  60. ul calc(ul a, ul b)
  61. {
  62.     return mul(fac[a + b], mul(fiv[a], fiv[b]));
  63. }
  65. ul f(ul n, ul m, ul t1, ul t2)
  66. {
  67.     ul ret = calc(n, m);
  68.     for (ul a = n, b = m, p = 1; ; p = !p) {
  69.         std::swap(a, b);
  70.         if (p) {
  71.             if (a < t1) {
  72.                 break;
  73.             }
  74.             a -= t1;
  75.             b += t1;
  76.             ret = minus(ret, calc(a, b));
  77.         } else {
  78.             if (b < t2) {
  79.                 break;
  80.             }
  81.             a += t2;
  82.             b -= t2;
  83.             ret = plus(ret, calc(a, b));
  84.         }
  85.     }
  86.     for (ul a = n, b = m, p = 1; ; p = !p) {
  87.         std::swap(a, b);
  88.         if (p) {
  89.             if (b < t2) {
  90.                 break;
  91.             }
  92.             a += t2;
  93.             b -= t2;
  94.             ret = minus(ret, calc(a, b));
  95.         } else {
  96.             if (a < t1) {
  97.                 break;
  98.             }
  99.             a -= t1;
  100.             b += t1;
  101.             ret = plus(ret, calc(a, b));
  102.         }
  103.     }
  104.     return ret;
  105. }
  107. ul sub[maxs + maxk + 2 + 1][maxs + maxk + 2 + 1];
  109. ul d[maxs + maxk + 2 + 1];
  110. ul e[maxs + maxk + 2 + 1];
  112. int main()
  113. {
  114.     fac[0] = 1;
  115.     for (ul i = 1; i <= maxn + maxm; ++i) {
  116.         fac[i] = mul(fac[i - 1], i);
  117.     }
  118.     fiv[maxn + maxm] = inverse(fac[maxn + maxm]);
  119.     for (ul i = maxn + maxm; i; --i) {
  120.         fiv[i - 1] = mul(fiv[i], i);
  121.     }
  122.     std::scanf("%u", &T);
  123.     for (ul Case = 1; Case <= T; ++Case) {
  124.         std::scanf("%u%u%u%u", &n, &m, &s, &k);
  125.         for (ul i = k + 1; i <= k + s; ++i) {
  126.             std::scanf("%u%u", &c[i].first, &c[i].second);
  127.             e[i] = i;
  128.         }
  129.         for (ul i = 1; i <= k; ++i) {
  130.             std::scanf("%u%u", &c[i].first, &c[i].second);
  131.             e[i] = i;
  132.         }
  133.         c[k + s + 1] = std::pair<ul, ul>(1, 1);
  134.         e[k + s + 1] = k + s + 1;
  135.         c[k + s + 2] = std::pair<ul, ul>(n, m);
  136.         e[k + s + 2] = k + s + 2;
  137.         std::sort(e + 1, e + k + s + 2 + 1, [&](ul a, ul b){return c[a] < c[b];});
  138.         for (ul i = 1; i <= k + s + 2; ++i) {
  139.             for (ul j = 1; j <= k + s + 2; ++j) {
  140.                 if (c[i].first > c[j].first || c[i].second > c[j].second) {
  141.                     sub[i][j] = 0;
  142.                 } else {
  143.                     const auto& to = c[j];
  144.                     const auto& from = c[i];
  145.                     sub[i][j] = f(to.first - from.first, to.second - from.second, from.first - from.second + 1 + m - n, from.second - from.first + 1);
  146.                 }
  147.             }
  148.         }
  149.         ul ans = 0;
  150.         for (ul mask = (1 << k) - 1; ~mask; --mask) {
  151.             tot = 0;
  152.             for (ul i = 1; i <= k + s + 2; ++i) {
  153.                 if (e[i] >= k + 1 || (mask >> e[i] - 1 & 1)) {
  154.                     ++tot;
  155.                     d[tot] = e[i];
  156.                 }
  157.             }
  158.             ul tans = 1;
  159.             for (ul i = 1, j = 2; j <= tot; ++i, ++j) {
  160.                 if (sub[d[i]][d[j]] == 0) {
  161.                     tans = 0;
  162.                     break;
  163.                 }
  164.                 tans = mul(tans, sub[d[i]][d[j]]);
  165.             }
  166.             if (tot - s - 2 & 1) {
  167.                 ans = minus(ans, tans);
  168.             } else {
  169.                 ans = plus(ans, tans);
  170.             }
  171.         }
  172.         std::printf("Case #%u: %u\n", Case, ans);
  173.     }
  174.     return 0;
  175. }

D、Spanning Tree Removal

参考https://www.zybuluo.com/qq290637843/note/1776933的情况一

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. ul n;
  12. ul f(ul x, ul y, ul n)
  13. {
  14.     return x + y <= n - 1 ? x + y : x + y - n + 1;
  15. }
  17. ul g(ul x, ul n)
  18. {
  19.     return x + x <= n - 1 ? n - x : n + 1 - x;
  20. }
  22. int main()
  23. {
  24.     std::scanf("%u", &T);
  25.     for (ul Case = 1; Case <= T; ++Case) {
  26.         std::scanf("%u", &n);
  27.         std::printf("Case #%u: %u\n", Case, n >> 1);
  28.         if (n & 1) {
  29.             for (ul i = 1; i <= (n >> 1); ++i) {
  30.                 std::printf("%u %u\n", n, f(1, i - 1, n));
  31.                 for (ul j = 1, gjm1 = 1; j <= n - 2; ++j, gjm1 = g(gjm1, n)) {
  32.                     std::printf("%u %u\n", f(gjm1, i - 1, n), f(g(gjm1, n), i - 1, n));
  33.                 }
  34.             }
  35.         } else {
  36.             ++n;
  37.             for (ul i = 1; i <= (n >> 1); ++i) {
  38.                 for (ul j = 1, gjm1 = 1; j <= n - 2; ++j, gjm1 = g(gjm1, n)) {
  39.                     std::printf("%u %u\n", f(gjm1, i - 1, n), f(g(gjm1, n), i - 1, n));
  40.                 }
  41.             }
  42.         }
  43.     }
  44.     return 0;
  45. }

E、Cave Escape

显然，能获得的边构成一棵树

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. ul n, m, sr, sc, tr, tc;
  12. ul a, b, c, p;
  14. const ul maxn = 1e3;
  15. const ul maxm = 1e3;
  17. ul x[maxn * maxm + 1];
  19. ul fa[maxn * maxm + 1];
  20. ul rk[maxn * maxm + 1];
  22. std::vector<std::pair<ul, ul>> edges[10001];
  24. ul getfather(ul x)
  25. {
  26.     return x == fa[x] ? x : fa[x] = getfather(fa[x]);
  27. }
  29. bool connect(ul x, ul y)
  30. {
  31.     x = getfather(x);
  32.     y = getfather(y);
  33.     if (x == y) {
  34.         return false;
  35.     }
  36.     if (rk[x] > rk[y]) {
  37.         fa[y] = x;
  38.     } else if (rk[y] > rk[x]) {
  39.         fa[x] = y;
  40.     } else {
  41.         fa[y] = x;
  42.         ++rk[x];
  43.     }
  44.     return true;
  45. }
  47. int main()
  48. {
  49.     std::scanf("%u", &T);
  50.     for (ul Case = 1; Case <= T; ++Case) {
  51.         std::scanf("%u%u%u%u%u%u", &n, &m, &sr, &sc, &tr, &tc);
  52.         std::scanf("%u%u%u%u%u%u", &x[1], &x[2], &a, &b, &c, &p);
  53.         for (ul i = 0; i <= p * p; ++i) {
  54.             edges[i].resize(0);
  55.         }
  56.         for (ul i = 3; i <= n * m; ++i) {
  57.             x[i] = (a * x[i - 1] + b * x[i - 2] + c) % p;
  58.         }
  59.         for (ul i = 1; i <= n * m; ++i) {
  60.             fa[i] = i;
  61.             rk[i] = 0;
  62.         }
  63.         for (ul i = 1; i <= n; ++i) {
  64.             for (ul j = 1; j <= m - 1; ++j) {
  65.                 ul s = (i - 1) * m + j;
  66.                 ul t = (i - 1) * m + j + 1;
  67.                 edges[x[s] * x[t]].push_back(std::pair<ul, ul>(s, t));
  68.             }
  69.         }
  70.         for (ul i = 1; i <= n - 1; ++i) {
  71.             for (ul j = 1; j <= m; ++j) {
  72.                 ul s = (i - 1) * m + j;
  73.                 ul t = i * m + j;
  74.                 edges[x[s] * x[t]].push_back(std::pair<ul, ul>(s, t));
  75.             }
  76.         }
  77.         ull ans = 0;
  78.         for (ul i = p * p; ~i; --i) {
  79.             for (const auto& e : edges[i]) {
  80.                 ul s = e.first;
  81.                 ul t = e.second;
  82.                 if (connect(s, t)) {
  83.                     ans += i;
  84.                 }
  85.             }
  86.         }
  87.         std::printf("Case #%u: %llu\n", Case, ans);
  88.     }
  89.     return 0;
  90. }

F、A Simple Problem On A Tree

重链剖分线段树

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul mod = 1e9 + 7;
  10. ul plus(ul a, ul b)
  11. {
  12.     return a + b < mod ? a + b : a + b - mod;
  13. }
  15. ul mul(ul a, ul b)
  16. {
  17.     return ull(a) * ull(b) % mod;
  18. }
  20. ul T;
  22. ul n;
  24. const ul maxn = 1e5;
  26. std::vector<ul> edges[maxn + 1];
  28. ul dfn[maxn + 1];
  29. ul fa[maxn + 1];
  30. ul hvhd[maxn + 1];
  31. ul bigson[maxn + 1];
  32. ul depth[maxn + 1];
  34. void search1(ul curr, ul prev, ul& sz)
  35. {
  36.     sz = 1;
  37.     ul bigsz = 0;
  38.     for (ul next : edges[curr]) {
  39.         if (next == prev) {
  40.             continue;
  41.         }
  42.         depth[next] = depth[curr] + 1;
  43.         fa[next] = curr;
  44.         ul tsz;
  45.         search1(next, curr, tsz);
  46.         sz += tsz;
  47.         if (tsz > bigsz) {
  48.             bigson[curr] = next;
  49.             bigsz = tsz;
  50.         }
  51.     }
  52. }
  54. ul tim;
  56. void search2(ul curr)
  57. {
  58.     ++tim;
  59.     dfn[curr] = tim;
  60.     if (bigson[curr]) {
  61.         hvhd[bigson[curr]] = hvhd[curr];
  62.         search2(bigson[curr]);
  63.     }
  64.     for (ul next : edges[curr]) {
  65.         if (next == fa[curr] || next == bigson[curr]) {
  66.             continue;
  67.         }
  68.         hvhd[next] = next;
  69.         search2(next);
  70.     }
  71. }
  73. class node {
  74. public:
  75.     ul sum[4];
  76.     ul a = ~ul(0);
  77.     ul b = ~ul(0);
  78.     ul c = ~ul(0);
  79. };
  81. ul sz;
  83. const ul maxsz = 1 << 17;
  85. node tree[maxsz << 1];
  87. void combine(ul x, ul y)
  88. {
  89.     if (!~tree[x].a && !~tree[x].c) {
  90.         return;
  91.     }
  92.     if (~tree[x].c) {
  93.         tree[y].a = ~ul(0);
  94.         tree[y].b = ~ul(0);
  95.         tree[y].c = tree[x].c;
  96.     } else if (~tree[y].a) {
  97.         tree[y].b = plus(mul(tree[x].a, tree[y].b), tree[x].b);
  98.         tree[y].a = mul(tree[x].a, tree[y].a);
  99.         tree[y].c = ~ul(0);
  100.     } else if (~tree[y].c) {
  101.         tree[y].a = ~ul(0);
  102.         tree[y].b = ~ul(0);
  103.         tree[y].c = plus(mul(tree[x].a, tree[y].c), tree[x].b);
  104.     } else {
  105.         tree[y].a = tree[x].a;
  106.         tree[y].b = tree[x].b;
  107.         tree[y].c = tree[x].c;
  108.     }
  109. }
  111. void push(ul x, bool down)
  112. {
  113.     if (~tree[x].a) {
  114.         ul a = tree[x].a;
  115.         ul a2 = mul(a, a);
  116.         ul a3 = mul(a2, a);
  117.         ul b = tree[x].b;
  118.         ul b2 = mul(b, b);
  119.         ul b3 = mul(b2, b);
  120.         ul a2b = mul(a2, b);
  121.         ul ab2 = mul(a, b2);
  122.         ul ab = mul(a, b);
  123.         tree[x].sum[3] = plus(plus(mul(a3, tree[x].sum[3]), mul(mul(3, a2b), tree[x].sum[2])), plus(mul(mul(3, ab2), tree[x].sum[1]), mul(b3, tree[x].sum[0])));
  124.         tree[x].sum[2] = plus(plus(mul(a2, tree[x].sum[2]), mul(mul(2, ab), tree[x].sum[1])), mul(b2, tree[x].sum[0]));
  125.         tree[x].sum[1] = plus(mul(a, tree[x].sum[1]), mul(b, tree[x].sum[0]));
  126.     } else if (~tree[x].c) {
  127.         ul c = tree[x].c;
  128.         ul c2 = mul(c, c);
  129.         ul c3 = mul(c2, c);
  130.         tree[x].sum[3] = mul(c3, tree[x].sum[0]);
  131.         tree[x].sum[2] = mul(c2, tree[x].sum[0]);
  132.         tree[x].sum[1] = mul(c, tree[x].sum[0]);
  133.     }
  134.     if (down) {
  135.         combine(x, x << 1);
  136.         combine(x, x << 1 | 1);
  137.     }
  138.     tree[x].a = ~ul(0);
  139.     tree[x].b = ~ul(0);
  140.     tree[x].c = ~ul(0);
  141. }
  143. void change(ul l, ul r, ul nl, ul nr, ul nid, ul a, ul b, ul c)
  144. {
  145.     tree[nid].sum[0] = nr - nl + 1;
  146.     push(nid, nl != nr);
  147.     if (l <= nl && r >= nr) {
  148.         tree[nid].a = a;
  149.         tree[nid].b = b;
  150.         tree[nid].c = c;
  151.         push(nid, nl != nr);
  152.         return;
  153.     }
  154.     ul midl = nl + nr >> 1;
  155.     ul midr = midl + 1;
  156.     if (l <= midl) {
  157.         change(l, r, nl, midl, nid << 1, a, b, c);
  158.     } else {
  159.         tree[nid << 1].sum[0] = midl - nl + 1;
  160.         push(nid << 1, nl != midl);
  161.     }
  162.     if (r >= midr) {
  163.         change(l, r, midr, nr, nid << 1 | 1, a, b, c);
  164.     } else {
  165.         tree[nid << 1 | 1].sum[0] = nr - midr + 1;
  166.         push(nid << 1 | 1, midr != nr);
  167.     }
  168.     for (ul i = 0; i <= 3; ++i) {
  169.         tree[nid].sum[i] = plus(tree[nid << 1].sum[i], tree[nid << 1 | 1].sum[i]);
  170.     }
  171. }
  173. ul query(ul l, ul r, ul nl, ul nr, ul nid)
  174. {
  175.     tree[nid].sum[0] = nr - nl + 1;
  176.     push(nid, nl != nr);
  177.     if (l <= nl && r >= nr) {
  178.         return tree[nid].sum[3];
  179.     }
  180.     ul midl = nl + nr >> 1;
  181.     ul midr = midl + 1;
  182.     ul ret = 0;
  183.     if (l <= midl) {
  184.         ret = plus(ret, query(l, r, nl, midl, nid << 1));
  185.     }
  186.     if (r >= midr) {
  187.         ret = plus(ret, query(l, r, midr, nr, nid << 1 | 1));
  188.     }
  189.     return ret;
  190. }
  192. ul q;
  194. int main()
  195. {
  196.     std::scanf("%u", &T);
  197.     for (ul Case = 1; Case <= T; ++Case) {
  198.         std::scanf("%u", &n);
  199.         for (ul i = 1; i <= n; ++i) {
  200.             bigson[i] = 0;
  201.             edges[i].resize(0);
  202.         }
  203.         for (ul i = 1; i <= n - 1; ++i) {
  204.             ul a, b;
  205.             std::scanf("%u%u", &a, &b);
  206.             edges[a].push_back(b);
  207.             edges[b].push_back(a);
  208.         }
  209.         search1(1, 0, n);
  210.         hvhd[1] = 1;
  211.         tim = 0;
  212.         search2(1);
  213.         for (ul i = 1; i <= n; ++i) {
  214.             ul w;
  215.             std::scanf("%u", &w);
  216.             change(dfn[i], dfn[i], 1, n, 1, ~ul(0), ~ul(0), w);
  217.         }
  218.         std::printf("Case #%u:\n", Case);
  219.         std::scanf("%u", &q);
  220.         for (ul i = 1; i <= q; ++i) {
  221.             ul type;
  222.             std::scanf("%u", &type);
  223.             if (type != 4) {
  224.                 ul u, v, w;
  225.                 std::scanf("%u%u%u", &u, &v, &w);
  226.                 while (hvhd[u] != hvhd[v]) {
  227.                     if (depth[hvhd[u]] > depth[hvhd[v]]) {
  228.                         std::swap(u, v);
  229.                     }
  230.                     if (type == 1) {
  231.                         change(dfn[hvhd[v]], dfn[v], 1, n, 1, ~ul(0), ~ul(0), w);
  232.                     } else if (type == 2) {
  233.                         change(dfn[hvhd[v]], dfn[v], 1, n, 1, 1, w, ~ul(0));
  234.                     } else if (type == 3) {
  235.                         change(dfn[hvhd[v]], dfn[v], 1, n, 1, w, 0, ~ul(0));
  236.                     }
  237.                     v = fa[hvhd[v]];
  238.                 }
  239.                 if (depth[u] > depth[v]) {
  240.                     std::swap(u, v);
  241.                 }
  242.                 if (type == 1) {
  243.                     change(dfn[u], dfn[v], 1, n, 1, ~ul(0), ~ul(0), w);
  244.                 } else if (type == 2) {
  245.                     change(dfn[u], dfn[v], 1, n, 1, 1, w, ~ul(0));
  246.                 } else if (type == 3) {
  247.                     change(dfn[u], dfn[v], 1, n, 1, w, 0, ~ul(0));
  248.                 }
  249.             } else {
  250.                 ul u, v;
  251.                 std::scanf("%u%u", &u, &v);
  252.                 ul ret = 0;
  253.                 while (hvhd[u] != hvhd[v]) {
  254.                     if (depth[hvhd[u]] > depth[hvhd[v]]) {
  255.                         std::swap(u, v);
  256.                     }
  257.                     ret = plus(ret, query(dfn[hvhd[v]], dfn[v], 1, n, 1));
  258.                     v = fa[hvhd[v]];
  259.                 }
  260.                 if (depth[u] > depth[v]) {
  261.                     std::swap(u, v);
  262.                 }
  263.                 ret = plus(ret, query(dfn[u], dfn[v], 1, n, 1));
  264.                 std::printf("%u\n", ret);
  265.             }
  266.         }
  267.     }
  268.     return 0;
  269. }

G、Play the game SET

将所有合法方案作为点，如果两个点之间有重复牌就不连边，其余全部连边，于是变为最大团问题。
最大团算法见此https://chaoli.club/index.php/5052/

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. ul n;
  12. std::map<std::string, std::pair<ul, ul>> strtov;
  14. const std::string name[4][3] = {{"one", "two", "three"}, {"diamond", "squiggle", "oval"}, {"solid", "striped", "open"}, {"red", "green", "purple"}};
  16. const ul maxn = 38;
  18. ul v[maxn + 1][4];
  20. char str[300];
  22. std::string tmp;
  24. ul tot;
  26. ul q[300][3];
  28. std::vector<ul> had[maxn + 1];
  30. using data = std::bitset<256>;
  32. data g[256];
  34. data ansr;
  36. data getfirst(const data& x)
  37. {
  38.     ul tmp = x._Find_next(0);
  39.     data ret;
  40.     ret[tmp] = 1;
  41.     return ret;
  42. }
  44. ul first(const data& x)
  45. {
  46.     return x._Find_next(0);
  47. }
  49. bool flag = false;
  51. void bk(const data& r, data p, data x)
  52. {
  53.     if (!p.any() && !x.any()) {
  54.         if (r.count() > ansr.count()) {
  55.             ansr = r;
  56.             if (r.count() == n / 3) {
  57.                 flag = true;
  58.             }
  59.         }
  60.         return;
  61.     }
  62.     data px = p | x;
  63.     data u = getfirst(px);
  64.     for (data tu = getfirst(px); px.any(); px &= ~tu, tu = getfirst(px)) {
  65.         if ((p & g[first(tu)]).count() > (p & g[first(u)]).count()) {
  66.             u = tu;
  67.         }
  68.     }
  69.     data ext = p & ~g[first(u)];
  70.     for (data v = getfirst(ext); ext.any(); p &= ~v, x |= v, ext &= ~v, v = getfirst(ext)) {
  71.         bk(r | v, p & g[first(v)], x & g[first(v)]);
  72.         if (flag) {
  73.             return;
  74.         }
  75.     }
  76. }
  78. int main()
  79. {
  80.     for (ul i = 0; i != 4; ++i) {
  81.         for (ul j = 0; j != 3; ++j) {
  82.             strtov[name[i][j]] = std::pair<ul, ul>(i, j);
  83.         }
  84.     }
  85.     std::scanf("%u", &T);
  86.     for (ul Case = 1; Case <= T; ++Case) {
  87.         std::scanf("%u", &n);
  88.         for (ul i = 1; i <= n; ++i) {
  89.             had[i].resize(0);
  90.             std::scanf("%s", str + 1);
  91.             for (ul j = 1; str[j]; ++j) {
  92.                 if (str[j] == ']') {
  93.                     auto p = strtov[tmp];
  94.                     v[i][p.first] = p.second;
  95.                     tmp.resize(0);
  96.                 } else if (str[j] != '[') {
  97.                     tmp.push_back(str[j]);
  98.                 }
  99.             }
  100.         }
  101.         tot = 0;
  102.         for (ul a = 1; a + 2 <= n; ++a) {
  103.             for (ul b = a + 1; b + 1 <= n; ++b) {
  104.                 for (ul c = b + 1; c <= n; ++c) {
  105.                     bool flag = true;
  106.                     for (ul i = 0; i != 4; ++i) {
  107.                         if ((v[a][i] + v[b][i] + v[c][i]) % 3) {
  108.                             flag = false;
  109.                             break;
  110.                         }
  111.                     }
  112.                     if (flag) {
  113.                         ++tot;
  114.                         q[tot][0] = a;
  115.                         q[tot][1] = b;
  116.                         q[tot][2] = c;
  117.                         had[a].push_back(tot);
  118.                         had[b].push_back(tot);
  119.                         had[c].push_back(tot);
  120.                     }
  121.                 }
  122.             }
  123.         }
  124.         for (ul i = 1; i <= tot; ++i) {
  125.             g[i] = 0;
  126.             for (ul j = 1; j <= tot; ++j) {
  127.                 if (i != j) {
  128.                     g[i][j] = 1;
  129.                 }
  130.             }
  131.         }
  132.         for (ul a = 1; a <= n; ++a) {
  133.             for (ul s = 0; s + 1 < had[a].size(); ++s) {
  134.                 for (ul t = s + 1; t < had[a].size(); ++t) {
  135.                     g[had[a][s]][had[a][t]] = 0;
  136.                     g[had[a][t]][had[a][s]] = 0;
  137.                 }
  138.             }
  139.         }
  140.         ansr = 0;
  141.         data all;
  142.         for (ul i = 1; i <= tot; ++i) {
  143.             all[i] = 1;
  144.         }
  145.         flag = false;
  146.         bk(0, all, all);
  147.         std::printf("Case #%u: %u\n", Case, ul(ansr.count()));
  148.         for (ul i = 1; i <= tot; ++i) {
  149.             if (ansr[i]) {
  150.                 std::printf("%u %u %u\n", q[i][0], q[i][1], q[i][2]);
  151.             }
  152.         }
  153.     }
  154.     return 0;
  155. }

H、Tree Partition

二分贪心

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. ul n;
  12. ul k;
  14. const ul maxn = 1e5;
  16. ul w[maxn + 1];
  18. std::vector<ul> edges[maxn + 1];
  20. std::vector<ull> stack[maxn + 1];
  22. void search(ul curr, ul prev, ull bound, ul& cnt, ull& sum)
  23. {
  24.     stack[curr].resize(0);
  25.     cnt = 0;
  26.     for (ul next : edges[curr]) {
  27.         if (next == prev) {
  28.             continue;
  29.         }
  30.         stack[curr].push_back(0);
  31.         ul tcnt;
  32.         search(next, curr, bound, tcnt, stack[curr].back());
  33.         cnt += tcnt;
  34.     }
  35.     std::sort(stack[curr].begin(), stack[curr].end());
  36.     sum = w[curr];
  37.     for (ul i = 0; i != stack[curr].size(); ++i) {
  38.         if (sum + stack[curr][i] > bound) {
  39.             cnt += stack[curr].size() - i;
  40.             break;
  41.         }
  42.         sum += stack[curr][i];
  43.     }
  44. }
  46. int main()
  47. {
  48.     std::scanf("%u", &T);
  49.     for (ul Case = 1; Case <= T; ++Case) {
  50.         std::scanf("%u%u", &n, &k);
  51.         for (ul i = 1; i <= n; ++i) {
  52.             edges[i].resize(0);
  53.         }
  54.         ull mx = 0;
  55.         for (ul i = 1; i <= n - 1; ++i) {
  56.             ul u, v;
  57.             std::scanf("%u%u", &u, &v);
  58.             edges[u].push_back(v);
  59.             edges[v].push_back(u);
  60.         }
  61.         for (ul i = 1; i <= n; ++i) {
  62.             std::scanf("%u", &w[i]);
  63.             mx = std::max(mx, ull(w[i]));
  64.         }
  65.         ull l = mx - 1, r = 1e14;
  66.         while (l + 1 != r) {
  67.             ull mid = l + r >> 1;
  68.             ul cnt;
  69.             ull s;
  70.             search(1, 0, mid, cnt, s);
  71.             if (cnt >= k) {
  72.                 l = mid;
  73.             } else {
  74.                 r = mid;
  75.             }
  76.         }
  77.         std::printf("Case #%u: %llu\n", Case, r);
  78.     }
  79.     return 0;
  80. }

I、Portal

首先将原问题重新叙述如下：
有一个长方形，有两个点，对于中的两点和，定义两点的距离为

找到最大的两点。
首先引入一个很符合直觉的猜想：对于中的紧致凸集，且是用维边界、维边界、……、维边界所描述的“平直边界凸集”，而有个紧致凸集，且包含了的所有维边界，那么就包含了。（我不知道怎么证明，但是至少在零一二三维空间上可以很直观感受这一点）
现在考虑将分为四个紧凸集的并：首先沿着两个传送门的中垂线将分为两个紧凸集和，那么被分为，注意无论在哪个部分中，函数定义中所用到的三个凸函数都至少有一个会失效（在第一部分，后两个函数失效；在第二部分，后两个函数失效；在第三部分，第三个函数失效；在第四部分，第二个函数失效），于是根据之前的猜想可知：对于任何一个部分，函数的最大值点一定取在一维边界上，换言之，一个点在角上，一个点在边或角上。但注意这里的“角”包括了中垂线和长方形的交点，“边”包括了中垂线。
现在考虑任取点，将其固定，于是作为关于的函数，三个函数中会自动失效一个，于是再次调用猜想可知，最大值点一定在一维边界上，也就是边或角上。
综合以上两点可知，一定有一个点在长方形的角上，或者在中垂线和长方形边的交点上，另一个点在边或角上。而注意距离中垂线和长方形边的交点最远的点一定在角上可知：一定有一个点在角上，另一个点在边或角上。证毕。

猜想的证明如下：
首先证明：对任何中的紧凸集，如果紧凸集（）的并能覆盖的边界，那就能覆盖。
考虑有一点没有被覆盖，将此点记为，考虑从到分别最近的点，连线段，分别过作线段的垂直超平面。而显然，中是不可能用少于或等于个超平面围出一个有界区域的，于是可知这些超平面围不出一个有界区域，从而有一个方向能不经过到达的边界，故的边界没有被覆盖，矛盾。

于是考虑有个紧凸集覆盖了某平直边界紧凸集的所有维边界，根据上方命题可知，维部分全被覆盖。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  7. using llf = long double;
  9. class vec {
  10. public:
  11.     llf x = 0;
  12.     llf y = 0;
  13.     vec()=default;
  14.     vec(llf a, llf b): x(a), y(b) {}
  15. };
  17. vec operator+(const vec& a, const vec& b)
  18. {
  19.     return vec(a.x + b.x, a.y + b.y);
  20. }
  22. vec operator-(const vec& a, const vec& b)
  23. {
  24.     return vec(a.x - b.x, a.y - b.y);
  25. }
  27. llf operator*(const vec& a, const vec& b)
  28. {
  29.     return a.x * b.x + a.y * b.y;
  30. }
  32. vec operator*(llf a, const vec& b)
  33. {
  34.     return vec(a * b.x, a * b.y);
  35. }
  37. vec operator*(const vec& a, llf b)
  38. {
  39.     return vec(a.x * b, a.y * b);
  40. }
  42. vec operator/(const vec& a, llf b)
  43. {
  44.     return vec(a.x / b, a.y / b);
  45. }
  47. llf len2(const vec& a, const vec& b)
  48. {
  49.     return (a - b) * (a - b);
  50. }
  52. llf len(const vec& a, const vec& b)
  53. {
  54.     return std::sqrt((a - b) * (a - b));
  55. }
  57. vec p1, p2;
  59. llf dis(const vec& a, const vec& b)
  60. {
  61.     return std::min(len(a, b), std::min(len(a, p1) + len(p2, b), len(a, p2) + len(p1, b)));
  62. }
  64. vec cs[5];
  66. vec rotate(const vec& a)
  67. {
  68.     return vec(-a.y, a.x);
  69. }
  71. bool calc(llf a, llf b, llf c, llf& t1, llf& t2)
  72. {
  73.     if (a < 1e-5 && a > -1e-5) {
  74.         t1 = -c / b;
  75.         t2 = -c / b;
  76.         return true;
  77.     }
  78.     llf delta = b * b - llf(4) * a * c;
  79.     if (delta < 0) {
  80.         return false;
  81.     }
  82.     t1 = (-b - std::sqrt(delta)) / a * llf(0.5);
  83.     t2 = (-b + std::sqrt(delta)) / a * llf(0.5);
  84.     return true;
  85. }
  87. llf calc(const vec& start, vec& ans)
  88. {
  89.     llf ret = 0;
  90.     vec o, xdir, ydir;
  91.     llf a, b;
  92.     if (len2(p1, start) < len2(p2, start)) {
  93.         a = len(start, p1) * llf(0.5);
  94.         b = std::sqrt(len2(start, p2) - len2(start, p1)) * llf(0.5);
  95.         o = (start + p2) * llf(0.5);
  96.         xdir = (p2 - start) / len(p2, start);
  97.         ydir = rotate(xdir);
  98.     } else if (len2(p2, start) < len2(p1, start)) {
  99.         a = len(start, p2) * llf(0.5);
  100.         b = std::sqrt(len2(start, p1) - len2(start, p2)) * llf(0.5);
  101.         o = (start + p1) * llf(0.5);
  102.         xdir = (p1 - start) / len(p1, start);
  103.         ydir = rotate(xdir);
  104.     } else {
  105.         for (ul i = 1; i <= 4; ++i) {
  106.             llf tmp = dis(start, cs[i]);
  107.             if (ret < tmp) {
  108.                 ans = cs[i];
  109.                 ret = tmp;
  110.             }
  111.         }
  112.         return ret;
  113.     }
  114.     for (ul i = 1; i <= 4; ++i) {
  115.         vec alpha = vec((cs[i - 1] - o) * xdir, (cs[i - 1] - o) * ydir);
  116.         vec beta = vec((cs[i] - o) * xdir, (cs[i] - o) * ydir);
  117.         llf tmp = dis(start, cs[i]);
  118.         if (ret < tmp) {
  119.             ans = cs[i];
  120.             ret = tmp;
  121.         }
  122.         llf t1, t2;
  123.         bool flag = calc(b * b * (alpha.x - beta.x) * (alpha.x - beta.x) - a * a * (alpha.y - beta.y) * (alpha.y - beta.y), 2 * (alpha.x * b * b * (beta.x - alpha.x) + a * a * alpha.y * (alpha.y - beta.y)), alpha.x * alpha.x * b * b - a * a * alpha.y * alpha.y - a * a * b * b, t1, t2);
  124.         if (flag) {
  125.             if (t1 >= 0 && t1 <= 1) {
  126.                 vec k = cs[i - 1] + t1 * (cs[i] - cs[i - 1]);
  127.                 llf tmp = dis(start, k);
  128.                 if (ret < tmp) {
  129.                     ans = k;
  130.                     ret = tmp;
  131.                 }
  132.             }
  133.             if (t2 >= 0 && t2 <= 1) {
  134.                 vec k = cs[i - 1] + t2 * (cs[i] - cs[i - 1]);
  135.                 llf tmp = dis(start, k);
  136.                 if (ret < tmp) {
  137.                     ans = k;
  138.                     ret = tmp;
  139.                 }
  140.             }
  141.         }
  142.     }
  143.     return ret;
  144. }
  146. ul T;
  148. int main()
  149. {
  150.     std::scanf("%u", &T);
  151.     for (ul Case = 1; Case <= T; ++Case) {
  152.         ul a, b, x1, x2, y1, y2;
  153.         std::scanf("%u%u%u%u%u%u", &a, &b, &x1, &y1, &x2, &y2);
  154.         p1 = vec(x1, y1);
  155.         p2 = vec(x2, y2);
  156.         cs[1] = vec(0, 0);
  157.         cs[2] = vec(a, 0);
  158.         cs[3] = vec(a, b);
  159.         cs[4] = vec(0, b);
  160.         cs[0] = cs[4];
  161.         llf ans = 0;
  162.         vec out1, out2;
  163.         for (ul i = 1; i <= 4; ++i) {
  164.             llf tans;
  165.             vec tout2;
  166.             tans = calc(cs[i], tout2);
  167.             if (tans > ans) {
  168.                 ans = tans;
  169.                 out1 = cs[i];
  170.                 out2 = tout2;
  171.             }
  172.         }
  173.         std::printf("Case #%u:\n", Case);
  174.         std::printf("%.20Lf %.20Lf\n%.20Lf %.20Lf\n", out1.x, out1.y, out2.x, out2.y);
  175.     }
  176.     return 0;
  177. }

J、Bob's Poor Math

直接看代码

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  9. ul n, m;
  11. const ul maxn = 1e4;
  12. const ul maxm = 1e4;
  14. class node {
  15. public:
  16.     ul son[10];
  17.     ull sum = 0;
  18.     node() {
  19.         std::memset(son, 0, sizeof(son));
  20.     }
  21. };
  23. ul tot;
  25. node tree[maxn * 10 + maxm * 10 + 2];
  27. ul stack[maxn * 10 + maxm * 10 + 2];
  29. ul remain;
  31. ul newnode()
  32. {
  33.     ul tmp;
  34.     if (remain) {
  35.         tmp = stack[remain];
  36.         --remain;
  37.     } else {
  38.         ++tot;
  39.         tmp = tot;
  40.     }
  41.     tree[tmp] = node();
  42.     return tmp;
  43. }
  45. void kill(ul& x)
  46. {
  47.     ++remain;
  48.     stack[remain] = x;
  49.     x = 0;
  50. }
  52. ull plus(ull a, ull b)
  53. {
  54.     ull c = 0;
  55.     ull i = 1;
  56.     while (a || b) {
  57.         ull k = (a % 10 + b % 10) % 10;
  58.         c += k * i;
  59.         a /= 10;
  60.         b /= 10;
  61.         i *= 10;
  62.     }
  63.     return c;
  64. }
  66. void add(ull x, ul root)
  67. {
  68.     static ul ins[10];
  69.     ull xx = x;
  70.     for (ul i = 0; i <= 9; ++i) {
  71.         ins[i] = x % 10;
  72.         x /= 10;
  73.     }
  74.     x = xx;
  75.     ul curr = root;
  76.     for (ul i = 9; ~i; --i) {
  77.         if (!tree[curr].son[ins[i]]) {
  78.             tree[curr].son[ins[i]] = newnode();
  79.         }
  80.         curr = tree[curr].son[ins[i]];
  81.         tree[curr].sum = plus(tree[curr].sum, x);
  82.     }
  83. }
  85. void shift(ul& root)
  86. {
  87.     for (ul i = 0; i <= 9; ++i) {
  88.         if (tree[root].son[i]) {
  89.             tree[root].sum = plus(tree[root].sum, tree[tree[root].son[i]].sum);
  90.         }
  91.     }
  92.     ul s = root;
  93.     root = newnode();
  94.     tree[root].son[0] = s;
  95.     using pulul = std::pair<ul, ul>;
  96.     static pulul stack[maxn * 10 + maxm * 10 + 2];
  97.     ul tot = 0;
  98.     ++tot;
  99.     stack[tot] = pulul(s, 9);
  100.     while (tot) {
  101.         auto curr = stack[tot].first;
  102.         auto index = stack[tot].second;
  103.         --tot;
  104.         tree[curr].sum /= 10;
  105.         for (ul i = 0; i != 10; ++i) {
  106.             if (tree[curr].son[i]) {
  107.                 if (index == 0) {
  108.                     kill(tree[curr].son[i]);
  109.                 } else {
  110.                     ++tot;
  111.                     stack[tot].first = tree[curr].son[i];
  112.                     stack[tot].second = index - 1;
  113.                 }
  114.             }
  115.         }
  116.     }
  117. }
  119. ull query(ull x, ul root)
  120. {
  121.     static ul ins[10];
  122.     for (ul i = 0; i <= 9; ++i) {
  123.         ins[i] = x % 10;
  124.         x /= 10;
  125.     }
  126.     ul curr = root;
  127.     ull ret2 = 0;
  128.     for (ul i = 9; ~i; --i) {
  129.         for (ul j = 9; ~j; --j) {
  130.             ul t = j < ins[i] ? j + 10 - ins[i] : j - ins[i];
  131.             if (tree[curr].son[t]) {
  132.                 ret2 *= 10;
  133.                 ret2 += j;
  134.                 curr = tree[curr].son[t];
  135.                 break;
  136.             }
  137.         }
  138.     }
  139.     return ret2;
  140. }
  142. ull sum(ull l, ull r, ul nid, ull nl, ull nr)
  143. {
  144.     if (l <= nl && r >= nr) {
  145.         return tree[nid].sum;
  146.     }
  147.     ull ret = 0;
  148.     ull part = (nr - nl + 1) / 10;
  149.     for (ull i = 0, ml = nl, mr = nl + part - 1; i <= 9; ++i, ml += part, mr += part) {
  150.         if (!tree[nid].son[i]) {
  151.             continue;
  152.         }
  153.         if (l <= mr && r >= ml) {
  154.             ret = plus(ret, sum(l, r, tree[nid].son[i], ml, mr));
  155.         }
  156.     }
  157.     return ret;
  158. }
  160. char str[100];
  162. int main()
  163. {
  164.     std::scanf("%u", &T);
  165.     for (ul Case = 1; Case <= T; ++Case) {
  166.         std::printf("Case #%u:\n", Case);
  167.         std::scanf("%u%u", &n, &m);
  168.         tot = 0;
  169.         remain = 0;
  170.         ul root = newnode();
  171.         for (ul i = 1; i <= n; ++i) {
  172.             ull a;
  173.             std::scanf("%llu", &a);
  174.             add(a, root);
  175.         }
  176.         for (ul i = 1; i <= m; ++i) {
  177.             std::scanf("%s", str + 1);
  178.             if (std::strcmp(str + 1, "Add") == 0) {
  179.                 ull a;
  180.                 std::scanf("%llu", &a);
  181.                 add(a, root);
  182.             } else if (std::strcmp(str + 1, "Query") == 0) {
  183.                 ull a;
  184.                 std::scanf("%llu", &a);
  185.                 std::printf("%llu\n", query(a, root));
  186.             } else if (std::strcmp(str + 1, "Shift") == 0) {
  187.                 shift(root);
  188.             } else if (std::strcmp(str + 1, "Sum") == 0) {
  189.                 ull l, r;
  190.                 std::scanf("%llu%llu", &l, &r);
  191.                 std::printf("%llu\n", sum(l, r, root, 0, 9999999999ull));
  192.             }
  193.         }
  194.     }
  195.     return 0;
  196. }

K、Color Graph

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. ul n, m;
  12. const ul maxn = 16;
  14. ul g(ul x)
  15. {
  16.     return x ^ x >> 1;
  17. }
  19. ul edges[maxn + 1];
  21. int main()
  22. {
  23.     std::scanf("%u", &T);
  24.     for (ul Case = 1; Case <= T; ++Case) {
  25.         std::scanf("%u%u", &n, &m);
  26.         for (ul i = 1; i <= n; ++i) {
  27.             edges[i] = 0;
  28.         }
  29.         for (ul i = 1; i <= m; ++i) {
  30.             ul u, v;
  31.             std::scanf("%u%u", &u, &v);
  32.             edges[u] |= 1 << v - 1;
  33.             edges[v] |= 1 << u - 1;
  34.         }
  35.         ul ans = 0;
  36.         ul tmp = 0;
  37.         for (ul i = 1; i != (1 << n); ++i) {
  38.             ul curr = g(i);
  39.             ul prev = g(i - 1);
  40.             ul id = __builtin_ctz(curr ^ prev) + 1;
  41.             tmp -= __builtin_popcount(edges[id] & ((prev >> id - 1 & 1) ? ~prev : prev));
  42.             tmp += __builtin_popcount(edges[id] & ((curr >> id - 1 & 1) ? ~curr : curr));
  43.             ans = std::max(tmp, ans);
  44.         }
  45.         std::printf("Case #%u: %u\n", Case, ans);
  46.     }
  47.     return 0;
  48. }

L、

M、Blood Pressure Game

狄克斯特拉费用流，注意由于是稠密图，不要用堆优化。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul maxn = 600;
  9. const ul maxm = maxn + 1;
  11. const li liinf = (li(1) << 31) - 1;
  12. const ll llinf = (ll(1) << 63) - 1;
  14. class mcmf {
  15. public:
  16.     class edge_t {
  17.     public:
  18.         ul to = 0;
  19.         li cap = 0;
  20.         li cost = 0;
  21.         edge_t()=default;
  22.         edge_t(ul to, li cap, li cost): to(to), cap(cap), cost(cost) {}
  23.     };
  24.     class node_t {
  25.     public:
  26.         ll pi;
  27.         ll sigma;
  28.         ul p;
  29.         li a;
  30.         ul vis;
  31.         std::vector<ul> edge;
  32.     };
  33.     edge_t edge[maxm + maxm + maxm * maxm << 1];
  34.     node_t node[maxm + maxm + 2];
  35.     std::vector<ul> stack;
  36.     bool instack[maxm + maxm + maxm * maxm << 1];
  37.     std::queue<ul> queue;
  38.     ul tim = 0;
  39.     ul n, m;
  40.     void init(ul n) {
  41.         this->n = n;
  42.         for (ul i = 0; i != n; ++i) {
  43.             node[i].edge.resize(0);
  44.             node[i].pi = 0;
  45.         }
  46.         std::memset(instack, false, sizeof(bool) * n);
  47.         stack.resize(0);
  48.         m = 0;
  49.     }
  50.     void addedge(ul from, ul to, li cap, li cost) {
  51.         edge[m] = edge_t(to, cap, cost);
  52.         ++m;
  53.         edge[m] = edge_t(from, 0, -cost);
  54.         ++m;
  55.         node[from].edge.push_back(m - 2);
  56.         node[to].edge.push_back(m - 1);
  57.     }
  58.     bool dikstra(ul s, ul t, li& flow, ll& cost) {
  59.         for (ul i = 0; i != n; ++i) {
  60.             node[i].sigma = llinf;
  61.         }
  62.         node[s].sigma = 0;
  63.         stack.push_back(s);
  64.         instack[s] = true;
  65.         while (stack.size()) {
  66.             ul small = 0;
  67.             for (ul i = 0; i != stack.size(); ++i) {
  68.                 if (node[stack[i]].sigma < node[stack[small]].sigma) {
  69.                     small = i;
  70.                 }
  71.             }
  72.             std::swap(stack[small], stack.back());
  73.             ul curr = stack.back();
  74.             stack.pop_back();
  75.             instack[curr] = false;
  76.             for (ul i : node[curr].edge) {
  77.                 edge_t& e = edge[i];
  78.                 if (e.cap > 0 && node[e.to].sigma > node[curr].sigma + e.cost + node[curr].pi - node[e.to].pi) {
  79.                     node[e.to].sigma = node[curr].sigma + e.cost + node[curr].pi - node[e.to].pi;
  80.                     if (!instack[e.to]) {
  81.                         stack.push_back(e.to);
  82.                         instack[e.to] = true;
  83.                     }
  84.                 }
  85.             }
  86.         }
  87.         if (node[t].sigma == llinf) {
  88.             return false;
  89.         }
  90.         while (queue.size()) {
  91.             queue.pop();
  92.         }
  93.         ++tim;
  94.         node[s].p = -1;
  95.         node[s].a = liinf;
  96.         queue.push(s);
  97.         node[s].vis = tim;
  98.         while (queue.size()) {
  99.             ul curr = queue.front();
  100.             queue.pop();
  101.             for (ul i : node[curr].edge) {
  102.                 edge_t& e = edge[i];
  103.                 ul nex = e.to;
  104.                 if (e.cap > 0 && node[nex].vis != tim && node[nex].sigma == node[curr].sigma + e.cost + node[curr].pi - node[nex].pi) {
  105.                     node[nex].p = i;
  106.                     node[nex].a = std::min(node[curr].a, e.cap);
  107.                     node[nex].vis = tim;
  108.                     queue.push(nex);
  109.                 }
  110.             }
  111.         }
  112.         flow += node[t].a;
  113.         cost += ll(node[t].sigma + node[t].pi - node[s].pi) * node[t].a;
  114.         ul u = t;
  115.         while (u != s) {
  116.             edge[node[u].p].cap -= node[t].a;
  117.             edge[node[u].p ^ 1].cap += node[t].a;
  118.             u = edge[node[u].p ^ 1].to;
  119.         }
  120.         for (ul i = 0; i != n; ++i) {
  121.             node[i].pi = node[i].sigma == llinf ? llinf : node[i].pi + node[i].sigma;
  122.         }
  123.         return true;
  124.     }
  125.     ll mincost(ul s, ul t) {
  126.         li flow = 0;
  127.         ll cost = 0;
  128.         while (dikstra(s, t, flow, cost));
  129.         return cost;
  130.     }
  131. };
  133. mcmf graph;
  135. ul T;
  137. ul n, m;
  139. ll a[maxn + 1];
  140. ll b[maxm + 1];
  143. int main()
  144. {
  145.     std::scanf("%u", &T);
  146.     for (ul Case = 1; Case <= T; ++Case) {
  147.         std::scanf("%u%u", &n, &m);
  148.         for (ul i = 1; i <= n; ++i) {
  149.             std::scanf("%lld", &a[i]);
  150.         }
  151.         for (ul i = 1; i <= m; ++i) {
  152.             std::scanf("%lld", &b[i]);
  153.         }
  154.         ll ans = 0;
  155.         for (ul i = 2; i <= n; ++i) {
  156.             ans += std::max(a[i], a[i - 1]) - std::min(a[i], a[i - 1]);
  157.         }
  158.         graph.init(2 + n + 1 + m);
  159.         for (ul i = 1; i <= n + 1; ++i) {
  160.             graph.addedge(0, i, 1, 0);
  161.         }
  162.         for (ul j = n + 1 + 1; j <= n + 1 + m; ++j) {
  163.             graph.addedge(j, n + 1 + m + 1, 1, 0);
  164.         }
  165.         for (ul i = 1; i <= n + 1; ++i) {
  166.             for (ul j = 1; j <= m; ++j) {
  167.                 ll alpha = 0;
  168.                 ll beta = 0;
  169.                 if (i != 1) {
  170.                     alpha += std::max(b[j], a[i - 1]) - std::min(b[j], a[i - 1]);
  171.                 }
  172.                 if (i != n + 1) {
  173.                     alpha += std::max(b[j], a[i]) - std::min(b[j], a[i]);
  174.                 }
  175.                 if (i != 1 && i != n + 1) {
  176.                     beta = std::max(a[i], a[i - 1]) - std::min(a[i], a[i - 1]);
  177.                 }
  178.                 graph.addedge(i, n + 1 + j, 1, beta - alpha);
  179.             }
  180.         }
  181.         std::printf("Case #%u:\n", Case);
  182.         li flow = 0;
  183.         ll cost = 0;
  184.         for (ul i = 1; i <= m; ++i) {
  185.             if (i != 1) {
  186.                 std::putchar(' ');
  187.             }
  188.             graph.dikstra(0, n + 1 + m + 1, flow, cost);
  189.             std::printf("%lld", ans - cost);
  190.         }
  191.         std::putchar('\n');
  192.         bool flag = false;
  193.         for (ul i = 1; i <= n + 1; ++i) {
  194.             for (ul eid : graph.node[i].edge) {
  195.                 const auto& e = graph.edge[eid];
  196.                 if (!e.cap && e.to >= n + 1 + 1) {
  197.                     ul j = e.to - n - 1;
  198.                     if (flag) {
  199.                         std::putchar(' ');
  200.                     }
  201.                     std::printf("%lld", b[j]);
  202.                     flag = true;
  203.                     break;
  204.                 }
  205.             }
  206.             if (i != n + 1) {
  207.                 if (flag) {
  208.                     std::putchar(' ');
  209.                 }
  210.                 std::printf("%lld", a[i]);
  211.                 flag = true;
  212.             }
  213.         }
  214.         std::putchar('\n');
  215.     }
  216.     return 0;
  217. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注