[关闭]
@qq290637843 2021-01-30T13:19:08.000000Z 字数 25524 阅读 501

2019南京

题目见https://www.jisuanke.com/contest/5528/challenges。

A、A Hard Problem

实际就是问最多选多少个数使得两两不为倍数关系。首先，选最大的是可行的。关于最大性，注意每个奇数所对应的所有中只能选一个，于是不可能选超过个

  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. int main()
  13. {
  14.     std::scanf("%u", &T);
  15.     for (ul Case = 1; Case <= T; ++Case) {
  16.         std::scanf("%u", &n);
  17.         std::printf("%u\n", (n + 1 >> 1) + 1);
  18.     }
  19.     return 0;
  20. }

B、Chessboard

倒着考虑，就是说每走一步挖掉一个格子，要求任何时刻剩余的格子构成的区域是满足要求的。那么显然，一开始只能选择从四角挖，接着，只能沿着剩余区域的一边走，不到端点不能转弯，于是乎任何时候都是从剩余区域挖掉一条边然后留下一个长方形。一开始的选角数量等于，接下来就是简单的选次作为删横边，次作为删竖边。

  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 mul(ul a, ul b)
  11. {
  12.     return ull(a) * ull(b) % mod;
  13. }
  15. void exgcd(li a, li b, li& x, li& y)
  16. {
  17.     if (b) {
  18.         exgcd(b, a % b, y, x);
  19.         y -= a / b * x;
  20.     } else {
  21.         x = 1;
  22.         y = 0;
  23.     }
  24. }
  26. ul inverse(ul a)
  27. {
  28.     li x, y;
  29.     exgcd(a, mod, x, y);
  30.     return x < 0 ? x + li(mod) : x;
  31. }
  33. ul T;
  35. ul n, m;
  37. const ul maxn = 1e6;
  38. const ul maxm = 1e6;
  40. ul fac[maxn + maxm + 1];
  42. ul fiv[maxn + maxm + 1];
  44. int main()
  45. {
  46.     fac[0] = 1;
  47.     for (ul i = 1; i <= maxn + maxm; ++i) {
  48.         fac[i] = mul(fac[i - 1], i);
  49.     }
  50.     fiv[maxn + maxm] = inverse(fac[maxn + maxm]);
  51.     for (ul i = maxn + maxm; i >= 1; --i) {
  52.         fiv[i - 1] = mul(fiv[i], i);
  53.     }
  54.     std::scanf("%u", &T);
  55.     for (ul Case = 1; Case <= T; ++Case) {
  56.         std::scanf("%u%u", &n, &m);
  57.         std::printf("%u\n", mul(mul((n >= 2) + 1, (m >= 2) + 1), mul(fac[n + m - 2], mul(fiv[n - 1], fiv[m - 1]))));
  58.     }
  59.     return 0;
  60. }

C、Digital Path

简单动态规划

  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. using pulul = std::pair<ul, ul>;
  10. using plipulul = std::pair<li, pulul>;
  12. const ul mod = 1e9 + 7;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < mod ? a + b : a + b - mod;
  17. }
  19. ul n, m;
  21. const ul maxn = 1000;
  22. const ul maxm = 1000;
  24. ul ans[maxn + 1][maxm + 1][5];
  26. ul out = 0;
  28. li val[maxn + 2][maxm + 2];
  30. std::vector<plipulul> pos;
  32. int main()
  33. {
  34.     std::scanf("%u%u", &n, &m);
  35.     for (ul j = 1; j <= m; ++j) {
  36.         val[0][j] = val[n + 1][j] = 1e9;
  37.     }
  38.     for (ul i = 1; i <= n; ++i) {
  39.         val[i][0] = val[i][m + 1] = 1e9;
  40.     }
  41.     for (ul i = 1; i <= n; ++i) {
  42.         for (ul j = 1; j <= m; ++j) {
  43.             std::scanf("%d", &val[i][j]);
  44.             pos.push_back(plipulul(val[i][j], pulul(i, j)));
  45.         }
  46.     }
  47.     std::sort(pos.begin(), pos.end());
  48.     for (const auto& p : pos) {
  49.         const auto& curr = p.second;
  50.         bool ishead = true;
  51.         bool istail = true;
  52.         for (const auto& prev : {pulul(curr.first + 1, curr.second), pulul(curr.first, curr.second + 1), pulul(curr.first - 1, curr.second), pulul(curr.first, curr.second - 1)}) {
  53.             if (val[prev.first][prev.second] == p.first - 1) {
  54.                 ishead = false;
  55.                 for (ul i = 1; i <= 4; ++i) {
  56.                     ans[curr.first][curr.second][std::min(i + 1, ul(4))] = plus(ans[curr.first][curr.second][std::min(i + 1, ul(4))], ans[prev.first][prev.second][i]);
  57.                 }
  58.             }
  59.             if (val[prev.first][prev.second] == p.first + 1) {
  60.                 istail = false;
  61.             }
  62.         }
  63.         if (ishead) {
  64.             ans[curr.first][curr.second][1] = 1;
  65.         }
  66.         if (istail) {
  67.             out = plus(out, ans[curr.first][curr.second][4]);
  68.         }
  69.     }
  70.     std::printf("%u\n", out);
  71.     return 0;
  72. }

D、Holes

首先将所有洞的出边全部砍掉。
于是实际就是要对每一个求，考虑分母和分子该怎么求。
由于

故

设，那么上二式即为
这是两个元稀疏方程，所以可以解决，但还是大了。
每个点都对应着两个方程。现在考虑对满足如下性质的点的任意取值：是第一行的，或者是个洞。接着，其余点都可以根据其正上方挨着那个点所对应的方程递推出一个值。现在得到的这个显然满足以下这些方程：既不是最后一行的，也不是洞正上方挨着的点，这些点所对应的方程。而可能不满足的方程数正好就是任意取值的那些点的数量。换言之，就是用那些“自变点”的表示出“因变点”的，并用剩余方程解出“自变点”的值。而这个递推过程可以完成，故实际最终只需要解两个元的线性方程组，故最终时间复杂度。

  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. using pulul = std::pair<ul, ul>;
  10. pulul operator+(const pulul& a, const pulul& b)
  11. {
  12.     return pulul(a.first + b.first, a.second + b.second);
  13. }
  15. const ul mod = 1e9 + 7;
  17. ul plus(ul a, ul b)
  18. {
  19.     return a + b < mod ? a + b : a + b - mod;
  20. }
  22. ul minus(ul a, ul b)
  23. {
  24.     return a < b ? a + mod - b : a - b;
  25. }
  27. ul mul(ul a, ul b)
  28. {
  29.     return ull(a) * ull(b) % mod;
  30. }
  32. void exgcd(li a, li b, li& x, li& y)
  33. {
  34.     if (b) {
  35.         exgcd(b, a % b, y, x);
  36.         y -= a / b * x;
  37.     } else {
  38.         x = 1;
  39.         y = 0;
  40.     }
  41. }
  43. ul inverse(ul a)
  44. {
  45.     li x, y;
  46.     exgcd(a, mod, x, y);
  47.     return x < 0 ? x + li(mod) : x;
  48. }
  50. ul T;
  52. ul n;
  54. ul k;
  56. ul tot;
  58. const ul maxn = 200;
  60. const ul maxk = 200;
  62. const ul maxtot = maxk + maxn;
  64. bool ishole[maxn + 1][maxn + 2];
  66. pulul holes[maxk + 1];
  68. pulul from[maxk + maxn + 1];
  70. ul fromid[maxn + 1][maxn + 2];
  72. class val_t {
  73. public:
  74.     ul dx[maxtot + 1];
  75.     ul dy[maxtot + 1];
  76.     ul c;
  77.     void init()
  78.     {
  79.         std::memset(dx + 1, 0, sizeof(ul) * tot);
  80.         std::memset(dy + 1, 0, sizeof(ul) * tot);
  81.         c = 0;
  82.     }
  83. };
  85. val_t operator+(const val_t& a, const val_t& b)
  86. {
  87.     static val_t ret;
  88.     for (ul i = 1; i <= tot; ++i) {
  89.         ret.dx[i] = plus(a.dx[i], b.dx[i]);
  90.     }
  91.     for (ul i = 1; i <= tot; ++i) {
  92.         ret.dy[i] = plus(a.dy[i], b.dy[i]);
  93.     }
  94.     ret.c = plus(a.c, b.c);
  95.     return ret;
  96. }
  98. val_t operator-(const val_t& a, const val_t& b)
  99. {
  100.     static val_t ret;
  101.     for (ul i = 1; i <= tot; ++i) {
  102.         ret.dx[i] = minus(a.dx[i], b.dx[i]);
  103.     }
  104.     for (ul i = 1; i <= tot; ++i) {
  105.         ret.dy[i] = minus(a.dy[i], b.dy[i]);
  106.     }
  107.     ret.c = minus(a.c, b.c);
  108.     return ret;
  109. }
  111. val_t operator*(const val_t& a, ul b)
  112. {
  113.     static val_t ret;
  114.     for (ul i = 1; i <= tot; ++i) {
  115.         ret.dx[i] = mul(a.dx[i], b);
  116.     }
  117.     for (ul i = 1; i <= tot; ++i) {
  118.         ret.dy[i] = mul(a.dy[i], b);
  119.     }
  120.     ret.c = mul(a.c, b);
  121.     return ret;
  122. }
  124. val_t operator/(const val_t& a, ul b)
  125. {
  126.     return a * inverse(b);
  127. }
  129. ul deg[maxn + 1][maxn + 2];
  131. template<typename T>
  132. T& at(T v[][maxn + 2], const pulul& p)
  133. {
  134.     return v[p.first][p.second];
  135. }
  137. val_t ans[maxn + 1][maxn + 2][2];
  139. pulul s;
  141. ul a[maxtot + 1][maxtot + 1];
  143. ul b[maxtot + 1];
  145. void solve(ul a[][maxtot + 1], ul b[], ul x[])
  146. {
  147.     for (ul i = 1; i <= tot; ++i) {
  148.         if (!a[i][i]) {
  149.             for (ul j = i + 1; j <= tot; ++j) {
  150.                 if (a[j][i]) {
  151.                     for (ul k = i; k <= tot; ++k) {
  152.                         std::swap(a[i][k], a[j][k]);
  153.                     }
  154.                     std::swap(b[i], b[j]);
  155.                     break;
  156.                 }
  157.             }
  158.         }
  159.         ul t = inverse(a[i][i]);
  160.         for (ul j = i; j <= tot; ++j) {
  161.             a[i][j] = mul(a[i][j], t);
  162.         }
  163.         b[i] = mul(b[i], t);
  164.         for (ul j = 1; j <= tot; ++j) {
  165.             if (j == i) {
  166.                 continue;
  167.             }
  168.             t = a[j][i];
  169.             if (t) {
  170.                 for (ul k = i; k <= tot; ++k) {
  171.                     a[j][k] = minus(a[j][k], mul(t, a[i][k]));
  172.                 }
  173.                 b[j] = minus(b[j], mul(t, b[i]));
  174.             }
  175.         }
  176.     }
  177.     std::memcpy(x + 1, b + 1, sizeof(ul) * tot);
  178. }
  180. ul x[maxtot + 1];
  181. ul y[maxtot + 1];
  183. int main()
  184. {
  185.     std::scanf("%u", &T);
  186.     for (ul Case = 1; Case <= T; ++Case) {
  187.         std::scanf("%u%u", &n, &k);
  188.         for (ul i = 0; i <= n; ++i) {
  189.             std::memset(ishole[i], false, sizeof(bool) * (n + 2));
  190.         }
  191.         deg[1][1] = 2;
  192.         for (ul j = 2; j <= n - 1; ++j) {
  193.             deg[1][j] = 3;
  194.         }
  195.         deg[1][n] = 2;
  196.         for (ul i = 2; i <= n - 1; ++i) {
  197.             deg[i][1] = 3;
  198.             for (ul j = 2; j <= n - 1; ++j) {
  199.                 deg[i][j] = 4;
  200.             }
  201.             deg[i][n] = 3;
  202.         }
  203.         deg[n][1] = 2;
  204.         for (ul j = 2; j <= n - 1; ++j) {
  205.             deg[n][j] = 3;
  206.         }
  207.         deg[n][n] = 2;
  208.         for (ul i = 1; i <= k; ++i) {
  209.             std::scanf("%u%u", &holes[i].first, &holes[i].second);
  210.             at(ishole, holes[i]) = true;
  211.         }
  212.         std::scanf("%u%u", &s.first, &s.second);
  213.         for (ul i = 1; i <= k; ++i) {
  214.             at(fromid, holes[i]) = i;
  215.             from[i] = holes[i];
  216.         }
  217.         tot = k;
  218.         for (ul j = 1; j <= n; ++j) {
  219.             if (!ishole[1][j]) {
  220.                 ++tot;
  221.                 fromid[1][j] = tot;
  222.                 from[tot] = pulul(1, j);
  223.             }
  224.         }
  225.         for (ul i = 1; i <= tot; ++i) {
  226.             at(ans, from[i])[0].init();
  227.             at(ans, from[i])[1].init();
  228.             at(ans, from[i])[0].dx[i] = 1;
  229.             at(ans, from[i])[1].dy[i] = 1;
  230.         }
  231.         for (pulul curr(2, 1); curr.first <= n; ++curr.first) {
  232.             for (curr.second = 1; curr.second <= n; ++curr.second) {
  233.                 if (at(ishole, curr)) {
  234.                     continue;
  235.                 }
  236.                 pulul up = curr + pulul(-1, 0);
  237.                 at(ans, curr)[0] = at(ans, up)[0];
  238.                 at(ans, curr)[1] = at(ans, up)[1] - at(ans, up)[0];
  239.                 for (const auto& next : {up + pulul(0, 1), up + pulul(-1, 0), up + pulul(0, -1)}) {
  240.                     if (next.first < 1 || next.second < 1 || next.second > n) {
  241.                         continue;
  242.                     }
  243.                     if (at(ishole, next)) {
  244.                         continue;
  245.                     }
  246.                     at(ans, curr)[0] = at(ans, curr)[0] - at(ans, next)[0] / at(deg, next);
  247.                     at(ans, curr)[1] = at(ans, curr)[1] - at(ans, next)[1] / at(deg, next);
  248.                     if (next == s) {
  249.                         at(ans, curr)[0].c = minus(at(ans, curr)[0].c, inverse(at(deg, s)));
  250.                     }
  251.                 }
  252.                 if (curr == s) {
  253.                     at(ans, curr)[0].c = minus(at(ans, curr)[0].c, inverse(at(deg, s)));
  254.                 }
  255.                 at(ans, curr)[0] = at(ans, curr)[0] * at(deg, curr);
  256.                 at(ans, curr)[1] = at(ans, curr)[1] * at(deg, curr);
  257.             }
  258.         }
  259.         ul eqtot = 0;
  260.         for (pulul curr(1, 1); curr.first <= n; ++curr.first) {
  261.             for (curr.second = 1; curr.second <= n; ++curr.second) {
  262.                 if (curr.first == n || at(ishole, curr + pulul(1, 0))) {
  263.                     ++eqtot;
  264.                     val_t tmp = at(ans, curr)[0];
  265.                     for (const auto& next : {curr + pulul(0, 1), curr + pulul(-1, 0), curr + pulul(0, -1)}) {
  266.                         if (next.first < 1 || next.second < 1 || next.second > n) {
  267.                             continue;
  268.                         }
  269.                         if (at(ishole, next)) {
  270.                             continue;
  271.                         }
  272.                         tmp = tmp - at(ans, next)[0] / at(deg, next);
  273.                         if (next == s) {
  274.                             tmp.c = minus(tmp.c, inverse(at(deg, s)));
  275.                         }
  276.                     }
  277.                     std::memcpy(a[eqtot] + 1, tmp.dx + 1, sizeof(ul) * tot);
  278.                     b[eqtot] = minus(0, tmp.c);
  279.                 }
  280.             }
  281.         }
  282.         solve(a, b, x);
  283.         eqtot = 0;
  284.         for (pulul curr(1, 1); curr.first <= n; ++curr.first) {
  285.             for (curr.second = 1; curr.second <= n; ++curr.second) {
  286.                 if (curr.first == n || at(ishole, curr + pulul(1, 0))) {
  287.                     ++eqtot;
  288.                     val_t tmp = at(ans, curr)[1] - at(ans, curr)[0];
  289.                     for (const auto& next : {curr + pulul(0, 1), curr + pulul(-1, 0), curr + pulul(0, -1)}) {
  290.                         if (next.first < 1 || next.second < 1 || next.second > n) {
  291.                             continue;
  292.                         }
  293.                         if (at(ishole, next)) {
  294.                             continue;
  295.                         }
  296.                         tmp = tmp - at(ans, next)[1] / at(deg, next);
  297.                     }
  298.                     std::memcpy(a[eqtot] + 1, tmp.dy + 1, sizeof(ul) * tot);
  299.                     b[eqtot] = minus(0, tmp.c);
  300.                     for (ul i = 1; i <= tot; ++i) {
  301.                         b[eqtot] = minus(b[eqtot], mul(x[i], tmp.dx[i]));
  302.                     }
  303.                 }
  304.             }
  305.         }
  306.         solve(a, b, y);
  307.         for (ul i = 1; i <= k; ++i) {
  308.             if (i != 1) {
  309.                 std::putchar(' ');
  310.             }
  311.             if (!x[i]) {
  312.                 std::printf("GG");
  313.             } else {
  314.                 std::printf("%u", mul(y[i], inverse(x[i])));
  315.             }
  316.         }
  317.         std::putchar('\n');
  318.     }
  319.     return 0;
  320. }

E、Observation

在正整数上是一个积性函数，证明见https://projecteuclid.org/download/pdf_1/euclid.bams/1183503695。 

  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 sp = 3162277;
  10. std::vector<ul> prime;
  12. std::vector<bool> notprime(sp + 1, false);
  14. ul T;
  16. const ul maxn = 1e6;
  18. ull f[maxn + 1];
  20. ull remain[maxn + 1];
  22. ull l, r, k, p;
  24. int main()
  25. {
  26.     for (ul i = 2; i <= sp; ++i) {
  27.         if (!notprime[i]) {
  28.             prime.push_back(i);
  29.         }
  30.         for (ul p : prime) {
  31.             if (p * i > sp) {
  32.                 break;
  33.             }
  34.             notprime[p * i] = true;
  35.             if (i % p == 0) {
  36.                 break;
  37.             }
  38.         }
  39.     }
  40.     std::scanf("%u", &T);
  41.     for (ul Case = 1; Case <= T; ++Case) {
  42.         std::scanf("%llu%llu%llu%llu", &l, &r, &k, &p);
  43.         ull ans = 0;
  44.         if (l == 0) {
  45.             ++l;
  46.             ans = (1 ^ k) % p;
  47.         }
  48.         for (ull i = l; i <= r; ++i) {
  49.             f[i - l + 1] = 6;
  50.             remain[i - l + 1] = i;
  51.         }
  52.         for (ull p : prime) {
  53.             if (p * p > r) {
  54.                 break;
  55.             }
  56.             for (ull t = (l + p - 1) / p * p; t <= r; t += p) {
  57.                 ull tmp = 1;
  58.                 while (remain[t - l + 1] % p == 0) {
  59.                     remain[t - l + 1] /= p;
  60.                     tmp *= p;
  61.                 }
  62.                 if (p == 2) {
  63.                     continue;
  64.                 }
  65.                 if (p & 2) {
  66.                     f[t - l + 1] *= tmp + 2 * (tmp - 1) / (p - 1);
  67.                 } else {
  68.                     f[t - l + 1] *= tmp;
  69.                 }
  70.             }
  71.         }
  72.         for (ull i = l; i <= r; ++i) {
  73.             if (remain[i - l + 1] != 1) {
  74.                 if (remain[i - l + 1] == 2) {
  75.                 } else if (remain[i - l + 1] & 2) {
  76.                     f[i - l + 1] *= remain[i - l + 1] + 2;
  77.                 } else {
  78.                     f[i - l + 1] *= remain[i - l + 1];
  79.                 }
  80.             }
  81.             ans = (ans + (f[i - l + 1] ^ k)) % p;
  82.         }
  83.         std::printf("%llu\n", ans);
  84.     }
  85.     return 0;
  86. }

F、Paper Grading

分治

  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 n, m;
  10. const ul maxn = 2e5;
  11. const ul maxm = 2e5;
  12. const ul maxlen = 2e5;
  14. char str[maxlen + 2];
  16. class node {
  17. public:
  18.     ul ch[26];
  19.     node() {
  20.         std::memset(ch, 0, sizeof(ch));
  21.     }
  22. };
  24. ul tot = 1;
  26. node tree[maxlen + 2];
  28. ul ptt[maxn + 1];
  30. ul dfn[maxlen + 2];
  31. ul bdfn[maxlen + 2];
  33. ul tim = 0;
  35. void search(ul curr) {
  36.     ++tim;
  37.     dfn[curr] = tim;
  38.     for (ul i = 0; i != 26; ++i) {
  39.         if (tree[curr].ch[i]) {
  40.             search(tree[curr].ch[i]);
  41.         }
  42.     }
  43.     bdfn[curr] = tim;
  44. }
  46. class data {
  47. public:
  48.     bool insert = false;
  49.     ul val = 0;
  50.     ul time = 0;
  51.     ul pos = 0;
  52.     ul dfn = 0;
  53. };
  55. ul ans[maxm + 1];
  57. data v[maxn + maxm * 4 + 1];
  59. ul stack1[maxn + maxm * 4 + 1];
  60. ul stack2[maxn + maxm * 4 + 1];
  61. ul stack3[maxn + maxm * 4 + 1];
  63. void solve3(ul l, ul r)
  64. {
  65.     if (v[stack3[l]].dfn == v[stack3[r]].dfn) {
  66.         return;
  67.     }
  68.     ul tmp = 0;
  69.     for (ul i = l, j = i; i <= r; i = j) {
  70.         for (j = i; j <= r && v[stack3[j]].dfn == v[stack3[i]].dfn; ++j) {
  71.             if (!v[stack3[j]].insert) {
  72.                 ans[v[stack3[j]].time] += v[stack3[j]].val * tmp;
  73.             }
  74.         }
  75.         for (j = i; j <= r && v[stack3[j]].dfn == v[stack3[i]].dfn; ++j) {
  76.             if (v[stack3[j]].insert) {
  77.                 tmp += v[stack3[j]].val;
  78.             }
  79.         }
  80.     }
  81. }
  83. void solve2(ul l, ul r)
  84. {
  85.     if (v[stack2[l]].pos == v[stack2[r]].pos) {
  86.         return;
  87.     }
  88.     ul midl, midr;
  89.     if ((l ^ r) & 1) {
  90.         midl = l + r >> 1;
  91.         midr = midl + 1;
  92.     } else {
  93.         midl = l + r >> 1;
  94.         midr = midl;
  95.     }
  96.     ul s = v[stack2[midl]].pos;
  97.     ul t = v[stack2[midr]].pos;
  98.     if (s == t) {
  99.         while (v[stack2[midl]].pos == s && v[stack2[midr]].pos == t) {
  100.             --midl;
  101.             ++midr;
  102.         }
  103.         if (v[stack2[midl]].pos != s) {
  104.             midr = midl + 1;
  105.         } else {
  106.             midl = midr - 1;
  107.         }
  108.     }
  109.     solve2(l, midl);
  110.     solve2(midr, r);
  111.     ul tot = 0;
  112.     bool flag = false;
  113.     for (ul i = l; i <= midl; ++i) {
  114.         if (v[stack2[i]].insert) {
  115.             ++tot;
  116.             stack3[tot] = stack2[i];
  117.             flag = true;
  118.         }
  119.     }
  120.     if (!flag) {
  121.         return;
  122.     }
  123.     flag = false;
  124.     for (ul i = midr; i <= r; ++i) {
  125.         if (!v[stack2[i]].insert) {
  126.             ++tot;
  127.             stack3[tot] = stack2[i];
  128.             flag = true;
  129.         }
  130.     }
  131.     if (!flag) {
  132.         return;
  133.     }
  134.     std::sort(stack3 + 1, stack3 + tot + 1, [](ul a, ul b){return v[a].dfn < v[b].dfn;});
  135.     solve3(1, tot);
  136. }
  138. void solve1(ul l, ul r)
  139. {
  140.     if (v[stack1[l]].time == v[stack1[r]].time) {
  141.         return;
  142.     }
  143.     ul midl, midr;
  144.     if ((l ^ r) & 1) {
  145.         midl = l + r >> 1;
  146.         midr = midl + 1;
  147.     } else {
  148.         midl = l + r >> 1;
  149.         midr = midl;
  150.     }
  151.     ul s = v[stack1[midl]].time;
  152.     ul t = v[stack1[midr]].time;
  153.     if (s == t) {
  154.         while (v[stack1[midl]].time == s && v[stack1[midr]].time == t) {
  155.             --midl;
  156.             ++midr;
  157.         }
  158.         if (v[stack1[midl]].time != s) {
  159.             midr = midl + 1;
  160.         } else {
  161.             midl = midr - 1;
  162.         }
  163.     }
  164.     solve1(l, midl);
  165.     solve1(midr, r);
  166.     ul tot = 0;
  167.     bool flag = false;
  168.     for (ul i = l; i <= midl; ++i) {
  169.         if (v[stack1[i]].insert) {
  170.             ++tot;
  171.             stack2[tot] = stack1[i];
  172.             flag = true;
  173.         }
  174.     }
  175.     if (!flag) {
  176.         return;
  177.     }
  178.     flag = false;
  179.     for (ul i = midr; i <= r; ++i) {
  180.         if (!v[stack1[i]].insert) {
  181.             ++tot;
  182.             stack2[tot] = stack1[i];
  183.             flag = true;
  184.         }
  185.     }
  186.     if (!flag) {
  187.         return;
  188.     }
  189.     std::sort(stack2 + 1, stack2 + tot + 1, [](ul a, ul b){return v[a].pos < v[b].pos;});
  190.     solve2(1, tot);
  191. }
  193. bool isquery[maxm + 1];
  195. int main()
  196. {
  197.     std::scanf("%u%u", &n, &m);
  198.     for (ul i = 1; i <= n; ++i) {
  199.         std::scanf("%s", str + 1);
  200.         ul curr = 1;
  201.         for (ul i = 1; str[i]; ++i) {
  202.             if (!tree[curr].ch[str[i] - 'a']) {
  203.                 ++tot;
  204.                 tree[curr].ch[str[i] - 'a'] = tot;
  205.             }
  206.             curr = tree[curr].ch[str[i] - 'a'];
  207.         }
  208.         ptt[i] = curr;
  209.     }
  210.     search(1);
  211.     tot = 0;
  212.     for (ul i = 1; i <= n; ++i) {
  213.         ++tot;
  214.         v[tot].insert = true;
  215.         v[tot].val = 1;
  216.         v[tot].time = 0;
  217.         v[tot].pos = i;
  218.         v[tot].dfn = dfn[ptt[i]];
  219.     };
  220.     for (ul t = 1; t <= m; ++t) {
  221.         ul opt;
  222.         std::scanf("%u", &opt);
  223.         if (opt == 1) {
  224.             ul i, j;
  225.             std::scanf("%u%u", &i, &j);
  226.             if (i == j) {
  227.                 continue;
  228.             }
  229.             ++tot;
  230.             v[tot].insert = true;
  231.             v[tot].val = -1;
  232.             v[tot].time = t;
  233.             v[tot].pos = i;
  234.             v[tot].dfn = dfn[ptt[i]];
  235.             ++tot;
  236.             v[tot].insert = true;
  237.             v[tot].val = -1;
  238.             v[tot].time = t;
  239.             v[tot].pos = j;
  240.             v[tot].dfn = dfn[ptt[j]];
  241.             std::swap(ptt[i], ptt[j]);
  242.             ++tot;
  243.             v[tot].insert = true;
  244.             v[tot].val = 1;
  245.             v[tot].time = t;
  246.             v[tot].pos = i;
  247.             v[tot].dfn = dfn[ptt[i]];
  248.             ++tot;
  249.             v[tot].insert = true;
  250.             v[tot].val = 1;
  251.             v[tot].time = t;
  252.             v[tot].pos = j;
  253.             v[tot].dfn = dfn[ptt[j]];
  254.         } else {
  255.             isquery[t] = true;
  256.             ul k, l, r;
  257.             std::scanf("%s%u%u%u", str + 1, &k, &l, &r);
  258.             ul len = std::strlen(str + 1);
  259.             if (k > len) {
  260.                 continue;
  261.             }
  262.             ul curr = 1;
  263.             bool flag = true;
  264.             for (ul i = 1; i <= k; ++i) {
  265.                 if (!tree[curr].ch[str[i] - 'a']) {
  266.                     flag = false;
  267.                     break;
  268.                 }
  269.                 curr = tree[curr].ch[str[i] - 'a'];
  270.             }
  271.             if (!flag) {
  272.                 continue;
  273.             }
  274.             ++tot;
  275.             v[tot].insert = false;
  276.             v[tot].val = 1;
  277.             v[tot].time = t;
  278.             v[tot].pos = r + 1;
  279.             v[tot].dfn = bdfn[curr] + 1;
  280.             ++tot;
  281.             v[tot].insert = false;
  282.             v[tot].val = -1;
  283.             v[tot].time = t;
  284.             v[tot].pos = l;
  285.             v[tot].dfn = bdfn[curr] + 1;
  286.             ++tot;
  287.             v[tot].insert = false;
  288.             v[tot].val = -1;
  289.             v[tot].time = t;
  290.             v[tot].pos = r + 1;
  291.             v[tot].dfn = dfn[curr];
  292.             ++tot;
  293.             v[tot].insert = false;
  294.             v[tot].val = 1;
  295.             v[tot].time = t;
  296.             v[tot].pos = l;
  297.             v[tot].dfn = dfn[curr];
  298.         }
  299.     }
  300.     for (ul i = 1; i <= tot; ++i) {
  301.         stack1[i] = i;
  302.     }
  303.     solve1(1, tot);
  304.     for (ul i = 1; i <= m; ++i) {
  305.         if (isquery[i]) {
  306.             std::printf("%u\n", ans[i]);
  307.         }
  308.     }
  309.     return 0;
  310. }

G、Poker Game

模拟。

  1. #pragma GCC target ("pclmul")
  2. #include <bits/stdc++.h>
  3. #include <emmintrin.h>
  4. #include <wmmintrin.h>
  6. using ul = std::uint32_t;
  7. using li = std::int32_t;
  8. using ull = std::uint64_t;
  9. using ll = std::int64_t;
  11. class card_t {
  12. public:
  13.     ul suit = 0;
  14.     ul number = 0;
  15.     ul id = 0;
  16.     card_t()=default;
  17.     card_t(ul x): suit((x + 12) / 13), number((x - 1) % 13 + 1), id(x) {}
  18. };
  20. ul T;
  22. card_t deck[16];
  24. ul potcnt[6] = {0, 100, 100, 100, 100, 100};
  26. card_t holecards[6][3];
  28. card_t communitycards[6];
  30. ul state[6];
  32. std::pair<ul, ul> getvalue(card_t v[])
  33. {
  34.     static std::pair<ul, ul> ret;
  35.     if (v[1].suit == v[2].suit && v[1].suit == v[3].suit && v[1].suit == v[4].suit && v[1].suit == v[5].suit) {
  36.         ret.first = 5;
  37.         ret.second = v[5].number;
  38.         if (v[1].number == 1) {
  39.             ret.second = 14;
  40.         }
  41.     } else if (v[1].number + 1 == v[2].number && v[2].number + 1 == v[3].number && v[3].number + 1 == v[4].number && v[4].number + 1 == v[5].number || v[1].number == 1 && v[2].number == 10 && v[3].number == 11 && v[4].number == 12 && v[5].number == 13) {
  42.         ret.first = 4;
  43.         ret.second = v[5].number;
  44.         if (v[1].number == 1 && v[5].number == 13) {
  45.             ret.second = 14;
  46.         }
  47.     } else if (v[1].number == v[3].number || v[2].number == v[4].number || v[3].number == v[5].number) {
  48.         ret.first = 3;
  49.         for (ul i = 5; i >= 3; --i) {
  50.             if (v[i].number == v[i - 2].number) {
  51.                 ret.second = v[i].number;
  52.                 break;
  53.             }
  54.         }
  55.         if (v[1].number == v[3].number && v[1].number == 1) {
  56.             ret.second = 14;
  57.         }
  58.     } else if (v[1].number == v[2].number || v[2].number == v[3].number || v[3].number == v[4].number || v[4].number == v[5].number) {
  59.         ret.first = 2;
  60.         for (ul i = 5; i >= 2; --i) {
  61.             if (v[i].number == v[i - 1].number) {
  62.                 ret.second = v[i].number;
  63.                 break;
  64.             }
  65.         }
  66.         if (v[1].number == v[2].number && v[1].number == 1) {
  67.             ret.second = 14;
  68.         }
  69.     } else {
  70.         ret.first = 1;
  71.         ret.second = v[5].number;
  72.         if (v[1].number == 1) {
  73.             ret.second = 14;
  74.         }
  75.     }
  76.     return ret;
  77. }
  79. std::vector<std::pair<ull, std::pair<ul, ul>>> map;
  81. std::vector<std::pair<ull, std::pair<ul, ul>>>::iterator find(ull x)
  82. {
  83.     auto it = std::lower_bound(map.begin(), map.end(), std::pair<ull, std::pair<ul, ul>>(x, std::pair<ul, ul>(0, 0)));
  84.     if (it == map.end() || it->first != x) {
  85.         return map.end();
  86.     } else {
  87.         return it;
  88.     }
  89. }
  91. const std::pair<ul, ul>& at(ull x)
  92. {
  93.     return find(x)->second;
  94. }
  96. ull base;
  98. inline ull gfmul(ull a, ull b)
  99. {
  100.     auto vc = _mm_clmulepi64_si128(_mm_cvtsi64_si128(a), _mm_cvtsi64_si128(b), 0);
  101.     auto vf = _mm_xor_si128(_mm_cvtsi64_si128(_mm_cvtsi128_si64(vc)), _mm_clmulepi64_si128(_mm_srli_si128(vc, 8), _mm_cvtsi64_si128(27ull), 0));
  102.     return _mm_cvtsi128_si64(_mm_xor_si128(_mm_cvtsi64_si128(_mm_cvtsi128_si64(vf)), _mm_clmulepi64_si128(_mm_srli_si128(vf, 8), _mm_cvtsi64_si128(27ull), 0)));
  103. }
  105. std::mt19937_64 rnd;
  107. card_t v1[6];
  108. card_t v2[6];
  109. ul v3[8];
  111. std::pair<ul, ul> ans[6];
  113. void getans(ul x)
  114. {
  115.     for (ul i = 1; i <= 5; ++i) {
  116.         v3[i] = communitycards[i].id;
  117.     }
  118.     for (ul i = 1; i <= 2; ++i) {
  119.         v3[i + 5] = holecards[x][i].id;
  120.     }
  121.     ans[x] = std::pair<ul, ul>(0, 0);
  122.     for (ul i = 1; i + 1 <= 7; ++i) {
  123.         for (ul j = i + 1; j <= 7; ++j) {
  124.             ull hash = 1;
  125.             for (ul k = 1; k <= 7; ++k) {
  126.                 if (k != i && k != j) {
  127.                     hash = gfmul(hash, base ^ v3[k]);
  128.                 }
  129.             }
  130.             ans[x] = std::max(ans[x], at(hash));
  131.         }
  132.     }
  133. }
  135. ul ord[53];
  137. int main()
  138. {
  139.     for (ul i = 1; i <= 52; ++i) {
  140.         ord[i] = i;
  141.     }
  142.     std::sort(ord + 1, ord + 53, [](ul a, ul b){return (a - 1) % 13 < (b - 1) % 13;});
  143.     rnd.seed(std::time(0));
  144.     base = rnd();
  145.     for (ul a1 = 1; a1 + 4 <= 52; ++a1) {
  146.         ull hash1 = base ^ ord[a1];
  147.         v1[1] = ord[a1];
  148.         for (ul a2 = a1 + 1; a2 + 3 <= 52; ++a2) {
  149.             ull hash2 = gfmul(hash1, base ^ ord[a2]);
  150.             v1[2] = ord[a2];
  151.             for (ul a3 = a2 + 1; a3 + 2 <= 52; ++a3) {
  152.                 ull hash3 = gfmul(hash2, base ^ ord[a3]);
  153.                 v1[3] = ord[a3];
  154.                 for (ul a4 = a3 + 1; a4 + 1 <= 52; ++a4) {
  155.                     ull hash4 = gfmul(hash3, base ^ ord[a4]);
  156.                     v1[4] = ord[a4];
  157.                     for (ul a5 = a4 + 1; a5 <= 52; ++a5) {
  158.                         ull hash5 = gfmul(hash4, base ^ ord[a5]);
  159.                         v1[5] = ord[a5];
  160.                         map.push_back(std::pair<ull, std::pair<ul, ul>>(hash5, getvalue(v1)));
  161.                     }
  162.                 }
  163.             }
  164.         }
  165.     }
  166.     std::sort(map.begin(), map.end());
  167.     std::scanf("%u", &T);
  168.     for (ul Case = 1; Case <= T; ++Case) {
  169.         ul tot = 0;
  170.         for (ul i = 1; i <= 15; ++i) {
  171.             ul tmp;
  172.             std::scanf("%u", &tmp);
  173.             deck[i] = tmp;
  174.         }
  175.         ul alive = 0;
  176.         ul last = 0;
  177.         for (ul i = 1; i <= 5; ++i) {
  178.             if (potcnt[i]) {
  179.                 ++alive;
  180.                 ++tot;
  181.                 holecards[i][1] = deck[tot];
  182.                 ++tot;
  183.                 holecards[i][2] = deck[tot];
  184.             }
  185.         }
  186.         std::memset(state, 0, sizeof(state));
  187.         if (potcnt[1] > 0) {
  188.             if (potcnt[1] >= 15 && holecards[1][1].suit == holecards[1][2].suit) {
  189.                 state[1] = 1;
  190.             } else {
  191.                 last = 1;
  192.                 --alive;
  193.             }
  194.         }
  195.         if (potcnt[2] > 0) {
  196.             if (potcnt[2] >= 15) {
  197.                 state[2] = 1;
  198.             } else if (holecards[2][1].number == 1 && holecards[2][2].number == 1) {
  199.                 state[2] = 3;
  200.             } else {
  201.                 last = 2;
  202.                 --alive;
  203.             }
  204.         }
  205.         if (potcnt[3] > 0) {
  206.             if (holecards[3][1].number == 1 || holecards[3][2].number == 1 || std::max(holecards[3][1].number, holecards[3][2].number) - std::min(holecards[3][1].number, holecards[3][2].number) < 3) {
  207.                 state[3] = 1 + ul(potcnt[3] < 15) * 2;
  208.             } else {
  209.                 last = 3;
  210.                 --alive;
  211.             }
  212.         }
  213.         if (potcnt[4] > 0) {
  214.             if (holecards[4][1].number > 11 || holecards[4][1].number == 1 || holecards[4][2].number > 11 || holecards[4][2].number == 1) {
  215.                 state[4] = 1 + ul(potcnt[4] < 15) * 2;
  216.             } else {
  217.                 last = 4;
  218.                 --alive;
  219.             }
  220.         }
  221.         if (potcnt[5] > 0) {
  222.             if (ul(state[1] != 0) + ul(state[2] != 0) + ul(state[3] != 0) + ul(state[4] != 0) == 1) {
  223.                 state[5] = 1 + ul(potcnt[5] < 15) * 2;
  224.             } else {
  225.                 last = 5;
  226.                 --alive;
  227.             }
  228.         }
  229.         for (ul i = 1; i <= 3; ++i) {
  230.             ++tot;
  231.             communitycards[i] = deck[tot];
  232.         }
  233.         if (state[1] == 1) {
  234.             state[1] = 2;
  235.         }
  236.         if (state[2] == 1) {
  237.             ull hashcurr = 1;
  238.             for (ul i = 1; i <= 3; ++i) {
  239.                 hashcurr = gfmul(hashcurr, base ^ communitycards[i].id);
  240.                 v1[i] = communitycards[i];
  241.             }
  242.             for (ul i = 1; i <= 2; ++i) {
  243.                 hashcurr = gfmul(hashcurr, base ^ holecards[2][i].id);
  244.                 v1[i + 3] = holecards[2][i];
  245.             }
  246.             if (at(hashcurr).first >= 2) {
  247.                 state[2] = 2;
  248.             } else {
  249.                 for (ul i = 1; i <= 5 && state[2] != 2; ++i) {
  250.                     ull hashcurr = 1;
  251.                     for (ul j = 1; j <= 5; ++j) {
  252.                         if (j != i) {
  253.                             hashcurr = gfmul(hashcurr, base ^ v1[j].id);
  254.                         }
  255.                     }
  256.                     for (ul t = 1; t <= 52; ++t) {
  257.                         ull hash = gfmul(hashcurr, base ^ t);
  258.                         auto it = find(hash);
  259.                         if (it != map.end() && it->second.first >= 4) {
  260.                             state[2] = 2;
  261.                             break;
  262.                         }
  263.                     }
  264.                 }
  265.             }
  266.             if (state[2] != 2) {
  267.                 --alive;
  268.                 last = 2;
  269.             }
  270.         }
  271.         if (state[3] == 1) {
  272.             bool flag = true;
  273.             for (ul i = 1; i <= 3; ++i) {
  274.                 ul j = i + 1;
  275.                 if (j == 4) {
  276.                     j = 1;
  277.                 }
  278.                 if (communitycards[i].number == communitycards[j].number) {
  279.                     ul t = communitycards[i].number;
  280.                     bool flag2 = false;
  281.                     for (ul i = 1; i <= 2; ++i) {
  282.                         if (holecards[3][i].number == t) {
  283.                             flag2 = true;
  284.                             break;
  285.                         }
  286.                     }
  287.                     if (!flag2) {
  288.                         flag = false;
  289.                         break;
  290.                     }
  291.                 }
  292.             }
  293.             if (flag) {
  294.                 state[3] = 2;
  295.             } else {
  296.                 --alive;
  297.                 last = 3;
  298.             }
  299.         }
  300.         if (state[4] == 1) {
  301.             ul maxcom = 0;
  302.             for (ul i = 1; i <= 3; ++i) {
  303.                 if (communitycards[i].number == 1) {
  304.                     maxcom = 14;
  305.                     break;
  306.                 }
  307.                 maxcom = std::max(maxcom, communitycards[i].number);
  308.             }
  309.             ul maxhole = 0;
  310.             for (ul i = 1; i <= 2; ++i) {
  311.                 if (holecards[4][i].number == 1) {
  312.                     maxhole = 14;
  313.                     break;
  314.                 }
  315.                 maxhole = std::max(maxhole, holecards[4][i].number);
  316.             }
  317.             if (maxhole >= maxcom) {
  318.                 state[4] = 2;
  319.             } else {
  320.                 --alive;
  321.                 last = 4;
  322.             }
  323.         }
  324.         if (state[5] == 1) {
  325.             state[5] = 2;
  326.         }
  327.         for (ul i = 4; i <= 5; ++i) {
  328.             ++tot;
  329.             communitycards[i] = deck[tot];
  330.         }
  331.         if (state[1] == 2) {
  332.             getans(1);
  333.             if (ans[1].first >= 2) {
  334.                 state[1] = 3;
  335.             } else {
  336.                 --alive;
  337.                 last = 1;
  338.             }
  339.         }
  340.         if (state[2] == 2) {
  341.             bool flag = false;
  342.             for (ul i = 1; i <= 5; ++i) {
  343.                 ul t = communitycards[1].suit;
  344.                 if (i == 1) {
  345.                     t = communitycards[2].suit;
  346.                 }
  347.                 bool flag2 = true;
  348.                 for (ul j = 1; j <= 5; ++j) {
  349.                     if (j == i) {
  350.                         continue;
  351.                     }
  352.                     if (communitycards[j].suit != t) {
  353.                         flag2 = false;
  354.                         break;
  355.                     }
  356.                 }
  357.                 if (flag2) {
  358.                     flag = true;
  359.                     break;
  360.                 }
  361.             }
  362.             if (!flag) {
  363.                 state[2] = 3;
  364.             } else {
  365.                 --alive;
  366.                 last = 2;
  367.             }
  368.         }
  369.         if (state[3] == 2) {
  370.             state[3] = 3;
  371.         }
  372.         if (state[4] == 2) {
  373.             getans(4);
  374.             if (ans[4].first >= 3) {
  375.                 state[4] = 3;
  376.             } else if (ans[4].first >= 2) {
  377.                 std::sort(communitycards + 1, communitycards + 6, [](const card_t& a, const card_t& b){return (a.number == 1) != (b.number == 1) ? b.number == 1 : a.number < b.number;});
  378.                 if (ans[4].second > communitycards[3].number && communitycards[3].number != 1) {
  379.                     state[4] = 3;
  380.                 }
  381.             }
  382.             if (state[4] != 3) {
  383.                 --alive;
  384.                 last = 4;
  385.             }
  386.         }
  387.         if (state[5] == 2) {
  388.             state[5] = 3;
  389.         }
  390.         std::pair<ul, ul> winval(0, 0);
  391.         ul winner = 0;
  392.         if (alive == 0) {
  393.             winner = last;
  394.         }
  395.         for (ul i = 1; i <= 5; ++i) {
  396.             if (state[i] == 3) {
  397.                 getans(i);
  398.                 if (winval <= ans[i]) {
  399.                     winval = ans[i];
  400.                     winner = i;
  401.                 }
  402.             }
  403.         }
  404.         if (winner) {
  405.             ul sum = 0;
  406.             for (ul i = 1; i <= 5; ++i) {
  407.                 if (i != winner) {
  408.                     sum += std::min(potcnt[i], 5 * state[i]);
  409.                     potcnt[i] -= std::min(potcnt[i], 5 * state[i]);
  410.                 }
  411.             }
  412.             potcnt[winner] += sum;
  413.         }
  414.     }
  415.     for (ul i = 1; i <= 5; ++i) {
  416.         std::printf("%u\n", potcnt[i]);
  417.     }
  418.     return 0;
  419. }

H、Prince and Princess

我一直没搞懂这种题要严格证明最优性该从哪里入手。
策略是：如果只有公主一人，什么都不用问，如果支持者多于其他人，则挨着一直问公主在哪，问次，一定有一个答案出现了至少次，就是答案。

  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 a, b, c;
  10. int main()
  11. {
  12.     std::scanf("%u%u%u", &a, &b, &c);
  13.     if (a == 1 && b == 0 && c == 0) {
  14.         std::printf("YES\n0\n");
  15.     } else if (a <= b + c) {
  16.         std::printf("NO\n");
  17.     } else {
  18.         std::printf("YES\n%u\n", (b + c << 1) + 1);
  19.     }
  20.     return 0;
  21. }

I、Space Station

注意和属于的不降正整数列一共只有个，于是可以记忆化搜索。用的是来哈希，用会撞哈希。

  1. #pragma GCC target ("pclmul")
  2. #include <bits/stdc++.h>
  3. #include <emmintrin.h>
  4. #include <wmmintrin.h>
  6. using ul = std::uint32_t;
  7. using li = std::int32_t;
  8. using ull = std::uint64_t;
  9. using ll = std::int64_t;
  11. const ul mod = 1e9 + 7;
  13. ul plus(ul a, ul b)
  14. {
  15.     return a + b < mod ? a + b : a + b - mod;
  16. }
  18. ul mul(ul a, ul b)
  19. {
  20.     return ull(a) * ull(b) % mod;
  21. }
  23. void exgcd(li a, li b, li& x, li& y)
  24. {
  25.     if (b) {
  26.         exgcd(b, a % b, y, x);
  27.         y -= a / b * x;
  28.     } else {
  29.         x = 1;
  30.         y = 0;
  31.     }
  32. }
  34. ul inverse(ul a)
  35. {
  36.     li x, y;
  37.     exgcd(a, mod, x, y);
  38.     return x < 0 ? x + li(mod) : x;
  39. }
  41. inline ull gfmul(ull a, ull b)
  42. {
  43.     auto vc = _mm_clmulepi64_si128(_mm_cvtsi64_si128(a), _mm_cvtsi64_si128(b), 0);
  44.     auto vf = _mm_xor_si128(_mm_cvtsi64_si128(_mm_cvtsi128_si64(vc)), _mm_clmulepi64_si128(_mm_srli_si128(vc, 8), _mm_cvtsi64_si128(27ull), 0));
  45.     return _mm_cvtsi128_si64(_mm_xor_si128(_mm_cvtsi64_si128(_mm_cvtsi128_si64(vf)), _mm_clmulepi64_si128(_mm_srli_si128(vf, 8), _mm_cvtsi64_si128(27ull), 0)));
  46. }
  48. ul n;
  50. ul cnt[51];
  52. std::unordered_map<ull, ul> ans;
  54. ull base;
  56. const ul maxn = 1e5;
  58. ul fac[maxn + 1];
  59. ul fiv[maxn + 1];
  61. ull hash = 1;
  63. ul sum;
  65. ul remain;
  67. ul search()
  68. {
  69.     if (sum >= 50 || !remain) {
  70.         return fac[remain];
  71.     }
  72.     auto it = ans.find(hash);
  73.     if (it != ans.end()) {
  74.         return it->second;
  75.     }
  76.     ul tmp = 0;
  77.     for (ul i = 1; i <= sum; ++i) {
  78.         if (!cnt[i]) {
  79.             continue;
  80.         }
  81.         --cnt[i];
  82.         sum += i;
  83.         --remain;
  84.         ull chash = hash;
  85.         hash = gfmul(hash, base ^ i);
  86.         ul t = search();
  87.         ++cnt[i];
  88.         sum -= i;
  89.         ++remain;
  90.         hash = chash;
  91.         tmp = plus(tmp, mul(cnt[i], t));
  92.     }
  93.     ans[hash] = tmp;
  94.     return tmp;
  95. }
  97. std::mt19937_64 rnd;
  99. int main()
  100. {
  101.     rnd.seed(std::time(0));
  102.     base = rnd();
  103.     fac[0] = 1;
  104.     for (ul i = 1; i <= maxn; ++i) {
  105.         fac[i] = mul(fac[i - 1], i);
  106.     }
  107.     fiv[maxn] = inverse(fac[maxn]);
  108.     for (ul i = maxn; i >= 1; --i) {
  109.         fiv[i - 1] = mul(fiv[i], i);
  110.     }
  111.     std::scanf("%u", &n);
  112.     std::scanf("%u", &sum);
  113.     for (ul i = 1; i <= n; ++i) {
  114.         ul a;
  115.         std::scanf("%u", &a);
  116.         ++cnt[a];
  117.         if (a) {
  118.             ++remain;
  119.         }
  120.     }
  121.     ul tmp = search();
  122.     std::printf("%u\n", mul(tmp, mul(fac[n], fiv[remain])));
  123.     return 0;
  124. }

J、Spy

关于最小权匹配的算法：https://www.zybuluo.com/qq290637843/note/1774018。

  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. using pllul = std::pair<ll, ul>;
  10. ul n;
  12. const ul maxn = 400;
  14. ll a[maxn + 1];
  16. ul p[maxn + 1];
  18. ll b[maxn + 1];
  20. ll c[maxn + 1];
  22. ul ord[maxn + 1];
  24. std::vector<pllul> sum;
  26. const ll inf = ll(2e18) + 1;
  28. ll w[maxn + 1][maxn + 1];
  30. ul x[maxn + 1];
  31. ul y[maxn + 1];
  33. void lapjv(ul n, const ll c[][maxn + 1], ul x[maxn + 1], ul y[maxn + 1])
  34. {
  35.     static ll u[maxn + 1];
  36.     static ll v[maxn + 1];
  37.     static ll d[maxn + 1];
  38.     static ul pred[maxn + 1];
  39.     static bool vis[maxn + 1];
  40.     std::memset(u + 1, 0, sizeof(ll) * n);
  41.     std::memset(x + 1, 0, sizeof(ul) * n);
  42.     std::memset(y + 1, 0, sizeof(ul) * n);
  43.     for (ul j = 1; j <= n; ++j) {
  44.         v[j] = 0;
  45.         for (ul i = 1; i <= n; ++i) {
  46.             v[j] = std::min(v[j], c[i][j]);
  47.         }
  48.     }
  49.     for (ul istar = 1; istar <= n; ++istar) {
  50.         for (ul j = 1; j <= n; ++j) {
  51.             d[j] = c[istar][j] - u[istar] - v[j];
  52.             pred[j] = istar;
  53.             vis[j] = false;
  54.         }
  55.         ul endj;
  56.         ll mu;
  57.         while (true) {
  58.             ul jstar;
  59.             mu = inf;
  60.             for (ul j = 1; j <= n; ++j) {
  61.                 if (!vis[j] && mu > d[j])  {
  62.                     jstar = j;
  63.                     mu = d[j];
  64.                 }
  65.             }
  66.             if (!y[jstar]) {
  67.                 endj = jstar;
  68.                 break;
  69.             }
  70.             vis[jstar] = true;
  71.             ul i = y[jstar];
  72.             for (ul j = 1; j <= n; ++j) {
  73.                 if (mu + c[i][j] - u[i] - v[j] < d[j]) {
  74.                     d[j] = mu + c[i][j] - u[i] - v[j];
  75.                     pred[j] = i;
  76.                 }
  77.             }
  78.         }
  79.         for (ul k = 1; k <= n; ++k) {
  80.             if (d[k] < mu) {
  81.                 v[k] -= mu - d[k];
  82.             }
  83.         }
  84.         ul j = endj;
  85.         while (true) {
  86.             ul i = pred[j];
  87.             y[j] = i;
  88.             std::swap(j, x[i]);
  89.             if (i == istar) {
  90.                 break;
  91.             }
  92.         }
  93.         for (ul i = 1; i <= istar; ++i) {
  94.             u[i] = c[i][x[i]] - v[x[i]];
  95.         }
  96.     }
  97. }
  99. int main()
  100. {
  101.     std::scanf("%u", &n);
  102.     for (ul i = 1; i <= n; ++i) {
  103.         std::scanf("%lld", &a[i]);
  104.         ord[i] = i;
  105.     }
  106.     for (ul i = 1; i <= n; ++i) {
  107.         std::scanf("%lld", &p[i]);
  108.     }
  109.     std::sort(ord + 1, ord + n + 1, [](ul x, ul y){return a[x] < a[y];});
  110.     sum.push_back(pllul(-inf, 0));
  111.     for (ul i = 1; i <= n; ++i) {
  112.         if (a[ord[i]] != sum.back().first) {
  113.             sum.push_back(pllul(a[ord[i]], sum.back().second));
  114.         }
  115.         sum.back().second += p[ord[i]];
  116.     }
  117.     for (ul i = 1; i <= n; ++i) {
  118.         std::scanf("%lld", &b[i]);
  119.     }
  120.     for (ul i = 1; i <= n; ++i) {
  121.         std::scanf("%lld", &c[i]);
  122.     }
  123.     for (ul i = 1; i <= n; ++i) {
  124.         for (ul j = 1; j <= n; ++j) {
  125.             w[i][j] = -ll(std::prev(std::lower_bound(sum.begin(), sum.end(), pllul(b[i] + c[j], 0)))->second);
  126.         }
  127.     }
  128.     lapjv(n, w, x, y);
  129.     ll ans = 0;
  130.     for (ul i = 1; i <= n; ++i) {
  131.         ans -= w[i][x[i]];
  132.     }
  133.     std::printf("%lld\n", ans);
  134.     return 0;
  135. }

K、Triangle

简单题

  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. using lf = double;
  10. class vec {
  11. public:
  12.     lf x = 0;
  13.     lf y = 0;
  14.     vec()=default;
  15.     vec(lf x, lf y): x(x), y(y) {}
  16. };
  18. vec operator+(const vec& a, const vec& b)
  19. {
  20.     return vec(a.x + b.x, a.y + b.y);
  21. }
  23. vec operator-(const vec& a, const vec& b)
  24. {
  25.     return vec(a.x - b.x, a.y - b.y);
  26. }
  28. lf operator*(const vec& a, const vec& b)
  29. {
  30.     return a.x * b.x + a.y * b.y;
  31. }
  33. lf operator^(const vec& a, const vec& b)
  34. {
  35.     return a.x * b.y - a.y * b.x;
  36. }
  38. vec operator*(lf a, const vec& b)
  39. {
  40.     return vec(a * b.x, a * b.y);
  41. }
  43. ul T;
  45. vec a, b, c, p, q;
  47. int main()
  48. {
  49.     std::scanf("%u", &T);
  50.     for (ul Case = 1; Case <= T; ++Case) {
  51.         std::scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y, &p.x, &p.y);
  52.         if (!(a - p ^ b - p) && (a - p) * (b - p) <= 0) {
  53.         } else if (!(a - p ^ c - p) && (a - p) * (b - p) <= 0) {
  54.             std::swap(b, c);
  55.         } else if (!(b - p ^ c - p) && (b - p) * (c - p) <= 0) {
  56.             std::swap(a, b);
  57.         } else {
  58.             std::printf("-1\n");
  59.             continue;
  60.         }
  61.         if ((a - c ^ b - c) < 0) {
  62.             std::swap(a, b);
  63.         }
  64.         lf s = a - c ^ p - c;
  65.         lf t = p - c ^ b - c;
  66.         if (s == t) {
  67.             q = c;
  68.         } else if (s < t) {
  69.             q = lf(0.5) * (s + t) / (c - b ^ p - b) * (c - b) + b;
  70.         } else {
  71.             q = lf(0.5) * (s + t) / (p - a ^ c - a) * (c - a) + a;
  72.         }
  73.         std::printf("%.20lf %.20lf\n", q.x, q.y);
  74.     }
  75.     return 0;
  76. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注