[关闭]
@qq290637843 2022-04-08T08:43:50.000000Z 字数 34546 阅读 384

2019徐州

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

A、Cat

首先由于对任何，

这说明要买的集合一定可以表示为一些严格分开的区间的并，其中每个区间都一次性买下。
现在注意对任何，，所以对任何连续区间，可以求出其异或值。
如果的异或值小于等于，那么可以一次性买下，故只考虑其余情况。
现在默认。
如果，那么由于，于是乎至多从首尾两个元素，一定能让异或值小于等于，故只需要分析是否能只损失一个：
①偶奇：异或值一开始就小于等于，不在此考虑范围内。
②偶偶：异或值小于等于。
③奇奇：异或值小于等于。
④奇偶：首先注意到，的异或值为或，总之小于等于。现在考虑其他可能性：如果删掉一个奇数，则结果为或再加上左边那段的异或值，总之大于等于，所以肯定不是最优的；而如果删掉一个偶数，则结果为或再加上右边那段的异或值，而右边那段一定是左奇右偶的形式，除非删掉的就是，否则右边那段的异或值一定大于等于，这说明不会比直接删价格更小。
如果，注意非空区间中，除了，只有形如左偶右奇且长为的倍数的区间的异或值才为，于是：
①偶奇：如果长为的倍数则无损失，如果长为，则损失任何一侧的两个都行。
②偶偶：如果长为，则损失右侧三个即可，如果长为，则损失右侧一个即可。
③奇奇：如果，如果长为，则损失左侧三个即可，如果长为，则损失左侧一个即可；如果，如果为，则无损失，如果为，则损失左侧一个即可。
④奇偶：如果，如果长为，则损失左右各一个，再损失任何一侧的两个，如果长为，则损失左右各一个；如果，如果为，则损失右侧一个，如果为，则左右各损失一个。

  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. ull l, r, s;
  12. int main()
  13. {
  14.     std::scanf("%u", &T);
  15.     for (ul Case = 1; Case <= T; ++Case) {
  16.         std::scanf("%llu%llu%llu", &l, &r, &s);
  17.         ull ans;
  18.         ull len = r - l + 1;
  19.         if (r - l + 1 == 1) {
  20.             if (s >= l) {
  21.                 ans = len;
  22.             } else {
  23.                 ans = len - 1;
  24.             }
  25.         } else {
  26.             if (((~r & 1) * r ^ (l & 1) * l ^ (len - (~r & 1) - (l & 1) >> 1 & 1)) <= s) {
  27.                 ans = len;
  28.             } else {
  29.                 if (s >= 1) {
  30.                     if (l & 1) {
  31.                         if (r & 1) {
  32.                             ans = len - 1;
  33.                         } else {
  34.                             ans = (l ^ (len - 2 >> 1 & 1)) <= s ? len - 1 : len - 2;
  35.                         }
  36.                     } else {
  37.                         if (r & 1) {
  38.                             ans = len;
  39.                         } else {
  40.                             ans = len - 1;
  41.                         }
  42.                     }
  43.                 } else {
  44.                     if (l & 1) {
  45.                         if (r & 1) {
  46.                             if ((len & 3) == 3) {
  47.                                 if (l == 1) {
  48.                                     ans = len;
  49.                                 } else {
  50.                                     ans = len - 3;
  51.                                 }
  52.                             } else {
  53.                                 ans = len - 1;
  54.                             }
  55.                         } else {
  56.                             if ((len & 3) == 0) {
  57.                                 if (l == 1) {
  58.                                     ans = len - 1;
  59.                                 } else {
  60.                                     ans = len - 4;
  61.                                 }
  62.                             } else {
  63.                                 ans = len - 2;
  64.                             }
  65.                         }
  66.                     } else {
  67.                         if (r & 1) {
  68.                             if ((len & 3) == 0) {
  69.                                 ans = len;
  70.                             } else {
  71.                                 ans = len - 2;
  72.                             }
  73.                         } else {
  74.                             if ((len & 3) == 3) {
  75.                                 ans = len - 3;
  76.                             } else {
  77.                                 ans = len - 1;
  78.                             }
  79.                         }
  80.                     }
  81.                 }
  82.             }
  83.         }
  84.         if (ans) {
  85.             std::printf("%llu\n", ans);
  86.         } else {
  87.             std::printf("-1\n");
  88.         }
  89.     }
  90.     return 0;
  91. }

B、Cats line up

换成另一个描述：求如下图的有向哈密顿路的个数，点被编号为，其中两点之间有边当且仅当。于是可以状态压缩动态规划，由此可知固定时，此关于为线性递推数列。所以可以先算出一些前项然后伯莱坎普梅西。

  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. inline ull gfmul(ull a, ull b)
  12. {
  13.     auto vc = _mm_clmulepi64_si128(_mm_cvtsi64_si128(a), _mm_cvtsi64_si128(b), 0);
  14.     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));
  15.     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)));
  16. }
  18. ull X, Y;
  20. std::mt19937_64 rnd;
  22. ull gethash(const std::vector<ul>& v)
  23. {
  24.     ull ret = 1;
  25.     for (ul i = 0; i != v.size(); i += 2) {
  26.         ret = gfmul(ret, Y ^ gfmul(X ^ v[i], X ^ v[i + 1]));
  27.     }
  28.     return ret;
  29. }
  31. const ul mod = 998244353;
  33. ul plus(ul a, ul b)
  34. {
  35.     return a + b < mod ? a + b : a + b - mod;
  36. }
  38. ul minus(ul a, ul b)
  39. {
  40.     return a < b ? a + mod - b : a - b;
  41. }
  43. ul mul(ul a, ul b)
  44. {
  45.     return ull(a) * ull(b) % mod;
  46. }
  48. void exgcd(li a, li b, li& x, li& y)
  49. {
  50.     if (b) {
  51.         exgcd(b, a % b, y, x);
  52.         y -= a / b * x;
  53.     } else {
  54.         x = 1;
  55.         y = 0;
  56.     }
  57. }
  59. ul inverse(ul a)
  60. {
  61.     li x, y;
  62.     exgcd(a, mod, x, y);
  63.     return x < 0 ? x + li(mod) : x;
  64. }
  66. class counter {
  67. public:
  68.     std::vector<ul> v;
  69.     ul cnt = 0;
  70.     counter()=default;
  71.     counter(const std::vector<ul>& a, ul b): v(a), cnt(b) {}
  72.     counter(std::vector<ul>&& a, ul b): v(std::move(a)), cnt(b) {}
  73. };
  75. const ul maxn2 = 1e6;
  76. const ul maxn = 100;
  77. const ul maxk = 3;
  79. std::unordered_map<ull, counter> map[maxn + 1]; 
  81. void regular(std::vector<ul>& v, ul n, ul k)
  82. {
  83.     for (ul i = 0; i != v.size(); ++i) {
  84.         if (v[i] + k <= n) {
  85.             v[i] = 0;
  86.         }
  87.     }
  88. }
  90. std::vector<ul> nextcon;
  92. bool check(std::vector<ul>& v)
  93. {
  94.     ul cnt = 0;
  95.     for (ul u : v) {
  96.         if (!u) {
  97.             ++cnt;
  98.             if (cnt == 3) {
  99.                 return false;
  100.             }
  101.         }
  102.     }
  103.     return true;
  104. }
  106. ul ans[maxk + 1][maxn2 + 1];
  108. ul bm(const ul s[], ul cc[], ul nn)
  109. {
  110.     static ul bb[1000];
  111.     static ul tt[1000];
  112.     cc[0] = 1;
  113.     bb[0] = 1;
  114.     ul tl;
  115.     ul bl = 0;
  116.     ul l = 0;
  117.     ul m = 1;
  118.     ul b = 1;
  119.     for (ul n = 0; n != nn; ++n) {
  120.         ul d = 0;
  121.         for (ul i = 0; i <= l; ++i) {
  122.             d = plus(d, mul(cc[i], s[n - i]));
  123.         }
  124.         if (d == 0) {
  125.             ++m;
  126.         } else if (l + l <= n) {
  127.             std::memcpy(tt, cc, sizeof(ul) * (l + 1));
  128.             tl = l;
  129.             std::memset(&cc[l + 1], 0, sizeof(ul) * (n - l - l + 1));
  130.             l = n + 1 - l;
  131.             ul lambda = mul(inverse(b), d);
  132.             for (ul i = 0; i <= bl; ++i) {
  133.                 cc[i + m] = minus(cc[i + m], mul(lambda, bb[i]));
  134.             }
  135.             bl = tl;
  136.             std::memcpy(bb, tt, sizeof(ul) * (bl + 1));
  137.             b = d;
  138.             m = 1;
  139.         } else {
  140.             ul lambda = mul(inverse(b), d);
  141.             for (ul i = 0; i <= bl; ++i) {
  142.                 cc[i + m] = minus(cc[i + m], mul(lambda, bb[i]));
  143.             }
  144.             ++m;
  145.         }
  146.     }
  147.     return l;
  148. }
  150. ul cc[maxk + 1][1000];
  152. ul len[maxk + 1];
  154. ul T;
  156. int main()
  157. {
  158.     rnd.seed(std::time(0));
  159.     X = rnd();
  160.     Y = rnd();
  161.     ans[1][0] = 1;
  162.     ans[2][0] = 1;
  163.     ans[2][1] = 1;
  164.     ans[3][0] = 1;
  165.     ans[3][1] = 1;
  166.     ans[3][2] = 2;
  167.     for (ul k = 1; k <= 3; ++k) {
  168.         map[k].clear();
  169.         if (k == 1) {
  170.             map[k][gethash({1, 1})] = counter({1, 1}, 1);
  171.         } else if (k == 2) {
  172.             map[k][gethash({1, 1, 2, 2})] = counter({1, 1, 2, 2}, 1);
  173.             map[k][gethash({1, 2})] = counter({1, 2}, 1);
  174.         } else if (k == 3) {
  175.             map[k][gethash({1, 1, 2, 2, 3, 3})] = counter({1, 1, 2, 2, 3, 3}, 1);
  176.             map[k][gethash({1, 2, 3, 3})] = counter({1, 2, 3, 3}, 1);
  177.             map[k][gethash({1, 3, 2, 2})] = counter({1, 3, 2, 2}, 1);
  178.             map[k][gethash({2, 3, 1, 1})] = counter({2, 3, 1, 1}, 1);
  179.             map[k][gethash({1, 2})] = counter({1, 2}, 1);
  180.             map[k][gethash({1, 3})] = counter({1, 3}, 1);
  181.             map[k][gethash({2, 3})] = counter({2, 3}, 1);
  182.         }
  183.         for (ul n = k; n + 1 <= maxn; ++n) {
  184.             map[n + 1].clear();
  185.             for (const auto& p : map[n]) {
  186.                 const auto& con = p.second.v;
  187.                 ul val = p.second.cnt;
  188.                 for (ul i = 0; i + 1 != con.size(); ++i) {
  189.                     if (!con[i]) {
  190.                         continue;
  191.                     }
  192.                     if ((i & 1) && con[i - 1] == con[i]) {
  193.                         continue;
  194.                     }
  195.                     for (ul j = i + 1; j != con.size(); ++j) {
  196.                         if (!con[j]) {
  197.                             continue;
  198.                         }
  199.                         if ((j & 1) && con[j - 1] == con[j]) {
  200.                             continue;
  201.                         }
  202.                         if ((i >> 1) == (j >> 1)) {
  203.                             continue;
  204.                         }
  205.                         nextcon.resize(0);
  206.                         nextcon.push_back(con[i ^ 1]);
  207.                         nextcon.push_back(con[j ^ 1]);
  208.                         for (ul a = 0; a != con.size(); a += 2) {
  209.                             if ((a >> 1) != (i >> 1) && (a >> 1) != (j >> 1)) {
  210.                                 nextcon.push_back(con[a]);
  211.                                 nextcon.push_back(con[a + 1]);
  212.                             }
  213.                         }
  214.                         regular(nextcon, n + 1, k);
  215.                         if (!check(nextcon)) {
  216.                             continue;
  217.                         }
  218.                         auto& next = map[n + 1][gethash(nextcon)];
  219.                         next.v = nextcon;
  220.                         next.cnt = plus(next.cnt, val);
  221.                     }
  222.                 }
  223.                 for (ul i = 0; i != con.size(); ++i) {
  224.                     if (!con[i]) {
  225.                         continue;
  226.                     }
  227.                     if ((i & 1) && con[i - 1] == con[i]) {
  228.                         continue;
  229.                     }
  230.                     nextcon = con;
  231.                     nextcon[i] = n + 1;
  232.                     regular(nextcon, n + 1, k);
  233.                     if (!check(nextcon)) {
  234.                         continue;
  235.                     }
  236.                     auto& next = map[n + 1][gethash(nextcon)];
  237.                     next.v = nextcon;
  238.                     next.cnt = plus(next.cnt, val);
  239.                 }
  240.                 nextcon = con;
  241.                 nextcon.push_back(n + 1);
  242.                 nextcon.push_back(n + 1);
  243.                 regular(nextcon, n + 1, k);
  244.                 if (!check(nextcon)) {
  245.                     continue;
  246.                 }
  247.                 auto& next = map[n + 1][gethash(nextcon)];
  248.                 next.v = nextcon;
  249.                 next.cnt = plus(next.cnt, val);
  250.             }
  251.         }
  252.         for (ul n = k; n <= maxn; ++n) {
  253.             for (const auto& p : map[n]) {
  254.                 if (p.second.v.size() == 2) {
  255.                     ans[k][n] = plus(ans[k][n], p.second.cnt);
  256.                 }
  257.             }
  258.             if (n != 1) {
  259.                 ans[k][n] = mul(2, ans[k][n]);
  260.             }
  261.         }
  262.     }
  263.     for (ul k = 1; k <= 3; ++k) {
  264.         len[k] = bm(ans[k], cc[k], maxn + 1);
  265.         for (ul n = maxn + 1; n <= maxn2; ++n) {
  266.             for (ul i = 1; i <= len[k]; ++i) {
  267.                 ans[k][n] = minus(ans[k][n], mul(cc[k][i], ans[k][n - i]));
  268.             }
  269.         }
  270.     }
  271.     std::scanf("%u", &T);
  272.     for (ul Case = 1; Case <= T; ++Case) {
  273.         ul n, k;
  274.         std::scanf("%u%u", &n, &k);
  275.         std::printf("%u\n", ans[k][n]);
  276.     }
  277.     return 0;
  278. }

C、<3 numbers

简单题

  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. ul T;
  13. ul l, r;
  15. ul mul(ul a, ul b, ul c)
  16. {
  17.     return ull(a) * ull(b) % c;
  18. }
  20. ul pow(ul a, ul b, ul c)
  21. {
  22.     ul ret = 1 % c;
  23.     while (b) {
  24.         if (b & 1) {
  25.             ret = mul(ret, a, c);
  26.         }
  27.         a = mul(a, a, c);
  28.         b >>= 1;
  29.     }
  30.     return ret;
  31. }
  33. std::mt19937 rnd;
  35. bool isprime(ul x)
  36. {
  37.     if (x == 1) {
  38.         return true;
  39.     }
  40.     if (x == 2) {
  41.         return true;
  42.     }
  43.     if (~x & 1) {
  44.         return false;
  45.     }
  46.     ul t = __builtin_ctz(x - 1);
  47.     ul s = x - 1 >> t;
  48.     for (ul cnt = 1; cnt <= 20; ++cnt) {
  49.         ul k = pow(rnd() % (x - 1) + 1, s, x);
  50.         if (k == 1) {
  51.             continue;
  52.         }
  53.         ul i = 0;
  54.         while (k != 1 && k != x - 1 && i + 1 != t) {
  55.             ++i;
  56.             k = mul(k, k, x);
  57.         }
  58.         if (k != x - 1) {
  59.             return false;
  60.         }
  61.     }
  62.     return true;
  63. }
  65. int main()
  66. {
  67.     rnd.seed(std::time(0));
  68.     std::scanf("%u", &T);
  69.     for (ul Case = 1; Case <= T; ++Case) {
  70.         std::scanf("%u%u", &l, &r);
  71.         if (r - l + 1 >= 420) {
  72.             std::printf("Yes\n");
  73.             continue;
  74.         }
  75.         ul x = 0;
  76.         for (ul i = l; i <= r; ++i) {
  77.             x += isprime(i);
  78.         }
  79.         std::printf(ull(x) * 3 < r - l + 1 ? "Yes\n" : "No\n");
  80.     }
  81.     return 0;
  82. }

D、Polycut

首先，关于割的那刀这样处理：对任何一个用点棱存储的凸多面体，如果多加一个约束，只需要研究这个约束和那些点或者边相交了，就能得到一个新的用点棱存储的凸多面体。
现在解决给定一个点棱存储的凸多面体的体积问题。首先是要解决一个点所连出去的边的排序问题。这个问题这样解决，考虑先将所有点的重心找到，记为，接着，对每个点，将其连出去的边投影到和相垂直的平面上，于是就可以以为极点对边进行极角排序，这样就知道每次走完一条边之后，接下来哪条边才是“向左转”该走的了。于是可以求出所有面，再接着就是很简单的工作了。
过了，数据没有问题。

  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. using llf = long double;
  13. const ull mod = 4179340454199820289ull;
  15. ull plus(ull a, ull b)
  16. {
  17.     return a + b < mod ? a + b : a + b - mod;
  18. }
  20. ull minus(ull a, ull b)
  21. {
  22.     return a < b ? a + mod - b : a - b;
  23. }
  25. ull mul(ll a, ll b)
  26. {
  27.     ll tmp = a * b - ll(llf(a) * llf(b) / llf(mod)) * ll(mod);
  28.     return tmp < 0 ? tmp + ll(mod) : (tmp < ll(mod) ? tmp : tmp - ll(mod));
  29. }
  31. void exgcd(ll a, ll b, ll& x, ll& y)
  32. {
  33.     if (b) {
  34.         exgcd(b, a % b, y, x);
  35.         y -= a / b * x;
  36.     } else {
  37.         x = 1;
  38.         y = 0;
  39.     }
  40. }
  42. ull inverse(ull a)
  43. {
  44.     ll x, y;
  45.     exgcd(a, mod, x, y);
  46.     return x < 0 ? x + ll(mod) : x;
  47. }
  49. class hashllf {
  50. public:
  51.     llf val = 0;
  52.     ull hash = 0;
  53.     hashllf()=default;
  54.     hashllf(li x): val(x), hash((x + mod) % mod) {}
  55.     hashllf(llf x): val(x), hash(0) {}
  56.     hashllf(llf a, ull b): val(a), hash(b) {}
  57.     operator llf() const {
  58.         return val;
  59.     }
  60. };
  62. hashllf operator+(const hashllf& a, const hashllf& b)
  63. {
  64.     return hashllf(a.val + b.val, plus(a.hash, b.hash));
  65. }
  67. hashllf operator-(const hashllf& a, const hashllf& b)
  68. {
  69.     return hashllf(a.val - b.val, minus(a.hash, b.hash));
  70. }
  72. hashllf operator*(const hashllf& a, const hashllf& b)
  73. {
  74.     return hashllf(a.val * b.val, mul(a.hash, b.hash));
  75. }
  77. hashllf operator/(const hashllf& a, const hashllf& b)
  78. {
  79.     return hashllf(a.val / b.val, mul(a.hash, inverse(b.hash)));
  80. }
  82. li sgn(const hashllf& x)
  83. {
  84.     return x.hash == 0 ? 0 : (x.val < 0 ? -1 : 1);
  85. }
  87. class vec {
  88. public:
  89.     hashllf x = 0;
  90.     hashllf y = 0;
  91.     hashllf z = 0;
  92.     vec()=default;
  93.     vec(hashllf a, hashllf b, hashllf c): x(a), y(b), z(c) {}
  94.     ul high() const {
  95.         return sgn(x) ? 3 : (sgn(y) ? 2 : (sgn(z) ? 1 : 0));
  96.     }
  97.     hashllf& operator[](ul i) {
  98.         return i == 1 ? z : (i == 2 ? y : x);
  99.     }
  100.     const hashllf& operator[](ul i) const {
  101.         return i == 1 ? z : (i == 2 ? y : x);
  102.     }
  103. };
  105. vec operator+(const vec& a, const vec& b)
  106. {
  107.     return vec(a.x + b.x, a.y + b.y, a.z + b.z);
  108. }
  110. vec operator-(const vec& a, const vec& b)
  111. {
  112.     return vec(a.x - b.x, a.y - b.y, a.z - b.z);
  113. }
  115. vec operator*(hashllf a, const vec& b)
  116. {
  117.     return vec(a * b.x, a * b.y, a * b.z);
  118. }
  120. vec operator*(const vec& a, hashllf b)
  121. {
  122.     return vec(a.x * b, a.y * b, a.z * b);
  123. }
  125. vec operator/(const vec& a, hashllf b)
  126. {
  127.     return vec(a.x / b, a.y / b, a.z / b);
  128. }
  130. hashllf operator*(const vec& a, const vec& b)
  131. {
  132.     return a.x * b.x + a.y * b.y + a.z * b.z;
  133. }
  135. ul n, m, k;
  137. ul totp;
  139. vec points[1 << 21];
  141. ul tote;
  143. std::pair<ul, ul> edges[1 << 21];
  145. std::vector<ul> pstack[4];
  147. std::vector<ul> estack[4];
  149. vec cutdir[4];
  150. vec cutx[4];
  151. vec cuty[4];
  153. hashllf cutbound[4];
  155. li type[1 << 21];
  157. std::vector<ul> tmpstack;
  159. std::priority_queue<llf, std::vector<llf>, std::greater<llf>> queue;
  161. llf myabs(llf x)
  162. {
  163.     return x < 0 ? -x : x;
  164. }
  166. class mygreater {
  167. public:
  168.     bool operator()(llf a, llf b){return myabs(a) > myabs(b);}
  169. };
  171. std::priority_queue<llf, std::vector<llf>, mygreater> queue2;
  173. llf getsum()
  174. {
  175.     while (queue2.size() >= 2) {
  176.         llf a = queue2.top();
  177.         queue2.pop();
  178.         llf b = queue2.top();
  179.         queue2.pop();
  180.         queue2.push(a + b);
  181.     }
  182.     llf tmp = queue2.top();
  183.     queue2.pop();
  184.     return tmp;
  185. }
  187. vec getw(const std::vector<ul>& pstack)
  188. {
  189.     vec ret(0, 0, 0);
  190.     for (auto p : pstack) {
  191.         ret = ret + points[p];
  192.     }
  193.     ret = ret / hashllf(li(pstack.size()));
  194.     for (auto p : pstack) {
  195.         queue2.push(points[p].x);
  196.     }
  197.     ret.x.val = getsum() / llf(pstack.size());
  198.     for (auto p : pstack) {
  199.         queue2.push(points[p].y);
  200.     }
  201.     ret.y.val = getsum() / llf(pstack.size());
  202.     for (auto p : pstack) {
  203.         queue2.push(points[p].z);
  204.     }
  205.     ret.z.val = getsum() / llf(pstack.size());
  206.     return ret;
  207. }
  209. hashllf vol1(const vec& a)
  210. {
  211.     return a * a;
  212. }
  214. hashllf vol2(const vec& a, const vec& b)
  215. {
  216.     hashllf aa = a * a;
  217.     hashllf bb = b * b;
  218.     hashllf ab = a * b;
  219.     return aa * bb - ab * ab;
  220. }
  222. hashllf vol3(const vec& a, const vec& b, const vec& c)
  223. {
  224.     hashllf aa = a * a;
  225.     hashllf ab = a * b;
  226.     hashllf ac = a * c;
  227.     hashllf bb = b * b;
  228.     hashllf bc = b * c;
  229.     hashllf cc = c * c;
  230.     return aa * bb * cc + hashllf(2) * ab * bc * ac - ac * bb * ac - aa * bc * bc - ab * ab * cc;
  231. }
  233. hashllf vol3p(const vec& a, const vec& b, const vec& c)
  234. {
  235.     return a.x * b.y * c.z + a.y * b.z * c.x + a.z * b.x * c.y - a.x * b.z * c.y - a.y * b.x * c.z - a.z * b.y * c.x;
  236. }
  238. void insert(std::vector<vec>& base, vec v)
  239. {
  240.     for (const auto u : base) {
  241.         ul uh = u.high();
  242.         if (sgn(v[uh])) {
  243.             v = v - v[uh] / u[uh] * u;
  244.         }
  245.     }
  246.     if (sgn(v.x) || sgn(v.y) || sgn(v.z)) {
  247.         base.push_back(v);
  248.     }
  249. }
  251. ul checkdim(const std::vector<ul>& pstack, vec& w)
  252. {
  253.     static std::vector<vec> base;
  254.     base.resize(0);
  255.     w = getw(pstack);
  256.     for (auto p : pstack) {
  257.         insert(base, points[p] - w);
  258.     }
  259.     return base.size();
  260. }
  262. ul region(llf x, llf y)
  263. {
  264.     return x < 0 ? (y < 0 ? 3 : 2) : (y < 0 ? 4 : 1);
  265. }
  267. std::vector<llf> ans;
  269. std::vector<ul> neibor[1 << 20];
  271. std::unordered_map<ull, ul> nextto;
  272. std::unordered_set<ull> already;
  274. ull base;
  275. std::mt19937_64 rnd;
  277. inline ull gfmul(ull a, ull b)
  278. {
  279.     auto vc = _mm_clmulepi64_si128(_mm_cvtsi64_si128(a), _mm_cvtsi64_si128(b), 0);
  280.     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));
  281.     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)));
  282. }
  284. std::set<ull> eset[4];
  286. void search(ul cutid)
  287. {
  288.     if (cutid == k + 1) {
  289.         if (pstack[k].empty()) {
  290.             ans.push_back(0);
  291.             return;
  292.         }
  293.         vec w = getw(pstack[k]);
  294.         for (ul p : pstack[k]) {
  295.             neibor[p].resize(0);
  296.         }
  297.         for (const auto e : estack[k]) {
  298.             neibor[edges[e].first].push_back(edges[e].second);
  299.             neibor[edges[e].second].push_back(edges[e].first);
  300.         }
  301.         nextto.clear();
  302.         for (auto p : pstack[k]) {
  303.             vec z = points[p] - w;
  304.             z = z / std::sqrt(z * z);
  305.             vec sq;
  306.             llf val = 0;
  307.             for (auto q : neibor[p]) {
  308.                 llf newval = vol2(points[q] - points[p], z);
  309.                 if (val < newval) {
  310.                     sq = points[q];
  311.                     val = newval;
  312.                 }
  313.             }
  314.             vec x = sq - points[p];
  315.             x = x - x * z * z;
  316.             x = x / std::sqrt(x * x);
  317.             vec y(z.y * x.z - z.z * x.y, z.z * x.x - z.x * x.z, z.x * x.y - z.y * x.x);
  318.             sort(neibor[p].begin(), neibor[p].end(), [&](ul a, ul b) {
  319.                     llf ax = (points[a] - points[p]) * x;
  320.                     llf ay = (points[a] - points[p]) * y;
  321.                     llf bx = (points[b] - points[p]) * x;
  322.                     llf by = (points[b] - points[p]) * y;
  323.                     return region(ax, ay) != region(bx, by) ? region(ax, ay) < region(bx, by) : ax * by - ay * bx > 0;});
  324.             neibor[p].push_back(neibor[p].front());
  325.             for (ul i = 0; i + 1 != neibor[p].size(); ++i) {
  326.                 nextto[gfmul(base ^ neibor[p][i + 1], p)] = neibor[p][i];
  327.             }
  328.         }
  329.         already.clear();
  330.         while (queue.size()) {
  331.             queue.pop();
  332.         }
  333.         for (auto p : pstack[k]) {
  334.             neibor[p].pop_back();
  335.             for (ul q : neibor[p]) {
  336.                 if (!already.insert(gfmul(base ^ p, q)).second) {
  337.                     continue;
  338.                 }
  339.                 for (ul i = q, j = nextto[gfmul(base ^ p, q)]; ; ) {
  340.                     queue.push(myabs(vol3p(points[p] - w, points[i] - w, points[j] - w)));
  341.                     ul newj = nextto[gfmul(base ^ i, j)];
  342.                     already.insert(gfmul(base ^ i, j));
  343.                     i = j;
  344.                     j = newj;
  345.                     if (j == p) {
  346.                         already.insert(gfmul(base ^ i, j));
  347.                         break;
  348.                     }
  349.                 }
  350.             }
  351.         }
  352.         while (queue.size() >= 2) {
  353.             llf a = queue.top();
  354.             queue.pop();
  355.             llf b = queue.top();
  356.             queue.pop();
  357.             queue.push(a + b);
  358.         }
  359.         ans.push_back(queue.top() / 6);
  360.         return;
  361.     }
  362.     for (li pn : {1, -1}) {
  363.         pstack[cutid].resize(0);
  364.         estack[cutid].resize(0);
  365.         eset[cutid].clear();
  366.         if (pstack[cutid - 1].empty()) {
  367.             search(cutid + 1);
  368.         }
  369.         tmpstack.resize(0);
  370.         for (ul p : pstack[cutid - 1]) {
  371.             type[p] = sgn(cutdir[cutid] * points[p] - cutbound[cutid]) * pn;
  372.             if (type[p] <= 0) {
  373.                 pstack[cutid].push_back(p);
  374.             }
  375.             if (type[p] == 0) {
  376.                 tmpstack.push_back(p);
  377.             }
  378.         }
  379.         for (ul e : estack[cutid - 1]) {
  380.             if (type[edges[e].first] <= 0 && type[edges[e].second] <= 0) {
  381.                 estack[cutid].push_back(e);
  382.                 eset[cutid].insert(gfmul(edges[e].first ^ base, edges[e].second ^ base));
  383.             }
  384.             if (type[edges[e].first] * type[edges[e].second] < 0) {
  385.                 const auto& a = points[edges[e].first];
  386.                 const auto& b = points[edges[e].second];
  387.                 ++totp;
  388.                 points[totp] = (cutbound[cutid] - a * cutdir[cutid]) / ((b - a) * cutdir[cutid]) * b + (cutbound[cutid] - b * cutdir[cutid]) / ((a - b) * cutdir[cutid]) * a;
  389.                 tmpstack.push_back(totp);
  390.                 pstack[cutid].push_back(totp);
  391.                 type[totp] = -1;
  392.                 ++tote;
  393.                 edges[tote].first = type[edges[e].first] < type[edges[e].second] ? edges[e].first : edges[e].second;
  394.                 edges[tote].second = totp;
  395.                 estack[cutid].push_back(tote);
  396.                 eset[cutid].insert(gfmul(edges[tote].first ^ base, edges[tote].second ^ base));
  397.             }
  398.         }
  399.         if (tmpstack.size()) {
  400.             vec w;
  401.             ul dim = checkdim(tmpstack, w);
  402.             if (dim != 0) {
  403.                 llf val = 0;
  404.                 ul sp;
  405.                 for (ul p : tmpstack) {
  406.                     llf newval = vol1(points[p] - w);
  407.                     if (val < newval) {
  408.                         val = newval;
  409.                         sp = p;
  410.                     }
  411.                 }
  412.                 vec x = (points[sp] - w) / std::sqrt(vol1(points[sp] - w));
  413.                 vec z = cutdir[cutid] / std::sqrt(vol1(cutdir[cutid]));
  414.                 vec y(z.y * x.z - z.z * x.y, z.z * x.x - z.x * x.z, z.x * x.y - z.y * x.x);
  415.                 if (dim == 1) {
  416.                     std::sort(tmpstack.begin(), tmpstack.end(), [&](ul a, ul b){return points[a] * x < points[b] * x;});
  417.                     for (ul i = 0; i + 1 != tmpstack.size(); ++i) {
  418.                         if (eset[cutid].find(gfmul(tmpstack[i] ^ base, tmpstack[i + 1] ^ base)) == eset[cutid].end()) {
  419.                             ++tote;
  420.                             edges[tote].first = tmpstack[i];
  421.                             edges[tote].second = tmpstack[i + 1];
  422.                             estack[cutid].push_back(tote);
  423.                             eset[cutid].insert(gfmul(edges[tote].first ^ base, edges[tote].second ^ base));
  424.                         }
  425.                     }
  426.                 } else if (dim == 2) {
  427.                     std::sort(tmpstack.begin(), tmpstack.end(), [&](ul a, ul b){
  428.                             llf ax = (points[a] - w) * x;
  429.                             llf ay = (points[a] - w) * y;
  430.                             llf bx = (points[b] - w) * x;
  431.                             llf by = (points[b] - w) * y;
  432.                             return region(ax, ay) != region(bx, by) ? region(ax, ay) < region(bx, by) : ax * by - ay * bx > 0;});
  433.                     tmpstack.push_back(tmpstack.front());
  434.                     for (ul i = 0; i + 1 != tmpstack.size(); ++i) {
  435.                         if (type[tmpstack[i]] != 0 || type[tmpstack[i + 1]] != 0) {
  436.                             ++tote;
  437.                             edges[tote].first = tmpstack[i];
  438.                             edges[tote].second = tmpstack[i + 1];
  439.                             estack[cutid].push_back(tote);
  440.                         }
  441.                     }
  442.                 }
  443.             }
  444.         }
  445.         if (pstack[cutid].size()) {
  446.             vec w;
  447.             ul dim = checkdim(pstack[cutid], w);
  448.             if (dim < 3) {
  449.                 pstack[cutid].resize(0);
  450.             }
  451.         }
  452.         search(cutid + 1);
  453.     }
  454. }
  456. int main()
  457. {
  458.     rnd.seed(std::time(0));
  459.     base = rnd();
  460.     std::scanf("%u%u%u", &n, &m, &k);
  461.     for (ul i = 1; i <= n; ++i) {
  462.         li x, y, z;
  463.         std::scanf("%d%d%d", &x, &y, &z);
  464.         points[totp] = vec(x, y, z);
  465.         pstack[0].push_back(totp);
  466.         ++totp;
  467.     }
  468.     --totp;
  469.     for (ul i = 1; i <= m; ++i) {
  470.         ++tote;
  471.         std::scanf("%u%u", &edges[tote].first, &edges[tote].second);
  472.         estack[0].push_back(tote);
  473.     }
  474.     for (ul i = 1; i <= k; ++i) {
  475.         li a, b, c, d;
  476.         std::scanf("%d%d%d%d", &a, &b, &c, &d);
  477.         cutdir[i] = vec(a, b, c);
  478.         cutbound[i] = d;
  479.     }
  480.     search(1);
  481.     std::sort(ans.begin(), ans.end());
  482.     for (const auto& a : ans) {
  483.         std::printf("%.20Le\n", a);
  484.     }
  485.     return 0;
  486. }

E、Multiply

简单题

  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. using llf = long double;
  13. ul T;
  15. ull plus(ull a, ull b, ull c)
  16. {
  17.     return a + b < c ? a + b : a + b - c;
  18. }
  20. ull minus(ull a, ull b, ull c)
  21. {
  22.     return a < b ? a + c - b : a - b;
  23. }
  25. ll mul(ll a, ll b, ll c)
  26. {
  27.     ll tmp = a * b - ll(llf(a) * llf(b) / llf(c)) * c;
  28.     return tmp < 0 ? tmp + c : (tmp < c ? tmp : tmp - c);
  29. }
  31. ull pow(ull a, ull b, ull c)
  32. {
  33.     ull ret = 1 % c;
  34.     while (b) {
  35.         if (b & 1) {
  36.             ret = mul(ret, a, c);
  37.         }
  38.         a = mul(a, a, c);
  39.         b >>= 1;
  40.     }
  41.     return ret;
  42. }
  44. std::mt19937_64 rnd;
  46. bool isprime(ull x)
  47. {
  48.     if (x == 1) {
  49.         return true;
  50.     }
  51.     if (x == 2) {
  52.         return true;
  53.     }
  54.     if (~x & 1) {
  55.         return false;
  56.     }
  57.     ul t = __builtin_ctzll(x - 1);
  58.     ull s = x - 1 >> t;
  59.     for (ul cnt = 1; cnt <= 20; ++cnt) {
  60.         ull k = pow(rnd() % (x - 1) + 1, s, x);
  61.         if (k == 1) {
  62.             continue;
  63.         }
  64.         ul i = 0;
  65.         while (k != 1 && k != x - 1 && i + 1 != t) {
  66.             ++i;
  67.             k = mul(k, k, x);
  68.         }
  69.         if (k != x - 1) {
  70.             return false;
  71.         }
  72.     }
  73.     return true;
  74. }
  76. ull gcd(ull a, ull b)
  77. {
  78.     while (b) {
  79.         b ^= a ^= b ^= a %= b;
  80.     }
  81.     return a;
  82. }
  84. ull rho(ull v)
  85. {
  86.     while (true) {
  87.         ull c = rnd() % (v - 1) + 1;
  88.         auto f = [&](ull x){return plus(mul(x, x, v), c, v);};
  89.         ull x = rnd() % v;
  90.         ull y = f(x);
  91.         while (x != y) {
  92.             ull tmp = gcd(minus(x, y, v), v);
  93.             if (tmp != 1) {
  94.                 return tmp;
  95.             }
  96.             x = f(x);
  97.             y = f(f(y));
  98.         }
  99.     }
  100. }
  102. std::vector<ull> facs;
  104. void getfact(ull x)
  105. {
  106.     static std::vector<ull> stack;
  107.     stack.resize(0);
  108.     facs.resize(0);
  109.     if (x != 1) {
  110.         stack.push_back(x);
  111.     }
  112.     while (stack.size()) {
  113.         ull curr = stack.back();
  114.         stack.pop_back();
  115.         if (isprime(curr)) {
  116.             facs.push_back(curr);
  117.         } else {
  118.             ull next = rho(curr);
  119.             stack.push_back(next);
  120.             stack.push_back(curr / next);
  121.         }
  122.     }
  123.     std::sort(facs.begin(), facs.end());
  124. }
  126. ul n;
  128. ull a;
  130. ull x, y;
  132. std::vector<std::pair<ull, ull>> faccntx;
  133. std::vector<std::pair<ull, ull>> faccnty;
  135. int main()
  136. {
  137.     rnd.seed(std::time(0));
  138.     std::scanf("%u", &T);
  139.     for (ul Case = 1; Case <= T; ++Case) {
  140.         std::scanf("%u%llu%llu", &n, &x, &y);
  141.         getfact(x);
  142.         std::sort(facs.begin(), facs.end());
  143.         faccntx.resize(0);
  144.         for (auto p : facs) {
  145.             if (faccntx.empty() || faccntx.back().first != p) {
  146.                 faccntx.push_back(std::pair<ull, ul>(p, 1));
  147.             } else {
  148.                 ++faccntx.back().second;
  149.             }
  150.         }
  151.         faccnty = faccntx;
  152.         for (auto& pc : faccnty) {
  153.             ull p = pc.first;
  154.             pc.second = 0;
  155.             ull pi = p;
  156.             ull tmp = y / p;
  157.             while (true) {
  158.                 pc.second += y / pi;
  159.                 if (pi > tmp) {
  160.                     break;
  161.                 } else {
  162.                     pi *= p;
  163.                 }
  164.             }
  165.         }
  166.         for (ul i = 1; i <= n; ++i) {
  167.             std::scanf("%llu", &a);
  168.             for (auto& pc : faccnty) {
  169.                 ull p = pc.first;
  170.                 ull pi = p;
  171.                 ull tmp = a / p;
  172.                 while (true) {
  173.                     pc.second -= a / pi;
  174.                     if (pi > tmp) {
  175.                         break;
  176.                     } else {
  177.                         pi *= p;
  178.                     }
  179.                 }
  180.             }
  181.         }
  182.         ull ans = 2e18;
  183.         for (ull i = 0; i != faccntx.size(); ++i) {
  184.             ans = std::min(ans, faccnty[i].second / faccntx[i].second);
  185.         }
  186.         std::printf("%llu\n", ans);
  187.     }
  188.     return 0;
  189. }

F、The Answer to the Ultimate Question of Life, The Universe, and Everything.

简单题

  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;
  10. using llf = long double;
  12. const ll maxv = 5000;
  13. const ll maxx = 200;
  15. std::string ans[maxx + 1];
  17. ll upcbrt(ll x)
  18. {
  19.     ll tmp = std::llround(std::cbrt(llf(x)));
  20.     while (tmp * tmp * tmp < x) {
  21.         ++tmp;
  22.     }
  23.     return tmp;
  24. }
  26. std::string tmp;
  28. std::stringstream ss;
  30. int main()
  31. {
  32.     for (ll a = -maxv, a3 = a * a * a; a3 * 3 <= maxx; ++a, a3 = a * a * a) {
  33.         for (ll b = std::max(upcbrt(-maxv * maxv * maxv - a3), a), b3 = b * b * b; b <= maxv && a3 + b3 * 2 <= maxx; ++b, b3 = b * b * b) {
  34.             for (ll c = std::max(upcbrt(-a * a * a - b * b * b), b), c3 = c * c * c; c <= maxv && a3 + b3 + c3 <= maxx; ++c, c3 = c * c * c) {
  35.                 ll v = a3 + b3 + c3;
  36.                 ss.str("");
  37.                 ss << a << ' ' << b << ' ' << c;
  38.                 tmp = ss.str();
  39.                 if (ans[v].empty() || ans[v].size() > tmp.size()) {
  40.                     std::swap(ans[v], tmp);
  41.                 }
  42.             }
  43.         }
  44.     }
  45.     std::freopen("Fdata.txt", "w", stdout);
  46.     std::printf("{");
  47.     for (ul i = 0; i <= maxx; ++i) {
  48.         if (i) {
  49.             std::printf(",");
  50.         }
  51.         std::cout << '\"' << ans[i] << '\"';
  52.     }
  53.     std::printf("}");
  54.     return 0;
  55. }
  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 ll maxx = 200;
  13. std::string ans[maxx + 1] = {"0 0 0","0 0 1","0 1 1","1 1 1","","","-1 -1 2","-1 0 2","0 0 2","0 1 2","1 1 2","-2 -2 3","-11 7 10","","","-1 2 2","0 2 2","1 2 2","-2 -1 3","-2 0 3","-2 1 3","-86 28 85","","","2 2 2","-1 -1 3","-1 0 3","0 0 3","0 1 3","1 1 3","","","","","-6 5 5","0 2 3","1 2 3","-3 0 4","-3 1 4","","","","","2 2 3","-7 -5 8","-3 2 4","-2 3 3","-8 6 7","-2 -2 4","","","-796 602 659","","-1 3 3","0 3 3","1 3 3","-2 0 4","-2 1 4","","","-4 -1 5","-4 0 5","2 3 3","-1 0 4","0 0 4","0 1 4","1 1 4","","","-4 2 5","-64 23 63","-1 2 4","0 2 4","1 2 4","","","","","-55 26 53","-66 -49 74","2 2 4","3 3 3","-11 -11 14","-2 3 4","","","","-4126 -1972 4271","-4 3 5","-7 6 6","-1 3 4","0 3 4","1 3 4","-5 -5 7","","","-22 14 20","-3 -1 5","-3 0 5","2 3 4","-6 -3 7","-3 4 4","-239 118 229","","","-7 -4 8","-3 2 5","-48 -28 51","-1165 -948 1345","-2 -2 5","","-881 -296 892","","","","-12 8 11","-2 -1 5","-2 0 5","3 3 4","-6 -2 7","-2 4 4","","","-1 -1 5","-1 0 5","0 0 5","0 1 5","1 1 5","0 4 4","1 4 4","","","-1 2 5","0 2 5","1 2 5","-6 2 7","2 4 4","-11 -9 13","-86 -77 103","","","2 2 5","-7 -3 8","","-2 3 5","-8 -7 10","-9 -5 10","-56 -50 67","","","-367 260 317","-1 3 5","0 3 5","1 3 5","-6 3 7","3 4 4","","","","-130 80 119","2 3 5","-7 -2 8","-3 4 5","-76 -68 91","-66 -59 79","","","","-7 -1 8","-7 0 8","-7 1 8","-6 -5 8","","","-8 7 7","","","-7 2 8","-13 -10 15","3 3 5","","-2 4 5","-14 9 13","-17 10 16","","","-4 5 5","-58 27 56","-1 4 5","0 4 5","1 4 5","-6 4 7","4 4 4","","","","-7 3 8","2 4 5","-48 -19 49","-24 15 22","-2 -2 6"};
  15. ul T;
  17. ul x;
  19. int main()
  20. {
  21.     std::cin >> T;
  22.     for (ul Case = 1; Case <= T; ++Case) {
  23.         std::cin >> x;
  24.         std::cout << (ans[x].empty() ? std::string("impossible") : ans[x]) << std::endl;
  25.     }
  26.     return 0;
  27. }

G、Factory

下文中，原题是要在满足：

的情况下最小化：
这不是一个标准的线性规划问题，现在引入一个新的变量，将问题改为在满足：
的情况下最小化：
接着，借助于强对偶定理（该定理的证明异常冗长，就不给出了），将问题对偶为在满足：
的情况下最大化：
而该问题实际显然和如下问题等价，在满足：
的情况下最大化
现在变成一个在维仿射空间里最大化一个非光滑凹函数的问题，也就是在仿射空间里最小化非光滑凸函数的问题。
由于非光滑，所以有些点并没有梯度，于是现在定义次梯度。
考虑欧式仿射空间（用表示的切空间的对偶空间）上有一凸函数，那么显然
所有满足这样条件的，均称为在处的次梯度。而显然，对任何一组凸函数，如果分别是它们在处的次梯度，那么也是是的次梯度。注意，是在处的次梯度并不意味着在某个单调递减，这意味着将移动到并不保证是下降的，于是次梯度算法并不称为次梯度下降算法。但是整体来说，只要步长设置满足一定要求，一定能收敛到最值点。关于这一点以及收敛速度的证明见：https://www.zybuluo.com/qq290637843/note/1776595。
接下来求次梯度：首先固定，设是使得最小的。那么具有次梯度
其中。故整体的次梯度为
而依据，那么的移动量为
但是这样收敛还是太慢了，个人将的定义换为“估计答案和当前答案的差”，其中“估计答案”是指当前最大答案乘的系数。正确性不会证。（这种自适应次梯度算法实际叫做Polyak's step length）

  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. using llf = long double;
  13. using lf = double;
  15. using d_t = lf;
  17. const ul maxn = 2e4;
  18. const ul maxk = 50;
  20. ul n, k;
  22. d_t t[maxn + 1][maxk + 1];
  24. d_t g[maxk + 1];
  26. d_t xchange[maxk + 1];
  28. bool gequal0;
  30. d_t M;
  32. d_t A;
  34. d_t T;
  36. d_t Acurr;
  38. const d_t beta = 0.00995;
  40. ull start;
  42. void f(d_t x[])
  43. {
  44.     std::memset(g + 1, 0, sizeof(d_t) * k);
  45.     d_t sum = 0;
  46.     for (ul j = 1; j <= k; ++j) {
  47.         sum += x[j];
  48.     }
  49.     for (ul j = 1; j <= k; ++j) {
  50.         x[j] /= sum;
  51.     }
  52.     sum = 0;
  53.     d_t gsum = 0;
  54.     for (ul i = 1; i <= n; ++i) {
  55.         d_t mn = t[i][1] * x[1];
  56.         ul a = 1;
  57.         for (ul j = 2; j <= k; ++j) {
  58.             if (t[i][j] * x[j] < mn) {
  59.                 mn = t[i][j] * x[j];
  60.                 a = j;
  61.             }
  62.         }
  63.         g[a] += t[i][a];
  64.         sum += mn;
  65.     }
  66.     A = std::max(A, sum);
  67.     Acurr = sum;
  68.     T = (1 + beta) * A - Acurr;
  69.     gequal0 = true;
  70.     for (ul j = 1; j <= k; ++j) {
  71.         gsum += g[j];
  72.         g[j] *= k;
  73.         if (g[j] != g[1]) {
  74.             gequal0 = false;
  75.         }
  76.     }
  77.     if (gequal0) {
  78.         return;
  79.     }
  80.     for (ul j = 1; j <= k; ++j) {
  81.         g[j] -= gsum;
  82.     }
  83.     d_t tmp = 0;
  84.     for (ul j = 1; j <= k; ++j) {
  85.         tmp += g[j] * g[j];
  86.     }
  87.     for (ul j = 1; j <= k; ++j) {
  88.         xchange[j] = T * k * (g[j] / tmp);
  89.     }
  90. }
  92. d_t x[maxk + 1];
  94. int main()
  95. {
  96.     std::scanf("%u%u", &n, &k);
  97.     for (ul i = 1; i <= n; ++i) {
  98.         for (ul j = 1; j <= k; ++j) {
  99.             ul tmp;
  100.             std::scanf("%u", &tmp);
  101.             t[i][j] = tmp;
  102.         }
  103.     }
  104.     for (ul j = 1; j <= k; ++j) {
  105.         x[j] = d_t(1) / d_t(k);
  106.     }
  107.     start = std::clock();
  108.     while (std::clock() - start < CLOCKS_PER_SEC * 2.9) {
  109.         f(x);
  110.         if (gequal0) {
  111.             std::printf("%.20lf\n", lf(A));
  112.             return 0;
  113.         }
  114.         for (ul j = 1; j <= k; ++j) {
  115.             x[j] += xchange[j];
  116.         }
  117.     }
  118.     std::printf("%.20lf\n", lf(A));
  119.     return 0;
  120. }

H、Yuuki and a problem

注意对于一个可重正整数集，如果其能表示出到，则其能表示出到，且此条件是充要的。于是原题变为次区间查询小于等于指定数的数之和，线段树套树堆即可。不知道为什么会给十五秒的时限。

  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. ul n, q;
  13. std::mt19937_64 rnd;
  15. class node {
  16. public:
  17.     ul val = 0;
  18.     ul cnt = 0;
  19.     ull sum = 0;
  20.     ul lson = 0;
  21.     ul rson = 0;
  22.     ull weight = 0;
  23.     node() {
  24.         weight = rnd();
  25.     }
  26. };
  28. ul stack[1 << 22];
  30. ul remain = 0;
  32. ul tot = 0;
  34. node tree[1 << 22];
  36. void update(ul x)
  37. {
  38.     tree[x].sum = tree[x].val * ull(tree[x].cnt) + tree[tree[x].lson].sum + tree[tree[x].rson].sum;
  39. }
  41. void lrotate(ul& x)
  42. {
  43.     ul y = tree[x].rson;
  44.     tree[x].rson = tree[y].lson;
  45.     tree[y].lson = x;
  46.     update(x);
  47.     update(y);
  48.     x = y;
  49. }
  51. void rrotate(ul& x)
  52. {
  53.     ul y = tree[x].lson;
  54.     tree[x].lson = tree[y].rson;
  55.     tree[y].rson = x;
  56.     update(x);
  57.     update(y);
  58.     x = y;
  59. }
  61. void insert(ul& x, ul v)
  62. {
  63.     if (!x) {
  64.         if (remain) {
  65.             x = stack[remain];
  66.             --remain;
  67.         } else {
  68.             ++tot;
  69.             x = tot;
  70.         }
  71.         tree[x] = node();
  72.         tree[x].val = v;
  73.         tree[x].cnt = 1;
  74.         update(x);
  75.         return;
  76.     }
  77.     if (tree[x].val == v) {
  78.         ++tree[x].cnt;
  79.         update(x);
  80.     } else if (tree[x].val < v) {
  81.         insert(tree[x].rson, v);
  82.         update(x);
  83.         if (tree[x].weight < tree[tree[x].rson].weight) {
  84.             lrotate(x);
  85.         }
  86.     } else if (tree[x].val > v) {
  87.         insert(tree[x].lson, v);
  88.         update(x);
  89.         if (tree[x].weight < tree[tree[x].lson].weight) {
  90.             rrotate(x);
  91.         }
  92.     }
  93. }
  95. void erase(ul& x, ul v)
  96. {
  97.     if (tree[x].val == v) {
  98.         if (tree[x].cnt >= 2) {
  99.             --tree[x].cnt;
  100.             update(x);
  101.             return;
  102.         }
  103.         if (!tree[x].lson || !tree[x].rson) {
  104.             ++remain;
  105.             stack[remain] = x;
  106.             x = tree[x].lson ^ tree[x].rson;
  107.         } else if (tree[tree[x].lson].weight > tree[tree[x].rson].weight) {
  108.             rrotate(x);
  109.             erase(x, v);
  110.         } else {
  111.             lrotate(x);
  112.             erase(x, v);
  113.         }
  114.     } else if (tree[x].val < v) {
  115.         erase(tree[x].rson, v);
  116.         update(x);
  117.     } else if (tree[x].val > v) {
  118.         erase(tree[x].lson, v);
  119.         update(x);
  120.     }
  121. }
  123. ull getsum(ul x, ull t)
  124. {
  125.     if (!x) {
  126.         return 0;
  127.     }
  128.     if (tree[x].val > t) {
  129.         return getsum(tree[x].lson, t);
  130.     } else if (tree[x].val == t) {
  131.         return tree[x].sum - tree[tree[x].rson].sum;
  132.     } else if (tree[x].val < t) {
  133.         return tree[x].sum - tree[tree[x].rson].sum + getsum(tree[x].rson, t);
  134.     }
  135. }
  137. const ul sz = 1 << 18;
  139. ul a[sz];
  141. ul heads[sz << 1];
  143. void seginsert(ul pos, ul v)
  144. {
  145.     for (pos |= sz; pos; pos >>= 1) {
  146.         insert(heads[pos], v);
  147.     }
  148. }
  150. void segerase(ul pos, ul v)
  151. {
  152.     for (pos |= sz; pos; pos >>= 1) {
  153.         erase(heads[pos], v);
  154.     }
  155. }
  157. ull getsum(ul l, ul r, ull t)
  158. {
  159.     ull ret = 0;
  160.     for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
  161.         if (~l & 1) {
  162.             ret += getsum(heads[l ^ 1], t);
  163.         }
  164.         if (r & 1) {
  165.             ret += getsum(heads[r ^ 1], t);
  166.         }
  167.     }
  168.     return ret;
  169. }
  171. int main()
  172. {
  173.     rnd.seed(std::time(0));
  174.     std::scanf("%u%u", &n, &q);
  175.     for (ul i = 1; i <= n; ++i) {
  176.         std::scanf("%u", &a[i]);
  177.         seginsert(i, a[i]);
  178.     }
  179.     for (ul i = 1; i <= q; ++i) {
  180.         ul qt;
  181.         std::scanf("%u", &qt);
  182.         if (qt == 1) {
  183.             ul x, y;
  184.             std::scanf("%u%u", &x, &y);
  185.             segerase(x, a[x]);
  186.             a[x] = y;
  187.             seginsert(x, y);
  188.         } else if (qt == 2) {
  189.             ul l, r;
  190.             std::scanf("%u%u", &l, &r);
  191.             ull t = 1;
  192.             while (true) {
  193.                 ull newt = getsum(l, r, t) + 1;
  194.                 if (newt == t) {
  195.                     break;
  196.                 }
  197.                 t = newt;
  198.             }
  199.             std::printf("%llu\n", t);
  200.         }
  201.     }
  202.     return 0;
  203. }

I、Interesting game

感觉这是个需要很麻烦分类讨论的题，搁置。

J、Loli, Yen-Jen, and a graph problem

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

  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. ul n;
  13. ul f(ul x, ul y, ul n)
  14. {
  15.     return x + y <= n - 1 ? x + y : x + y - n + 1;
  16. }
  18. ul g(ul x, ul n)
  19. {
  20.     return x + x <= n - 1 ? n - x : n + 1 - x;
  21. }
  23. const ul maxn = 1000;
  25. std::vector<ul> roads[(maxn >> 1) + 1];
  27. int main()
  28. {
  29.     std::scanf("%u", &n);
  30.     if (n & 1) {
  31.         for (ul i = 1; i <= ((n - 1) >> 1); ++i) {
  32.             roads[i].push_back(n);
  33.             roads[i].push_back(f(1, i - 1, n));
  34.             for (ul j = 1, gj1 = g(1, n); j <= n - 2; ++j, gj1 = g(gj1, n)) {
  35.                 roads[i].push_back(f(gj1, i - 1, n));
  36.             }
  37.             roads[i].push_back(n);
  38.         }
  39.         for (ul i = 1; i <= n - 1; ++i) {
  40.             if (i + i <= n - 1) {
  41.                 for (ul j = 0; j <= i; ++j) {
  42.                     if (j) {
  43.                         std::putchar(' ');
  44.                     }
  45.                     std::printf("%u", roads[i][j]);
  46.                 }
  47.                 std::putchar('\n');
  48.             } else {
  49.                 for (ul j = n - i; j <= n; ++j) {
  50.                     if (j != n - i) {
  51.                         std::putchar(' ');
  52.                     }
  53.                     std::printf("%u", roads[n - i][j]);
  54.                 }
  55.                 std::putchar('\n');
  56.             }
  57.         }
  58.     } else {
  59.         for (ul i = 1; i <= (n >> 1); ++i) {
  60.             roads[i].push_back(f(1, i - 1, n + 1));
  61.             for (ul j = 1, gj1 = g(1, n + 1); j <= n - 1; ++j, gj1 = g(gj1, n + 1)) {
  62.                 roads[i].push_back(f(gj1, i - 1, n + 1));
  63.             }
  64.         }
  65.         for (ul i = 1; i <= n - 1; ++i) {
  66.             if (i + i <= n - 2) {
  67.                 for (ul j = 0; j <= i; ++j) {
  68.                     if (j) {
  69.                         std::putchar(' ');
  70.                     }
  71.                     std::printf("%u", roads[i][j]);
  72.                 }
  73.                 std::putchar('\n');
  74.             } else if (i <= n - 2) {
  75.                 for (ul j = n - 1 - i; j <= n - 1; ++j) {
  76.                     if (j != n - 1 - i) {
  77.                         std::putchar(' ');
  78.                     }
  79.                     std::printf("%u", roads[n - 1 - i][j]);
  80.                 }
  81.                 std::putchar('\n');
  82.             } else {
  83.                 for (ul j = 0; j <= n - 1; ++j) {
  84.                     if (j) {
  85.                         std::putchar(' ');
  86.                     }
  87.                     std::printf("%u", roads[n >> 1][j]);
  88.                 }
  89.                 std::putchar('\n');
  90.             }
  91.         }
  92.     }
  93.     return 0;
  94. }

K、K-rectangle

用表示解决的覆盖问题所需最小花费，那么显然满足如下递推式：

注意对于固定的，关于构成一不增函数，且会构成一些相等的段，现在考虑其中一段，记其值为，那么在该段当中，假设，那么选优于选当且仅当：
故对于该段中可以使用斜率优化，且斜率只和有关而与处其他信息无关。并且注意到，随增大，关于构成的相等段只会发生合并而不会发生分裂，所以只需要维护一个“逐渐合并的分段凸壳”，并维护出每个分段的最优即可。
现在考虑怎么从这些分段中选出最优分段。考虑两个分段（注意是递减的），其对应和，那么优于当且仅当：
故对于最优段的选取又可以使用斜率优化，但是要注意一个问题，内层的斜率优化过程只有凸壳合并，但外层的斜率优化有从后缀删点过程，这意味着原先不在凸壳上的某些点可能会因为从后缀删点而浮到凸壳上，所以外层的斜率优化要树上斜率优化。

  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;
  10. using pulll = std::pair<ul, ll>;
  12. ul n;
  14. const ul maxn = 4e5;
  16. ll k;
  18. ll x[maxn + 1];
  19. ll y[maxn + 1];
  21. ll f[maxn + 1];
  23. class data1 {
  24. public:
  25.     ul prev = 0;
  26.     ul next = 0;
  27.     ll x = 0;
  28.     ll f = 0;
  29. };
  31. ul tot = 0;
  33. data1 point1[maxn + 1];
  35. class edge_t {
  36. public:
  37.     ul to = 0;
  38.     ul nex = 0;
  39. };
  41. edge_t edge[maxn + maxn + 1];
  42. ul totedge;
  43. ul head[maxn + 1];
  44. ul rhead[maxn + 1];
  45. ul rank[maxn + 1];
  47. void addedge(ul a, ul b)
  48. {
  49.     ++totedge;
  50.     if (!head[a]) {
  51.         head[a] = totedge;
  52.     }
  53.     edge[totedge].to = b;
  54.     if (rhead[a]) {
  55.         edge[rhead[a]].nex = totedge;
  56.     }
  57.     rhead[a] = totedge;
  58. }
  60. ul fa[maxn + 1];
  62. std::vector<pulll> stack;
  64. void getcen(ul curr, ul prev, ul totsz, ul& sz, ul& mnmxsz, ul& mnmxsznid)
  65. {
  66.     sz = 1;
  67.     ul mxsz = 0;
  68.     for (ul eid = head[curr]; eid; eid = edge[eid].nex) {
  69.         ul nex = edge[eid].to;
  70.         if (rank[nex]) {
  71.             continue;
  72.         }
  73.         if (nex == prev) {
  74.             continue;
  75.         }
  76.         ul sonsz;
  77.         getcen(nex, curr, totsz, sonsz, mnmxsz, mnmxsznid);
  78.         mxsz = std::max(mxsz, sonsz);
  79.         sz += sonsz;
  80.     }
  81.     mxsz = std::max(mxsz, totsz - sz);
  82.     if (mnmxsz > mxsz) {
  83.         mnmxsz = mxsz;
  84.         mnmxsznid = curr;
  85.     }
  86. }
  88. void getsz(ul curr, ul prev, ul& sz)
  89. {
  90.     sz = 1;
  91.     for (ul eid = head[curr]; eid; eid = edge[eid].nex) {
  92.         ul nex = edge[eid].to;
  93.         if (rank[nex]) {
  94.             continue;
  95.         }
  96.         if (nex == prev) {
  97.             continue;
  98.         }
  99.         ul sonsz;
  100.         getsz(nex, curr, sonsz);
  101.         sz += sonsz;
  102.     }
  103. }
  105. class hull1 {
  106. public:
  107.     ul left = 0;
  108.     ul right = 0;
  109.     ul ptr = 0;
  110.     ll y = 0;
  111.     void pop_back() {
  112.         if (ptr == right) {
  113.             ptr = point1[right].prev;
  114.         }
  115.         right = point1[right].prev;
  116.         point1[right].next = 0;
  117.     }
  118.     void pop_front() {
  119.         if (ptr == left) {
  120.             ptr = point1[left].next;
  121.         }
  122.         left = point1[left].next;
  123.         point1[left].prev = 0;
  124.     }
  126. };
  128. std::vector<hull1> hulls;
  130. class data2 {
  131. public:
  132.     ll y = 0;
  133.     ll fmxy = 0;
  134. };
  136. data2 point2[maxn + 1];
  138. bool check(const data1& a, const data1& b, const data1& c)
  139. {
  140.     return (b.f - a.f) * (c.x - b.x) >= (c.f - b.f) * (b.x - a.x);
  141. }
  143. bool check(const data2& a, const data2& b, const data2& c)
  144. {
  145.     return (b.fmxy - a.fmxy) * (c.y - b.y) >= (c.fmxy - b.fmxy) * (b.y - a.y);
  146. }
  148. void merge(hull1& a, hull1& b)
  149. {
  150.     ll y = b.y;
  151.     while (true) {
  152.         if (point1[a.right].prev && check(point1[point1[a.right].prev], point1[a.right], point1[b.left])) {
  153.             a.pop_back();
  154.         } else if (point1[b.left].next && check(point1[a.right], point1[b.left], point1[point1[b.left].next])) {
  155.             b.pop_front();
  156.         } else {
  157.             break;
  158.         }
  159.     }
  160.     bool flag = b.left == b.ptr;
  161.     point1[a.right].next = b.left;
  162.     point1[b.left].prev = a.right;
  163.     b.left = a.left;
  164.     if (flag) {
  165.         b.ptr = a.ptr;
  166.         while (point1[b.ptr].next && point1[point1[b.ptr].next].f - point1[b.ptr].f < y * (point1[point1[b.ptr].next].x - point1[b.ptr].x)) {
  167.             b.ptr = point1[b.ptr].next;
  168.         }
  169.     }
  170. }
  172. std::vector<data2> hull2;
  174. ul it;
  176. void search(ul curr, ul rk)
  177. {
  178.     while (it && hull2[it].fmxy - hull2[it - 1].fmxy > (hull2[it].y - hull2[it - 1].y) * (-x[curr] - k)) {
  179.         --it;
  180.     }
  181.     f[curr] = std::min(f[curr], hull2[it].y * (x[curr] + k) + hull2[it].fmxy);
  182.     for (ul eid = head[curr]; eid; eid = edge[eid].nex) {
  183.         ul next = edge[eid].to;
  184.         if (next < curr) {
  185.             continue;
  186.         }
  187.         if (rank[next] > rk) {
  188.             continue;
  189.         }
  190.         search(next, rk);
  191.     }
  192. }
  194. int main()
  195. {
  196.     std::scanf("%u%lld", &n, &k);
  197.     for (ul i = 1; i <= n; ++i) {
  198.         std::scanf("%lld%lld", &x[i], &y[i]);
  199.     }
  200.     stack.push_back(pulll(0, 1e9));
  201.     for (ul i = 1; i <= n; ++i) {
  202.         while (stack.back().second <= y[i]) {
  203.             stack.pop_back();
  204.         }
  205.         fa[i] = stack.back().first;
  206.         stack.push_back(pulll(i, y[i]));
  207.         addedge(i, fa[i]);
  208.         addedge(fa[i], i);
  209.     }
  210.     for (ul i = 0; i <= n; ++i) {
  211.         while (!rank[i]) {
  212.             ul sz;
  213.             getsz(i, 0, sz);
  214.             ul mnmxsz = sz, mnmxsznid;
  215.             getcen(i, -1, sz, sz, mnmxsz, mnmxsznid);
  216.             rank[mnmxsznid] = sz;
  217.         }
  218.     }
  219.     for (ul i = 1; i <= n; ++i) {
  220.         f[i] = 3e12;
  221.     }
  222.     for (ul i = 1; i <= n; ++i) {
  223.         hull1 tmp;
  224.         ++tot;
  225.         tmp.left = tot;
  226.         tmp.right = tot;
  227.         tmp.y = y[i];
  228.         tmp.ptr = tot;
  229.         point1[tot].x = x[i];
  230.         point1[tot].f = f[i - 1];
  231.         while (hulls.size() && hulls.back().y <= y[i]) {
  232.             merge(hulls.back(), tmp);
  233.             hulls.pop_back();
  234.         }
  235.         hulls.push_back(tmp);
  236.         point2[i].y = y[i];
  237.         point2[i].fmxy = point1[tmp.ptr].f - point1[tmp.ptr].x * y[i];
  238.         hull2.resize(0);
  239.         for (ul j = i; j && rank[j] <= rank[i]; j = fa[j]) {
  240.             while (hull2.size() >= 2 && check(hull2[hull2.size() - 2], hull2.back(), point2[j])) {
  241.                 hull2.pop_back();
  242.             }
  243.             hull2.push_back(point2[j]);
  244.         }
  245.         it = hull2.size() - 1;
  246.         search(i, rank[i]);
  247.     }
  248.     std::printf("%lld\n", f[n]);
  249.     return 0;
  250. }

L、Loli, Yen-Jen, and a cool problem

字典树的后缀自动机

  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;
  12. class sam_t {
  13. public:
  14.     ul las;
  15.     class node {
  16.     public:
  17.         ul ch[26];
  18.         ul len = 0;
  19.         ul fa = 0;
  20.         node() {
  21.             std::memset(ch, 0, sizeof(ch));
  22.         }
  23.     };
  24.     std::vector<node> st = std::vector<node>(1e6);
  25.     void add(ul c)
  26.     {
  27.         ul p = las;
  28.         if (st[p].ch[c]) {
  29.             las = st[p].ch[c];
  30.             return;
  31.         }
  32.         ul np = las = st.size();
  33.         st.push_back(node());
  34.         st[np].len = st[p].len + 1;
  35.         for ( ; p && !st[p].ch[c]; p = st[p].fa) {
  36.             st[p].ch[c] = np;
  37.         }
  38.         if (!p) {
  39.             st[np].fa = 1;
  40.         } else {
  41.             ul q = st[p].ch[c];
  42.             if (st[q].len == st[p].len + 1) {
  43.                 st[np].fa = q;
  44.             } else {
  45.                 ul nq = st.size();
  46.                 st.push_back(node());
  47.                 st[nq] = st[q];
  48.                 st[nq].len = st[p].len + 1;
  49.                 st[q].fa = st[np].fa = nq;
  50.                 for ( ; p && st[p].ch[c] == q; p = st[p].fa) {
  51.                     st[p].ch[c] = nq;
  52.                 }
  53.             }
  54.         }
  55.     }
  56.     void init() {
  57.         las = 1;
  58.         st.resize(0);
  59.         st.resize(2);
  60.     }
  61. };
  63. sam_t sam;
  65. const ul maxn = 3e5;
  67. ul n;
  69. ul q;
  71. char s[maxn + 2];
  73. std::vector<ul> sons[maxn + 1];
  75. ul las[maxn + 1];
  77. std::deque<std::pair<ul, ul>> queue;
  79. ul fa[ul(1e6)][20];
  81. ul cnt[ul(1e6)];
  83. std::vector<ul> sons2[ul(1e6)];
  85. ul depth[ul(1e6)];
  87. void search(ul curr)
  88. {
  89.     for (ul t = 1; (1 << t) <= depth[curr]; ++t) {
  90.         fa[curr][t] = fa[fa[curr][t - 1]][t - 1];
  91.     }
  92.     for (ul next : sons2[curr]) {
  93.         fa[next][0] = curr;
  94.         depth[next] = depth[curr] + 1;
  95.         search(next);
  96.         cnt[curr] += cnt[next];
  97.     }
  98. }
  100. int main()
  101. {
  102.     std::scanf("%u%u", &n, &q);
  103.     std::scanf("%s", s + 1);
  104.     for (ul i = 2; i <= n; ++i) {
  105.         ul f;
  106.         std::scanf("%u", &f);
  107.         sons[f].push_back(i);
  108.     }
  109.     sam.init();
  110.     queue.push_back(std::pair<ul, ul>(0, 1));
  111.     las[0] = 1;
  112.     while (queue.size()) {
  113.         auto curr = queue.front();
  114.         queue.pop_front();
  115.         sam.las = las[curr.first];
  116.         sam.add(s[curr.second] - 'A');
  117.         las[curr.second] = sam.las;
  118.         curr.first = curr.second;
  119.         for (ul next : sons[curr.first]) {
  120.             curr.second = next;
  121.             queue.push_back(curr);
  122.         }
  123.     }
  124.     for (ul i = 2; i != sam.st.size(); ++i) {
  125.         sons2[sam.st[i].fa].push_back(i);
  126.     }
  127.     for (ul i = 1; i <= n; ++i) {
  128.         ++cnt[las[i]];
  129.     }
  130.     search(1);
  131.     for (ul i = 1; i <= q; ++i) {
  132.         ul x, l;
  133.         std::scanf("%u%u", &x, &l);
  134.         x = las[x];
  135.         for (ul t = 31 - __builtin_clz(depth[x]); ~t; --t) {
  136.             if (depth[x] >= (1 << t) && sam.st[fa[x][t]].len >= l) {
  137.                 x = fa[x][t];
  138.             }
  139.         }
  140.         std::printf("%u\n", cnt[x]);
  141.     }
  142.     return 0;
  143. }

M、Kill the tree

对每个子树求重心。

  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. ul n;
  13. const ul maxn = 2e5;
  15. std::vector<ul> edges[maxn + 1];
  17. ul sz[maxn + 1];
  19. ul cen[maxn + 1];
  21. ul fa[maxn + 1];
  23. ul type[maxn + 1];
  25. void search(ul curr, ul prev)
  26. {
  27.     sz[curr] = 1;
  28.     cen[curr] = curr;
  29.     for (ul next : edges[curr]) {
  30.         if (next == prev) {
  31.             continue;
  32.         }
  33.         fa[next] = curr;
  34.         search(next, curr);
  35.         if (sz[curr] <= sz[next]) {
  36.             cen[curr] = cen[next];
  37.         }
  38.         sz[curr] += sz[next];
  39.         while (sz[curr] - sz[cen[curr]] > sz[cen[curr]]) {
  40.             cen[curr] = fa[cen[curr]];
  41.         }
  42.     }
  43.     if (sz[curr] - sz[cen[curr]] == sz[cen[curr]]) {
  44.         type[curr] = 2;
  45.     } else {
  46.         type[curr] = 1;
  47.     }
  48. }
  50. int main()
  51. {
  52.     std::scanf("%u", &n);
  53.     for (ul i = 1; i <= n - 1; ++i) {
  54.         ul a, b;
  55.         std::scanf("%u%u", &a, &b);
  56.         edges[a].push_back(b);
  57.         edges[b].push_back(a);
  58.     }
  59.     search(1, 0);
  60.     for (ul i = 1; i <= n; ++i) {
  61.         if (type[i] == 2) {
  62.             std::printf("%u %u\n", std::min(cen[i], fa[cen[i]]), std::max(cen[i], fa[cen[i]]));
  63.         } else {
  64.             std::printf("%u\n", cen[i]);
  65.         }
  66.     }
  67.     return 0;
  68. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注