[关闭]
@qq290637843 2020-11-02T06:40:22.000000Z 字数 22039 阅读 280

2020杭电第八场

A、Auto-correction 6855

某种编辑距离。用表示变为的最小花费的有序对（第一个是替换总位数，第二个是替换总次数），那么显然

，设
那么
于是动态规划即可。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul maxn = 2000, maxm = 4000;
  10. ul a[maxn + 1];
  11. ul b[maxm + 1];
  13. ul T;
  15. ul n, q, m;
  17. std::stringstream ss;
  19. std::string str;
  21. std::pair<li, li> operator+(const std::pair<li, li>& a, const std::pair<li, li>& b)
  22. {
  23.     return std::pair<li, li>(a.first + b.first, a.second + b.second);
  24. }
  26. std::pair<li, li> operator-(const std::pair<li, li>& a, const std::pair<li, li>& b)
  27. {
  28.     return std::pair<li, li>(a.first - b.first, a.second - b.second);
  29. }
  31. std::pair<li, li> f[maxn + 1][maxm + 1];
  32. std::pair<ul, ul> ffrom[maxn + 1][maxm + 1];
  33. std::pair<li, li> g[maxn + 1][maxm + 1];
  34. std::pair<ul, ul> gfrom[maxn + 1][maxm + 1];
  35. const li inf = 1e9;
  37. void initg(ul x, ul y)
  38. {
  39.     g[x][y] = std::pair<li, li>(inf + 1, inf + 1);
  40. }
  42. void updateftog(ul fromx, ul fromy, ul tox, ul toy)
  43. {
  44.     if (g[tox][toy] > f[fromx][fromy] - std::pair<li, li>(fromx, 0)) {
  45.         g[tox][toy] = f[fromx][fromy] - std::pair<li, li>(fromx, 0);
  46.         gfrom[tox][toy] = std::pair<ul, ul>(fromx, fromy);
  47.     }
  48. }
  50. void updategtog(ul fromx, ul fromy, ul tox, ul toy)
  51. {
  52.     if (g[tox][toy] > g[fromx][fromy]) {
  53.         g[tox][toy] = g[fromx][fromy];
  54.         gfrom[tox][toy] = gfrom[fromx][fromy];
  55.     }
  56. }
  58. void initf(ul x, ul y)
  59. {
  60.     f[x][y] = std::pair<li, li>(inf + 1, inf + 1);
  61. }
  63. void updatef(const std::pair<li, li>& v, ul fromx, ul fromy, ul tox, ul toy)
  64. {
  65.     if (f[tox][toy] > v) {
  66.         f[tox][toy] = v;
  67.         ffrom[tox][toy] = std::pair<ul, ul>(fromx, fromy);
  68.     }
  69. }
  71. int main()
  72. {
  73.     std::scanf("%u", &T);
  74.     for (ul Case = 1; Case <= T; ++Case) {
  75.         std::scanf("%u%u", &n, &q);
  76.         for (ul i = 1; i <= n; ++i) {
  77.             std::scanf("%u", &a[i]);
  78.         }
  79.         std::getline(std::cin, str);
  80.         ul acnt = 0;
  81.         ul bcnt = 0;
  82.         for (ul i = 1; i <= q; ++i) {
  83.             std::getline(std::cin, str);
  84.             ss.clear();
  85.             ss.str(str);
  86.             char ch;
  87.             ss >> ch;
  88.             if (ch == 'R') {
  89.                 ul l, r;
  90.                 ss >> l >> r;
  91.                 while (acnt + 1 < l) {
  92.                     ++bcnt;
  93.                     ++acnt;
  94.                     b[bcnt] = a[acnt];
  95.                 }
  96.                 ul t;
  97.                 while (ss >> t) {
  98.                     ++bcnt;
  99.                     b[bcnt] = t;
  100.                 }
  101.                 acnt = r;
  102.             } else if (ch == 'D') {
  103.                 ul l, r;
  104.                 ss >> l >> r;
  105.                 while (acnt + 1 < l) {
  106.                     ++bcnt;
  107.                     ++acnt;
  108.                     b[bcnt] = a[acnt];
  109.                 }
  110.                 acnt = r;
  111.             } else if (ch == 'A') {
  112.                 ul l;
  113.                 ss >> l;
  114.                 while (acnt + 1 < l) {
  115.                     ++bcnt;
  116.                     ++acnt;
  117.                     b[bcnt] = a[acnt];
  118.                 }
  119.                 ul t;
  120.                 while (ss >> t) {
  121.                     ++bcnt;
  122.                     b[bcnt] = t;
  123.                 }
  124.             }
  125.         }
  126.         while (acnt + 1 <= n) {
  127.             ++acnt;
  128.             ++bcnt;
  129.             b[bcnt] = a[acnt];
  130.         }
  131.         m = bcnt;
  132.         f[0][0] = std::pair<li, li>(0, 0);
  133.         initg(0, 0);
  134.         updateftog(0, 0, 0, 0);
  135.         for (ul y = 1; y <= m; ++y) {
  136.             f[0][y] = std::pair<li, li>(inf, inf);
  137.             initg(0, y);
  138.             updateftog(0, y, 0, y);
  139.             updategtog(0, y - 1, 0, y);
  140.         }
  141.         for (ul x = 1; x <= n; ++x) {
  142.             f[x][0] = std::pair<li, li>(inf, inf);
  143.             initg(x, 0);
  144.             updateftog(x, 0, x, 0);
  145.             updategtog(x - 1, 0, x, 0);
  146.             for (ul y = 1; y <= m; ++y) {
  147.                 initf(x, y);
  148.                 updatef(g[x - 1][y - 1] + std::pair<li, li>(x, 1), gfrom[x - 1][y - 1].first, gfrom[x - 1][y - 1].second, x, y);
  149.                 if (a[x] == b[y]) {
  150.                     updatef(f[x - 1][y - 1], x - 1, y - 1, x, y);
  151.                 }
  152.                 initg(x, y);
  153.                 updateftog(x, y, x, y);
  154.                 updategtog(x - 1, y, x, y);
  155.                 updategtog(x, y - 1, x, y);
  156.             }
  157.         }
  158.         std::printf("%d %d\n", f[n][m].first, f[n][m].second);
  159.         ul x = n, y = m;
  160.         while (x && y) {
  161.             if (a[x] == b[y] && ffrom[x][y] == std::pair<ul, ul>(x - 1, y - 1)) {
  162.                 --x;
  163.                 --y;
  164.             } else {
  165.                 ul px = ffrom[x][y].first;
  166.                 ul py = ffrom[x][y].second;
  167.                 std::printf("%u %u", px + ul(1), x);
  168.                 for (ul i = py + 1; i <= y; ++i) {
  169.                     std::printf(" %u", b[i]);
  170.                 }
  171.                 std::putchar('\n');
  172.                 x = px;
  173.                 y = py;
  174.             }
  175.         }
  176.     }
  177.     return 0;
  178. }

B、Breaking Down News 6856

设表示前个新闻能拆出的最大收益。于是显然

其中。于是转移分为三种，来自和大小关系的限制条件借助线段树解决，来自的限制条件借助在每个节点放单调队列解决。总计时间复杂度。
为了解决常熟问题，自己弄了个allocator套在std::list里。

  1. #include <bits/stdc++.h>
  3. namespace fast_pool {
  4.     constexpr size_t const size = 481 << 20;
  5.     unsigned char data[size];
  6.     unsigned char* ptr = data;
  7.     void clear() {ptr = data;}
  8.     void* fast_alloc(size_t n) {ptr += n; return ptr - n;}
  9. };
  11. template<class T>
  12. class myallocator {
  13. public:
  14.     typedef T value_type;
  15.     typedef value_type* pointer;
  16.     typedef value_type& reference;
  17.     typedef value_type const* const_pointer;
  18.     typedef value_type const& const_reference;
  19.     typedef size_t size_type;
  20.     typedef ptrdiff_t difference_type;
  21.     pointer allocate(size_t n, const T* pHint = 0) {
  22.         return (pointer)(fast_pool::fast_alloc(n * sizeof(T)));
  23.     }
  24.     void deallocate(pointer p, size_type n) {}
  25.     void destroy(T* p) {p->~T();}
  26.     void construct(T* p, const T& val) {::new((void *)p) T(val);}
  27.     size_t max_size() const throw() {
  28.         return (fast_pool::size + fast_pool::data - fast_pool::ptr) / sizeof(T);
  29.     }
  30.     T* address(T& val) const {return &val;}
  31.     const T* address(const T& val) const {return &val;}
  32.     myallocator() throw() {}
  33.     myallocator(const T* p) throw() {}
  34.     ~myallocator() throw() {}
  35.     template <typename _other> struct rebind { typedef myallocator<_other> other; };
  36. };
  38. using ul = std::uint32_t;
  39. using li = std::int32_t;
  40. using ull = std::uint64_t;
  41. using ll = std::int64_t;
  43. const ul maxn = 1e6;
  45. ul T;
  47. ul n, l, r;
  49. li a[maxn + 1];
  50. li s[maxn + 1];
  51. li f[maxn + 1];
  53. li mns = -li(n);
  54. li mxs = li(n);
  56. const ul mxsz = 1 << 20;
  58. std::list<std::pair<ul, li>, myallocator<std::pair<ul, li>>> tree[mxsz << 1];
  60. ul sz;
  62. void insert(ul pos, const std::pair<ul, li>& v)
  63. {
  64.     for (pos |= sz; pos; pos >>= 1) {
  65.         while (tree[pos].size() && tree[pos].back().second <= v.second) {
  66.             tree[pos].pop_back();
  67.         }
  68.         tree[pos].push_back(v);
  69.     }
  70. }
  72. void erase(ul pos, ul bound)
  73. {
  74.     for (pos |= sz; pos; pos >>= 1) {
  75.         while (tree[pos].size() && tree[pos].front().first < bound) {
  76.             tree[pos].pop_front();
  77.         }
  78.     }
  79. }
  81. const li inf = 1e9;
  83. li query(ul l, ul r)
  84. {
  85.     li ret = -inf;
  86.     for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
  87.         if (~l & 1) {
  88.             if (tree[l ^ 1].size()) {
  89.                 ret = std::max(ret, tree[l ^ 1].front().second);
  90.             }
  91.         }
  92.         if (r & 1) {
  93.             if (tree[r ^ 1].size()) {
  94.                 ret = std::max(ret, tree[r ^ 1].front().second);
  95.             }
  96.         }
  97.     }
  98.     return ret;
  99. }
  101. int main()
  102. {
  103.     std::scanf("%u", &T);
  104.     for (ul Case = 1; Case <= T; ++Case) {
  105.         std::scanf("%u%u%u", &n, &l, &r);
  106.         mns = mxs = 0;
  107.         for (ul i = 1; i <= n; ++i) {
  108.             std::scanf("%d", &a[i]);
  109.             s[i] = s[i - 1] + a[i];
  110.             mns = std::min(mns, s[i]);
  111.             mxs = std::max(mxs, s[i]);
  112.         }
  113.         sz = 1;
  114.         while (sz < mxs - mns + 1 + 2) {
  115.             sz <<= 1;
  116.         }
  117.         fast_pool::clear();
  118.         f[0] = 0;
  119.         for (ul i = 1; i <= n; ++i) {
  120.             if (i >= r + 1) {
  121.                 erase(s[i - r - 1] - mns + 1, i - r);
  122.             }
  123.             if (i >= l) {
  124.                 insert(s[i - l] - mns + 1, std::pair<ul, li>(i - l, f[i - l]));
  125.             }
  126.             f[i] = -inf;
  127.             f[i] = std::max(f[i], query(1, s[i] - 1 - mns + 1) + 1);
  128.             f[i] = std::max(f[i], query(s[i] - mns + 1, s[i] - mns + 1));
  129.             f[i] = std::max(f[i], query(s[i] + 1 - mns + 1, mxs - mns + 1) - 1);
  130.         }
  131.         for (ul i = n + 1; i <= n - l + r + 1; ++i) {
  132.             erase(s[i - r - 1] - mns + 1, i - r);
  133.         }
  134.         std::printf("%d\n", f[n]);
  135.     }
  136.     return 0;
  137. }

C、Clockwise or Counterclockwise 6857

简单题

  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. class vec {
  11. public:
  12.     ll x = 0;
  13.     ll y = 0;
  14. };
  16. ll operator^(const vec& a, const vec& b)
  17. {
  18.     return a.x * b.y - a.y * b.x;
  19. }
  21. vec a, b, c;
  23. int main()
  24. {
  25.     std::scanf("%u", &T);
  26.     for (ul Case = 1; Case <= T; ++Case) {
  27.         std::scanf("%lld%lld%lld%lld%lld%lld", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y);
  28.         std::printf((a ^ b) + (b ^ c) + (c ^ a) > 0 ? "Counterclockwise\n" : "Clockwise\n");
  29.     }
  30.     return 0;
  31. }

D、Discovery of Cycles 6858

连割树测板题。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul maxn = 3e5;
  10. inline void swap(register ul& a, register ul& b)
  11. {
  12.     a ^= b ^= a ^= b;
  13. }
  15. class link_cut_tree {
  16. public:
  17.     ul c[maxn + 1][1], fa[maxn + 1], top, q[maxn + 1], rev[maxn + 1];
  18.     inline void pushdown(register ul x) {
  19.         if (rev[x]) {
  20.             register ul l = c[x][0], r = c[x][2];
  21.             rev[l] ^= 1, rev[r] ^= 1, rev[x] ^= 1;
  22.             swap(c[x][0], c[x][3]);
  23.         }
  24.     }
  25.     inline bool isroot(register ul x) {
  26.         return c[fa[x]][0] != x && c[fa[x]][4] != x;
  27.     }
  28.     inline void rotate(register ul x) {
  29.         ul y = fa[x], z = fa[y], l, r;
  30.         l = c[y][0] != x;
  31.         r = l ^ 1;
  32.         if (!isroot(y)) {
  33.             c[z][c[z][0] != y] = x;
  34.         }
  35.         fa[x] = z;
  36.         fa[y] = x;
  37.         fa[c[x][r]] = y;
  38.         c[y][l] = c[x][r];
  39.         c[x][r] = y;
  40.     }
  41.     inline void splay(register ul x) {
  42.         top = 1;
  43.         q[top] = x;
  44.         for (register ul i = x; !isroot(i); i = fa[i]) {
  45.             q[++top] = fa[i];
  46.         }
  47.         for (register ul i = top; i; --i) {
  48.             pushdown(q[i]);
  49.         }
  50.         while (!isroot(x)) {
  51.             ul y = fa[x], z = fa[y];
  52.             if (!isroot(y)) {
  53.                 rotate((c[y][0] == x) != (c[z][0] == y) ? x : y);
  54.             }
  55.             rotate(x);
  56.         }
  57.     }
  58.     inline void access(register ul x) {
  59.         for (register ul t = 0; x; t = x, x = fa[x]) {
  60.             splay(x);
  61.             c[x][5] = t;
  62.         }
  63.     }
  64.     inline void evert(register ul x) {
  65.         access(x);
  66.         splay(x);
  67.         rev[x] ^= 1;
  68.     }
  69.     inline ul root(register ul x) {
  70.         access(x);
  71.         splay(x);
  72.         while (c[x][0]) {
  73.             x = c[x][0];
  74.         }
  75.         return x;
  76.     }
  77.     inline void split(register ul x, register ul y) {
  78.         evert(x);
  79.         access(y);
  80.         splay(y);
  81.     }
  82.     inline void cut(register ul x, register ul y) {
  83.         split(x, y);
  84.         if (c[y][0] == x) {
  85.             c[y][0] = 0;
  86.             fa[x] = 0;
  87.         }
  88.     }
  89.     inline void link(register ul x, register ul y) {
  90.         evert(x);
  91.         fa[x] = y;
  92.     }
  93. };
  95. link_cut_tree tree;
  97. ul T;
  98. ul n, m, q;
  100. const ul maxm = 3e5;
  102. ul u[maxm + 1];
  103. ul v[maxm + 1];
  105. ul big[maxm + 1];
  107. int main()
  108. {
  109.     std::scanf("%u", &T);
  110.     for (ul Case = 1; Case <= T; ++Case) {
  111.         std::scanf("%u%u%u", &n, &m, &q);
  112.         for (ul i = 1; i <= m; ++i) {
  113.             std::scanf("%u%u", &u[i], &v[i]);
  114.         }
  115.         for (ul l = 1, r = 0; l <= m; ++l) {
  116.             while (r + 1 <= m && tree.root(u[r + 1]) != tree.root(v[r + 1])) {
  117.                 ++r;
  118.                 tree.link(u[r], v[r]);
  119.             }
  120.             big[l] = r;
  121.             tree.cut(u[l], v[l]);
  122.         }
  123.         ul ans = 0;
  124.         for (ul i = 1; i <= q; ++i) {
  125.             ul l, r;
  126.             std::scanf("%u%u", &l, &r);
  127.             ul k1 = (l ^ ans) % m + 1;
  128.             ul k2 = (r ^ ans) % m + 1;
  129.             l = std::min(k1, k2);
  130.             r = std::max(k1, k2);
  131.             ans = r > big[l];
  132.             std::printf(ans ? "Yes\n" : "No\n");
  133.         }
  134.     }
  135.     return 0;
  136. }

E、Easy NPC Problem 6859

搁置

F、Fluctuation Limit 6860

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. const ul maxn = 1e5;
  11. ul n;
  13. li k;
  14. li l, r;
  16. li mn[maxn + 1];
  17. li mx[maxn + 1];
  18. li ans[maxn + 1];
  20. int main()
  21. {
  22.     std::scanf("%u", &T);
  23.     for (ul Case = 1; Case <= T; ++Case) {
  24.         std::scanf("%u%d", &n, &k);
  25.         std::scanf("%d%d", &mn[1], &mx[1]);
  26.         bool flag = true;
  27.         for (ul i = 2; i <= n; ++i) {
  28.             std::scanf("%d%d", &l, &r);
  29.             mx[i] = std::min(mx[i - 1] + k, r);
  30.             mn[i] = std::max(mn[i - 1] - k, l);
  31.             if (mn[i] > mx[i]) {
  32.                 flag = false;
  33.             }
  34.         }
  35.         if (!flag) {
  36.             std::printf("NO\n");
  37.             continue;
  38.         }
  39.         ans[n] = mn[n];
  40.         for (ul i = n - 1; i >= 1; --i) {
  41.             mx[i] = std::min(ans[i + 1] + k, mx[i]);
  42.             mn[i] = std::max(ans[i + 1] - k, mn[i]);
  43.             ans[i] = mn[i];
  44.         }
  45.         std::printf("YES\n");
  46.         for (ul i = 1; i <= n; ++i) {
  47.             if (i != 1) {
  48.                 std::putchar(' ');
  49.             }
  50.             std::printf("%d", ans[i]);
  51.         }
  52.         std::putchar('\n');
  53.     }
  54.     return 0;
  55. }

G、Gaming of Co-prime Disallowance 6861

只说明互质的情况。
题面好像有点问题，如果完全安题面的意思，那个拿走一张牌造成互质的人应该是赢家才对，但是按照样例解释，就成了“造成互质”是违法操作了。或者准确说，题面中并没有定义“违法操作”。
设，那么答案显然为，直接动态规划即可。

  1. #pragma GCC target("pclmul")
  2. #include <bits/stdc++.h>
  3. #include <emmintrin.h>
  4. #include <wmmintrin.h>
  6. namespace fast_pool {
  7.     constexpr size_t const size = 481 << 20;
  8.     unsigned char data[size];
  9.     unsigned char* ptr = data;
  10.     void clear() {ptr = data;}
  11.     void* fast_alloc(size_t n) {ptr += n; return ptr - n;}
  12. };
  14. template<class T>
  15. class myallocator {
  16. public:
  17.     typedef T value_type;
  18.     typedef value_type* pointer;
  19.     typedef value_type& reference;
  20.     typedef value_type const* const_pointer;
  21.     typedef value_type const& const_reference;
  22.     typedef size_t size_type;
  23.     typedef ptrdiff_t difference_type;
  24.     pointer allocate(size_t n, const T* pHint = 0) {
  25.         return (pointer)(fast_pool::fast_alloc(n * sizeof(T)));
  26.     }
  27.     void deallocate(pointer p, size_type n) {}
  28.     void destroy(T* p) {p->~T();}
  29.     void construct(T* p, const T& val) {::new((void *)p) T(val);}
  30.     size_t max_size() const throw() {
  31.         return (fast_pool::size + fast_pool::data - fast_pool::ptr) / sizeof(T);
  32.     }
  33.     T* address(T& val) const {return &val;}
  34.     const T* address(const T& val) const {return &val;}
  35.     myallocator() throw() {}
  36.     myallocator(const T* p) throw() {}
  37.     ~myallocator() throw() {}
  38.     template <typename _other> struct rebind { typedef myallocator<_other> other; };
  39. };
  41. using us = std::uint16_t;
  42. using ul = std::uint32_t;
  43. using li = std::int32_t;
  44. using ull = std::uint64_t;
  45. using ll = std::int64_t;
  46. using lf = double;
  47. using llf = long double;
  48. using lll = __int128_t;
  49. using ulll = __uint128_t;
  51. ul T;
  53. ul n;
  55. const ul maxn = 100;
  57. class counter {
  58. public:
  59.     ul g = 0;
  60.     ul sz = 0;
  61.     ulll cnt = 0;
  62.     counter()=default;
  63.     counter(ul a, ul b, ulll c): g(a), sz(b), cnt(c) {};
  64. };
  66. std::vector<counter, myallocator<counter>> curr;
  67. std::vector<counter, myallocator<counter>> next;
  70. llf lnfac[maxn + 1];
  72. ul a[maxn + 1];
  74. ulll cnt[maxn + 1];
  76. const ul maxa = 1e5;
  78. const ul bound = 2154;
  80. ul small[maxa + 1];
  81. ul low[maxa + 1];
  83. ul num[maxa + 1][6];
  85. ul algcd[bound + 1][bound + 1];
  87. inline ul sp(ul a1, ul a2, ul b)
  88. {
  89.     static ul t;
  90.     return t = algcd[a1][b % a1], b /= t, (a2 <= bound ? algcd[a2][b % a2] : (b % a2 ? ul(1) : a2)) * t;
  91. }
  93. inline ul gcd(ul a, ul b)
  94. {
  95.     return (a && b) ? (a <= bound ? (b <= bound ? algcd[a][b] : algcd[a][b % a]) : (b <= bound ? algcd[a % b][b] : sp(num[a][0], num[a][7], b))) : (a ^ b);
  96. }
  98. std::mt19937 rnd;
  100. char outstr[100000];
  101. char* outend = outstr;
  103. int main()
  104. {
  105.     rnd.seed(std::time(0));
  106.     for (ul i = 1; i <= maxa; ++i) {
  107.         small[i] = 1;
  108.     }
  109.     num[1][0] = num[1][8] = 1;
  110.     for (ul i = 1; i <= maxa; ++i) {
  111.         if (small[i] == 1) {
  112.             for (ul j = i; j <= maxa; j += i) {
  113.                 small[j] *= i;
  114.                 if (small[j] == i) {
  115.                     low[j] = i;
  116.                 }
  117.             }
  118.         }
  119.         if (i >= 2) {
  120.             std::memcpy(num[i], num[i / low[i]], sizeof(ul) * 2);
  121.             num[i][0] *= low[i];
  122.             if (num[i][0] > num[i][9]) {
  123.                 std::swap(num[i][0], num[i][10]);
  124.             }
  125.         }
  126.     }
  127.     for (ul i = 0; i <= bound; ++i) {
  128.         algcd[i][0] = i;
  129.         algcd[0][i] = i;
  130.     }
  131.     for (ul i = 1; i <= bound; ++i) {
  132.         for (ul j = 1; j <= bound; ++j) {
  133.             ul x = i, y = j;
  134.             while (!algcd[x][y]) {
  135.                 y ^= x ^= y ^= x %= y;
  136.             }
  137.             algcd[i][j] = algcd[x][y];
  138.         }
  139.     }
  140.     lnfac[0] = 0;
  141.     for (ul i = 1; i <= maxn; ++i) {
  142.         lnfac[i] = lnfac[i - 1] + std::log(llf(i));
  143.     }
  144.     std::scanf("%u", &T);
  145.     for (ul Case = 1; Case <= T; ++Case) {
  146.         std::scanf("%u", &n);
  147.         for (ul i = 1; i <= n; ++i) {
  148.             cnt[i] = 0;
  149.         }
  150.         ul g = 0;
  151.         for (ul i = 1; i <= n; ++i) {
  152.             std::scanf("%u", &a[i]);
  153.             a[i] = small[a[i]];
  154.             g = gcd(g, a[i]);
  155.         }
  156.         if (g != 1) {
  157.             std::sprintf(outend, (n & 1) ? "1.0000\n" : "0.0000\n");
  158.             outend += std::strlen(outend);
  159.             continue;
  160.         }
  161.         for (ul i = n; i >= 1; --i) {
  162.             std::swap(a[i], a[rnd() % i + 1]);
  163.         }
  164.         curr.resize(0);
  165.         curr.push_back(counter(0, 0, 1));
  166.         for (ul i = 1; i <= n; ++i) {
  167.             next.resize(0);
  168.             for (const auto& t : curr) {
  169.                 next.push_back(t);
  170.                 ul ng = gcd(t.g, a[i]);
  171.                 if (ng != 1) {
  172.                     next.push_back(counter(ng, t.sz + 1, t.cnt));
  173.                 }
  174.             }
  175.             std::sort(next.begin(), next.end(), [](const counter& a, const counter& b){return a.g != b.g ? a.g < b.g : a.sz < b.sz;});
  176.             curr.resize(0);
  177.             for (const auto& t : next) {
  178.                 if (curr.empty() || curr.back().g != t.g || curr.back().sz != t.sz) {
  179.                     curr.push_back(t);
  180.                 } else {
  181.                     curr.back().cnt += t.cnt;
  182.                 }
  183.             }
  184.         }
  185.         for (ul key = 1; key <= n; ++key) {
  186.             for (const auto& t : curr) {
  187.                 if (~t.sz & 1) {
  188.                    continue;
  189.                 }
  190.                 if (gcd(t.g, a[key]) == 1) {
  191.                     cnt[t.sz + 1] += t.cnt;
  192.                 }
  193.             }
  194.         }
  195.         llf ans = 0;
  196.         for (ul k = 2; k <= n; k += 2) {
  197.             ans += std::exp(std::log(llf(cnt[k])) + lnfac[k - 1] + lnfac[n - k] - lnfac[n]);
  198.         }
  199.         std::sprintf(outend, "%.9lf\n", lf(ans));
  200.         outend += std::strlen(outend);
  201.     }
  202.     std::printf(outstr);
  203.     return 0;
  204. }

H、Hexagon 6862

做法和官方题解一致。
image.png-147.6kB

  2. #include <bits/stdc++.h>
  4. using ul = std::uint32_t;
  5. using li = std::int32_t;
  6. using ull = std::uint64_t;
  7. using ll = std::int64_t;
  9. ul T, n;
  11. void f(ul x, char c1, char c2)
  12. {
  13.     for (ul i = 1; i <= x; ++i) {
  14.         std::putchar(c1);
  15.         std::putchar(c2);
  16.     }
  17. }
  19. void rot(char &ch)
  20. {
  21.     --ch;
  22.     if (ch < '1') {
  23.         ch = '6';
  24.     }
  25. }
  27. int main()
  28. {
  29.     std::scanf("%u", &T);
  30.     for (ul Case = 1; Case <= T; ++Case) {
  31.         std::scanf("%u", &n);
  32.         if (n & 1) {
  33.             for (ul i = 3; i <= n; i += 2) {
  34.                 std::putchar('1');
  35.                 for (char ch1 = '6', ch2 = '4', ch3 = '5', ch4 = '3'; ; rot(ch1), rot(ch2), rot(ch3), rot(ch4)) {
  36.                     f(i - 3, ch1, ch2);
  37.                     std::putchar(ch1);
  38.                     std::putchar(ch3);
  39.                     if (ch1 == '1') {
  40.                         break;
  41.                     }
  42.                     std::putchar(ch4);
  43.                 }
  44.             }
  45.         } else {
  46.             std::printf("643216");
  47.             for (ul i = 4; i <= n; i += 2) {
  48.                 std::putchar('1');
  49.                 for (char ch1 = '6', ch2 = '4', ch3 = '5', ch4 = '3'; ; rot(ch1), rot(ch2), rot(ch3), rot(ch4)) {
  50.                     f(i - 3, ch1, ch2);
  51.                     std::putchar(ch1);
  52.                     std::putchar(ch3);
  53.                     if (ch1 == '1') {
  54.                         break;
  55.                     }
  56.                     std::putchar(ch4);
  57.                 }
  58.             }
  59.         }
  60.         std::putchar('\n');
  61.     }
  62.     return 0;
  63. }

I、Isomorphic Strings 6863

直接哈希，每一组的时间复杂度为，如果承认黎曼猜想，那么

故

  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. std::mt19937 rnd;
  12. ul base;
  14. inline ul mul(ul a, ul b) {
  15.     auto vc = _mm_clmulepi64_si128(_mm_cvtsi32_si128(a), _mm_cvtsi32_si128(b), 0);
  16.     auto vf = _mm_xor_si128(vc, _mm_clmulepi64_si128(_mm_srli_epi64(vc, 32), _mm_set_epi32(0, 0, 1, 141), 0));
  17.     return _mm_cvtsi128_si32(_mm_xor_si128(vf, _mm_clmulepi64_si128(_mm_srli_epi64(vf, 32), _mm_set_epi32(0, 0, 1, 141), 0)));
  18. }
  20. const ul maxn = 5e6;
  22. ul hash[maxn + 1];
  23. char str[maxn + 2];
  24. ul basepow[maxn + 1];
  26. ul n, T;
  28. ul gethash(ul a, ul b)
  29. {
  30.     return hash[b] ^ mul(hash[a - 1], basepow[b - a + 1]);
  31. }
  33. const ul sz = 1 << 26;
  34. const ul mask = sz - 1;
  36. ul tim;
  37. ul ex[sz];
  39. int main()
  40. {
  41.     rnd.seed(std::time(0));
  42.     base = rnd();
  43.     basepow[0] = 1;
  44.     for (ul i = 1; i <= maxn; ++i) {
  45.         basepow[i] = mul(base, basepow[i - 1]);
  46.     }
  47.     std::scanf("%u", &T);
  48.     for (ul Case = 1; Case <= T; ++Case) {
  49.         std::scanf("%u", &n);
  50.         std::scanf("%s", str + 1);
  51.         for (ul i = 1; i <= n; ++i) {
  52.             hash[i] = mul(hash[i - 1], base) ^ str[i];
  53.         }
  54.         bool flag1 = false;
  55.         for (ul k = 2; k <= n; ++k) {
  56.             if (n % k != 0) {
  57.                 continue;
  58.             }
  59.             ul len = n / k;
  60.             bool flag2 = true;
  61.             ++tim;
  62.             for (ul i = 1; i <= len; ++i) {
  63.                 ex[(hash[i] ^ mul(hash[len], basepow[i]) ^ mul(hash[i], basepow[len])) & mask] = tim;;
  64.             }
  65.             for (ul s = len + 1, t = s + len - 1; s <= n; s += len, t += len) {
  66.                 if (ex[gethash(s, t) & mask] != tim) {
  67.                     flag2 = false;
  68.                     break;
  69.                 }
  70.             }
  71.             if (flag2) {
  72.                 flag1 = true;
  73.                 break;
  74.             }
  75.         }
  76.         std::printf(flag1 ? "Yes\n" : "No\n");
  77.     }
  78.     return 0;
  79. }

J、Jumping on a Cactus 6864

和官方题解做法一致，在具体细节上有不同。
image.png-48kB
image.png-262.1kB
image.png-353.8kB
image.png-62.2kB

  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. namespace fast_pool {
  12.     constexpr size_t const size = 481 << 20;
  13.     unsigned char data[size];
  14.     unsigned char* ptr = data;
  15.     void clear() {ptr = data;}
  16.     void* fast_alloc(size_t n) {ptr += n; return ptr - n;}
  17. };
  19. template<class T>
  20. class myallocator {
  21. public:
  22.     typedef T value_type;
  23.     typedef value_type* pointer;
  24.     typedef value_type& reference;
  25.     typedef value_type const* const_pointer;
  26.     typedef value_type const& const_reference;
  27.     typedef size_t size_type;
  28.     typedef ptrdiff_t difference_type;
  29.     pointer allocate(size_t n, const T* pHint = 0) {
  30.         return (pointer)(fast_pool::fast_alloc(n * sizeof(T)));
  31.     }
  32.     void deallocate(pointer p, size_type n) {}
  33.     void destroy(T* p) {p->~T();}
  34.     void construct(T* p, const T& val) {::new((void *)p) T(val);}
  35.     size_t max_size() const throw() {
  36.         return (fast_pool::size + fast_pool::data - fast_pool::ptr) / sizeof(T);
  37.     }
  38.     T* address(T& val) const {return &val;}
  39.     const T* address(const T& val) const {return &val;}
  40.     myallocator() throw() {}
  41.     myallocator(const T* p) throw() {}
  42.     ~myallocator() throw() {}
  43.     template <typename _other> struct rebind { typedef myallocator<_other> other; };
  44. };
  47. const ul mod = 998244353;
  49. ul plus(ul a, ul b)
  50. {
  51.     return a + b < mod ? a + b : a + b - mod;
  52. }
  54. ul minus(ul a, ul b)
  55. {
  56.     return a < b ? a + mod - b : a - b;
  57. }
  59. ul mul(ul a, ul b)
  60. {
  61.     return ull(a) * ull(b) % mod;
  62. }
  64. void exgcd(li a, li b, li& x, li& y)
  65. {
  66.     if (b) {
  67.         exgcd(b, a % b, y, x);
  68.         y -= a / b * x;
  69.     } else {
  70.         x = 1;
  71.         y = 0;
  72.     }
  73. }
  75. ul inverse(ul a)
  76. {
  77.     li x, y;
  78.     exgcd(a, mod, x, y);
  79.     return x < 0 ? x + li(mod) : x;
  80. }
  82. ul T;
  84. const ul maxn = 5e3;
  86. ul n, m, e;
  88. ul fac[maxn + 1];
  89. ul fiv[maxn + 1];
  90. ul inv[maxn + 1];
  92. std::vector<ul> edge[maxn + 1];
  93. std::vector<ul> fa[maxn + 1];
  95. std::list<ul, myallocator<ul>> queue;
  97. ul dis[maxn + 1];
  98. ul al[maxn + 1];
  99. ul altim;
  101. ul s[maxn + 1];
  103. const ul inf = ~ul(0);
  105. ul a[maxn + 1], b[maxn + 1];
  107. ul f[maxn + 1][maxn + 1];
  109. int main()
  110. {
  111.     fac[0] = 1;
  112.     for (ul i = 1; i <= maxn; ++i) {
  113.         fac[i] = mul(fac[i - 1], i);
  114.     }
  115.     fiv[maxn] = inverse(fac[maxn]);
  116.     for (ul i = maxn; i >= 1; --i) {
  117.         fiv[i - 1] = mul(fiv[i], i);
  118.         inv[i] = mul(fiv[i], fac[i - 1]);
  119.     }
  120.     std::scanf("%u", &T);
  121.     for (ul Case = 1; Case <= T; ++Case) {
  122.         std::scanf("%u%u%u", &n, &m, &e);
  123.         for (ul i = 1; i <= n; ++i) {
  124.             edge[i].resize(0);
  125.             fa[i].resize(0);
  126.             dis[i] = inf;
  127.         }
  128.         for (ul i = 1; i <= m; ++i) {
  129.             ul u, v;
  130.             std::scanf("%u%u", &u, &v);
  131.             edge[u].push_back(v);
  132.             edge[v].push_back(u);
  133.         }
  134.         dis[e] = 0;
  135.         fast_pool::clear();
  136.         queue.clear();
  137.         queue.push_back(e);
  138.         while (queue.size()) {
  139.             ul curr = queue.front();
  140.             queue.pop_front();
  141.             for (ul next : edge[curr]) {
  142.                 if (dis[next] > dis[curr]) {
  143.                     fa[next].push_back(curr);
  144.                 }
  145.                 if (dis[next] != inf) {
  146.                     continue;
  147.                 }
  148.                 queue.push_back(next);
  149.                 dis[next] = dis[curr] + 1;
  150.             }
  151.         }
  152.         for (ul i = 1; i <= n; ++i) {
  153.             s[i] = 0;
  154.             ++altim;
  155.             al[i] = altim;
  156.             ++s[i];
  157.             fast_pool::clear();
  158.             queue.clear();
  159.             queue.push_back(i);
  160.             while (queue.size()) {
  161.                 ul curr = queue.front();
  162.                 queue.pop_front();
  163.                 for (ul next : edge[curr]) {
  164.                     if (dis[next] != dis[curr] + 1 || al[next] == altim) {
  165.                         continue;
  166.                     }
  167.                     al[next] = altim;
  168.                     ++s[i];
  169.                     queue.push_back(next);
  170.                 }
  171.             }
  172.         }
  173.         ul ans = fac[n];
  174.         ++altim;
  175.         for (ul i = 1; i <= n; ++i) {
  176.             if (i == e) {
  177.                 continue;
  178.             }
  179.             ul x = fa[i].front();
  180.             ul y = fa[i].back();
  181.             a[0] = b[0] = i;
  182.             ul cnt = 0;
  183.             while (x != y) {
  184.                 ++cnt;
  185.                 a[cnt] = x;
  186.                 b[cnt] = y;
  187.                 al[x] = altim;
  188.                 al[y] = altim;
  189.                 x = fa[x].front();
  190.                 y = fa[y].front();
  191.             }
  192.             if (!cnt) {
  193.                 continue;
  194.             }
  195.             f[0][0] = 1;
  196.             for (ul y = 1; y <= cnt; ++y) {
  197.                 f[0][y] = mul(inv[s[b[y]]], f[0][y - 1]);
  198.             }
  199.             for (ul x = 1; x <= cnt; ++x) {
  200.                 f[x][0] = mul(inv[s[a[x]]], f[x - 1][0]);
  201.                 for (ul y = 1; y <= cnt; ++y) {
  202.                     f[x][y] = mul(inv[s[a[x]] + s[b[y]] - s[i]], plus(f[x - 1][y], f[x][y - 1]));
  203.                 }
  204.             }
  205.             ans = mul(ans, f[cnt][cnt]);
  206.         }
  207.         for (ul i = 1; i <= n; ++i) {
  208.             if (altim != al[i]) {
  209.                 ans = mul(ans, inv[s[i]]);
  210.             }
  211.         }
  212.         std::printf("%u\n", ans);
  213.     }
  214.     return 0;
  215. }

K、Kidnapper's Matching Problem 6865

向量串匹配，相等的定义是差属于某子空间。求出代表元后哈希即可。

  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 ul mul(ul a, ul b) {
  12.     auto vc = _mm_clmulepi64_si128(_mm_cvtsi32_si128(a), _mm_cvtsi32_si128(b), 0);
  13.     auto vf = _mm_xor_si128(vc, _mm_clmulepi64_si128(_mm_srli_epi64(vc, 32), _mm_set_epi32(0, 0, 1, 141), 0));
  14.     return _mm_cvtsi128_si32(_mm_xor_si128(vf, _mm_clmulepi64_si128(_mm_srli_epi64(vf, 32), _mm_set_epi32(0, 0, 1, 141), 0)));
  15. }
  17. ul T;
  19. const ul maxn = 2e5;
  20. const ul maxm = 5e4;
  22. ul n, m, k;
  24. std::vector<ul> base;
  26. ul wash(ul x)
  27. {
  28.     for (ul t : base) {
  29.         x = std::min(x, x ^ t);
  30.     }
  31.     return x;
  32. }
  34. ul a[maxn + 1];
  35. ul b[maxm + 1];
  36. ul hasha[maxn + 1];
  37. ul hashb;
  39. std::mt19937 rnd;
  41. ul basepow[maxn + 1];
  43. const ul mod = 1e9 + 7;
  45. ul plus(ul a, ul b)
  46. {
  47.     return a + b < mod ? a + b : a + b - mod;
  48. }
  50. ul twopow[maxn + 1];
  52. ul gethash(ul l, ul r)
  53. {
  54.     return hasha[r] ^ mul(hasha[l - 1], basepow[r - l + 1]);
  55. }
  57. int main()
  58. {
  59.     twopow[0] = 1;
  60.     for (ul i = 1; i <= maxn; ++i) {
  61.         twopow[i] = plus(twopow[i - 1], twopow[i - 1]);
  62.     }
  63.     rnd.seed(std::time(0));
  64.     const ul hashbase = rnd();
  65.     basepow[0] = 1;
  66.     for (ul i = 1; i <= maxn; ++i) {
  67.         basepow[i] = mul(basepow[i - 1], hashbase);
  68.     }
  69.     std::scanf("%u", &T);
  70.     for (ul Case = 1; Case <= T; ++Case) {
  71.         std::scanf("%u%u%u", &n, &m, &k);
  72.         for (ul i = 1; i <= n; ++i) {
  73.             std::scanf("%u", &a[i]);
  74.         }
  75.         for (ul i = 1; i <= m; ++i) {
  76.             std::scanf("%u", &b[i]);
  77.         }
  78.         base.resize(0);
  79.         for (ul i = 1; i <= k; ++i) {
  80.             ul s;
  81.             std::scanf("%u", &s);
  82.             s = wash(s);
  83.             if (s) {
  84.                 base.push_back(s);
  85.             }
  86.         }
  87.         hashb = 0;
  88.         for (ul i = 1; i <= m; ++i) {
  89.             hashb = mul(hashb, hashbase) ^ wash(b[i]);
  90.         }
  91.         for (ul i = 1; i <= n; ++i) {
  92.             hasha[i] = mul(hasha[i - 1], hashbase) ^ wash(a[i]);
  93.         }
  94.         ul ans = 0;
  95.         for (ul i = 1, j = m; j <= n; ++i, ++j) {
  96.             if (gethash(i, j) == hashb) {
  97.                 ans = plus(ans, twopow[i - 1]);
  98.             }
  99.         }
  100.         std::printf("%u\n", ans);
  101.     }
  102.     return 0;
  103. }

L、Linuber File System 6866

用表示当的严格祖先总计造成的调整的情况下，的子树至少需要多少次调整。用表示的子节点的集合，那么显然

其中求和部分和卷和部分都可以滑窗完成，总时间，不知道为什么题解会多一个对数。而且官方题解那个表达式还写错了。

  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 maxn = 2e3;
  13. ul T;
  15. ul n;
  17. std::vector<ul> edge[maxn + 1];
  19. li l[maxn + 1], r[maxn + 1];
  21. using seg_t = std::pair<li, li>;
  22. using node_t = std::pair<seg_t, ul>;
  24. std::vector<node_t> f[maxn + 1];
  25. std::vector<node_t> tmp1;
  26. std::vector<node_t> tmp2;
  28. const li inf = 1e9 + 1;
  30. void search(ul curr, ul prev)
  31. {
  32.     for (ul next : edge[curr]) {
  33.         if (next == prev) {
  34.             continue;
  35.         }
  36.         search(next, curr);
  37.     }
  38.     tmp1.resize(0);
  39.     tmp1.push_back(node_t(seg_t(-inf, l[curr] - 1), inf));
  40.     tmp1.push_back(node_t(seg_t(l[curr], r[curr]), 0));
  41.     tmp1.push_back(node_t(seg_t(r[curr] + 1, inf), inf));
  42.     for (ul next : edge[curr]) {
  43.         if (next == prev) {
  44.             continue;
  45.         }
  46.         tmp2.resize(0);
  47.         for (auto it1 = tmp1.begin(), it2 = f[next].begin(); it1 != tmp1.end() && it2 != f[next].end(); ) {
  48.             li l = std::max(it1->first.first, it2->first.first);
  49.             li r = std::min(it1->first.second, it2->first.second);
  50.             tmp2.push_back(node_t(seg_t(l, r), it1->second + it2->second));
  51.             if (it1->first.second < it2->first.second) {
  52.                 ++it1;
  53.             } else if (it2->first.second < it1->first.second) {
  54.                 ++it2;
  55.             } else {
  56.                 ++it1;
  57.                 ++it2;
  58.             }
  59.         }
  60.         tmp1.resize(0);
  61.         for (const auto& t : tmp2) {
  62.             if (tmp1.empty() || tmp1.back().second != t.second) {
  63.                 tmp1.push_back(t);
  64.             } else {
  65.                 tmp1.back().first.second = t.first.second;
  66.             }
  67.         }
  68.     }
  69.     ul mn = inf;
  70.     for (const auto& t : tmp1) {
  71.         mn = std::min(mn, t.second);
  72.     }
  73.     f[curr].resize(0);
  74.     for (const auto& t : tmp1) {
  75.         if (t.second == mn) {
  76.             f[curr].push_back(t);
  77.         } else {
  78.             f[curr].push_back(node_t(t.first, mn + 1));
  79.         }
  80.     }
  81. }
  83. int main()
  84. {
  85.     std::scanf("%u", &T);
  86.     for (ul Case = 1; Case <= T; ++Case) {
  87.         std::scanf("%u", &n);
  88.         for (ul i = 1; i <= n; ++i) {
  89.             edge[i].resize(0);
  90.         }
  91.         for (ul i = 1; i <= n - 1; ++i) {
  92.             ul u, v;
  93.             std::scanf("%u%u", &u, &v);
  94.             edge[u].push_back(v);
  95.             edge[v].push_back(u);
  96.         }
  97.         for (ul i = 1; i <= n; ++i) {
  98.             std::scanf("%d%d", &l[i], &r[i]);
  99.         }
  100.         search(1, 0);
  101.         for (const auto& t : f[1]) {
  102.             if (t.first.first <= 0 && t.first.second >= 0) {
  103.                 std::printf("%u\n", t.second);
  104.             }
  105.         }
  106.     }
  107.     return 0;
  108. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注