[关闭]
@qq290637843 2021-01-08T06:28:52.000000Z 字数 21860 阅读 265

2020杭电第二场

A、Total Eclipse 6763

简单题

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. ul T;
  14. const ul maxn = 1e5;
  16. ul n, m;
  18. ul rk[maxn + 1];
  19. ul fa[maxn + 1];
  21. std::map<ul, std::vector<ul>> b;
  23. ul getfather(ul x)
  24. {
  25.     return x == fa[x] ? x : fa[x] = getfather(fa[x]);
  26. }
  28. bool connect(ul a, ul b)
  29. {
  30.     a = getfather(a);
  31.     b = getfather(b);
  32.     if (a == b) {
  33.         return false;
  34.     } else if (rk[a] > rk[b]) {
  35.         fa[b] = a;
  36.     } else if (rk[b] > rk[a]) {
  37.         fa[a] = b;
  38.     } else {
  39.         fa[a] = b;
  40.         ++rk[b];
  41.     }
  42.     return true;
  43. }
  45. std::vector<ul> edge[maxn + 1];
  47. bool al[maxn + 1];
  49. int main()
  50. {
  51.     std::ios::sync_with_stdio(false);
  52.     std::cin.tie(0);
  53.     iss.tie(0);
  54.     oss.tie(0);
  55.     std::getline(std::cin, instr, char(0));
  56.     iss.str(instr);
  57.     iss >> T;
  58.     for (ul Case = 1; Case <= T; ++Case) {
  59.         iss >> n >> m;
  60.         b.clear();
  61.         for (ul i = 1; i <= n; ++i) {
  62.             al[i] = false;
  63.             edge[i].resize(0);
  64.             ul t;
  65.             iss >> t;
  66.             b[t].push_back(i);
  67.             rk[i] = 0;
  68.             fa[i] = i;
  69.         }
  70.         for (ul i = 1; i <= m; ++i) {
  71.             ul u, v;
  72.             iss >> u >> v;
  73.             edge[u].push_back(v);
  74.             edge[v].push_back(u);
  75.         }
  76.         b[0];
  77.         ul cnt = 0;
  78.         ull ans = 0;
  79.         for (auto it = b.rbegin(), nit = std::next(it); nit != b.rend(); it = nit, ++nit) {
  80.             for (ul u : it->second) {
  81.                 ++cnt;
  82.                 al[u] = true;
  83.                 for (ul v : edge[u]) {
  84.                     if (!al[v]) {
  85.                         continue;
  86.                     }
  87.                     if (connect(u, v)) {
  88.                         --cnt;
  89.                     }
  90.                 }
  91.             }
  92.             ans += ull(cnt) * (it->first - nit->first);
  93.         }
  94.         oss << ans << '\n';
  95.     }
  96.     std::cout << oss.str();
  97.     return 0;
  98. }

B、Blood Pressure Game 6764

官方题解如下：
image.png-178.5kB
image.png-51.3kB

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. ul T;
  14. const ul maxn = 600;
  16. ul n, k;
  18. ul a[maxn + 1];
  20. const ul mod = 1e9 + 7;
  22. ul plus(ul a, ul b)
  23. {
  24.     return a + b < mod ? a + b : a + b - mod;
  25. }
  27. ul minus(ul a, ul b)
  28. {
  29.     return a < b ? a + mod - b : a - b;
  30. }
  32. ul mul(ul a, ul b)
  33. {
  34.     return ull(a) * ull(b) % mod;
  35. }
  37. class counter {
  38. public:
  39.     ul len = 0;
  40.     ul cnt = 0;
  41.     counter()=default;
  42.     counter(ul a, ul b): len(a), cnt(b) {}
  43. };
  45. std::vector<counter> f[2][maxn + 1][3];
  47. std::vector<counter> tmp;
  49. int main()
  50. {
  51.     std::ios::sync_with_stdio(false);
  52.     std::cin.tie(0);
  53.     iss.tie(0);
  54.     oss.tie(0);
  55.     std::getline(std::cin, instr, char(0));
  56.     iss.str(instr);
  57.     iss >> T;
  58.     for (ul Case = 1; Case <= T; ++Case) {
  59.         iss >> n >> k;
  60.         for (ul i = 1; i <= n; ++i) {
  61.             iss >> a[i];
  62.         }
  63.         std::sort(a + 1, a + n + 1);
  64.         for (ul j = 1; j <= n; ++j) {
  65.             for (ul t = 0; t <= 2; ++t) {
  66.                 f[1][j][t].resize(0);
  67.             }
  68.         }
  69.         f[1][4][0] = std::vector<counter>(1, counter(0, 1));
  70.         f[1][5][1] = std::vector<counter>(1, counter(0, 2));
  71.         for (ul i = 1; i + 1 <= n; ++i) {
  72.             for (ul j = 1; j <= i + 1; ++j) {
  73.                 for (ul t = 0; t <= 2; ++t) {
  74.                     f[i + 1 & 1][j][t].resize(0);
  75.                 }
  76.             }
  77.             for (ul j = 1; j <= i; ++j) {
  78.                 for (ul t = 0; t <= 2; ++t) {
  79.                     ul tmp = (j + j - t) * (a[i + 1] - a[i]);
  80.                     for (const auto& c : f[i & 1][j][t]) {
  81.                         if (j + 1 > t) {
  82.                             f[i + 1 & 1][j + 1][t].push_back(counter(c.len + tmp, mul(c.cnt, j + 1 - t)));
  83.                         }
  84.                         if (2 > t) {
  85.                             f[i + 1 & 1][j + 1][t + 1].push_back(counter(c.len + tmp, mul(c.cnt, 2 - t)));
  86.                         }
  87.                         if (j > 1) {
  88.                             f[i + 1 & 1][j - 1][t].push_back(counter(c.len + tmp, mul(c.cnt, j - 1)));
  89.                         }
  90.                         if (j + j > t) {
  91.                             f[i + 1 & 1][j][t].push_back(counter(c.len + tmp, mul(c.cnt, j + j - t)));
  92.                         }
  93.                         if (2 > t) {
  94.                             f[i + 1 & 1][j][t + 1].push_back(counter(c.len + tmp, mul(c.cnt, 2 - t)));
  95.                         }
  96.                     }
  97.                 }
  98.             }
  99.             for (ul j = 1; j <= i + 1; ++j) {
  100.                 for (ul t = 0; t <= 2; ++t) {
  101.                     std::sort(f[i + 1 & 1][j][t].begin(), f[i + 1 & 1][j][t].end(), [](const counter& a, const counter& b){return a.len > b.len;});
  102.                     tmp.resize(0);
  103.                     for (const auto& c : f[i + 1 & 1][j][t]) {
  104.                         if (tmp.empty() || c.len != tmp.back().len) {
  105.                             if (tmp.size() == k) {
  106.                                 break;
  107.                             }
  108.                             tmp.push_back(c);
  109.                         } else {
  110.                             tmp.back().cnt = plus(tmp.back().cnt, c.cnt);
  111.                         }
  112.                     }
  113.                     std::swap(tmp, f[i + 1 & 1][j][t]);
  114.                 }
  115.             }
  116.         }
  117.         for (ul i = 0; i != k; ++i) {
  118.             if (i >= f[n & 1][6][2].size()) {
  119.                 oss << "-1\n";
  120.             } else {
  121.                 oss << f[n & 1][7][2][i].len << ' ' << f[n & 1][8][2][i].cnt << '\n';
  122.             }
  123.         }
  124.     }
  125.     std::cout << oss.str();
  126.     return 0;
  127. }

C、Count on a Tree II Striking Back 6765

官方题解如下：
image.png-111.9kB
来估计一下到底需要取到多少。姑且假设随机数生成器能做到完全独立（虽然实际做不到，但这是没办法的）。现在设执行了次实验（足够大），故对于个颜色，其颜色权值的最小值在次实验的平均值近似为正态分布，。
对于两个符合正态分布的随机变量（不保证独立），且，则有如下上界

其中而

于是如果取为，，正确概率至少能大于一半。

然而实际上，取这么大会超时，所以，我只能选择取到，但我不知道怎么证明取到是足够的

  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. std::mt19937 rnd;
  10. ul T;
  12. ul n, m;
  14. ul cnt;
  15. const ul maxn = 5e5;
  17. ul col[maxn + 1];
  19. const ul k = 35;
  21. ul w[maxn + 1][k + 1];
  23. ul head[maxn + 1];
  25. class edge {
  26. public:
  27.     ul to = 0;
  28.     ul next = 0;
  29.     edge()=default;
  30.     edge(ul a, ul b): to(a), next(b) {}
  31. };
  33. ul tot;
  35. edge edges[maxn + maxn];
  37. ul bigson[maxn + 1];
  38. ul fa[maxn + 1];
  39. ul size[maxn + 1];
  40. ul depth[maxn + 1];
  42. ul hvhd[maxn + 1];
  44. ul lsiz[maxn + 1];
  46. void search1(ul curr, ul prev)
  47. {
  48.     bigson[curr] = 0;
  49.     size[curr] = 1;
  50.     ul mxsz = 0;
  51.     for (ul nextid = head[curr]; nextid; nextid = edges[nextid].next) {
  52.         ul next = edges[nextid].to;
  53.         if (next == prev) {
  54.             continue;
  55.         }
  56.         search1(next, curr);
  57.         size[curr] += size[next];
  58.         if (size[next] > mxsz) {
  59.             mxsz = size[next];
  60.             bigson[curr] = next;
  61.         }
  62.     }
  63.     lsiz[curr] = size[curr];
  64.     if (bigson[curr]) {
  65.         lsiz[curr] -= size[bigson[curr]];
  66.     }
  67. }
  69. void search2(ul curr, ul prev)
  70. {
  71.     fa[curr] = prev;
  72.     for (ul nextid = head[curr]; nextid; nextid = edges[nextid].next) {
  73.         ul next = edges[nextid].to;
  74.         if (next == prev) {
  75.             continue;
  76.         }
  77.         if (next == bigson[curr]) {
  78.             hvhd[next] = hvhd[curr];
  79.         } else {
  80.             hvhd[next] = next;
  81.         }
  82.         depth[next] = depth[curr] + 1;
  83.         search2(next, curr);
  84.     }
  85. }
  87. ul lson[maxn + 1];
  88. ul rson[maxn + 1];
  89. ul lbound[maxn + 1];
  90. ul rbound[maxn + 1];
  92. ul tree[maxn + 1][k + 1];
  94. const ul inf = ~ul(0);
  96. void query(ul l, ul r, ul curr, ul ret[])
  97. {
  98.     if (l <= lbound[curr] && r >= rbound[curr]) {
  99.         for (ul i = 1; i <= k; ++i) {
  100.             ret[i] = std::min(ret[i], tree[curr][i]);
  101.         }
  102.         return;
  103.     }
  104.     if (l <= depth[curr] && r >= depth[curr]) {
  105.         for (ul i = 1; i <= k; ++i) {
  106.             ret[i] = std::min(ret[i], w[col[curr]][i]);
  107.         }
  108.     }
  109.     if (l < depth[curr] && lson[curr]) {
  110.         query(l, r, lson[curr], ret);
  111.     }
  112.     if (r > depth[curr] && rson[curr]) {
  113.         query(l, r, rson[curr], ret);
  114.     }
  115. }
  117. void build(ul curr)
  118. {
  119.     std::memcpy(tree[curr] + 1, w[col[curr]] + 1, sizeof(ul) * k);
  120.     if (lson[curr]) {
  121.         build(lson[curr]);
  122.         for (ul i = 1; i <= k; ++i) {
  123.             tree[curr][i] = std::min(tree[curr][i], tree[lson[curr]][i]);
  124.         }
  125.     }
  126.     if (rson[curr]) {
  127.         build(rson[curr]);
  128.         for (ul i = 1; i <= k; ++i) {
  129.             tree[curr][i] = std::min(tree[curr][i], tree[rson[curr]][i]);
  130.         }
  131.     }
  132. }
  134. void change(ul pos, ul curr, ul y)
  135. {
  136.     if (depth[curr] > pos) {
  137.         change(pos, lson[curr], y);
  138.     } else if (depth[curr] < pos) {
  139.         change(pos, rson[curr], y);
  140.     }
  141.     std::memcpy(tree[curr] + 1, w[col[curr]] + 1, sizeof(ul) * k);
  142.     if (lson[curr]) {
  143.         for (ul i = 1; i <= k; ++i) {
  144.             tree[curr][i] = std::min(tree[curr][i], tree[lson[curr]][i]);
  145.         }
  146.     }
  147.     if (rson[curr]) {
  148.         for (ul i = 1; i <= k; ++i) {
  149.             tree[curr][i] = std::min(tree[curr][i], tree[rson[curr]][i]);
  150.         }
  151.     }
  152. }
  154. ul root[maxn + 1];
  156. ull query(ul u, ul v)
  157. {
  158.     static ul ret[k + 1];
  159.     for (ul i = 1; i <= k; ++i) {
  160.         ret[i] = inf;
  161.     }
  162.     while (true) {
  163.         if (hvhd[u] == hvhd[v]) {
  164.             query(std::min(depth[u], depth[v]), std::max(depth[u], depth[v]), root[hvhd[u]], ret);
  165.             break;
  166.         }
  167.         if (depth[hvhd[u]] > depth[hvhd[v]]) {
  168.             std::swap(u, v);
  169.         }
  170.         query(depth[hvhd[v]], depth[v], root[hvhd[v]], ret);
  171.         v = fa[hvhd[v]];
  172.     }
  173.     ull sret = 0;
  174.     for (ul i = 1; i <= k; ++i) {
  175.         sret += ret[i];
  176.     }
  177.     return sret;
  178. }
  180. ul node[maxn + 1];
  182. ul deal(ul l, ul r)
  183. {
  184.     if (l == r + 1) {
  185.         return 0;
  186.     }
  187.     ul sum = 0;
  188.     for (ul i = l; i <= r; ++i) {
  189.         sum += lsiz[node[i]];
  190.     }
  191.     ul sum2 = 0;
  192.     for (ul i = l; i <= r; ++i) {
  193.         sum2 += lsiz[node[i]];
  194.         if (sum2 + sum2 >= sum) {
  195.             lson[node[i]] = deal(l, i - 1);
  196.             rson[node[i]] = deal(i + 1, r);
  197.             lbound[node[i]] = l;
  198.             rbound[node[i]] = r;
  199.             return node[i];
  200.         }
  201.     }
  202. }
  204. ul prevtime = 0;
  206. double gettime()
  207. {
  208.     ul tmp = std::clock();
  209.     double ret = double(tmp - prevtime) / CLOCKS_PER_SEC;
  210.     prevtime = tmp;
  211.     return ret;
  212. }
  214. int main()
  215. {
  216.     rnd.seed(std::time(0));
  217.     std::scanf("%u", &T);
  218.     for (ul Case = 1; Case <= T; ++Case) {
  219.         std::scanf("%u%u", &n, &m);
  220.         for (ul i = 1; i <= n; ++i) {
  221.             for (ul j = 1; j <= k; ++j) {
  222.                 w[i][j] = rnd();
  223.             }
  224.         }
  225.         tot = 0;
  226.         for (ul i = 1; i <= n; ++i) {
  227.             std::scanf("%u", &col[i]);
  228.             head[i] = 0;
  229.         }
  230.         for (ul i = 1; i <= n - 1; ++i) {
  231.             ul u, v;
  232.             std::scanf("%u%u", &u, &v);
  233.             ++tot;
  234.             edges[tot].to = v;
  235.             edges[tot].next = head[u];
  236.             head[u] = tot;
  237.             ++tot;
  238.             edges[tot].to = u;
  239.             edges[tot].next = head[v];
  240.             head[v] = tot;
  241.         }
  242.         search1(1, 0);
  243.         hvhd[1] = 1;
  244.         depth[1] = 0;
  245.         search2(1, 0);
  246.         for (ul i = 1; i <= n; ++i) {
  247.             if (hvhd[i] != i) {
  248.                 continue;
  249.             }
  250.             ul md = 0;
  251.             for (ul j = i; j; j = bigson[j]) {
  252.                 node[depth[j]] = j;
  253.                 md = depth[j];
  254.             }
  255.             root[i] = deal(depth[i], md);
  256.         }
  257.         for (ul i = 1; i <= n; ++i) {
  258.             if (i == hvhd[i]) {
  259.                 build(root[i]);
  260.             }
  261.         }
  262.         cnt = 0;
  263.         for (ul i = 1; i <= m; ++i) {
  264.             ul q;
  265.             std::scanf("%u", &q);
  266.             if (q == 1) {
  267.                 ul x, y;
  268.                 std::scanf("%u%u", &x, &y);
  269.                 x ^= cnt;
  270.                 y ^= cnt;
  271.                 col[x] = y;
  272.                 change(depth[x], root[hvhd[x]], y);
  273.             } else {
  274.                 ul a, b, c, d;
  275.                 std::scanf("%u%u%u%u", &a, &b, &c, &d);
  276.                 a ^= cnt;
  277.                 b ^= cnt;
  278.                 c ^= cnt;
  279.                 d ^= cnt;
  280.                 if (query(a, b) < query(c, d)) {
  281.                     ++cnt;
  282.                     std::printf("Yes\n");
  283.                 } else {
  284.                     std::printf("No\n");
  285.                 }
  286.             }
  287.         }
  288.     }
  289.     prevtime = 0;
  290.     return 0;
  291. }

D、Diamond Rush 6766

官方题解如下：
image.png-213.8kB

  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 pulul = std::pair<ul, ul>;
  9. ul prevtime = 0;
  11. double gettime()
  12. {
  13.     ul tmp = std::clock();
  14.     double ret = double(tmp - prevtime) / CLOCKS_PER_SEC;
  15.     prevtime = tmp;
  16.     return ret;
  17. }
  19. std::mt19937 rnd;
  21. const ul mod = 1e9 + 7;
  23. ul plus(ul a, ul b)
  24. {
  25.     return a + b < mod ? a + b : a + b - mod;
  26. }
  28. ul minus(ul a, ul b)
  29. {
  30.     return a < b ? a + mod - b : a - b;
  31. }
  33. ul mul(ul a, ul b)
  34. {
  35.     return ull(a) * ull(b) % mod;
  36. }
  38. const ul maxn = 400;
  40. ul T;
  42. ul a[maxn + 1][maxn + 1];
  43. ul n;
  44. ul q;
  46. ul ans11[maxn + 1][maxn + 1];
  47. ul ansnn[maxn + 1][maxn + 1];
  49. pulul f[maxn + 1][maxn + 1];
  50. pulul fr[maxn + 1][maxn + 1];
  51. pulul fl[maxn + 1][maxn + 1];
  53. class node {
  54. public:
  55.     ul hash = 0;
  56.     ul val = 0;
  57.     ul cnt = 0;
  58.     ul lson = 0;
  59.     ul rson = 0;
  60.     node()=default;
  61. };
  63. ul tot = 0;
  65. node tree[ul(1e7)];
  67. ul basepow[maxn * maxn + 1];
  68. ul n2pow[maxn + maxn + 1];
  70. void insert(ul pos, ul& root, ul l, ul r)
  71. {
  72.     ++tot;
  73.     tree[tot] = tree[root];
  74.     root = tot;
  75.     tree[root].hash = plus(tree[root].hash, basepow[pos]);
  76.     tree[root].val = plus(tree[root].val, n2pow[pos]);
  77.     ++tree[root].cnt;
  78.     if (l == r) {
  79.         return;
  80.     }
  81.     ul mid = l + r >> 1;
  82.     if (pos <= mid) {
  83.         insert(pos, tree[root].lson, l, mid);
  84.     } else {
  85.         insert(pos, tree[root].rson, mid + 1, r);
  86.     }
  87. }
  89. bool compare(ul x, ul y, ul l, ul r)
  90. {
  91.     if (l == r) {
  92.         return tree[x].cnt < tree[y].cnt;
  93.     }
  94.     if (tree[tree[x].rson].hash != tree[tree[y].rson].hash) {
  95.         return compare(tree[x].rson, tree[y].rson, (l + r >> 1) + 1, r);
  96.     } else {
  97.         return compare(tree[x].lson, tree[y].lson, l, l + r >> 1);
  98.     }
  99. }
  101. bool compare(ul x1, ul x2, ul y1, ul y2, ul l, ul r)
  102. {
  103.     if (l == r) {
  104.         return tree[x1].cnt + tree[x2].cnt < tree[y1].cnt + tree[y2].cnt;
  105.     }
  106.     if (plus(tree[tree[x1].rson].hash, tree[tree[x2].rson].hash) != plus(tree[tree[y1].rson].hash, tree[tree[y2].rson].hash)) {
  107.         return compare(tree[x1].rson, tree[x2].rson, tree[y1].rson, tree[y2].rson, (l + r >> 1) + 1, r);
  108.     } else {
  109.         return compare(tree[x1].lson, tree[x2].lson, tree[y1].lson, tree[y2].lson, l, l + r >> 1);
  110.     }
  111. }
  113. int main()
  114. {
  115.     rnd.seed(std::time(0));
  116.     std::scanf("%u", &T);
  117.     for (ul Case = 1; Case <= T; ++Case) {
  118.         tot = 0;
  119.         std::scanf("%u%u", &n, &q);
  120.         ul base = rnd() % mod;
  121.         basepow[0] = 1;
  122.         n2pow[0] = 1;
  123.         for (ul i = 1; i <= n * n; ++i) {
  124.             basepow[i] = mul(basepow[i - 1], base);
  125.             n2pow[i] = mul(n2pow[i - 1], n * n);
  126.         }
  127.         for (ul i = 1; i <= n; ++i) {
  128.             for (ul j = 1; j <= n; ++j) {
  129.                 std::scanf("%u", &a[i][j]);
  130.             }
  131.         }
  132.         for (ul i = 1; i <= n; ++i) {
  133.             for (ul j = 1; j <= n; ++j) {
  134.                 if (i == 1) {
  135.                     if (j == 1) {
  136.                         ans11[i][j] = 0;
  137.                     } else {
  138.                         ans11[i][j] = ans11[i][j - 1];
  139.                     }
  140.                 } else {
  141.                     if (j == 1) {
  142.                         ans11[i][j] = ans11[i - 1][j];
  143.                     } else {
  144.                         ans11[i][j] = compare(ans11[i - 1][j], ans11[i][j - 1], 1, n * n) ? ans11[i][j - 1] : ans11[i - 1][j];
  145.                     }
  146.                 }
  147.                 insert(a[i][j], ans11[i][j], 1, n * n);
  148.             }
  149.         }
  150.         for (ul i = n; i >= 1; --i) {
  151.             for (ul j = n; j >= 1; --j) {
  152.                 if (i == n) {
  153.                     if (j == n) {
  154.                         ansnn[i][j] = 0;
  155.                     } else {
  156.                         ansnn[i][j] = ansnn[i][j + 1];
  157.                     }
  158.                 } else {
  159.                     if (j == n) {
  160.                         ansnn[i][j] = ansnn[i + 1][j];
  161.                     } else {
  162.                         ansnn[i][j] = compare(ansnn[i + 1][j], ansnn[i][j + 1], 1, n * n) ? ansnn[i][j + 1] : ansnn[i + 1][j];
  163.                     }
  164.                 }
  165.                 f[i][j] = pulul(ans11[i][j], ansnn[i][j]);
  166.                 insert(a[i][j], ansnn[i][j], 1, n * n);
  167.                 fl[i][j] = f[i][j];
  168.                 if (i != n && j != 1) {
  169.                     fl[i][j] = compare(fl[i][j].first, fl[i][j].second, fl[i + 1][j - 1].first, fl[i + 1][j - 1].second, 1, n * n) ? fl[i + 1][j - 1] : fl[i][j];
  170.                 }
  171.             }
  172.         }
  173.         for (ul i = 1; i <= n; ++i) {
  174.             for (ul j = 1; j <= n; ++j) {
  175.                 fr[i][j] = f[i][j];
  176.                 if (i != 1 && j != n) {
  177.                     fr[i][j] = compare(fr[i][j].first, fr[i][j].second, fr[i - 1][j + 1].first, fr[i - 1][j + 1].second, 1, n * n) ? fr[i - 1][j + 1] : fr[i][j];
  178.                 }
  179.             }
  180.         }
  181.         for (ul i = 1; i <= q; ++i) {
  182.             ul xl, xr, yl, yr;
  183.             std::scanf("%u%u%u%u", &xl, &xr, &yl, &yr);
  184.             pulul tmp(0, 0);
  185.             if (xr != n && yl != 1) {
  186.                 tmp = compare(tmp.first, tmp.second, fl[xr + 1][yl - 1].first, fl[xr + 1][yl - 1].second, 1, n * n) ? fl[xr + 1][yl - 1] : tmp;
  187.             }
  188.             if (xl != 1 && yr != n) {
  189.                 tmp = compare(tmp.first, tmp.second, fr[xl - 1][yr + 1].first, fr[xl - 1][yr + 1].second, 1, n * n) ? fr[xl - 1][yr + 1] : tmp;
  190.             }
  191.             std::printf("%u\n", plus(tree[tmp.first].val, tree[tmp.second].val));
  192.         }
  193.     }
  194.     return 0;
  195. }

E、New Equipments 6767

简单题

  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. li m;
  14. const ul maxn = 50;
  16. const li liinf = (li(1) << 31) - 1;
  17. const ll llinf = (ll(1) << 63) - 1;
  19. class achieve_t {
  20. public:
  21.     ul to = 0;
  22.     ll sigma = 0;
  23.     achieve_t()=default;
  24.     achieve_t(ul to, ll sigma): to(to), sigma(sigma) {}
  25. };
  27. bool operator<(const achieve_t& a, const achieve_t& b)
  28. {
  29.     return a.sigma > b.sigma;
  30. }
  32. class mcmf {
  33. public:
  34.     class edge_t {
  35.     public:
  36.         ul to = 0;
  37.         li cap = 0;
  38.         ll cost = 0;
  39.         edge_t()=default;
  40.         edge_t(ul to, li cap, ll cost): to(to), cap(cap), cost(cost) {}
  41.     };
  42.     class node_t {
  43.     public:
  44.         ll pi;
  45.         ll sigma;
  46.         ul p;
  47.         li a;
  48.         ul vis;
  49.         std::vector<ul> edge;
  50.     };
  51.     node_t node[maxn + maxn * maxn + 2];
  52.     edge_t edge[maxn * maxn + maxn + maxn * maxn << 1];
  53.     std::priority_queue<achieve_t> heap;
  54.     std::queue<ul> queue;
  55.     ul tim = 0;
  56.     ul n, m;
  57.     void init(ul n) {
  58.         this->n = n;
  59.         for (ul i = 0; i != n; ++i) {
  60.             node[i].edge.resize(0);
  61.             node[i].pi = 0;
  62.         }
  63.         m = 0;
  64.     }
  65.     void addedge(ul from, ul to, li cap, ll cost) {
  66.         edge[m] = edge_t(to, cap, cost);
  67.         ++m;
  68.         edge[m] = edge_t(from, 0, -cost);
  69.         ++m;
  70.         node[from].edge.push_back(m - 2);
  71.         node[to].edge.push_back(m - 1);
  72.     }
  73.     bool dikstra(ul s, ul t, li& flow, ll& cost) {
  74.         for (ul i = 0; i != n; ++i) {
  75.             node[i].sigma = llinf;
  76.         }
  77.         while (heap.size()) {
  78.             heap.pop();
  79.         }
  80.         heap.push(achieve_t(s, 0));
  81.         node[s].sigma = 0;
  82.         while (heap.size()) {
  83.             auto ach = heap.top();
  84.             heap.pop();
  85.             if (ach.sigma > node[ach.to].sigma) {
  86.                 continue;
  87.             }
  88.             for (ul i : node[ach.to].edge) {
  89.                 edge_t& e = edge[i];
  90.                 if (e.cap > 0 && node[e.to].sigma > ach.sigma + e.cost + node[ach.to].pi - node[e.to].pi) {
  91.                     node[e.to].sigma = ach.sigma + e.cost + node[ach.to].pi - node[e.to].pi;
  92.                     heap.push(achieve_t(e.to, ach.sigma + e.cost + node[ach.to].pi - node[e.to].pi));
  93.                 }
  94.             }
  95.         }
  96.         if (node[t].sigma == llinf) {
  97.             return false;
  98.         }
  99.         while (queue.size()) {
  100.             queue.pop();
  101.         }
  102.         ++tim;
  103.         node[s].p = -1;
  104.         node[s].a = liinf;
  105.         queue.push(s);
  106.         node[s].vis = tim;
  107.         while (queue.size()) {
  108.             ul curr = queue.front();
  109.             queue.pop();
  110.             for (ul i : node[curr].edge) {
  111.                 edge_t& e = edge[i];
  112.                 ul nex = e.to;
  113.                 if (e.cap > 0 && node[nex].vis != tim && node[nex].sigma == node[curr].sigma + e.cost + node[curr].pi - node[nex].pi) {
  114.                     node[nex].p = i;
  115.                     node[nex].a = std::min(node[curr].a, e.cap);
  116.                     node[nex].vis = tim;
  117.                     queue.push(nex);
  118.                 }
  119.             }
  120.         }
  121.         flow += node[t].a;
  122.         cost += ll(node[t].sigma + node[t].pi - node[s].pi) * node[t].a;
  123.         ul u = t;
  124.         while (u != s) {
  125.             edge[node[u].p].cap -= node[t].a;
  126.             edge[node[u].p ^ 1].cap += node[t].a;
  127.             u = edge[node[u].p ^ 1].to;
  128.         }
  129.         for (ul i = 0; i != n; ++i) {
  130.             node[i].pi = node[i].sigma == llinf ? llinf : node[i].pi + node[i].sigma;
  131.         }
  132.         return true;
  133.     }
  134.     ll mincost(ul s, ul t) {
  135.         li flow = 0;
  136.         ll cost = 0;
  137.         while (dikstra(s, t, flow, cost));
  138.         return cost;
  139.     }
  140. };
  142. mcmf graph;
  144. ll a[maxn + 1], b[maxn + 1], c[maxn + 1];
  146. std::vector<li> need[maxn + 1];
  147. std::vector<ul> al;
  148. using pulull = std::pair<ul, ull>;
  149. std::vector<pulull> set;
  151. std::map<ul, ul> id;
  153. int main()
  154. {
  155.     std::scanf("%u", &T);
  156.     for (ul Case = 1; Case <= T; ++Case) {
  157.         std::scanf("%u%d", &n, &m);
  158.         al.resize(0);
  159.         for (ul i = 1; i <= n; ++i) {
  160.             std::scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
  161.             need[i].resize(0);
  162.             ll tmp = -2 * a[i];
  163.             if (b[i] > tmp) {
  164.                 for (ul j = 1; j <= m && j <= n; ++j) {
  165.                     need[i].push_back(j);
  166.                     al.push_back(j);
  167.                 }
  168.             } else if (b[i] < m * tmp) {
  169.                 for (ul j = m; m - j + 1 <= n && j >= 1; --j) {
  170.                     need[i].push_back(j);
  171.                     al.push_back(j);
  172.                 }
  173.             } else {
  174.                 set.resize(0);
  175.                 for (ll j = b[i] / tmp - 100; j <= b[i] / tmp + 100; ++j) {
  176.                     if (j < 1) {
  177.                         continue;
  178.                     }
  179.                     if (j > m) {
  180.                         continue;
  181.                     }
  182.                     set.push_back(pulull(j, a[i] * j * j + b[i] * j + c[i]));
  183.                 }
  184.                 std::sort(set.begin(), set.end(), [](const pulull& a, const pulull& b){return a.second < b.second;});
  185.                 set.resize(std::min(ul(n), ul(m)));
  186.                 for (auto p : set) {
  187.                     need[i].push_back(p.first);
  188.                     al.push_back(p.first);
  189.                 }
  190.             }
  191.         }
  192.         std::sort(al.begin(), al.end());
  193.         al.resize(std::unique(al.begin(), al.end()) - al.begin());
  194.         ul tim = n;
  195.         for (auto a : al) {
  196.             ++tim;
  197.             id[a] = tim;
  198.         }
  199.         ++tim;
  200.         graph.init(tim + 1);
  201.         for (ul i = 1; i <= n; ++i) {
  202.             graph.addedge(0, i, 1, 0);
  203.             for (ll j : need[i]) {
  204.                 graph.addedge(i, id[j], 1, a[i] * j * j + b[i] * j + c[i]);
  205.             }
  206.         }
  207.         for (auto a : al) {
  208.             graph.addedge(id[a], tim, 1, 0);
  209.         }
  210.         li flow = 0;
  211.         ll cost = 0;
  212.         for (li i = 1; i <= n; ++i) {
  213.             if (i != 1) {
  214.                 std::putchar(' ');
  215.             }
  216.             while (i > flow) {
  217.                 graph.dikstra(0, tim, flow, cost);
  218.             }
  219.             std::printf("%lld", cost);
  220.         }
  221.         std::putchar('\n');
  222.     }
  223.     return 0;
  224. }

F、The Oculus 6768

简单题

  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. ul T;
  11. const ul maxn = 1e6;
  13. ull fib[maxn + maxn + 2];
  15. int main()
  16. {
  17.     fib[0] = fib[1] = 1;
  18.     for (ul i = 2; i <= maxn + maxn + 1; ++i) {
  19.         fib[i] = fib[i - 1] + fib[i - 2];
  20.     }
  21.     std::scanf("%u", &T);
  22.     for (ul Case = 1; Case <= T; ++Case) {
  23.         ul al, bl, cl;
  24.         ull a = 0, b = 0, c = 0;
  25.         ul ai, bi, ci;
  26.         std::scanf("%u", &al);
  27.         for (ul i = 1; i <= al; ++i) {
  28.             std::scanf("%u", &ai);
  29.             if (ai) {
  30.                 a += fib[i];
  31.             }
  32.         }
  33.         std::scanf("%u", &bl);
  34.         for (ul i = 1; i <= bl; ++i) {
  35.             std::scanf("%u", &bi);
  36.             if (bi) {
  37.                 b += fib[i];
  38.             }
  39.         }
  40.         std::scanf("%u", &cl);
  41.         for (ul i = 1; i <= cl; ++i) {
  42.             std::scanf("%u", &ci);
  43.             if (ci) {
  44.                 c += fib[i];
  45.             }
  46.         }
  47.         ull t = a * b - c;
  48.         for (ul i = 1; ; ++i) {
  49.             if (fib[i] == t) {
  50.                 std::printf("%u\n", i);
  51.                 break;
  52.             }
  53.         }
  54.     }
  55.     return 0;
  56. }

G、In Search of Gold 6769

官方题解如下：
image.png-124.9kB

  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. const ul maxn = 2e4;
  11. const ul maxk = 20;
  13. ul n, k;
  15. class edge {
  16. public:
  17.     ul a = 0;
  18.     ul b = 0;
  19.     ul to = 0;
  20.     edge()=default;
  21.     edge(ul x, ul y, ul z): to(x), a(y), b(z) {}
  22. };
  24. std::vector<edge> edges[maxn + 1];
  26. ull f[maxn + 1][maxk + 1];
  28. ull tmpf[maxk + 1];
  29. ull initf[maxk + 1];
  31. const ull inf = 2e13;
  33. ull bound;
  35. ul search(ul curr, ul prev)
  36. {
  37.     std::memcpy(f[curr], initf, sizeof(ull) * (k + 1));
  38.     f[curr][0] = 0;
  39.     ul currcnt = 0;
  40.     for (const auto& e : edges[curr]) {
  41.         ul next = e.to;
  42.         if (next == prev) {
  43.             continue;
  44.         }
  45.         ul nextcnt = search(next, curr);
  46.         std::memcpy(tmpf, initf, sizeof(ull) * (k + 1));
  47.         for (ul x = 0; x <= k && x <= currcnt; ++x) {
  48.             if (f[curr][x] == inf) {
  49.                 continue;
  50.             }
  51.             for (ul y = 0; x + y <= k && y <= nextcnt; ++y) {
  52.                 if (f[next][y] == inf) {
  53.                     continue;
  54.                 }
  55.                 if (f[curr][x] + f[next][y] + e.b <= bound) {
  56.                     tmpf[x + y] = std::min(tmpf[x + y], std::max(f[curr][x], f[next][y] + e.b));
  57.                 }
  58.                 if (x + y != k && f[curr][x] + f[next][y] + e.a <= bound) {
  59.                     tmpf[x + y + 1] = std::min(tmpf[x + y + 1], std::max(f[curr][x], f[next][y] + e.a));
  60.                 }
  61.             }
  62.         }
  63.         std::memcpy(f[curr], tmpf, sizeof(ull) * (k + 1));
  64.         currcnt += nextcnt + 1;
  65.     }
  66.     return currcnt;
  67. }
  69. int main()
  70. {
  71.     for (ul i = 0; i <= maxk; ++i) {
  72.         initf[i] = inf;
  73.     }
  74.     std::scanf("%u", &T);
  75.     for (ul Case = 1; Case <= T; ++Case) {
  76.         std::scanf("%u%u", &n, &k);
  77.         for (ul i = 1; i <= n; ++i) {
  78.             edges[i].resize(0);
  79.         }
  80.         for (ul i = 1; i <= n - 1; ++i) {
  81.             ul u, v, a, b;
  82.             std::scanf("%u%u%u%u", &u, &v, &a, &b);
  83.             edges[u].push_back(edge(v, a, b));
  84.             edges[v].push_back(edge(u, a, b));
  85.         }
  86.         ull l = n - 2, r = 2e13;
  87.         while (l + 1 != r) {
  88.             bound = l + r >> 1;
  89.             search(1, 0);
  90.             if (f[1][k] == inf) {
  91.                 l = bound;
  92.             } else {
  93.                 r = bound;
  94.             }
  95.         }
  96.         std::printf("%llu\n", r);
  97.     }
  98.     return 0;
  99. }

H、Dynamic Convex Hull 6770

官方题解如下：
image.png-211.5kB
image.png-8.9kB

  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. const ul maxn = 1e5;
  11. const ul maxm = 1e5;
  13. ul n, m;
  15. ul a[maxn + maxm + 1];
  16. ull b[maxn + maxm + 1];
  17. ul l[maxn + maxm + 1];
  18. bool erased[maxn + maxm + 1];
  20. ull ans[maxm + 1];
  22. ul tot;
  24. ul x[maxm + 1];
  26. const ul sz = 1 << 17;
  28. std::vector<ul> tos[sz << 1];
  29. std::vector<ul> froms[sz << 1];
  31. void insert(ul l, ul r, ul v)
  32. {
  33.     for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
  34.         if (~l & 1) {
  35.             froms[l ^ 1].push_back(v);
  36.         }
  37.         if (r & 1) {
  38.             froms[r ^ 1].push_back(v);
  39.         }
  40.     }
  41. }
  43. void insert(ul pos, ul v)
  44. {
  45.     for (pos |= sz; pos; pos >>= 1) {
  46.         tos[pos].push_back(v);
  47.     }
  48. }
  50. ull f(ull x, ull a, ull b)
  51. {
  52.     return (x - a) * (x - a) * (x - a) * (x - a) + b;
  53. }
  55. const ull inf = 9e18;
  57. void deal(ul xl, ul xr, ul fl, ul fr, ul nid)
  58. {
  59.     if (xl == xr + 1) {
  60.         return;
  61.     }
  62.     ul mid = xl + xr >> 1;
  63.     ull tmpans = inf;
  64.     ul lbound, rbound;
  65.     for (ul i = fl; i <= fr; ++i) {
  66.         ull cans = f(x[tos[nid][mid]], a[froms[nid][i]], b[froms[nid][i]]);
  67.         if (tmpans > cans) {
  68.             tmpans = cans;
  69.             lbound = i;
  70.             rbound = i;
  71.         } else if (tmpans == cans) {
  72.             rbound = i;
  73.         }
  74.     }
  75.     deal(xl, mid - 1, fl, lbound, nid);
  76.     deal(mid + 1, xr, rbound, fr, nid);
  77.     ans[tos[nid][mid]] = std::min(ans[tos[nid][mid]], tmpans);
  78. }
  80. int main()
  81. {
  82.     std::scanf("%u", &T);
  83.     for (ul Case = 1; Case <= T; ++Case) {
  84.         for (ul i = 0; i != sz + sz; ++i) {
  85.             tos[i].resize(0);
  86.             froms[i].resize(0);
  87.         }
  88.         std::scanf("%u%u", &n, &m);
  89.         tot = n;
  90.         for (ul i = 1; i <= n; ++i) {
  91.             std::scanf("%u%llu", &a[i], &b[i]);
  92.             l[i] = 1;
  93.             erased[i] = false;
  94.         }
  95.         for (ul i = 1; i <= m; ++i) {
  96.             x[i] = 0;
  97.             ul k;
  98.             std::scanf("%u", &k);
  99.             if (k == 1) {
  100.                 ++tot;
  101.                 std::scanf("%u%llu", &a[tot], &b[tot]);
  102.                 erased[tot] = false;
  103.                 l[tot] = i;
  104.             } else if (k == 2) {
  105.                 ul t;
  106.                 std::scanf("%u", &t);
  107.                 erased[t] = true;
  108.                 insert(l[t], i, t);
  109.             } else if (k == 3) {
  110.                 ans[i] = inf;
  111.                 std::scanf("%u", &x[i]);
  112.                 insert(i, i);
  113.             }
  114.         }
  115.         for (ul i = 1; i <= tot; ++i) {
  116.             if (!erased[i]) {
  117.                 insert(l[i], m, i);
  118.             }
  119.         }
  120.         for (ul i = 1; i != sz + sz; ++i) {
  121.             if (froms[i].size() && tos[i].size()) {
  122.                 std::sort(froms[i].begin(), froms[i].end(), [](ul s, ul t){return a[s] < a[t];});
  123.                 std::sort(tos[i].begin(), tos[i].end(), [](ul s, ul t){return x[s] < x[t];});
  124.                 deal(0, tos[i].size() - 1, 0, froms[i].size() - 1, i);
  125.             }
  126.         }
  127.         for (ul i = 1; i <= m; ++i) {
  128.             if (x[i]) {
  129.                 if (ans[i] == inf) {
  130.                     std::printf("-1\n");
  131.                 } else {
  132.                     std::printf("%llu\n", ans[i]);
  133.                 }
  134.             }
  135.         }
  136.     }
  137.     return 0;
  138. }

I、It's All Squares 6771

暴力

  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. const ul maxn = 400;
  11. const ul maxm = 400;
  13. ul n, m, q;
  15. ul w[maxn + 1][maxm + 1];
  17. std::vector<ul> stack;
  19. std::vector<bool> instack(maxn * maxm + 1, false);
  21. std::vector<ul> bounds[maxn + 1];
  23. char str[4000002];
  25. int main()
  26. {
  27.     std::scanf("%u", &T);
  28.     for (ul Case = 1; Case <= T; ++Case) {
  29.         std::scanf("%u%u%u", &n, &m, &q);
  30.         for (ul i = 1; i <= n; ++i) {
  31.             for (ul j = 1; j <= m; ++j) {
  32.                 std::scanf("%u", &w[i][j]);
  33.             }
  34.         }
  35.         for (ul i = 1; i <= q; ++i) {
  36.             ul x, y;
  37.             std::scanf("%u%u%s", &x, &y, str + 1);
  38.             ul mnx = x, mxx = x;
  39.             for (ul i = 1; str[i]; ++i) {
  40.                 if (str[i] == 'L') {
  41.                     bounds[x].push_back(y);
  42.                     --x;
  43.                 } else if (str[i] == 'R') {
  44.                     ++x;
  45.                     bounds[x].push_back(y);
  46.                 } else if (str[i] == 'D') {
  47.                     --y;
  48.                 } else if (str[i] == 'U') {
  49.                     ++y;
  50.                 }
  51.                 mnx = std::min(mnx, x);
  52.                 mxx = std::max(mxx, x);
  53.             }
  54.             for (ul x = mnx + 1; x <= mxx; ++x) {
  55.                 std::sort(bounds[x].begin(), bounds[x].end());
  56.                 for (ul i = 0; i != bounds[x].size(); i += 2) {
  57.                     for (ul y = bounds[x][i] + 1; y <= bounds[x][i + 1]; ++y) {
  58.                         if (!instack[w[x][y]]) {
  59.                             instack[w[x][y]] = true;
  60.                             stack.push_back(w[x][y]);
  61.                         }
  62.                     }
  63.                 }
  64.                 bounds[x].resize(0);
  65.             }
  66.             std::printf("%u\n", ul(stack.size()));
  67.             for (ul k : stack) {
  68.                 instack[k] = false;
  69.             }
  70.             stack.resize(0);
  71.         }
  72.     }
  73.     return 0;
  74. }

J、Lead of Wisdom 6772

暴力

  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. const ul maxn = 50;
  11. const ul maxk = 50;
  13. ul n, k;
  15. class eq {
  16. public:
  17.     ul a = 0;
  18.     ul b = 0;
  19.     ul c = 0;
  20.     ul d = 0;
  21.     eq()=default;
  22. };
  24. std::vector<eq> eqs[maxk + 1];
  26. ull ans = 0;
  28. ul a = 100, b = 100, c = 100, d = 100;
  30. void search(ul curr)
  31. {
  32.     if (curr == k + 1) {
  33.         ans = std::max(ans, ull(a) * ull(b) * ull(c) * ull(d));
  34.         return;
  35.     }
  36.     if (eqs[curr].size() == 0) {
  37.         search(curr + 1);
  38.         return;
  39.     }
  40.     for (const auto& e : eqs[curr]) {
  41.         a += e.a;
  42.         b += e.b;
  43.         c += e.c;
  44.         d += e.d;
  45.         search(curr + 1);
  46.         a -= e.a;
  47.         b -= e.b;
  48.         c -= e.c;
  49.         d -= e.d;
  50.     }
  51. }
  53. int main()
  54. {
  55.     std::scanf("%u", &T);
  56.     for (ul Case = 1; Case <= T; ++Case) {
  57.         std::scanf("%u%u", &n, &k);
  58.         for (ul i = 1; i <= k; ++i) {
  59.             eqs[i].resize(0);
  60.         }
  61.         for (ul i = 1; i <= n; ++i) {
  62.             ul t;
  63.             std::scanf("%u", &t);
  64.             eqs[t].push_back(eq());
  65.             std::scanf("%u%u%u%u", &eqs[t].back().a, &eqs[t].back().b, &eqs[t].back().c, &eqs[t].back().d);
  66.         }
  67.         std::sort(eqs + 1, eqs + k + 1, [](const std::vector<eq>& a, const std::vector<eq>& b){return a.size() < b.size();});
  68.         ans = 0;
  69.         search(1);
  70.         std::printf("%llu\n", ans);
  71.     }
  72.     return 0;
  73. }

L、String Distance 6774

代码中dp[x][y]表示和的公共子序列要长达，则该公共子序列在中末尾下标最小是多少。
right[i][c]表示中第一个为的字符的下标。
ans[i][y]表示和的公共子序列要长达，则该公共子序列在中末尾下标最小是多少。

  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, q;
  11. const ul maxn = 1e5;
  12. const ul maxm = 20;
  14. char a[maxn + 1];
  15. char b[maxm + 1];
  17. ul dp[maxm + 1][maxm + 1];
  19. ul right[maxn + 2][26];
  20. ul ans[maxn + 1][maxm + 1];
  22. int main()
  23. {
  24.     std::scanf("%u", &T);
  25.     for (ul Case = 1; Case <= T; ++Case) {
  26.         std::scanf("%s%s", a + 1, b + 1);
  27.         n = std::strlen(a + 1);
  28.         m = std::strlen(b + 1);
  29.         for (ul i = 0; i != 26; ++i) {
  30.             right[n + 1][i] = n + 1;
  31.         }
  32.         for (ul i = n; i; --i) {
  33.             std::memcpy(right[i], right[i + 1], sizeof(ul) * 26);
  34.             right[i][a[i] - 'a'] = i;
  35.         }
  36.         for (ul i = 1; i <= n; ++i) {
  37.             for (ul x = 0; x <= m; ++x) {
  38.                 dp[x][0] = i - 1;
  39.                 for (ul y = 1; y <= x; ++y) {
  40.                     if (x == y) {
  41.                         if (dp[x - 1][y - 1] == n + 1) {
  42.                             dp[x][y] = n + 1;
  43.                         } else {
  44.                             dp[x][y] = right[dp[x - 1][y - 1] + 1][b[x] - 'a'];
  45.                         }
  46.                     } else {
  47.                         dp[x][y] = dp[x - 1][y];
  48.                         if (dp[x - 1][y - 1] != n + 1) {
  49.                             dp[x][y] = std::min(dp[x][y], right[dp[x - 1][y - 1] + 1][b[x] - 'a']);
  50.                         }
  51.                     }
  52.                 }
  53.             }
  54.             for (ul x = 0; x <= m; ++x) {
  55.                 ans[i][x] = dp[m][x];
  56.             }
  57.         }
  58.         std::scanf("%u", &q);
  59.         for (ul i = 1; i <= q; ++i) {
  60.             ul l, r;
  61.             std::scanf("%u%u", &l, &r);
  62.             for (ul i = m; ~i; --i) {
  63.                 if (ans[l][i] <= r) {
  64.                     std::printf("%u\n", r - l + 1 + m - i - i);
  65.                     break;
  66.                 }
  67.             }
  68.         }
  69.     }
  70.     return 0;
  71. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注