[关闭]
@qq290637843 2021-03-10T13:44:44.000000Z 字数 20044 阅读 234

2019沈阳

一共有十三道题，其中十道题在此处可以提交https://ac.nowcoder.com/acm/contest/7830。
另外三道题的题面可以找我qq联系要题面，这三道题中有两道我有数据，但给我数据的人要求不外传，所以我只能帮忙代运行代码。

A、Leftbest

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. std::set<ul> set;
  10. int main()
  11. {
  12.     ull ans = 0;
  13.     ul n;
  14.     std::scanf("%u", &n);
  15.     for (ul i = 1; i <= n; ++i) {
  16.         ul a;
  17.         std::scanf("%u", &a);
  18.         auto it = std::next(set.insert(a).first);
  19.         if (it != set.end()) {
  20.             ans += *it;
  21.         }
  22.     }
  23.     std::printf("%llu\n", ans);
  24.     return 0;
  25. }

B、First Date

显然最短路长度关于构成一个凹函数，所以可以根据相邻两个采样点的次导数以及值来判断是否足够接近。

  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 lf = double;
  8. using llf = long double;
  10. ul n, m, s, t;
  11. const ul maxn = 200;
  13. class edge_t {
  14. public:
  15.     llf x = 0;
  16.     llf y = 0;
  17.     ul to = 0;
  18.     edge_t()=default;
  19.     edge_t(ul a, llf b, llf c): to(a), x(b), y(c) {}
  20. };
  22. class ach_t {
  23. public:
  24.     llf dis = 0;
  25.     ul to = 0;
  26.     ach_t()=default;
  27.     ach_t(ul a, llf b): to(a), dis(b) {}
  28. };
  30. bool operator<(const ach_t& a, const ach_t& b)
  31. {
  32.     return a.dis > b.dis;
  33. }
  35. std::vector<edge_t> edges[maxn + 1];
  37. const llf inf = 1e15;
  39. void calc(llf a, llf& ans, llf& dans)
  40. {
  41.     static llf dis[maxn + 1];
  42.     static llf ddis[maxn + 1];
  43.     static bool al[maxn + 1];
  44.     static std::priority_queue<ach_t> heap;
  45.     for (ul i = 1; i <= n; ++i) {
  46.         dis[i] = inf;
  47.         al[i] = false;
  48.     }
  49.     dis[s] = 0;
  50.     ddis[s] = 0;
  51.     heap.push(ach_t(s, 0));
  52.     while (heap.size()) {
  53.         auto curr = heap.top();
  54.         heap.pop();
  55.         if (al[curr.to]) {
  56.             continue;
  57.         }
  58.         al[curr.to] = true;
  59.         for (const auto& e : edges[curr.to]) {
  60.             llf newdis = a * e.y + e.x + curr.dis;
  61.             if (newdis < dis[e.to]) {
  62.                 dis[e.to] = newdis;
  63.                 ddis[e.to] = ddis[curr.to] + e.y;
  64.                 heap.push(ach_t(e.to, newdis));
  65.             }
  66.         }
  67.     }
  68.     ans = dis[t];
  69.     dans = ddis[t];
  70. }
  72. class point {
  73. public:
  74.     llf a = 0;
  75.     llf dis = 0;
  76.     llf ddis = 0;
  77.     point()=default;
  78.     point(llf x, llf y, llf z): a(x), dis(y), ddis(z) {}
  79. };
  81. std::vector<point> stack;
  83. std::priority_queue<llf, std::vector<llf>, std::greater<llf>> heap;
  85. const llf eps = 1e-4;
  87. int main()
  88. {
  89.     std::scanf("%u%u%u%u", &n, &m, &s, &t);
  90.     for (ul i = 1; i <= m; ++i) {
  91.         ul u, v;
  92.         lf x, y;
  93.         std::scanf("%u%u%lf%lf", &u, &v, &x, &y);
  94.         edges[u].push_back(edge_t(v, x, y));
  95.         edges[v].push_back(edge_t(u, x, y));
  96.     }
  97.     llf tans, tdans;
  98.     calc(0, tans, tdans);
  99.     stack.push_back(point(0, tans, tdans));
  100.     calc(1, tans, tdans);
  101.     stack.push_back(point(1, tans, tdans));
  102.     while (stack.size() >= 2) {
  103.         auto p2 = stack.back();
  104.         llf d2 = p2.ddis;
  105.         llf y2 = p2.dis;
  106.         llf x2 = p2.a;
  107.         stack.pop_back();
  108.         auto p1 = stack.back();
  109.         llf d1 = p1.ddis;
  110.         llf y1 = p1.dis;
  111.         llf x1 = p1.a;
  112.         if (ll(d2) == ll(d1)) {
  113.             heap.push((y1 + y2) * (x2 - x1) * llf(0.5));
  114.             continue;
  115.         }
  116.         point p3;
  117.         llf kk = x2 - x1;
  118.         llf sp = -(-d1 * kk + (y2 - y1)) * (-d2 * kk + (y2 - y1)) / (d1 - d2) / kk;
  119.         if (sp <= eps) {
  120.             heap.push((y1 + y2) * (x2 - x1) * llf(0.5));
  121.             continue;
  122.         }
  123.         p3.a = ((y2 - y1) + (x1 * d1 - x2 * d2)) / (d1 - d2);
  124.         calc(p3.a, p3.dis, p3.ddis);
  125.         stack.push_back(p3);
  126.         stack.push_back(p2);
  127.     }
  128.     while (heap.size() >= 2) {
  129.         auto a = heap.top();
  130.         heap.pop();
  131.         auto b = heap.top();
  132.         heap.pop();
  133.         heap.push(a + b);
  134.     }
  135.     std::printf("%.6lf\n", lf(heap.top()));
  136.     return 0;
  137. }

C、Sequence

第一个表达式的来源会用到https://chaoli.club/index.php/5490/
对于第个位置，使其好的数列数量为：

故所有好的（数列，位置）对的数量为
其中
可以直接多项式求商得出，将此记为，于是原式变为
这显然是一次卷积就能完成的。

  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 vul = std::vector<ul>;
  9. ul n, L;
  11. const ul maxn = 1e5;
  13. const ul base = 998244353;
  15. const ul& mod = base;
  17. ul plus(ul a, ul b)
  18. {
  19.     return a + b < base ? a + b : a + b - base;
  20. }
  22. ul minus(ul a, ul b)
  23. {
  24.     return a < b ? a + base - b : a - b;
  25. }
  27. ul mul(ul a, ul b)
  28. {
  29.     return ull(a) * ull(b) % base;
  30. }
  32. void exgcd(li a, li b, li& x, li& y)
  33. {
  34.     if (b) {
  35.         exgcd(b, a % b, y, x);
  36.         y -= x * (a / b);
  37.     } else {
  38.         x = 1;
  39.         y = 0;
  40.     }
  41. }
  43. ul inverse(ul a)
  44. {
  45.     li x, y;
  46.     exgcd(a, base, x, y);
  47.     return x < 0 ? x + li(base) : x;
  48. }
  50. ul pow(ul a, ul b)
  51. {
  52.     ul ret = 1;
  53.     ul temp = a;
  54.     while (b) {
  55.         if (b & 1) {
  56.             ret = mul(ret, temp);
  57.         }
  58.         temp = mul(temp, temp);
  59.         b >>= 1;
  60.     }
  61.     return ret;
  62. }
  64. class polynomial : public vul {
  65. public:
  66.     void clearzero() {
  67.         while (size() && !back()) {
  68.             pop_back();
  69.         }
  70.     }
  71.     polynomial()=default;
  72.     polynomial(const vul& a): vul(a) { }
  73.     polynomial(vul&& a): vul(std::move(a)) { }
  74.     ul degree() const {
  75.         return size() - 1;
  76.     }
  77.     ul operator()(ul x) const {
  78.         ul ret = 0;
  79.         for (ul i = size() - 1; ~i; --i) {
  80.             ret = mul(ret, x);
  81.             ret = plus(ret, vul::operator[](i));
  82.         }
  83.         return ret;
  84.     }
  85. };
  87. polynomial& operator-=(polynomial& a, const polynomial& b)
  88. {
  89.     a.resize(std::max(a.size(), b.size()), 0);
  90.     for (ul i = 0; i != b.size(); ++i) {
  91.         a[i] = minus(a[i], b[i]);
  92.     }
  93.     a.clearzero();
  94.     return a;
  95. }
  97. polynomial operator-(const polynomial& a, const polynomial& b)
  98. {
  99.     polynomial ret = a;
  100.     return ret -= b;
  101. }
  103. class ntt_t {
  104. public:
  105.     static const ul lgsz = 20;
  106.     static const ul sz = 1 << lgsz;
  107.     static const ul g = 3;
  108.     ul w[sz + 1];
  109.     ul leninv[lgsz + 1];
  110.     ntt_t() {
  111.         ul wn = pow(g, (base - 1) >> lgsz);
  112.         w[0] = 1;
  113.         for (ul i = 1; i <= sz; ++i) {
  114.             w[i] = mul(w[i - 1], wn);
  115.         }
  116.         leninv[lgsz] = inverse(sz);
  117.         for (ul i = lgsz - 1; ~i; --i) {
  118.             leninv[i] = plus(leninv[i + 1], leninv[i + 1]);
  119.         }
  120.     }
  121.     void operator()(vul& v, ul& n, bool inv) {
  122.         ul lgn = 0;
  123.         while ((1 << lgn) < n) {
  124.             ++lgn;
  125.         }
  126.         n = 1 << lgn;
  127.         v.resize(n, 0);
  128.         for (ul i = 0, j = 0; i != n; ++i) {
  129.             if (i < j) {
  130.                 std::swap(v[i], v[j]);
  131.             }
  132.             ul k = n >> 1;
  133.             while (k & j) {
  134.                 j &= ~k;
  135.                 k >>= 1;
  136.             }
  137.             j |= k;
  138.         }
  139.         for (ul lgmid = 0; (1 << lgmid) != n; ++lgmid) {
  140.             ul mid = 1 << lgmid;
  141.             ul len = mid << 1;
  142.             for (ul i = 0; i != n; i += len) {
  143.                 for (ul j = 0; j != mid; ++j) {
  144.                     ul t0 = v[i + j];
  145.                     ul t1 = mul(w[inv ? (len - j << lgsz - lgmid - 1) : (j << lgsz - lgmid - 1)], v[i + j + mid]);
  146.                     v[i + j] = plus(t0, t1);
  147.                     v[i + j + mid] = minus(t0, t1);
  148.                 }
  149.             }
  150.         }
  151.         if (inv) {
  152.             for (ul i = 0; i != n; ++i) {
  153.                 v[i] = mul(v[i], leninv[lgn]);
  154.             }
  155.         }
  156.     }
  157. } ntt;
  159. polynomial& operator*=(polynomial& a, const polynomial& b)
  160. {
  161.     if (!b.size() || !a.size()) {
  162.         a.resize(0);
  163.         return a;
  164.     }
  165.     polynomial temp = b;
  166.     ul npmp1 = a.size() + b.size() - 1;
  167.     if (ull(a.size()) * ull(b.size()) <= ull(npmp1) * ull(50)) {
  168.         temp.resize(0);
  169.         temp.resize(npmp1, 0);
  170.         for (ul i = 0; i != a.size(); ++i) {
  171.             for (ul j = 0; j != b.size(); ++j) {
  172.                 temp[i + j] = plus(temp[i + j], mul(a[i], b[j]));
  173.             }
  174.         }
  175.         a = temp;
  176.         a.clearzero();
  177.         return a;
  178.     }
  179.     ntt(a, npmp1, false);
  180.     ntt(temp, npmp1, false);
  181.     for (ul i = 0; i != npmp1; ++i) {
  182.         a[i] = mul(a[i], temp[i]);
  183.     }
  184.     ntt(a, npmp1, true);
  185.     a.clearzero();
  186.     return a;
  187. }
  189. polynomial operator*(const polynomial& a, const polynomial& b)
  190. {
  191.     polynomial ret = a;
  192.     return ret *= b;
  193. }
  195. polynomial& operator*=(polynomial& a, ul b)
  196. {
  197.     if (!b) {
  198.         a.resize(0);
  199.         return a;
  200.     }
  201.     for (ul i = 0; i != a.size(); ++i) {
  202.         a[i] = mul(a[i], b);
  203.     }
  204.     return a;
  205. }
  207. polynomial operator*(const polynomial& a, ul b)
  208. {
  209.     polynomial ret = a;
  210.     return ret *= b;
  211. }
  213. polynomial inverse(const polynomial& a, ul lgdeg)
  214. {
  215.     polynomial ret({inverse(a[0])});
  216.     polynomial temp;
  217.     polynomial tempa;
  218.     for (ul i = 0; i != lgdeg; ++i) {
  219.         tempa.resize(0);
  220.         tempa.resize(1 << i << 1, 0);
  221.         for (ul j = 0; j != tempa.size() && j != a.size(); ++j) {
  222.             tempa[j] = a[j];
  223.         }
  224.         temp = ret * (polynomial({2}) - tempa * ret);
  225.         if (temp.size() > (1 << i << 1)) {
  226.             temp.resize(1 << i << 1, 0);
  227.         }
  228.         temp.clearzero();
  229.         std::swap(temp, ret);
  230.     }
  231.     return ret;
  232. }
  234. ul fac[maxn + 1];
  235. ul fiv[maxn + 1];
  237. polynomial p1, p2, p3;
  239. ul binomial(ul a, ul b)
  240. {
  241.     return mul(fac[a], mul(fiv[b], fiv[a - b]));
  242. }
  244. int main()
  245. {
  246.     std::scanf("%u%u", &n, &L);
  247.     L %= mod;
  248.     fac[0] = 1;
  249.     for (ul i = 1; i <= n; ++i) {
  250.         fac[i] = mul(fac[i - 1], i);
  251.     }
  252.     fiv[n] = inverse(fac[n]);
  253.     for (ul i = n; i; --i) {
  254.         fiv[i - 1] = mul(fiv[i], i);
  255.     }
  256.     p1.resize(n);
  257.     p2.resize(n);
  258.     for (ul i = 1, Li = L; i <= n; ++i, Li = mul(Li, L)) {
  259.         p1[i - 1] = mul(Li, fiv[i]);
  260.         p2[i - 1] = fiv[i];
  261.     }
  262.     p2 = inverse(p2, 32 - __builtin_clz(n - 1));
  263.     p2.resize(n);
  264.     p3 = p1 * p2;
  265.     p3.resize(n);
  266.     p1.resize(n);
  267.     p2.resize(n);
  268.     for (ul r = n - 1, Lnm1mr = 1; r >= 1; --r, Lnm1mr = mul(Lnm1mr, L)) {
  269.         p1[r] = mul(mul(mul(mul(p3[r], fac[r]), binomial(n, r + 1)), Lnm1mr), fac[r - 1]);
  270.         if (r & 1) {
  271.             p1[r] = minus(0, p1[r]);
  272.         }
  273.         p2[r] = fiv[r];
  274.     }
  275.     p2[0] = fiv[0];
  276.     std::reverse(p1.begin(), p1.end());
  277.     p3 = p1 * p2;
  278.     p3.resize(n);
  279.     std::reverse(p3.begin(), p3.end());
  280.     for (ul k = 1; k <= n - 1; ++k) {
  281.         p3[k] = mul(p3[k], fiv[k - 1]);
  282.         if (k & 1) {
  283.             p3[k] = minus(0, p3[k]);
  284.         }
  285.         std::printf("%u ", p3[k]);
  286.     }
  287.     std::printf("0\n");
  288.     return 0;
  289. }

D、Quickpow

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  7. using llf = long double;
  9. ul n;
  10. const ul maxn = 1e5;
  12. ul a[maxn + 1];
  14. ul mn = 1e9;
  16. ul cnt[11];
  18. int main()
  19. {
  20.     std::scanf("%u", &n);
  21.     for (ul i = 1; i <= n; ++i) {
  22.         std::scanf("%u", &a[i]);
  23.         mn = std::min(mn, a[i]);
  24.     }
  25.     for (ul i = 1; i <= n; ++i) {
  26.         a[i] -= mn;
  27.         ++cnt[a[i]];
  28.     }
  29.     llf sum = 0;
  30.     for (ul i = 10; ~i; --i) {
  31.         sum = sum * std::exp(llf(1));
  32.         sum += llf(cnt[i]);
  33.     }
  34.     for (ul i = 1; i <= n; ++i) {
  35.         if (i != 1) {
  36.             std::putchar(' ');
  37.         }
  38.         std::printf("%.8lf", std::exp(llf(a[i])) / sum);
  39.     }
  40.     std::putchar('\n');
  41.     return 0;
  42. }

E、Capture Stars

虚线圆的圆心称为，小圆圆心称为，大圆圆心称为，于是

故构成一个椭圆，其以和为焦点。现以为极心建立极坐标系，以为零度方向。于是该椭圆的方程为
现在考虑两点的距离，显然此二点的距离为
于是点所对应的圆能框住某点当且仅当：
即
借助万能公式并将记为，上式改为：
解二次方程即可。

  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;
  8. using lf = double;
  10. ul T;
  12. ul n;
  14. const ul maxn = 1e4;
  16. llf R, r;
  18. llf in()
  19. {
  20.     lf tmp;
  21.     std::scanf("%lf", &tmp);
  22.     return tmp;
  23. }
  25. void calc(llf a, llf b, llf c, llf& ans1, llf& ans2)
  26. {
  27.     llf delta = std::max(b * b - llf(4) * a * c, llf(0));
  28.     ans1 = (-b - std::sqrt(delta)) / (a + a);
  29.     ans2 = (-b + std::sqrt(delta)) / (a + a);
  30. }
  32. ul tot;
  33. std::pair<llf, char> v[maxn + maxn + 1];
  35. int main()
  36. {
  37.     std::scanf("%u", &T);
  38.     for (ul Case = 1; Case <= T; ++Case) {
  39.         std::scanf("%u", &n);
  40.         R = in();
  41.         r = in();
  42.         tot = 0;
  43.         for (ul i = 1; i <= n; ++i) {
  44.             llf x = in();
  45.             llf y = in();
  46.             llf rhos = std::sqrt((x - r) * (x - r) + y * y);
  47.             llf costhetas = (x - r) / rhos;
  48.             llf sinthetas = y / rhos;
  49.             llf t1, t2;
  50.             calc(r * r * R + R * rhos * rhos + 2 * r * R * rhos * costhetas, -4 * r * R * rhos * sinthetas, -r * r * r + 2 * r * r * R + r * rhos * rhos - 2 * r * R * rhos * costhetas, t1, t2);
  51.             if (t1 > t2) {
  52.                 std::swap(t1, t2);
  53.             }
  54.             ++tot;
  55.             v[tot].first = t1;
  56.             v[tot].second = '(';
  57.             ++tot;
  58.             v[tot].first = t2;
  59.             v[tot].second = ')';
  60.         }
  61.         std::sort(v + 1, v + n + n + 1);
  62.         ul mx = 0;
  63.         ul cnt = 0;
  64.         for (ul i = 1; i <= n + n; ++i) {
  65.             if (v[i].second == '(') {
  66.                 ++cnt;
  67.                 mx = std::max(mx, cnt);
  68.             } else if (v[i].second == ')') {
  69.                 --cnt;
  70.             }
  71.         }
  72.         std::printf("%u\n", mx);
  73.     }
  74.     return 0;
  75. }

F、Crossroads

没有数据，搁置

G、Triangulation

简单题

  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;
  8. using lf = double;
  10. ul n;
  12. const ul maxn = 200;
  14. ll x[maxn + 1];
  15. ll y[maxn + 1];
  17. bool already[maxn + 1][maxn + 1];
  18. ul ans[maxn + 1][maxn + 1];
  20. const ul mod = 998244353;
  22. ul plus(ul a, ul b)
  23. {
  24.     return a + b < mod ? a + b : a + b - mod;
  25. }
  27. ul mul(ul a, ul b)
  28. {
  29.     return ull(a) * ull(b) % mod;
  30. }
  32. ul calc(ul l, ul r)
  33. {
  34.     if (already[l][r]) {
  35.         return ans[l][r];
  36.     }
  37.     already[l][r] = true;
  38.     if (l + 1 == r) {
  39.         return ans[l][r] = 1;
  40.     }
  41.     for (ul m = l + 1; m + 1 <= r; ++m) {
  42.         if ((x[r] - x[m]) * (y[l] - y[m]) - (x[l] - x[m]) * (y[r] - y[m]) > 0) {
  43.             ans[l][r] = plus(ans[l][r], mul(calc(l, m), calc(m, r)));
  44.         }
  45.     }
  46.     return ans[l][r];
  47. }
  49. int main()
  50. {
  51.     std::scanf("%u", &n);
  52.     ll sum = 0;
  53.     for (ul i = 1; i <= n; ++i) {
  54.         std::scanf("%lld%lld", &x[i], &y[i]);
  55.         if (i != 1) {
  56.             sum += x[i - 1] * y[i] - x[i] * y[i - 1];
  57.         }
  58.     }
  59.     sum += x[n] * y[1] - x[1] * y[n];
  60.     if (sum < 0) {
  61.         std::reverse(x + 1, x + n + 1);
  62.         std::reverse(y + 1, y + n + 1);
  63.     }
  64.     std::printf("%u\n", calc(1, n));
  65.     return 0;
  66. }

H、Points

简单题

  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;
  10. const ul maxn = 2e5;
  12. ul d[maxn + 1];
  14. ul cnt = 0;
  16. int main()
  17. {
  18.     std::scanf("%u", &n);
  19.     for (ul i = 1; i <= n - 1; ++i) {
  20.         ul a, b;
  21.         std::scanf("%u%u", &a, &b);
  22.         ++d[a];
  23.         ++d[b];
  24.     }
  25.     for (ul i = 1; i <= n; ++i) {
  26.         if (d[i] == 1) {
  27.             ++cnt;
  28.         }
  29.     }
  30.     std::printf("%u\n", cnt);
  31.     return 0;
  32. }

I、Parallel Network Analysis

一个排列如果满足以下二条件之一，则称其为双调排列：
1、升降升，且首项大于等于尾项；
2、降升降，且首项小于等于尾项。
注意，升降、降升、升、降序列都复合以上要求。
现在考虑有一长为的双调序列，那么简单分类讨论可证（为了符合直观印象，建议画图），和都是长为的双调序列，且第一个序列的最大值小于等于第二个序列的最小值。由此可知，如果一个长为的序列一开始是双调的，那么只要经过次这样的合并过程就变成升序列了。
现在假设有一长的序列，其中前已经是升序，后已经是升序，那么显然和都是长为的双调序列（第一个显然是升降序列，第二个显然是降升序列，建议画图一眼看出），且第一个序列的最大值小于等于第二个序列的最小值，接着再使用上一段的结论可以得到长为的升序列。

  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;
  10. std::vector<std::pair<ul, ul>> a[106];
  12. void bisort(ul l, ul r, ul tot)
  13. {
  14.     if (l + 1 == r) {
  15.         return;
  16.     }
  17.     ++tot;
  18.     for (ul i = l, j = r + l >> 1; j != r; ++i, ++j) {
  19.         if (j < n) {
  20.             a[tot].push_back(std::pair<ul, ul>(i, j));
  21.         }
  22.     }
  23.     bisort(l, l + r >> 1, tot);
  24.     bisort(l + r >> 1, r, tot);
  25. }
  27. void sort(ul l, ul r, ul tot)
  28. {
  29.     if (l + 1 == r) {
  30.         return;
  31.     }
  32.     sort(l, l + r >> 1, tot - __builtin_ctz(r - l));
  33.     sort(l + r >> 1, r, tot - __builtin_ctz(r - l));
  34.     tot -= __builtin_ctz(r - l);
  35.     ++tot;
  36.     for (ul i = l, j = r - 1; i < j; ++i, --j) {
  37.         if (j < n) {
  38.             a[tot].push_back(std::pair<ul, ul>(i, j));
  39.         }
  40.     }
  41.     bisort(l, l + r >> 1, tot);
  42.     bisort(l + r >> 1, r, tot);
  43. }
  45. int main()
  46. {
  47.     std::scanf("%u", &n);
  48.     ul tot = 0;
  49.     ul k = 32 - __builtin_clz(n - 1);
  50.     if (n == 1 || n == 0) {
  51.         k = 0;
  52.     }
  53.     for (ul i = 1; i <= k; ++i) {
  54.         tot += i;
  55.     }
  56.     sort(0, 1 << k, tot);
  57.     std::printf("%u\n", tot);
  58.     for (ul i = 1; i <= tot; ++i) {
  59.         std::printf("%u\n", ul(a[i].size()));
  60.         for (auto p : a[i]) {
  61.             std::printf("%u %u\n", p.first, p.second);
  62.         }
  63.     }
  64.     return 0;
  65. }

J、Graph

根据一号操作的要求可知，图任何时刻都是一个森林，故考虑用割连树维护。关于查询，考虑给每个需要的点对定义一个随机数，分别给和所属的树异或上该，于是所有点对都连通当且仅当每棵树的异或值都是。

  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. inline void swap(ul& a, ul& b)
  11. {
  12.     a ^= b ^= a ^= b;
  13. }
  15. class link_cut_tree {
  16. public:
  17.     ul c[maxn + 1][2], fa[maxn + 1], top, q[maxn + 1], rev[maxn + 1];
  18.     ull sum[maxn + 1];
  19.     ul cnt;
  20.     inline void init(ul n) {
  21.         for (ul i = 1; i <= n; ++i) {
  22.             c[i][0] = c[i][1] = fa[i] = rev[i] = sum[i] = 0;
  23.         }
  24.         cnt = 0;
  25.     }
  26.     inline void cfa(ul x, ul y) {
  27.         if (fa[x]) {
  28.             sum[fa[x]] ^= sum[x];
  29.         }
  30.         fa[x] = y;
  31.         if (fa[x]) {
  32.             sum[fa[x]] ^= sum[x];
  33.         }
  34.     }
  35.     inline void pushdown(ul x) {
  36.         if (rev[x]) {
  37.             ul l = c[x][0], r = c[x][1];
  38.             rev[l] ^= 1, rev[r] ^= 1, rev[x] ^= 1;
  39.             swap(c[x][0], c[x][1]);
  40.         }
  41.     }
  42.     inline bool isroot(ul x) {
  43.         return c[fa[x]][0] != x && c[fa[x]][1] != x;
  44.     }
  45.     inline void rotate(ul x) {
  46.         ul y = fa[x], z = fa[y], l, r;
  47.         l = c[y][0] != x;
  48.         r = l ^ 1;
  49.         if (!isroot(y)) {
  50.             c[z][c[z][0] != y] = x;
  51.         }
  52.         ull tmp1 = sum[x] ^ sum[c[x][r]];
  53.         ull tmp2 = sum[y] ^ sum[x];
  54.         sum[y] ^= tmp1;
  55.         sum[x] ^= tmp2;
  56.         fa[x] = z;
  57.         fa[y] = x;
  58.         fa[c[x][r]] = y;
  59.         c[y][l] = c[x][r];
  60.         c[x][r] = y;
  61.     }
  62.     inline void splay(ul x) {
  63.         top = 1;
  64.         q[top] = x;
  65.         for (ul i = x; !isroot(i); i = fa[i]) {
  66.             q[++top] = fa[i];
  67.         }
  68.         for (ul i = top; i; --i) {
  69.             pushdown(q[i]);
  70.         }
  71.         while (!isroot(x)) {
  72.             ul y = fa[x], z = fa[y];
  73.             if (!isroot(y)) {
  74.                 rotate((c[y][0] == x) != (c[z][0] == y) ? x : y);
  75.             }
  76.             rotate(x);
  77.         }
  78.     }
  79.     inline void access(ul x) {
  80.         ul xx = x;
  81.         for (ul t = 0; x; t = x, x = fa[x]) {
  82.             splay(x);
  83.             c[x][1] = t;
  84.         }
  85.         splay(xx);
  86.     }
  87.     inline void evert(ul x) {
  88.         access(x);
  89.         rev[x] ^= 1;
  90.     }
  91.     inline void cut(ul x, ul y) {
  92.         evert(x);
  93.         if (sum[x]) {
  94.             --cnt;
  95.         }
  96.         access(y);
  97.         c[y][0] = 0;
  98.         cfa(x, 0);
  99.         access(x);
  100.         if (sum[x]) {
  101.             ++cnt;
  102.         }
  103.         access(y);
  104.         if (sum[y]) {
  105.             ++cnt;
  106.         }
  107.     }
  108.     inline void link(ul x, ul y) {
  109.         evert(x);
  110.         if (sum[x]) {
  111.             --cnt;
  112.         }
  113.         access(y);
  114.         if (sum[y]) {
  115.             --cnt;
  116.         }
  117.         cfa(x, y);
  118.         if (sum[y]) {
  119.             ++cnt;
  120.         }
  121.     }
  122.     inline void change(ul x, ull v) {
  123.         access(x);
  124.         if (sum[x]) {
  125.             --cnt;
  126.         }
  127.         sum[x] ^= v;
  128.         if (sum[x]) {
  129.             ++cnt;
  130.         }
  131.     }
  132. };
  134. link_cut_tree tree;
  136. ul T;
  137. ul n, q;
  139. std::map<ull, ull> w;
  141. std::mt19937_64 rnd;
  143. int main()
  144. {
  145.     rnd.seed(std::time(0));
  146.     std::scanf("%u", &T);
  147.     for (ul Case = 1; Case <= T; ++Case) {
  148.         std::scanf("%u%u", &n, &q);
  149.         tree.init(n);
  150.         for (ul i = 1; i <= q; ++i) {
  151.             ul Type;
  152.             std::scanf("%u", &Type);
  153.             if (Type != 5) {
  154.                 ul u, v;
  155.                 std::scanf("%u%u", &u, &v);
  156.                 if (Type == 1) {
  157.                     tree.link(u, v);
  158.                 } else if (Type == 2) {
  159.                     tree.cut(u, v);
  160.                 } else if (Type == 3) {
  161.                     ull t = w[ull(u) << 32 | v] = rnd();
  162.                     tree.change(u, t);
  163.                     tree.change(v, t);
  164.                 } else if (Type == 4) {
  165.                     ull t = w[ull(u) << 32 | v];
  166.                     tree.change(u, t);
  167.                     tree.change(v, t);
  168.                 }
  169.             } else {
  170.                 std::printf(tree.cnt ? "NO\n" : "YES\n");
  171.             }
  172.         }
  173.     }
  174.     return 0;
  175. }

K、Rooted Tree

就是问的整数划分方案数，直接五边形数定理。

  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 vul = std::vector<ul>;
  9. ul n;
  11. const ul base = 998244353;
  13. ul plus(ul a, ul b)
  14. {
  15.     return a + b < base ? a + b : a + b - base;
  16. }
  18. ul minus(ul a, ul b)
  19. {
  20.     return a < b ? a + base - b : a - b;
  21. }
  23. ul mul(ul a, ul b)
  24. {
  25.     return ull(a) * ull(b) % base;
  26. }
  28. void exgcd(li a, li b, li& x, li& y)
  29. {
  30.     if (b) {
  31.         exgcd(b, a % b, y, x);
  32.         y -= x * (a / b);
  33.     } else {
  34.         x = 1;
  35.         y = 0;
  36.     }
  37. }
  39. ul inverse(ul a)
  40. {
  41.     li x, y;
  42.     exgcd(a, base, x, y);
  43.     return x < 0 ? x + li(base) : x;
  44. }
  46. ul pow(ul a, ul b)
  47. {
  48.     ul ret = 1;
  49.     ul temp = a;
  50.     while (b) {
  51.         if (b & 1) {
  52.             ret = mul(ret, temp);
  53.         }
  54.         temp = mul(temp, temp);
  55.         b >>= 1;
  56.     }
  57.     return ret;
  58. }
  60. class polynomial : public vul {
  61. public:
  62.     void clearzero() {
  63.         while (size() && !back()) {
  64.             pop_back();
  65.         }
  66.     }
  67.     polynomial()=default;
  68.     polynomial(const vul& a): vul(a) { }
  69.     polynomial(vul&& a): vul(std::move(a)) { }
  70.     ul degree() const {
  71.         return size() - 1;
  72.     }
  73.     ul operator()(ul x) const {
  74.         ul ret = 0;
  75.         for (ul i = size() - 1; ~i; --i) {
  76.             ret = mul(ret, x);
  77.             ret = plus(ret, vul::operator[](i));
  78.         }
  79.         return ret;
  80.     }
  81. };
  83. polynomial& operator+=(polynomial& a, const polynomial& b)
  84. {
  85.     a.resize(std::max(a.size(), b.size()), 0);
  86.     for (ul i = 0; i != b.size(); ++i) {
  87.         a[i] = plus(a[i], b[i]);
  88.     }
  89.     a.clearzero();
  90.     return a;
  91. }
  93. polynomial operator+(const polynomial& a, const polynomial& b)
  94. {
  95.     polynomial ret = a;
  96.     return ret += b;
  97. }
  99. polynomial& operator-=(polynomial& a, const polynomial& b)
  100. {
  101.     a.resize(std::max(a.size(), b.size()), 0);
  102.     for (ul i = 0; i != b.size(); ++i) {
  103.         a[i] = minus(a[i], b[i]);
  104.     }
  105.     a.clearzero();
  106.     return a;
  107. }
  109. polynomial operator-(const polynomial& a, const polynomial& b)
  110. {
  111.     polynomial ret = a;
  112.     return ret -= b;
  113. }
  115. class ntt_t {
  116. public:
  117.     static const ul lgsz = 20;
  118.     static const ul sz = 1 << lgsz;
  119.     static const ul g = 3;
  120.     ul w[sz + 1];
  121.     ul leninv[lgsz + 1];
  122.     ntt_t() {
  123.         ul wn = pow(g, (base - 1) >> lgsz);
  124.         w[0] = 1;
  125.         for (ul i = 1; i <= sz; ++i) {
  126.             w[i] = mul(w[i - 1], wn);
  127.         }
  128.         leninv[lgsz] = inverse(sz);
  129.         for (ul i = lgsz - 1; ~i; --i) {
  130.             leninv[i] = plus(leninv[i + 1], leninv[i + 1]);
  131.         }
  132.     }
  133.     void operator()(vul& v, ul& n, bool inv) {
  134.         ul lgn = 0;
  135.         while ((1 << lgn) < n) {
  136.             ++lgn;
  137.         }
  138.         n = 1 << lgn;
  139.         v.resize(n, 0);
  140.         for (ul i = 0, j = 0; i != n; ++i) {
  141.             if (i < j) {
  142.                 std::swap(v[i], v[j]);
  143.             }
  144.             ul k = n >> 1;
  145.             while (k & j) {
  146.                 j &= ~k;
  147.                 k >>= 1;
  148.             }
  149.             j |= k;
  150.         }
  151.         for (ul lgmid = 0; (1 << lgmid) != n; ++lgmid) {
  152.             ul mid = 1 << lgmid;
  153.             ul len = mid << 1;
  154.             for (ul i = 0; i != n; i += len) {
  155.                 for (ul j = 0; j != mid; ++j) {
  156.                     ul t0 = v[i + j];
  157.                     ul t1 = mul(w[inv ? (len - j << lgsz - lgmid - 1) : (j << lgsz - lgmid - 1)], v[i + j + mid]);
  158.                     v[i + j] = plus(t0, t1);
  159.                     v[i + j + mid] = minus(t0, t1);
  160.                 }
  161.             }
  162.         }
  163.         if (inv) {
  164.             for (ul i = 0; i != n; ++i) {
  165.                 v[i] = mul(v[i], leninv[lgn]);
  166.             }
  167.         }
  168.     }
  169. } ntt;
  171. polynomial& operator*=(polynomial& a, const polynomial& b)
  172. {
  173.     if (!b.size() || !a.size()) {
  174.         a.resize(0);
  175.         return a;
  176.     }
  177.     polynomial temp = b;
  178.     ul npmp1 = a.size() + b.size() - 1;
  179.     if (ull(a.size()) * ull(b.size()) <= ull(npmp1) * ull(50)) {
  180.         temp.resize(0);
  181.         temp.resize(npmp1, 0);
  182.         for (ul i = 0; i != a.size(); ++i) {
  183.             for (ul j = 0; j != b.size(); ++j) {
  184.                 temp[i + j] = plus(temp[i + j], mul(a[i], b[j]));
  185.             }
  186.         }
  187.         a = temp;
  188.         a.clearzero();
  189.         return a;
  190.     }
  191.     ntt(a, npmp1, false);
  192.     ntt(temp, npmp1, false);
  193.     for (ul i = 0; i != npmp1; ++i) {
  194.         a[i] = mul(a[i], temp[i]);
  195.     }
  196.     ntt(a, npmp1, true);
  197.     a.clearzero();
  198.     return a;
  199. }
  201. polynomial operator*(const polynomial& a, const polynomial& b)
  202. {
  203.     polynomial ret = a;
  204.     return ret *= b;
  205. }
  207. polynomial& operator*=(polynomial& a, ul b)
  208. {
  209.     if (!b) {
  210.         a.resize(0);
  211.         return a;
  212.     }
  213.     for (ul i = 0; i != a.size(); ++i) {
  214.         a[i] = mul(a[i], b);
  215.     }
  216.     return a;
  217. }
  219. polynomial operator*(const polynomial& a, ul b)
  220. {
  221.     polynomial ret = a;
  222.     return ret *= b;
  223. }
  225. polynomial inverse(const polynomial& a, ul lgdeg)
  226. {
  227.     polynomial ret({inverse(a[0])});
  228.     polynomial temp;
  229.     polynomial tempa;
  230.     for (ul i = 0; i != lgdeg; ++i) {
  231.         tempa.resize(0);
  232.         tempa.resize(1 << i << 1, 0);
  233.         for (ul j = 0; j != tempa.size() && j != a.size(); ++j) {
  234.             tempa[j] = a[j];
  235.         }
  236.         temp = ret * (polynomial({2}) - tempa * ret);
  237.         if (temp.size() > (1 << i << 1)) {
  238.             temp.resize(1 << i << 1, 0);
  239.         }
  240.         temp.clearzero();
  241.         std::swap(temp, ret);
  242.     }
  243.     return ret;
  244. }
  246. polynomial v;
  248. int main()
  249. {
  250.     std::scanf("%u", &n);
  251.     v.resize(n);
  252.     v[0] = 1;
  253.     for (ul k = 1; k * (3 * k - 1) <= 2 * (n - 1); ++k) {
  254.         ul t;
  255.         t = (k & 1) ? minus(0, 1) : ul(1);
  256.         if (k * (3 * k + 1) / 2 <= n - 1) {
  257.             v[k * (3 * k + 1) >> 1] = t;
  258.         }
  259.         v[k * (3 * k - 1) >> 1] = t;
  260.     }
  261.     v = inverse(v, n - 1 ? ul(32 - __builtin_clz(n - 1)) : ul(0));
  262.     v.resize(n);
  263.     std::printf("%u\n", v[n - 1]);
  264.     return 0;
  265. }

L、Flowers

二分贪心

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul n, m;
  10. const ul maxn = 300000;
  12. ul T;
  14. ul a[maxn + 1];
  16. int main()
  17. {
  18.     std::scanf("%u", &T);
  19.     for (ul Case = 1; Case <= T; ++Case) {
  20.         std::scanf("%u%u", &n, &m);
  21.         for (ul i = 1; i <= n; ++i) {
  22.             std::scanf("%u", &a[i]);
  23.         }
  24.         ull l = 0, r = ull(1e9) * ull(n) / ull(m) + 1;
  25.         while (l + 1 != r) {
  26.             ull mid = l + r >> 1;
  27.             ul Q = 0;
  28.             ull R = 0;
  29.             for (ul i = 1; i <= n; ++i) {
  30.                 if (a[i] >= mid) {
  31.                     ++Q;
  32.                 } else {
  33.                     R += a[i];
  34.                     if (R >= mid) {
  35.                         R -= mid;
  36.                         ++Q;
  37.                     }
  38.                 }
  39.             }
  40.             if (Q >= m) {
  41.                 l = mid;
  42.             } else {
  43.                 r = mid;
  44.             }
  45.         }
  46.         std::printf("%llu\n", l);
  47.     }
  48.     return 0;
  49. }

M、Interesting Strings

出题人给的数据过了，但是不知道是不是强化之后的数据。

  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 uss = std::uint8_t;
  9. const ul maxlen = 2e5;
  11. ul T;
  13. class pam_t {
  14. public:
  15.     ul las;
  16.     class node {
  17.     public:
  18.         ul ch[26];
  19.         ul len = 0;
  20.         ul fa = 0;
  21.         ul anc = 0;
  22.         node()=default;
  23.         node(ul a, ul b): len(a), fa(b) {
  24.             std::memset(ch, 0, sizeof(ch));
  25.         }
  26.     };
  27.     std::vector<node> st = std::vector<node>(maxlen + 2);
  28.     std::vector<uss> str = std::vector<uss>(maxlen + 1);
  29.     ul newnode(ul len, ul fail = 0) {
  30.         st.push_back(node(len, fail));
  31.         return st.size() - 1;
  32.     }
  33.     ul getfail(ul x, ul n) {
  34.         while (str[n - st[x].len - 1] != str[n]) {
  35.             x = st[x].fa;
  36.         }
  37.         return x;
  38.     }
  39.     bool add(ul c) {
  40.         ul i = str.size();
  41.         str.push_back(c);
  42.         ul cur = getfail(las, i);
  43.         bool flag = false;
  44.         if (!st[cur].ch[c]) {
  45.             ul nw = newnode(st[cur].len + 2, st[getfail(st[cur].fa, i)].ch[c]);
  46.             st[cur].ch[c] = nw;
  47.             st[nw].anc = st[nw].len - st[st[nw].fa].len != st[st[nw].fa].len - st[st[st[nw].fa].fa].len ? st[nw].fa : st[st[nw].fa].anc;
  48.             flag = true;
  49.         }
  50.         las = st[cur].ch[c];
  51.         return flag;
  52.     }
  53.     void init() {
  54.         str.resize(0);
  55.         str.resize(1, 26);
  56.         st.resize(0);
  57.         newnode(0, 1);
  58.         st[1].anc = 0;
  59.         newnode(-1, 0);
  60.         las = 0;
  61.     }
  62. };
  64. pam_t pam;
  66. char str[maxlen + 2];
  68. li f[maxlen + 1][4];
  70. li g[maxlen + 1][3];
  72. ul gdiff[maxlen + 1][3];
  74. ul Case;
  76. li getg(li x, ul y, li diff, li fx)
  77. {
  78.     if (x == fx) {
  79.         return f[x][y] - x;
  80.     }
  81.     if (gdiff[x][y] == diff) {
  82.         return g[x][y];
  83.     }
  84.     gdiff[x][y] = diff;
  85.     return g[x][y] = std::max(f[x][y] - x, getg(x - diff, y, diff, fx));
  86. }
  88. int main()
  89. {
  90.     std::scanf("%u", &T);
  91.     for (Case = 1; Case <= T; ++Case) {
  92.         pam.init();
  93.         std::scanf("%s", str + 1);
  94.         li len = std::strlen(str + 1);
  95.         for (li x = 1; x <= len; ++x) {
  96.             pam.add(str[x] - 'a');
  97.             gdiff[x][0] = gdiff[x][1] = gdiff[x][2] = 0;
  98.             for (ul y = 1; y <= 3; ++y) {
  99.                 f[x][y] = f[x - 1][y];
  100.                 for (ul las = pam.las; las; las = pam.st[las].anc) {
  101.                     li diff = pam.st[las].len - pam.st[pam.st[las].fa].len;
  102.                     li z = x - pam.st[pam.st[las].anc].len - diff;
  103.                     li fz = x - pam.st[las].len;
  104.                     f[x][y] = std::max(f[x][y], x + getg(z, y - 1, diff, fz));
  105.                 }
  106.             }
  107.         }
  108.         std::printf("%u\n", f[len][3]);
  109.     }
  110.     return 0;
  111. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注