[关闭]
@qq290637843 2021-04-15T11:48:32.000000Z 字数 29287 阅读 425

2019西安

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

A、City

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul n, m;
  10. ull ans = 0;
  12. int main()
  13. {
  14.     std::scanf("%u%u", &n, &m);
  15.     for (ul x = 0; x <= n; ++x) {
  16.         for (ul y = 0; y <= m; ++y) {
  17.             ans += ull(std::min(x, n - x) * 2 + 1) * ull(std::min(y, m - y) * 2 + 1) - 1 >> 1;
  18.         }
  19.     }
  20.     std::printf("%llu\n", ans);
  21.     return 0;
  22. }

B、Black and White

注意本题不同于常规之处，轴向上，轴向右。
首先在图上画上的直线，于是可以分批处理每一步的贡献。为了方便起见，作出如下调整：当时，将问题变为：后步左侧的白减黑，减掉，前步右侧的黑减白，再两倍；当时，将问题变为：前步左侧的白减黑，减掉，后步右侧的黑减白，再两倍（下文将会把新目标值记为）。于是两个问题分别变为：当时，偶标向上步数减去奇标向上步数；当时，奇标向右步数减去偶标向右步数。
现在将正权标的数量记为，符权标的数量记为（时，偶标为正权标，奇标为负权标；时，奇标为正权标，偶标为负权标）。于是：
①时，答案为：；
②时，答案为：。
（注意，上述两算式，只要任何地方非法都为零）。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul mod = 998244353;
  10. ul mul(ul a, ul b)
  11. {
  12.     return ull(a) * ull(b) % mod;
  13. }
  15. void exgcd(li a, li b, li& x, li& y)
  16. {
  17.     if (b) {
  18.         exgcd(b, a % b, y, x);
  19.         y -= a / b * x;
  20.     } else {
  21.         x = 1;
  22.         y = 0;
  23.     }
  24. }
  26. ul inverse(ul a)
  27. {
  28.     li x, y;
  29.     exgcd(a, mod, x, y);
  30.     return x < 0 ? x + li(mod) : x;
  31. }
  33. const ul maxsz = 2e5;
  35. ul fac[maxsz + 1];
  36. ul fiv[maxsz + 1];
  38. ul T;
  40. li n, m, k;
  42. ul binomial(li a, li b)
  43. {
  44.     return (b >= 0 && b <= a) ? mul(fac[a], mul(fiv[a - b], fiv[b])) : ul(0);
  45. }
  47. int main()
  48. {
  49.     fac[0] = 1;
  50.     for (ul i = 1; i <= maxsz; ++i) {
  51.         fac[i] = mul(fac[i - 1], i);
  52.     }
  53.     fiv[maxsz] = inverse(fac[maxsz]);
  54.     for (ul i = maxsz; i >= 1; --i) {
  55.         fiv[i - 1] = mul(fiv[i], i);
  56.     }
  57.     std::scanf("%u", &T);
  58.     for (ul Case = 1; Case <= T; ++Case) {
  59.         std::scanf("%d%d%d", &n, &m, &k);
  60.         k += k;
  61.         li ans;
  62.         if (n <= m) {
  63.             if (n & 1) {
  64.                 --k;
  65.             }
  66.             li p = (n + m) / 2;
  67.             li q = (n + m + 1) / 2;
  68.             if ((n ^ k) & 1) {
  69.                 ans = 0;
  70.             } else {
  71.                 ans = mul(binomial(p, (n + k) / 2), binomial(q, (n - k) / 2));
  72.             }
  73.         } else {
  74.             if (m & 1) {
  75.                 if (n & 1) {
  76.                     --k;
  77.                 } else {
  78.                     ++k;
  79.                 }
  80.             }
  81.             li p = (n + m + 1) / 2;
  82.             li q = (n + m) / 2;
  83.             if ((m ^ k) & 1) {
  84.                 ans = 0;
  85.             } else {
  86.                 ans = mul(binomial(p, (m + k) / 2), binomial(q, (m - k) / 2));
  87.             }
  88.         }
  89.         std::printf("%u\n", ans);
  90.     }
  91.     return 0;
  92. }

C、Dirichlet k -th root

首先注意到，如果有一函数满足，比如质因数个数函数即可，那么将可以定义的导函数为，这样定义的导函数满足以下规则

于是等价于，即，于是

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul mod = 998244353;
  10. ul plus(ul a, ul b)
  11. {
  12.     return a + b < mod ? a + b : a + b - mod;
  13. }
  15. ul minus(ul a, ul b)
  16. {
  17.     return a < b ? a + mod - b : a - b;
  18. }
  20. ul mul(ul a, ul b)
  21. {
  22.     return ull(a) * ull(b) % mod;
  23. }
  25. void exgcd(li a, li b, li& x, li& y)
  26. {
  27.     if (b) {
  28.         exgcd(b, a % b, y, x);
  29.         y -= a / b * x;
  30.     } else {
  31.         x = 1;
  32.         y = 0;
  33.     }
  34. }
  36. ul inverse(ul a)
  37. {
  38.     li x, y;
  39.     exgcd(a, mod, x, y);
  40.     return x < 0 ? x + li(mod) : x;
  41. }
  43. const ul maxn = 1e5;
  45. ul g[maxn + 1];
  46. ul f[maxn + 1];
  48. class node {
  49. public:
  50.     ul next = 0;
  51.     ul val = 0;
  52. };
  54. ul n, k;
  56. ul tot = 0;
  57. node nodes[1066751];
  59. ul head[maxn + 1];
  60. ul ln[maxn + 1];
  62. std::vector<bool> notprime(maxn + 1, false);
  63. std::vector<ul> primes;
  65. int main()
  66. {
  67.     std::scanf("%u%u", &n, &k);
  68.     for (ul i = 2; i <= n; ++i) {
  69.         if (!notprime[i]) {
  70.             primes.push_back(i);
  71.             ln[i] = 1;
  72.         }
  73.         for (ul p : primes) {
  74.             if (i * p > n) {
  75.                 break;
  76.             }
  77.             notprime[i * p] = true;
  78.             ln[i * p] = ln[i] + 1;
  79.             if (i % p == 0) {
  80.                 break;
  81.             }
  82.         }
  83.     }
  84.     for (ul i = 1; i <= n; ++i) {
  85.         for (ul j = i + i; j <= n; j += i) {
  86.             ++tot;
  87.             nodes[tot].val = i;
  88.             nodes[tot].next = head[j];
  89.             head[j] = tot;
  90.         }
  91.     }
  92.     ul kinv = inverse(k);
  93.     for (ul i = 1; i <= n; ++i) {
  94.         std::scanf("%u", &g[i]);
  95.     }
  96.     f[1] = 1;
  97.     for (ul x = 2; x <= n; ++x) {
  98.         for (ul it = head[x]; it; it = nodes[it].next) {
  99.             ul d = nodes[it].val;
  100.             f[x] = plus(f[x], minus(mul(f[d], mul(g[x / d], ln[x / d])), mul(k, mul(mul(f[d], ln[d]), g[x / d]))));
  101.         }
  102.         f[x] = mul(mul(f[x], kinv), inverse(ln[x]));
  103.     }
  104.     for (ul i = 1; i <= n; ++i) {
  105.         if (i != 1) {
  106.             std::putchar(' ');
  107.         }
  108.         std::printf("%u", f[i]);
  109.     }
  110.     std::putchar('\n');
  111.     return 0;
  112. }

D、Fire

用表示从节点出发完成任务并回到且还能离开，最晚第几天中午必须到，表示从节点出发完成任务留在的子树中某个叶子上，最晚第几天中午必须到。
于是只考虑该怎么转移，下文中下标不再表示节点编号，而是表示“当前节点的第几个子节点”，且子节点已经依据从小到大排序。


预处理以及以及即可。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  7. using llf = long double;
  9. const ul maxn = 1e5;
  11. std::vector<ul> edges[maxn + 1];
  13. ll k;
  15. ll a[maxn + 1];
  17. ul n;
  19. ll f[maxn + 1];
  20. ll g[maxn + 1];
  21. ll sz[maxn + 1];
  23. ll sum[maxn + 1];
  24. ll premin[maxn + 1];
  25. ll sufmin[maxn + 1];
  27. void search(ul curr, ul prev)
  28. {
  29.     sz[curr] = 1;
  30.     if (edges[curr].size() == 1) {
  31.         f[curr] = std::min(a[curr], a[curr] + k - 2);
  32.         g[curr] = a[curr];
  33.         return;
  34.     }
  35.     for (ul next : edges[curr]) {
  36.         if (next == prev) {
  37.             continue;
  38.         }
  39.         search(next, curr);
  40.         sz[curr] += sz[next];
  41.     }
  42.     std::sort(edges[curr].begin(), edges[curr].end(), [&](ul a, ul b){return (a == prev) != (b == prev) ? a == prev : f[a] + sz[a] + sz[a] - 1 < f[b] + sz[b] + sz[b] - 1;});
  43.     sum[0] = 0;
  44.     premin[0] = 1e18;
  45.     for (ul i = 1; i != edges[curr].size(); ++i) {
  46.         ul t = edges[curr][i];
  47.         sum[i] = sum[i - 1] + sz[t] + sz[t];
  48.         premin[i] = std::min(premin[i - 1], f[t] - sum[i - 1]);
  49.     }
  50.     sufmin[edges[curr].size()] = 1e18;
  51.     for (ul i = edges[curr].size() - 1; i; --i) {
  52.         ul t = edges[curr][i];
  53.         sufmin[i] = std::min(sufmin[i + 1], f[t] - sum[i - 1]);
  54.     }
  55.     f[curr] = std::min(std::min(a[curr], premin[edges[curr].size() - 1] - 1), a[curr] + k - sum[edges[curr].size() - 1] - 2);
  56.     g[curr] = -1e18;
  57.     for (ul b = 1; b != edges[curr].size(); ++b) {
  58.         ul t = edges[curr][b];
  59.         ll tmp = std::min(std::min(std::min(std::min(a[curr], premin[b - 1] - 1), sufmin[b + 1] - 1 + sz[t] + sz[t]), g[t] - 1 - sum[edges[curr].size() - 1] + sz[t] + sz[t]), a[curr] + k - sum[edges[curr].size() - 1] + sz[t] + sz[t] - 2);
  60.         g[curr] = std::max(g[curr], tmp);
  61.     }
  62. }
  64. int main()
  65. {
  66.     std::scanf("%u%lld", &n, &k);
  67.     for (ul i = 1; i <= n - 1; ++i) {
  68.         ul x, y;
  69.         std::scanf("%u%u", &x, &y);
  70.         edges[x].push_back(y);
  71.         edges[y].push_back(x);
  72.     }
  73.     edges[1].push_back(0);
  74.     for (ul i = 1; i <= n; ++i) {
  75.         std::scanf("%lld", &a[i]);
  76.     }
  77.     search(1, 0);
  78.     std::printf("%lld\n", g[1] < 0 ? ll(-1) : g[1]);
  79.     return 0;
  80. }

E、Flow

简单题

  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 = 1e5;
  10. class edge_t {
  11. public:
  12.     ul to;
  13.     ul val;
  14.     edge_t()=default;
  15.     edge_t(ul a, ul b): to(a), val(b) {}
  16. };
  18. std::vector<edge_t> edges[maxn + 1];
  20. ull sum = 0;
  22. std::vector<ul> tmp;
  24. ull s[maxn + 1];
  26. ul n, m;
  28. int main()
  29. {
  30.     std::scanf("%u%u", &n, &m);
  31.     for (ul i = 1; i <= m; ++i) {
  32.         ul x, y, z;
  33.         std::scanf("%u%u%u", &x, &y, &z);
  34.         edges[x].push_back(edge_t(y, z));
  35.         edges[y].push_back(edge_t(x, z));
  36.         sum += z;
  37.     }
  38.     sum /= m / edges[1].size();
  39.     for (auto e : edges[1]) {
  40.         tmp.resize(0);
  41.         for (ul prev = 1, curr = e.to; ; e = edges[e.to][0].to == prev ? edges[e.to][1] : edges[e.to][0], prev = curr, curr = e.to) {
  42.             tmp.push_back(e.val);
  43.             if (e.to == n) {
  44.                 break;
  45.             }
  46.         }
  47.         std::sort(tmp.begin(), tmp.end());
  48.         for (ul i = 0; i != tmp.size(); ++i) {
  49.             s[i] += tmp[i] - (i ? tmp[i - 1] : ul(0));
  50.         }
  51.     }
  52.     ull ans = 0;
  53.     for (ul i = 0; i != tmp.size(); ++i) {
  54.         ull able = std::min(sum, s[i]);
  55.         sum -= able;
  56.         ans += able * i;
  57.     }
  58.     std::printf("%llu\n", ans);
  59.     return 0;
  60. }

F、Game

爬山

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. li check(ul a, ul b)
  9. {
  10.     if (a == b || a == 30 || b == 30) {
  11.         return 0;
  12.     } else if (a == 31 && b == 32) {
  13.         return -1;
  14.     } else if (a == 32 && b == 31) {
  15.         return 1;
  16.     } else if (a == 31) {
  17.         return 1;
  18.     } else if (b == 31) {
  19.         return -1;
  20.     } else if (a > b) {
  21.         return 1;
  22.     } else {
  23.         return -1;
  24.     }
  25. }
  27. li check(ul a[], ul b[])
  28. {
  29.     for (ul ai = 1, bi = 1; ; ) {
  30.         if (ai == 25 || bi == 25) {
  31.             return bi - ai;
  32.         }
  33.         li tmp = check(a[ai], b[bi]);
  34.         if (tmp >= 0) {
  35.             ++bi;
  36.         }
  37.         if (tmp <= 0) {
  38.             ++ai;
  39.         }
  40.     }
  41.     return 0;
  42. }
  44. ul check2(ul a[], ul b[])
  45. {
  46.     ul ret = 0;
  47.     if (check(a, b) >= 0) {
  48.         ++ret;
  49.     }
  50.     for (ul i = 1; i + 1 <= 24; ++i) {
  51.         for (ul j = i + 1; j <= 24; ++j) {
  52.             if (b[i] == b[j]) {
  53.                 continue;
  54.             }
  55.             std::swap(b[i], b[j]);
  56.             if (check(a, b) >= 0) {
  57.                 ++ret;
  58.             }
  59.             std::swap(b[i], b[j]);
  60.         }
  61.     }
  62.     return ret;
  63. }
  65. ul T;
  67. ul a[25] = {0, 40, 39, 38, 38, 37, 37, 36, 36, 35, 35, 34, 34, 34, 33, 33, 33, 32, 32, 32, 31, 31, 31, 30, 30};
  68. ul b[25] = {0, 40, 39, 38, 38, 37, 37, 36, 36, 35, 35, 34, 34, 34, 33, 33, 33, 32, 32, 32, 31, 31, 31, 30, 30};
  70. std::mt19937_64 rnd;
  72. void sf(ul a[])
  73. {
  74.     for (ul i = 24; i >= 1; --i) {
  75.         std::swap(a[i], a[rnd() % i + 1]);
  76.     }
  77. }
  79. std::pair<ul, ul> sp[500];
  80. ul tot;
  82. int main()
  83. {
  84.     for (ul i = 1; i + 1 <= 24; ++i) {
  85.         for (ul j = i + 1; j <= 24; ++j) {
  86.             ++tot;
  87.             sp[tot].first = i;
  88.             sp[tot].second = j;
  89.         }
  90.     }
  91.     rnd.seed(std::time(0));
  92.     std::scanf("%u", &T);
  93.     for (ul Case = 1; Case <= T; ++Case) {
  94.         for (ul i = 1; i <= 24; ++i) {
  95.             std::scanf("%u", &a[i]);
  96.         }
  97.         ul cnt = 0;
  98.         while (true) {
  99.             ul tmp = check2(a, b);
  100.             while (tmp) {
  101.                 bool flag = false;
  102.                 for (ul i = tot; i >= 1; --i) {
  103.                     std::swap(sp[rnd() % i + 1], sp[i]);
  104.                     ul s = sp[i].first;
  105.                     ul t = sp[i].second;
  106.                     if (b[s] == b[t]) {
  107.                         continue;
  108.                     }
  109.                     std::swap(b[s], b[t]);
  110.                     ul tmp2 = check2(a, b);
  111.                     if (tmp2 < tmp) {
  112.                         tmp = tmp2;
  113.                         flag = true;
  114.                         break;
  115.                     }
  116.                     std::swap(b[s], b[t]);
  117.                 }
  118.                 if (!flag) {
  119.                     break;
  120.                 }
  121.             }
  122.             if (tmp == 0) {
  123.                 for (ul i = 1; i <= 24; ++i) {
  124.                     if (i != 1) {
  125.                         std::putchar(' ');
  126.                     }
  127.                     std::printf("%u", b[i]);
  128.                 }
  129.                 std::putchar('\n');
  130.                 break;
  131.             }
  132.             sf(b);
  133.         }
  134.     }
  135.     return 0;
  136. }

G、Happiness

模拟

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul n;
  9. const ul maxn = 300;
  11. class problem {
  12. public:
  13.     ul time = 0;
  14.     ul pen = 0;
  15. };
  17. class person {
  18. public:
  19.     problem p[11];
  20.     ul cnt = 0;
  21.     ul sum = 0;
  22.     ul id = 0;
  23. };
  25. person guy[maxn + 1];
  27. std::string instr;
  29. std::stringstream ss;
  30. std::stringstream ss2;
  32. bool operator<(const person& a, const person& b)
  33. {
  34.     if (a.cnt != b.cnt) {
  35.         return a.cnt > b.cnt;
  36.     }
  37.     if (a.sum != b.sum) {
  38.         return a.sum < b.sum;
  39.     }
  40.     for (ul i = 10 - a.cnt + 1; i <= 10; ++i) {
  41.         if (a.p[i].time != b.p[i].time) {
  42.             return a.p[i].time < b.p[i].time;
  43.         }
  44.     }
  45.     return a.id > b.id;
  46. }
  48. person pang;
  50. ul set;
  52. ul mn[11];
  54. ul mnmn = 301;
  56. ul stack[11];
  58. int main()
  59. {
  60.     std::getline(std::cin, instr);
  61.     ss.clear();
  62.     ss.str(instr);
  63.     for (ul i = 1; i <= 10; ++i) {
  64.         mn[i] = 301;
  65.     }
  66.     ss >> n;
  67.     ul mx = 0;
  68.     for (ul i = 1; i <= n - 1; ++i) {
  69.         std::getline(std::cin, instr);
  70.         ss.clear();
  71.         ss.str(instr);
  72.         guy[i].id = i;
  73.         for (ul j = 1; j <= 10; ++j) {
  74.             std::getline(ss, instr, ',');
  75.             if (instr == "-") {
  76.                 guy[i].p[j].time = 301;
  77.                 guy[i].p[j].pen = 11;
  78.             } else {
  79.                 ss2.clear();
  80.                 ss2.str(instr);
  81.                 ss2 >> guy[i].p[j].time >> guy[i].p[j].pen;
  82.                 ++guy[i].cnt;
  83.                 guy[i].sum += guy[i].p[j].time + guy[i].p[j].pen * 20;
  84.                 mx = std::max(mx, guy[i].p[j].time);
  85.                 mn[j] = std::min(mn[j], guy[i].p[j].time);
  86.                 mnmn = std::min(mnmn, mn[j]);
  87.             }
  88.         }
  89.         std::sort(guy[i].p + 1, guy[i].p + 11, [](const problem& a, const problem& b){return a.time > b.time;});
  90.     }
  91.     std::sort(guy + 1, guy + n);
  92.     std::getline(std::cin, instr);
  93.     ss.clear();
  94.     ss.str(instr);
  95.     guy[n].id = n;
  96.     for (ul j = 1; j <= 10; ++j) {
  97.         std::getline(ss, instr, ',');
  98.         if (instr == "-") {
  99.             pang.p[j].time = 301;
  100.             pang.p[j].pen = 11;
  101.         } else {
  102.             ss2.clear();
  103.             ss2.str(instr);
  104.             ss2 >> pang.p[j].time >> pang.p[j].pen;
  105.             set |= 1 << j;
  106.         }
  107.     }
  108.     ul ans = 0;
  109.     for (ul mask = set; ; mask = mask - 1 & set) {
  110.         ul tot = 0;
  111.         ul sum = 0;
  112.         for (ul i = 1; i <= 10; ++i) {
  113.             if (mask >> i & 1) {
  114.                 ++tot;
  115.                 stack[tot] = i;
  116.                 sum += pang.p[i].time;
  117.             }
  118.         }
  119.         if (sum > 300) {
  120.             continue;
  121.         }
  122.         do {
  123.             guy[n].cnt = tot;
  124.             guy[n].sum = 0;
  125.             for (ul i = 1; i <= 10; ++i) {
  126.                 guy[n].p[i].time = 301;
  127.                 guy[n].p[i].pen = 11;
  128.             }
  129.             ul currans = 0;
  130.             ul cmx = 0;
  131.             ul cmn = 301;
  132.             for (ul i = 1; i <= tot; ++i) {
  133.                 guy[n].p[stack[i]].time = guy[n].p[stack[i - 1]].time + pang.p[stack[i]].time;
  134.                 guy[n].p[stack[i]].pen = pang.p[stack[i]].pen;
  135.                 guy[n].sum += guy[n].p[stack[i]].time + guy[n].p[stack[i]].pen * 20;
  136.                 cmx = std::max(guy[n].p[stack[i]].time, cmx);
  137.                 cmn = std::min(guy[n].p[stack[i]].time, cmn);
  138.                 if (guy[n].p[stack[i]].time <= mn[stack[i]]) {
  139.                     currans += 800;
  140.                 }
  141.             }
  142.             if (mask) {
  143.                 if (cmx >= mx) {
  144.                     currans += 500;
  145.                 }
  146.                 if (cmn <= mnmn) {
  147.                     currans += 700;
  148.                 }
  149.             }
  150.             std::sort(guy[n].p + 1, guy[n].p + 11, [](const problem& a, const problem& b){return a.time > b.time;});
  151.             ul r = std::upper_bound(guy + 1, guy + n, guy[n]) - guy;
  152.             currans += 5000 / r;
  153.             if (r <= n / 10) {
  154.                 currans += 1200;
  155.             } else if (r <= n / 10 * 3) {
  156.                 currans += 800;
  157.             } else if (r <= n / 10 * 6) {
  158.                 currans += 400;
  159.             }
  160.             ans = std::max(ans, currans);
  161.         } while (std::next_permutation(stack + 1, stack + tot + 1));
  162.         if (!mask) {
  163.             break;
  164.         }
  165.     }
  166.     std::printf("%u\n", ans);
  167.     return 0;
  168. }

H、king

首先假设有一合法结果，于是该结果的首尾下标差最大为，而由于其总共有至少个间隔，故最小间隔一定小于等于，注意时该值都等于，所以仅时单独处理。
现在设表示结果中大小为的间隔的数量，那么显然有以下两个不等式

由此可知
从而
所以只需要考虑满足以上条件的那些即可。注意所有的的的总和小于等于，故满足上述条件的至多有，所以不用担心时间复杂度。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul n;
  9. const ul maxn = 2e5;
  11. ul p;
  13. ul b[maxn + 1];
  14. ul binv[maxn + 1];
  15. ul bpre[maxn + 1];
  16. ul bpreinv[maxn + 1];
  18. ul T;
  20. ul mul(ul a, ul b)
  21. {
  22.     return ull(a) * ull(b) % p;
  23. }
  25. void exgcd(li a, li b, li& x, li& y)
  26. {
  27.     if (b) {
  28.         exgcd(b, a % b, y, x);
  29.         y -= a / b * x;
  30.     } else {
  31.         x = 1;
  32.         y = 0;
  33.     }
  34. }
  36. ul inverse(ul a)
  37. {
  38.     li x, y;
  39.     exgcd(a, p, x, y);
  40.     return x < 0 ? x + li(p) : x;
  41. }
  43. std::mt19937_64 rnd;
  45. class hashmap {
  46. public:
  47.     class node {
  48.     public:
  49.         ul key = 0;
  50.         ul val = 0;
  51.     };
  52.     bool ex[1 << 20];
  53.     node v[1 << 20];
  54.     ul sz;
  55.     ul a;
  56.     ul b;
  57.     const ul mod = 1e9 + 7;
  58.     void init(ul n)
  59.     {
  60.         a = rnd() % (mod - 1) + 1;
  61.         b = rnd() % mod;
  62.         sz = 1;
  63.         while (sz + sz < n + n + n) {
  64.             sz <<= 1;
  65.         }
  66.         std::memset(ex, false, sz * sizeof(bool));
  67.     }
  68.     ul& operator[](ul x)
  69.     {
  70.         ul h = (ull(x) * ull(a) + b) % mod & sz - 1;
  71.         while (true) {
  72.             if (!ex[h]) {
  73.                 ex[h] = true;
  74.                 v[h].key = x;
  75.                 v[h].val = 0;
  76.                 return v[h].val;
  77.             }
  78.             if (v[h].key == x) {
  79.                 return v[h].val;
  80.             }
  81.             h = h + 1 & sz - 1;
  82.         }
  83.     }
  84. };
  86. hashmap cnt;
  88. hashmap len;
  90. ul calc(ul q)
  91. {
  92.     len.init(n + n);
  93.     ul ret = 0;
  94.     for (ul i = n; i >= 1; --i) {
  95.         ul& l = len[b[i]];
  96.         l = std::max(l, len[mul(b[i], q)] + 1);
  97.         ret = std::max(ret, l);
  98.     }
  99.     return ret;
  100. }
  102. int main()
  103. {
  104.     rnd.seed(std::time(0));
  105.     std::scanf("%u", &T);
  106.     for (ul Case = 1; Case <= T; ++Case) {
  107.         std::scanf("%u%u", &n, &p);
  108.         bpre[0] = 1;
  109.         for (ul i = 1; i <= n; ++i) {
  110.             std::scanf("%u", &b[i]);
  111.             bpre[i] = mul(bpre[i - 1], b[i]);
  112.         }
  113.         bpreinv[n] = inverse(bpre[n]);
  114.         for (ul i = n; i >= 1; --i) {
  115.             bpreinv[i - 1] = mul(bpreinv[i], b[i]);
  116.             binv[i] = mul(bpreinv[i], bpre[i - 1]);
  117.         }
  118.         ul ans = 0;
  119.         if (n <= 4) {
  120.             for (ul i = 1; i + 1 <= n; ++i) {
  121.                 for (ul j = i + 1; j <= n; ++j) {
  122.                     ul q = mul(b[j], binv[i]);
  123.                     ans = std::max(ans, calc(q));
  124.                 }
  125.             }
  126.         } else {
  127.             cnt.init(n + n - 3);
  128.             for (ul i = 1; i + 1 <= n; ++i) {
  129.                 for (ul j = i + 1; j <= n && j <= i + 2; ++j) {
  130.                     cnt[mul(b[j], binv[i])] += 3 ^ j - i;
  131.                 }
  132.             }
  133.             for (ul i = 0; i != cnt.sz; ++i) {
  134.                 if (!cnt.ex[i] || cnt.v[i].val < (n + 1) / 2 * 3 - n - 2) {
  135.                     continue;
  136.                 }
  137.                 ans = std::max(ans, calc(cnt.v[i].key));
  138.             }
  139.         }
  140.         if (ans * 2 >= n) {
  141.             std::printf("%u\n", ans);
  142.         } else {
  143.             std::printf("-1\n");
  144.         }
  145.     }
  146.     return 0;
  147. }

I、Moon

牛客这道题没放spj，肏你妈。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  7. using lll = __int128;
  8. using llf = long double;
  9. using lf = double;
  11. li sgn(lll x)
  12. {
  13.     return x < 0 ? -1 : (x > 0 ? 1 : 0);
  14. }
  16. const lll bound = 1e18;
  18. bool less(lll a, lll b, lll c, lll d)
  19. {
  20.     if (sgn(a) != sgn(c)) {
  21.         return sgn(a) < sgn(c);
  22.     }
  23.     if (a < 0) {
  24.         return less(-c, d, -a, b);
  25.     }
  26.     lll q1 = a / b;
  27.     lll r1 = a - b * q1;
  28.     lll q2 = c / d;
  29.     lll r2 = c - d * q2;
  30.     if (q1 != q2) {
  31.         return q1 < q2;
  32.     }
  33.     if (r1 == 0 || r2 == 0) {
  34.         return r1 < r2;
  35.     }
  36.     if (b <= bound && d <= bound) {
  37.         return r1 * d < r2 * b;
  38.     }
  39.     return less(d, r2, b, r1);
  40. }
  42. ul n;
  43. const ul maxn = 1e5;
  45. lll in()
  46. {
  47.     ll tmp;
  48.     std::scanf("%lld", &tmp);
  49.     return tmp;
  50. }
  52. class vec {
  53. public:
  54.     lll x = 0;
  55.     lll y = 0;
  56.     lll z = 0;
  57.     vec()=default;
  58.     vec(lll a, lll b, lll c): x(a), y(b), z(c) {}
  59. };
  61. class vecd {
  62. public:
  63.     llf x = 0;
  64.     llf y = 0;
  65.     llf z = 0;
  66.     vecd()=default;
  67.     vecd(llf a, llf b, llf c): x(a), y(b), z(c) {}
  68.     vecd(const vec& a): x(a.x), y(a.y), z(a.z) {}
  69. };
  71. std::ostream& operator<<(std::ostream& os, const vecd& a)
  72. {
  73.     return os << '{' << a.x << ',' << a.y << ',' << a.z << '}';
  74. }
  76. vec p[maxn + 1];
  77. vec p2[maxn + 1];
  79. std::vector<ul> stack1;
  80. std::vector<ul> stack2;
  81. std::vector<ul> stackpbuttom;
  82. std::vector<ul> stackptop;
  83. std::vector<ul> stacknbuttom;
  84. std::vector<ul> stackntop;
  85. std::vector<ul> stacktop;
  86. std::vector<ul> stackbuttom;
  88. lll gcd(lll a, lll b)
  89. {
  90.     a = a < 0 ? -a : a;
  91.     b = b < 0 ? -b : b;
  92.     while (b) {
  93.         b ^= a ^= b ^= a %= b;
  94.     }
  95.     return a;
  96. }
  98. vec operator^(const vec& a, const vec& b)
  99. {
  100.     vec ret = vec(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);
  101.     lll g = gcd(gcd(ret.x, ret.y), ret.z);
  102.     if (g) {
  103.         ret.x /= g;
  104.         ret.y /= g;
  105.         ret.z /= g;
  106.     }
  107.     return ret;
  108. }
  110. vec operator-(const vec& a)
  111. {
  112.     return vec(-a.x, -a.y, -a.z);
  113. }
  115. vecd operator-(const vecd& a, const vecd& b)
  116. {
  117.     return vecd(a.x - b.x, a.y - b.y, a.z - b.z);
  118. }
  120. vecd operator^(const vecd& a, const vecd& b)
  121. {
  122.     return vecd(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);
  123. }
  125. lll operator*(const vec& a, const vec& b)
  126. {
  127.     return a.x * b.x + a.y * b.y + a.z * b.z;
  128. }
  130. llf operator*(const vecd& a, const vecd& b)
  131. {
  132.     return a.x * b.x + a.y * b.y + a.z * b.z;
  133. }
  135. vecd operator*(llf a, const vecd& b)
  136. {
  137.     return vecd(a * b.x, a * b.y, a * b.z);
  138. }
  140. vecd operator*(const vecd& a, llf b)
  141. {
  142.     return vecd(a.x * b, a.y * b, a.z * b);
  143. }
  145. vecd operator/(const vecd& a, llf b)
  146. {
  147.     return vecd(a.x / b, a.y / b, a.z / b);
  148. }
  150. llf norm(const vecd& a)
  151. {
  152.     return std::sqrt(a * a);
  153. }
  155. vecd normalize(const vecd& a)
  156. {
  157.     llf len = std::max(std::max(a.x < 0 ? -a.x : a.x, a.y < 0 ? -a.y : a.y), a.z < 0 ? -a.z : a.z);
  158.     if (!len) {
  159.         return a;
  160.     }
  161.     vecd b = a / len;
  162.     auto n = norm(b);
  163.     return b / n;
  164. }
  166. lll det(const vec& a, const vec& b, const vec& c)
  167. {
  168.     return a.x * b.y * c.z + a.y * b.z * c.x + a.z * b.x * c.y - a.z * b.y * c.x - a.y * b.x * c.z - a.x * b.z * c.y;
  169. }
  171. void gethull(std::vector<ul>& stack1, std::vector<ul>& stack2, std::vector<ul>& stack3)
  172. {
  173.     std::sort(stack1.begin(), stack1.end(), [&](ul i, ul j){
  174.         const vec& a = p[i];
  175.         const vec& b = p[j];
  176.         if ((a.z == 0) != (b.z == 0)) {
  177.             return a.z == 0;
  178.         }
  179.         if (a.z && b.z) {
  180.             return a.x * b.z != b.x * a.z ? a.x * b.z < b.x * a.z : a.y * b.z > b.y * a.z;
  181.         }
  182.         if ((a.x == 0) != (b.x == 0)) {
  183.             return a.x == 0;
  184.         }
  185.         if (a.x && b.x) {
  186.             return a.y * b.x < b.y * a.x;
  187.         }
  188.         return false;
  189.     });
  190.     stack2.resize(0);
  191.     for (auto i : stack1) {
  192.         while (stack2.size() >= 2) {
  193.             const vec& a = p[stack2[stack2.size() - 2]];
  194.             const vec& b = p[stack2[stack2.size() - 1]];
  195.             const vec& c = p[i];
  196.             bool flag = det(a, b, c) <= 0;
  197.             if (flag) {
  198.                 stack2.pop_back();
  199.             } else {
  200.                 break;
  201.             }
  202.         }
  203.         stack2.push_back(i);
  204.     }
  205.     std::reverse(stack1.begin(), stack1.end());
  206.     stack3.resize(0);
  207.     for (auto i : stack1) {
  208.         while (stack3.size() >= 2) {
  209.             const vec& a = p[stack3[stack3.size() - 2]];
  210.             const vec& b = p[stack3[stack3.size() - 1]];
  211.             const vec& c = p[i];
  212.             bool flag = det(a, b, c) <= 0;
  213.             if (flag) {
  214.                 stack3.pop_back();
  215.             } else {
  216.                 break;
  217.             }
  218.         }
  219.         stack3.push_back(i);
  220.     }
  221. }
  223. void gethulld(std::vector<ul>& stack1, std::vector<ul>& stack2, std::vector<ul>& stack3)
  224. {
  225.     std::sort(stack1.begin(), stack1.end(), [&](ul i, ul j){
  226.         const vec& a = p2[i];
  227.         const vec& b = p2[j];
  228.         if ((a.z == 0) != (b.z == 0)) {
  229.             return a.z == 0;
  230.         }
  231.         if (a.z && b.z) {
  232.             bool flag1 = less(b.x, b.z, a.x, a.z);
  233.             bool flag2 = less(a.x, a.z, b.x, b.z);
  234.             return (flag1 || flag2) ? flag2 : less(a.y, a.z, b.y, b.z);
  235.         }
  236.         if ((a.x == 0) != (b.x == 0)) {
  237.             return a.x == 0;
  238.         }
  239.         if (a.x && b.x) {
  240.             return less(-a.y, -a.x, -b.y, -b.x);
  241.         }
  242.         return false;
  243.     });
  244.     stack2.resize(0);
  245.     for (auto i : stack1) {
  246.         while (stack2.size() >= 2) {
  247.             const vec& a = p[stack2[stack2.size() - 2]];
  248.             const vec& b = p[stack2[stack2.size() - 1]];
  249.             const vec& c = p[i];
  250.             bool flag = det(a, b, c) <= 0;
  251.             if (flag) {
  252.                 stack2.pop_back();
  253.             } else {
  254.                 break;
  255.             }
  256.         }
  257.         stack2.push_back(i);
  258.     }
  259.     std::reverse(stack1.begin(), stack1.end());
  260.     stack3.resize(0);
  261.     for (auto i : stack1) {
  262.         while (stack3.size() >= 2) {
  263.             const vec& a = p[stack3[stack3.size() - 2]];
  264.             const vec& b = p[stack3[stack3.size() - 1]];
  265.             const vec& c = p[i];
  266.             bool flag = det(a, b, c) <= 0;
  267.             if (flag) {
  268.                 stack3.pop_back();
  269.             } else {
  270.                 break;
  271.             }
  272.         }
  273.         stack3.push_back(i);
  274.     }
  275. }
  277. bool out(const vec& a, const vec& b, const vec& c)
  278. {
  279.     return det(a, b, c) <= 0;
  280. }
  282. llf myacos(llf a)
  283. {
  284.     return std::acos(std::max(std::min(a, llf(1)), llf(-1)));
  285. }
  287. llf cnt(const vec& a, const vec& b, const vec& c)
  288. {
  289.     return myacos((normalize(normalize(a) ^ normalize(b)) * normalize(normalize(b) ^ normalize(c))));
  290. }
  292. bool operator==(const vec& a, const vec& b)
  293. {
  294.     return a.x == b.x && a.y == b.y && a.z == b.z;
  295. }
  297. const llf pi = std::acos(llf(-1));
  298. const llf hpi = pi * llf(0.5);
  300. std::priority_queue<llf, std::vector<llf>, std::greater<llf>> heap;
  302. int main()
  303. {
  304.     std::scanf("%u", &n);
  305.     if (n <= 2) {
  306.         std::printf("1.0\n");
  307.         return 0;
  308.     }
  309.     for (ul i = 1; i <= n; ++i) {
  310.         p[i].x = in();
  311.         p[i].y = in();
  312.         p[i].z = in();
  313.         lll g = gcd(gcd(p[i].x, p[i].y), p[i].z);
  314.         p[i].x /= g;
  315.         p[i].y /= g;
  316.         p[i].z /= g;
  317.     }
  318.     stack1.resize(0);
  319.     for (ul i = 1; i <= n; ++i) {
  320.         if (p[i].z > 0 || p[i].z == 0 && p[i].x < 0 || p[i].z == 0 && p[i].x == 0 && p[i].y > 0) {
  321.             stack1.push_back(i);
  322.         }
  323.     }
  324.     gethull(stack1, stackpbuttom, stackptop);
  325.     stack1.resize(0);
  326.     for (ul i = 1; i <= n; ++i) {
  327.         if (p[i].z < 0 || p[i].z == 0 && p[i].x > 0 || p[i].z == 0 && p[i].x == 0 && p[i].y < 0) {
  328.             stack1.push_back(i);
  329.             p[i].x = -p[i].x;
  330.             p[i].y = -p[i].y;
  331.             p[i].z = -p[i].z;
  332.         }
  333.     }
  334.     gethull(stack1, stacknbuttom, stackntop);
  335.     ul s = 0;
  336.     ul t = 0;
  337.     vec zdi;
  338.     vec xdi;
  339.     vec ydi;
  340.     vecd zdir;
  341.     vecd xdir;
  342.     vecd ydir;
  343.     if (!stackpbuttom.size() || !stacknbuttom.size()) {
  344.         zdir = zdi = vec(0, 0, 1);
  345.         ydir = ydi = vec(0, 1, 0);
  346.         xdir = xdi = vec(1, 0, 0);
  347.     } else {
  348.         ul s = 0;
  349.         ul t = 0;
  350.         for (ul i = 0; i + 1 < stackpbuttom.size() && !s && !t; ++i) {
  351.             const vec& a = p[stackpbuttom[i]];
  352.             const vec& b = p[stackpbuttom[i + 1]];
  353.             ul l = 0, r = stackntop.size();
  354.             while (l + 1 != r) {
  355.                 ul mid = l + r >> 1;
  356.                 const vec& c = p[stackntop[mid - 1]];
  357.                 const vec& d = p[stackntop[mid]];
  358.                 bool flag = (a ^ b) * (normalize(d) - normalize(c)) >= 0;
  359.                 if (flag) {
  360.                     l = mid;
  361.                 } else {
  362.                     r = mid;
  363.                 }
  364.             }
  365.             const vec& c = p[stackntop[l]];
  366.             if (out(a, b, c)) {
  367.                 s = stackpbuttom[i];
  368.                 t = stackpbuttom[i + 1];
  369.             }
  370.         }
  371.         for (ul i = 0; i + 1 < stacknbuttom.size() && !s && !t; ++i) {
  372.             const vec& a = p[stacknbuttom[i]];
  373.             const vec& b = p[stacknbuttom[i + 1]];
  374.             ul l = 0, r = stackptop.size();
  375.             while (l + 1 != r) {
  376.                 ul mid = l + r >> 1;
  377.                 const vec& c = p[stackptop[mid - 1]];
  378.                 const vec& d = p[stackptop[mid]];
  379.                 bool flag = (a ^ b) * (normalize(d) - normalize(c)) >= 0;
  380.                 if (flag) {
  381.                     l = mid;
  382.                 } else {
  383.                     r = mid;
  384.                 }
  385.             }
  386.             const vec& c = p[stackptop[l]];
  387.             if (out(a, b, c)) {
  388.                 t = stacknbuttom[i];
  389.                 s = stacknbuttom[i + 1];
  390.             }
  391.         }
  392.         for (ul i = 0; i + 1 < stackptop.size() && !s && !t; ++i) {
  393.             const vec& a = p[stackptop[i]];
  394.             const vec& b = p[stackptop[i + 1]];
  395.             ul l = 0, r = stacknbuttom.size();
  396.             while (l + 1 != r) {
  397.                 ul mid = l + r >> 1;
  398.                 const vec& c = p[stacknbuttom[mid - 1]];
  399.                 const vec& d = p[stacknbuttom[mid]];
  400.                 bool flag = (a ^ b) * (normalize(d) - normalize(c)) >= 0;
  401.                 if (flag) {
  402.                     l = mid;
  403.                 } else {
  404.                     r = mid;
  405.                 }
  406.             }
  407.             const vec& c = p[stacknbuttom[l]];
  408.             if (out(a, b, c)) {
  409.                 s = stackptop[i];
  410.                 t = stackptop[i + 1];
  411.             }
  412.         }
  413.         for (ul i = 0; i + 1 < stackntop.size() && !s && !t; ++i) {
  414.             const vec& a = p[stackntop[i]];
  415.             const vec& b = p[stackntop[i + 1]];
  416.             ul l = 0, r = stackpbuttom.size();
  417.             while (l + 1 != r) {
  418.                 ul mid = l + r >> 1;
  419.                 const vec& c = p[stackpbuttom[mid - 1]];
  420.                 const vec& d = p[stackpbuttom[mid]];
  421.                 bool flag = (a ^ b) * (normalize(d) - normalize(c)) >= 0;
  422.                 if (flag) {
  423.                     l = mid;
  424.                 } else {
  425.                     r = mid;
  426.                 }
  427.             }
  428.             const vec& c = p[stackpbuttom[l]];
  429.             if (out(a, b, c)) {
  430.                 t = stackntop[i];
  431.                 s = stackntop[i + 1];
  432.             }
  433.         }
  434.         if (!s && !t) {
  435.             std::printf("0.0\n");
  436.             return 0;
  437.         }
  438.         for (ul i : stack1) {
  439.             p[i].x = -p[i].x;
  440.             p[i].y = -p[i].y;
  441.             p[i].z = -p[i].z;
  442.         }
  443.         zdi = p[s] ^ p[t];
  444.         ydi = p[s];
  445.         xdi = ydi ^ zdi;
  446.         stack1.resize(0);
  447.         stack2.resize(0);
  448.         for (ul i = 1; i <= n; ++i) {
  449.             if (p[i] * zdi == 0) {
  450.                 if (p[i] * xdi < 0 || p[i] * xdi == 0 && p[i] * ydi > 0) {
  451.                     stack1.push_back(i);
  452.                 } else {
  453.                     stack2.push_back(i);
  454.                 }
  455.             }
  456.         }
  457.         std::sort(stack1.begin(), stack1.end(), [&](ul i, ul j){
  458.             const vec& a = p[i];
  459.             const vec& b = p[j];
  460.             lll ax = a * xdi;
  461.             lll bx = b * xdi;
  462.             lll ay = a * ydi;
  463.             lll by = b * ydi;
  464.             if ((ax == 0) != (bx == 0)) {
  465.                 return ax == 0;
  466.             }
  467.             if (ax && bx) {
  468.                 return less(-ay, -ax, -by, -bx);
  469.             }
  470.             return false;
  471.         });
  472.         std::sort(stack2.begin(), stack2.end(), [&](ul i, ul j){
  473.             const vec& a = p[i];
  474.             const vec& b = p[j];
  475.             lll ax = a * xdi;
  476.             lll bx = b * xdi;
  477.             lll ay = a * ydi;
  478.             lll by = b * ydi;
  479.             if ((ax == 0) != (bx == 0)) {
  480.                 return ax == 0;
  481.             }
  482.             if (ax && bx) {
  483.                 return less(ay, ax, by, bx);
  484.             }
  485.             return false;
  486.         });
  487.         if (stack2.empty()) {
  488.             xdir = normalize(xdi);
  489.             ydir = normalize(ydi);
  490.             zdir = normalize(zdi);
  491.         } else {
  492.             const vec& a = p[stack1.back()];
  493.             const vec& b = p[stack2.front()];
  494.             lll ax = a * xdi;
  495.             lll bx = b * xdi;
  496.             lll ay = a * ydi;
  497.             lll by = b * ydi;
  498.             if (ax == 0 && bx != 0 || ax != 0 && bx != 0 && less(-ay, -ax, by, bx)) {
  499.                 zdi = b ^ a;
  500.                 ydi = b;
  501.                 xdi = ydi ^ zdi;
  502.                 xdir = normalize(xdi);
  503.                 ydir = normalize(ydi);
  504.                 zdir = normalize(zdi);
  505.             } else if (p[stack2.back()] * xdi != 0 && ax != 0 && (bx == 0 || less(by, bx, -ay, -ax))) {
  506.                 for (ul i = 1; i <= n; ++i) {
  507.                     if (p[i] * zdi > 0) {
  508.                         std::printf("0.5\n");
  509.                         return 0;
  510.                     }
  511.                 }
  512.                 std::printf("1.0\n");
  513.                 return 0;
  514.             } else {
  515.                 xdi = -zdi;
  516.                 zdi = b;
  517.                 ydi = zdi ^ xdi;
  518.                 xdir = normalize(xdi);
  519.                 ydir = normalize(ydi);
  520.                 zdir = normalize(zdi);
  521.                 stack1.resize(0);
  522.                 for (ul i = 1; i <= n; ++i) {
  523.                     if (p[i] * xdi != 0 || p[i] * ydi != 0) {
  524.                         stack1.push_back(i);
  525.                     }
  526.                 }
  527.                 std::sort(stack1.begin(), stack1.end(), [&](ul i, ul j){
  528.                     const vec& a = p[i];
  529.                     const vec& b = p[j];
  530.                     lll ax = a * xdi;
  531.                     lll bx = b * xdi;
  532.                     lll ay = a * ydi;
  533.                     lll by = b * ydi;
  534.                     if (ax && bx) {
  535.                         return less(-ay, -ax, -by, -bx);
  536.                     }
  537.                     if (!ax && !bx) {
  538.                         return (ay > 0) > (by > 0);
  539.                     }
  540.                     if (ax && !bx) {
  541.                         return by < 0;
  542.                     }
  543.                     if (!ax && bx) {
  544.                         return ay > 0;
  545.                     }
  546.                     return false;
  547.                 });
  548.                 vecd u = normalize(vecd(p[stack1.front()] * xdir, p[stack1.front()] * ydir, 0));
  549.                 vecd v = normalize(vecd(p[stack1.back()] * xdir, p[stack1.back()] * ydir, 0));
  550.                 std::printf("%.12lf\n", lf(llf(1) - myacos(u * v) / pi / llf(2)));
  551.                 return 0;
  552.             }
  553.         }
  554.     }
  555.     for (ul i = 1; i <= n; ++i) {
  556.         p2[i] = vec(p[i] * xdi, p[i] * ydi, p[i] * zdi);
  557.     }
  558.     stack1.resize(0);
  559.     for (ul i = 1; i <= n; ++i) {
  560.         stack1.push_back(i);
  561.     }
  562.     gethulld(stack1, stackbuttom, stacktop);
  563.     llf ans = 0;
  564.     for (ul i = 0; i + 2 < stackbuttom.size(); ++i) {
  565.         heap.push(cnt(p[stackbuttom[i]], p[stackbuttom[i + 1]], p[stackbuttom[i + 2]]));
  566.     }
  567.     for (ul i = 0; i + 2 < stacktop.size(); ++i) {
  568.         heap.push(cnt(p[stacktop[i]], p[stacktop[i + 1]], p[stacktop[i + 2]]));
  569.     }
  570.     heap.push(cnt(p[stackbuttom[stackbuttom.size() - 2]], p[stacktop[0]], p[stacktop[1]]));
  571.     heap.push(cnt(p[stacktop[stacktop.size() - 2]], p[stackbuttom[0]], p[stackbuttom[1]]));
  572.     while (heap.size() >= 2) {
  573.         llf a = heap.top();
  574.         heap.pop();
  575.         llf b = heap.top();
  576.         heap.pop();
  577.         heap.push(a + b);
  578.     }
  579.     ans = heap.top() + pi + pi;
  580.     std::printf("%.12lf\n", lf(ans / pi / llf(4)));
  581.     return 0;
  582. }

J、Permutation

考虑这样一个状态：区间中左边区域中的数（除了某个别）可以随便乱排，右边区域中的数（除了某个别）可以随便乱排，第一个大情况是左边和右边无交，那么现在假设中最小的数在处，如果在中，那么说明的可行范围就是，而剩余问题化为，如果在中，那么说明的可行范围就是，而剩余问题化为，如果在上述两个区间之外，说明不能被移动，问题化为和，第二个大情况是和有交，说明剩余数都可以乱排。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul mod = 998244353;
  10. ul plus(ul a, ul b)
  11. {
  12.     return a + b < mod ? a + b : a + b - mod;
  13. }
  15. ul minus(ul a, ul b)
  16. {
  17.     return a < b ? a + mod - b : a - b;
  18. }
  20. ul mul(ul a, ul b)
  21. {
  22.     return ull(a) * ull(b) % mod;
  23. }
  25. ul T;
  27. ul n, c;
  29. ul sz;
  31. const ul mxsz = 1 << 19;
  33. const ul maxn = 5e5;
  35. ul fac[maxn + 1];
  37. ul v[maxn + 1];
  39. ul tree[mxsz << 1];
  41. ul query(ul l, ul r)
  42. {
  43.     ul ret = 0;
  44.     for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
  45.         if (~l & 1) {
  46.             ret = v[ret] < v[tree[l ^ 1]] ? ret : tree[l ^ 1];
  47.         }
  48.         if (r & 1) {
  49.             ret = v[ret] < v[tree[r ^ 1]] ? ret : tree[r ^ 1];
  50.         }
  51.     }
  52.     return ret;
  53. }
  55. void change(ul pos, ul val)
  56. {
  57.     v[pos] = val;
  58.     for (pos |= sz, pos >>= 1; pos; pos >>= 1) {
  59.         tree[pos] = v[tree[pos << 1]] < v[tree[pos << 1 | 1]] ? tree[pos << 1] : tree[pos << 1 | 1];
  60.     }
  61. }
  63. void build(ul n)
  64. {
  65.     sz = 1;
  66.     while (n + 2 > sz) {
  67.         sz <<= 1;
  68.     }
  69.     tree[sz] = 0;
  70.     for (ul i = 1; i <= n; ++i) {
  71.         tree[sz | i] = i;
  72.     }
  73.     for (ul i = n + 1; i != sz; ++i) {
  74.         tree[sz | i] = 0;
  75.     }
  76.     for (ul i = sz - 1; i; --i) {
  77.         tree[i] = v[tree[i << 1]] < v[tree[i << 1 | 1]] ? tree[i << 1] : tree[i << 1 | 1];
  78.     }
  79. }
  81. ul search(ul l, ul r, ul x, ul y)
  82. {
  83.     if (r - l + 1 < (x + y) * c) {
  84.         return fac[r - l + 1 - std::max(x, ul(1)) + 1 - std::max(y, ul(1)) + 1];
  85.     }
  86.     ul cut = query(l, r);
  87.     if (cut + 1 <= l + x * c) {
  88.         change(cut, maxn + 1);
  89.         return mul(x * c - (x - 1), search(l, r, x + 1, y));
  90.     }
  91.     if (cut + y * c >= r + 1) {
  92.         change(cut, maxn + 1);
  93.         return mul(y * c - (y - 1), search(l, r, x, y + 1));
  94.     }
  95.     return mul(search(l, cut - 1, x, cut - l >= c ? 1 : 0), search(cut + 1, r, r - cut >= c ? 1 : 0, y));
  96. }
  98. int main()
  99. {
  100.     fac[0] = 1;
  101.     for (ul i = 1; i <= maxn; ++i) {
  102.         fac[i] = mul(fac[i - 1], i);
  103.     }
  104.     std::scanf("%u", &T);
  105.     v[0] = maxn + 1;
  106.     for (ul Case = 1; Case <= T; ++Case) {
  107.         std::scanf("%u%u", &n, &c);
  108.         for (ul i = 1; i <= n; ++i) {
  109.             std::scanf("%u", &v[i]);
  110.         }
  111.         build(n);
  112.         std::printf("%u\n", search(1, n, 0, 0));
  113.     }
  114.     return 0;
  115. }

K、All Pair Maximum Flow

　　对于一个简单无向平面图（已经给出了到平面的嵌入），可以将边分为三类：连杆、外边、内边。考虑图的所有点双连通分量，在这些分量之外的边叫做连杆，对于一个点双连通分量，其最大的圈上的边叫做外边，其余边叫做内边。再将点分为两类：外点、内点。所有连杆以及外边上的点都叫外点，其余点都叫内点。
　　如果没有点双连通分量，则其显然为一个森林，如果其有点双连通分量，任取其一，称为。现考虑记该点双连通分量的最大圈为，中容量最小的边记为（如果有多个，任取其中一个即可），所在的圈中肯定有最小的，该圈记为。现在考虑建立一个新图，将中所有边的边权增加的边权，再把的边权改为，这样得到的新容量网络叫做。现在证明，对任何两个外点和，在中能够分离的最小割和中能够分离的最小割是相等的。
　　首先说明，无论在还是在中都有如下命题成立：如果存在有中边的最小割，那么存在刚好有中两条边，且刚好有中两条边，且其中一条边是的最小割。首先根据平面性以及和都是外点可知，有中边的最小割一定可以刚好有的两条边，且刚好有的两条边（严格在拓扑里说清楚这一点并不平凡），如果此割没有，则考虑将从中边到中边的其中一系列边换成，总有一个系列满足换完之后依旧是分离和的割，且由于是中容量最小的边，该换边行为并不会导致割增大。
　　接着注意到，任何满足“没中边，或者，存在刚好有中两条边，且刚好有中两条边，且其中一条边是”的割，在和中的值一定是相等的，因为正好在中的边权的减少量就是别的边的增加量，故在中能够分离的最小割和中能够分离的最小割是相等的。
　　接着，可以靠此方法，将中的边砍掉得到新图，该过程一直执行下去，直到最后得到一个森林，之后就很简单了。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  7. using llf = long double;
  9. const ul maxn = 2e5;
  10. ul n, m;
  12. std::map<ul, ull> graph[maxn + 1];
  14. ul next(ul a, ul b)
  15. {
  16.     auto it = std::next(graph[b].find(a));
  17.     return it == graph[b].end() ? graph[b].begin()->first : it->first;
  18. }
  20. class vec {
  21. public:
  22.     ll x = 0;
  23.     ll y = 0;
  24.     vec()=default;
  25.     vec(ll a, ll b): x(a), y(b) {}
  26. };
  28. vec operator+(const vec& a, const vec& b)
  29. {
  30.     return vec(a.x + b.x, a.y + b.y);
  31. }
  33. vec operator-(const vec& a, const vec& b)
  34. {
  35.     return vec(a.x - b.x, a.y - b.y);
  36. }
  38. ll operator*(const vec& a, const vec& b)
  39. {
  40.     return a.x * b.x + a.y * b.y;
  41. }
  43. ll operator^(const vec& a, const vec& b)
  44. {
  45.     return a.x * b.y - a.y * b.x;
  46. }
  48. ul tot = 0;
  50. vec p[maxn + 1];
  52. const ll tau = 104653;
  54. ll lowersqrt(ll x)
  55. {
  56.     ll tmp = std::llround(std::sqrt(llf(x)));
  57.     if (tmp * tmp > x) {
  58.         --tmp;
  59.     }
  60.     return tmp;
  61. }
  63. std::mt19937_64 rnd;
  65. using pulul = std::pair<ul, ul>;
  67. class hashmap {
  68. public:
  69.     class node {
  70.     public:
  71.         pulul key;
  72.         ul val = 0;
  73.     };
  74.     bool ex[1 << 22];
  75.     node v[1 << 22];
  76.     ul sz;
  77.     ul a;
  78.     ul b;
  79.     ul c;
  80.     const ul mod = 1e9 + 7;
  81.     void init(ul n)
  82.     {
  83.         a = rnd() % (mod - 1) + 1;
  84.         b = rnd() % (mod - 1) + 1;
  85.         c = rnd() % mod;
  86.         sz = 1;
  87.         while (sz + sz < n + n + n) {
  88.             sz <<= 1;
  89.         }
  90.         std::memset(ex, false, sz * sizeof(bool));
  91.     }
  92.     ul& operator[](const pulul& x)
  93.     {
  94.         ul h = (ull(x.first) * ull(a) + ull(x.second) * ull(b) + ull(c)) % mod & sz - 1;
  95.         while (true) {
  96.             if (!ex[h]) {
  97.                 ex[h] = true;
  98.                 v[h].key = x;
  99.                 v[h].val = 0;
  100.                 return v[h].val;
  101.             }
  102.             if (v[h].key == x) {
  103.                 return v[h].val;
  104.             }
  105.             h = h + 1 & sz - 1;
  106.         }
  107.     }
  108. };
  110. hashmap state;
  112. ul stack[maxn + 1];
  114. using pullpulul = std::pair<ull, pulul>;
  116. std::priority_queue<pullpulul, std::vector<pullpulul>, std::greater<pullpulul>> heap;
  118. std::priority_queue<pullpulul> heap2;
  120. ul fa[maxn + 1];
  121. ul rk[maxn + 1];
  122. ul cnt[maxn + 1];
  124. ul getfather(ul x)
  125. {
  126.     return x == fa[x] ? x : fa[x] = getfather(fa[x]);
  127. }
  129. void connect(ul x, ul y)
  130. {
  131.     x = getfather(x);
  132.     y = getfather(y);
  133.     if (rk[x] < rk[y]) {
  134.         fa[x] = y;
  135.         cnt[y] += cnt[x];
  136.     } else if (rk[x] > rk[y]) {
  137.         fa[y] = x;
  138.         cnt[x] += cnt[y];
  139.     } else {
  140.         fa[x] = y;
  141.         cnt[y] += cnt[x];
  142.         ++rk[y];
  143.     }
  144. }
  146. const ul mod = 998244353;
  148. ul plus(ul a, ul b)
  149. {
  150.     return a + b < mod ? a + b : a + b - mod;
  151. }
  153. ul mul(ul a, ul b)
  154. {
  155.     return ull(a) * ull(b) % mod;
  156. }
  158. int main()
  159. {
  160.     rnd.seed(std::time(0));
  161.     for (vec a(1, 0); a.x * a.x <= tau; ++a.x) {
  162.         ll t = lowersqrt(tau - a.x * a.x);
  163.         for (a.y = 0; a.y <= t; ++a.y) {
  164.             if (std::__gcd(a.x, a.y < 0 ? -a.y : a.y) != 1) {
  165.                 continue;
  166.             }
  167.             ++tot;
  168.             p[tot] = a;
  169.         }
  170.     }
  171.     std::sort(p + 1, p + tot + 1, [](const vec& a, const vec& b){return a.y * b.x < b.y * a.x;});
  172.     for (ul i = tot + 1; i <= maxn; ++i) {
  173.         p[i] = vec(-p[i - tot].y, p[i - tot].x);
  174.     }
  175.     for (ul i = 2; i <= maxn; ++i) {
  176.         p[i] = p[i - 1] + p[i];
  177.     }
  178.     std::scanf("%u%u", &n, &m);
  179.     for (ul i = 1; i <= m; ++i) {
  180.         ul u, v;
  181.         ull c;
  182.         std::scanf("%u%u%llu", &u, &v, &c);
  183.         graph[u][v] = c;
  184.         graph[v][u] = c;
  185.     }
  186.     state.init(m + m);
  187.     for (ul s = 1; s <= n; ++s) {
  188.         for (auto& e : graph[s]) {
  189.             ul t = e.first;
  190.             if (state[pulul(s, t)]) {
  191.                 continue;
  192.             }
  193.             ul tot = 1;
  194.             stack[1] = s;
  195.             ll sum = 0;
  196.             for (ul i = s, j = t; ; ) {
  197.                 sum += p[i] ^ p[j];
  198.                 if (j == s) {
  199.                     break;
  200.                 }
  201.                 ++tot;
  202.                 stack[tot] = j;
  203.                 ul nexj = next(i, j);
  204.                 i = j;
  205.                 j = nexj;
  206.             }
  207.             stack[0] = stack[tot];
  208.             ul tmp = sum < 0 ? 1 : 2;
  209.             for (ul i = 1; i <= tot; ++i) {
  210.                 ul s = stack[i - 1];
  211.                 ul t = stack[i];
  212.                 if (tmp == 2) {
  213.                     heap.push(pullpulul(graph[s][t], pulul(s, t)));
  214.                 }
  215.                 state[pulul(s, t)] = tmp;
  216.             }
  217.         }
  218.     }
  219.     while (heap.size()) {
  220.         auto c = heap.top();
  221.         heap.pop();
  222.         if (state[pulul(c.second.second, c.second.first)] == 2) {
  223.             continue;
  224.         }
  225.         if (graph[c.second.first][c.second.second] != c.first) {
  226.             continue;
  227.         }
  228.         for (ul i = c.second.first, j = next(c.second.second, c.second.first); j != c.second.first; ) {
  229.             ull a = graph[i][j] += c.first;
  230.             graph[j][i] += c.first;
  231.             state[pulul(i, j)] = 2;
  232.             heap.push(pullpulul(a, pulul(i, j)));
  233.             ul nexj = next(i, j);
  234.             i = j;
  235.             j = nexj;
  236.         }
  237.         graph[c.second.first].erase(c.second.second);
  238.         graph[c.second.second].erase(c.second.first);
  239.     }
  240.     for (ul i = 1; i <= n; ++i) {
  241.         cnt[i] = 1;
  242.         fa[i] = i;
  243.     }
  244.     for (ul i = 1; i <= n; ++i) {
  245.         for (auto& e : graph[i]) {
  246.             if (e.first > i) {
  247.                 break;
  248.             }
  249.             heap2.push(pullpulul(e.second, pulul(i, e.first)));
  250.         }
  251.     }
  252.     ul ans = 0;
  253.     while (heap2.size()) {
  254.         auto c = heap2.top();
  255.         heap2.pop();
  256.         ul x = getfather(c.second.first);
  257.         ul y = getfather(c.second.second);
  258.         ans = plus(ans, mul(c.first % mod, mul(cnt[x], cnt[y])));
  259.         connect(x, y);
  260.     }
  261.     std::printf("%u\n", ans);
  262.     return 0;
  263. }

L、

M、value

对每个非幂，考虑所有的幂，总共个，子集枚举。

  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 = 1e5;
  10. ul n;
  12. li a[maxn + 1];
  13. li b[maxn + 1];
  15. bool al[maxn + 1];
  17. ll ans = 0;
  19. ul js[18];
  21. ll tans[1 << 17];
  23. li minus[1 << 17][17];
  25. int main()
  26. {
  27.     std::scanf("%u", &n);
  28.     for (ul i = 1; i <= n; ++i) {
  29.         std::scanf("%d", &a[i]);
  30.     }
  31.     for (ul i = 1; i <= n; ++i) {
  32.         std::scanf("%d", &b[i]);
  33.     }
  34.     ul tot = 31 - __builtin_clz(n);
  35.     for (ul mask = 2; mask < (1 << tot + 1); mask += 2) {
  36.         for (ul cmask = mask; cmask; cmask ^= 1 << __builtin_ctz(cmask)) {
  37.             ul i = __builtin_ctz(cmask);
  38.             for (ul j = i << 1; j <= tot; j += i) {
  39.                 if (mask >> j & 1) {
  40.                     ++minus[mask][j];
  41.                 }
  42.             }
  43.         }
  44.     }
  45.     ans = a[1];
  46.     for (ul i = 2; i <= n; ++i) {
  47.         if (al[i]) {
  48.             continue;
  49.         }
  50.         ul tot = 0;
  51.         for (ull j = i; j <= n; j *= i) {
  52.             ++tot;
  53.             js[tot] = j;
  54.             al[j] = true;
  55.         }
  56.         ll mx = 0;
  57.         tans[0] = 0;
  58.         for (ul mask = 2; mask < (1 << tot + 1); mask += 2) {
  59.             ul id = 31 - __builtin_clz(mask);
  60.             tans[mask] = tans[mask ^ 1 << id] + a[js[id]];
  61.             ll tt = tans[mask];
  62.             for (ul j = 1; j <= tot; ++j) {
  63.                 tt -= ll(minus[mask][j]) * ll(b[js[j]]);
  64.             }
  65.             mx = std::max(mx, tt);
  66.         }
  67.         ans += mx;
  68.     }
  69.     std::printf("%lld\n", ans);
  70.     return 0;
  71. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注