[关闭]
@qq290637843 2020-09-28T05:02:19.000000Z 字数 31730 阅读 734

2020杭电第十场

A、Anti-hash Test 6877

　　该题需要用到有限Thue-Morse串的紧致后缀自动机。关于其结构的证明见https://chaoli.club/index.php/5638，当然，此论文的证明有一些纰漏，暂时没能解决。
　　虽然那篇论文里犯了错误，不等于该题解就要继承那个错误。在该题解中，左右特殊子串定义如下：
（1）如果一个串满足以下两个条件的析取，则称是的左特殊子串：
　　①是的前缀；
　　②存在不同的字符和满足和都是的子串；
（2）如果一个串满足以下两个条件的析取，则称是的右特殊子串：
　　①是的后缀；
　　②存在不同的字符和满足和都是的子串；
如果一个串既是的左特殊子串，又是的右特殊子串，则称为的双特殊子串。
　　于是可知，的紧致后缀自动机中所保留的点对应的就是的双特殊子串。
　　对于输入，只要将作为输入在的紧致后缀自动机上运行，最后到达的节点，实际上就是满足“是的子串且是的双特殊子串”的最短的。并且还要注意到，如果紧致后缀自动机中经过（是字符，是字符串）到达，那么是满足“是的子串，且是双特殊子串”中最短的。
　　所以题目做法就是，将输入作为的禁止后缀自动机的输入，得到一个节点。接着，该节点所能表示的那些子串的出现次数就是从其出发到紧致后缀自动机的接受态的路线数量（每一条路线都是一个后缀），于是就形成了一个从右向左的线性递推式，可以用伯莱坎普梅西算法直接获取递推式而不必自己在那弄矩阵。关于伯莱坎普梅西算法，见https://chaoli.club/index.php/5641。
　　现在既然已经知道怎么求一个节点所对应字符串在中的出现次数，那么还有第二个问题要处理。也就是说要解决“对于节点，有多少其子串不包含于的更短的双特殊子串”，于是这时就要借助于双特殊子串的性质（自己思考），以及论文中的一些结论（假定它们是对的，因为那个纰漏我实在没空处理了），来确定的严格子串中那些极长的的双特殊子串。统一方法是：已知是的双特殊字串，如果是极长的满足“既是的严格子串，又是的双特殊子串”的串，那么一定要不在紧致后缀自动机上走一条边就到达，要不就是的后缀。于是乎，就可以解决上面的问题了。于是，这些极长串就划定了一些区间，它们互相之间不包含而且能覆盖那个长的双特殊子串（这一点请读者自己思考）。于是问题就成了：在一大区间上，有一些小区间，它们之间无包含关系，求大区间有多少子区间不包含于任何一个小区间。此问题请参考华林公式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 uss = std::uint8_t;
  8. using llf = long double;
  10. const ul maxlen = 1e6;
  12. ul T;
  14. ull n;
  16. char s[maxlen + 1];
  18. std::map<std::string, ul> cnt[4];
  20. ul cntcnt[4][1 << 3];
  22. enum str_class {
  23.     tau,
  24.     sigma,
  25.     barsigma,
  26.     bartau,
  27.     eps,
  28.     nst
  29. };
  31. class state {
  32. public:
  33.     str_class c = eps;
  34.     ul i = 0;
  35.     state()=default;
  36.     state(str_class a, ul b): c(a), i(b) {}
  37. };
  39. bool check(ul& pos, str_class c, ul stri)
  40. {
  41.     ul len = 1 << stri;
  42.     for (ul i = 0; s[pos] && i != len; ++pos, ++i) {
  43.         if (s[pos] != ((__builtin_popcount(i) ^ (c != tau)) & 1) + 'a') {
  44.             return false;
  45.         }
  46.     }
  47.     return true;
  48. }
  50. void onestep(ul& pos, state& curr)
  51. {
  52.     if (curr.c == eps) {
  53.         if (s[pos] == 'a') {
  54.             if (check(pos, tau, 0)) {
  55.                 curr.c = tau;
  56.                 curr.i = 0;
  57.             } else {
  58.                 curr.c = nst;
  59.             }
  60.         } else if (s[pos] == 'b') {
  61.             if (check(pos, bartau, 0)) {
  62.                 curr.c = bartau;
  63.                 curr.i = 0;
  64.             } else {
  65.                 curr.c = nst;
  66.             }
  67.         }
  68.     } else if (curr.c == tau) {
  69.         if (curr.i == 0) {
  70.             if (s[pos] == 'a') {
  71.                 if (check(pos, tau, 1)) {
  72.                     curr.c = bartau;
  73.                     curr.i = 2;
  74.                 } else {
  75.                     curr.c = nst;
  76.                 }
  77.             } else if (s[pos] == 'b') {
  78.                 if (check(pos, bartau, 0)) {
  79.                     curr.c = tau;
  80.                     curr.i = 1;
  81.                 } else {
  82.                     curr.c = nst;
  83.                 }
  84.             }
  85.         } else if (curr.i == n - 2) {
  86.             if (s[pos] == 'a') {
  87.                 if (check(pos, tau, n - 3) && check(pos, tau, n - 2)) {
  88.                     curr.c = tau;
  89.                     curr.i = n;
  90.                 } else {
  91.                     curr.c = nst;
  92.                 }
  93.             } else if (s[pos] == 'b') {
  94.                 if (check(pos, bartau, n - 2) && check(pos, bartau, n - 1)) {
  95.                     curr.c = tau;
  96.                     curr.i = n;
  97.                 } else {
  98.                     curr.c = nst;
  99.                 }
  100.             }
  101.         } else {
  102.             if (s[pos] == 'a') {
  103.                 if (check(pos, tau, curr.i - 1)) {
  104.                     curr.c = sigma;
  105.                     ++curr.i;
  106.                 } else {
  107.                     curr.c = nst;
  108.                 }
  109.             } else if (s[pos] == 'b') {
  110.                 if (check(pos, bartau, curr.i)) {
  111.                     curr.c = tau;
  112.                     ++curr.i;
  113.                 } else {
  114.                     curr.c = nst;
  115.                 }
  116.             }
  117.         }
  118.     } else if (curr.c == sigma) {
  119.         if (curr.i == n - 2) {
  120.             if (s[pos] == 'a') {
  121.                 if (check(pos, tau, n - 3) && check(pos, bartau, n - 1)) {
  122.                     curr.c = tau;
  123.                     curr.i = n;
  124.                 } else {
  125.                     curr.c = nst;
  126.                 }
  127.             } else if (s[pos] == 'b') {
  128.                 if (check(pos, bartau, n - 4) && check(pos, bartau, n - 3)) {
  129.                     curr.c = tau;
  130.                     curr.i = n;
  131.                 } else {
  132.                     curr.c = nst;
  133.                 }
  134.             }
  135.         } else {
  136.             if (s[pos] == 'a') {
  137.                 if (check(pos, tau, curr.i - 1)) {
  138.                     curr.c = tau;
  139.                     ++curr.i;
  140.                 } else {
  141.                     curr.c = nst;
  142.                 }
  143.             } else if (s[pos] == 'b') {
  144.                 if (check(pos, bartau, curr.i - 2) && check(pos, bartau, curr.i - 1)) {
  145.                     curr.c = bartau;
  146.                     ++curr.i;
  147.                 } else {
  148.                     curr.c = nst;
  149.                 }
  150.             }
  151.         }
  152.     } else if (curr.c == barsigma) {
  153.         if (curr.i == n - 2) {
  154.             if (s[pos] == 'a') {
  155.                 if (check(pos, tau, n - 4) && check(pos, tau, n - 3) && check(pos, bartau, n - 1)) {
  156.                     curr.c = tau;
  157.                     curr.i = n;
  158.                 } else {
  159.                     curr.c = nst;
  160.                 }
  161.             } else if (s[pos] == 'b') {
  162.                 if (check(pos, bartau, n - 3)) {
  163.                     curr.c = tau;
  164.                     curr.i = n;
  165.                 } else {
  166.                     curr.c = nst;
  167.                 }
  168.             }
  169.         } else {
  170.             if (s[pos] == 'a') {
  171.                 if (check(pos, tau, curr.i - 2) && check(pos, tau, curr.i - 1)) {
  172.                     curr.c = tau;
  173.                     ++curr.i;
  174.                 } else {
  175.                     curr.c = nst;
  176.                 }
  177.             } else if (s[pos] == 'b') {
  178.                 if (check(pos, bartau, curr.i - 1)) {
  179.                     curr.c = bartau;
  180.                     ++curr.i;
  181.                 } else {
  182.                     curr.c = nst;
  183.                 }
  184.             }
  185.         }
  186.     } else if (curr.c == bartau) {
  187.         if (curr.i == 0) {
  188.             if (s[pos] == 'a') {
  189.                 if (check(pos, tau, 0)) {
  190.                     curr.c = bartau;
  191.                     curr.i = 1;
  192.                 } else {
  193.                     curr.c = nst;
  194.                 }
  195.             } else if (s[pos] == 'b') {
  196.                 if (check(pos, bartau, 1)) {
  197.                     curr.c = tau;
  198.                     curr.i = 2;
  199.                 } else {
  200.                     curr.c = nst;
  201.                 }
  202.             }
  203.         } else if (curr.i == n - 2) {
  204.             if (s[pos] == 'a') {
  205.                 if (check(pos, tau, n - 2)) {
  206.                     curr.c = tau;
  207.                     curr.i = n;
  208.                 } else {
  209.                     curr.c = nst;
  210.                 }
  211.             } else if (s[pos] == 'b') {
  212.                 if (check(pos, bartau, n - 1)) {
  213.                     curr.c = tau;
  214.                     curr.i = n;
  215.                 } else {
  216.                     curr.c = nst;
  217.                 }
  218.             }
  219.         } else {
  220.             if (s[pos] == 'a') {
  221.                 if (check(pos, tau, curr.i)) {
  222.                     curr.c = bartau;
  223.                     ++curr.i;
  224.                 } else {
  225.                     curr.c = nst;
  226.                 }
  227.             } else if (s[pos] == 'b') {
  228.                 if (check(pos, bartau, curr.i - 1)) {
  229.                     curr.c = barsigma;
  230.                     ++curr.i;
  231.                 } else {
  232.                     curr.c = nst;
  233.                 }
  234.             }
  235.         }
  236.     }
  237. }
  239. const ul mod = 1e9 + 7;
  241. ul plus(ul a, ul b)
  242. {
  243.     return a + b < mod ? a + b : a + b - mod;
  244. }
  246. ul minus(ul a, ul b)
  247. {
  248.     return a < b ? a + mod - b : a - b;
  249. }
  251. ul mul(ul a, ul b)
  252. {
  253.     return ull(a) * ull(b) % mod;
  254. }
  256. void exgcd(li a, li b, li& x, li& y)
  257. {
  258.     if (b) {
  259.         exgcd(b, a % b, y, x);
  260.         y -= a / b * x;
  261.     } else {
  262.         x = 1;
  263.         y = 0;
  264.     }
  265. }
  267. ul inverse(ul a)
  268. {
  269.     li x, y;
  270.     exgcd(a, mod, x, y);
  271.     return x < 0 ? li(mod) + x : x;
  272. }
  274. ul ppow(ul a, ull b)
  275. {
  276.     ul ret = 1;
  277.     while (b) {
  278.         if (b & 1) {
  279.             ret = mul(ret, a);
  280.         }
  281.         a = mul(a, a);
  282.         b >>= 1;
  283.     }
  284.     return ret;
  285. }
  287. const ul maxllen = 64;
  289. ul ans[10][maxllen];
  290. ul cc[10][maxllen + 1];
  291. ul len[10];
  293. ul bm(const ul s[], ul cc[], ul nn)
  294. {
  295.     static ul bb[maxllen + 1];
  296.     static ul tt[maxllen + 1];
  297.     cc[0] = 1;
  298.     bb[0] = 1;
  299.     ul tl;
  300.     ul bl = 0;
  301.     ul l = 0;
  302.     ul m = 1;
  303.     ul b = 1;
  304.     for (ul n = 0; n != nn; ++n) {
  305.         ul d = 0;
  306.         for (ul i = 0; i <= l; ++i) {
  307.             d = plus(d, mul(cc[i], s[n - i]));
  308.         }
  309.         if (d == 0) {
  310.             ++m;
  311.         } else if (l + l <= n) {
  312.             std::memcpy(tt, cc, sizeof(ul) * (l + 1));
  313.             tl = l;
  314.             std::memset(&cc[l + 1], 0, sizeof(ul) * (n - l - l + 1));
  315.             l = n + 1 - l;
  316.             ul lambda = mul(inverse(b), d);
  317.             for (ul i = 0; i <= bl; ++i) {
  318.                 cc[i + m] = minus(cc[i + m], mul(lambda, bb[i]));
  319.             }
  320.             bl = tl;
  321.             std::memcpy(bb, tt, sizeof(ul) * (bl + 1));
  322.             b = d;
  323.             m = 1;
  324.         } else {
  325.             ul lambda = mul(inverse(b), d);
  326.             for (ul i = 0; i <= bl; ++i) {
  327.                 cc[i + m] = minus(cc[i + m], mul(lambda, bb[i]));
  328.             }
  329.             ++m;
  330.         }
  331.     }
  332.     return l;
  333. }
  336. ul linearrec(const ul s[], const ul tcc[], ul len, ull n)
  337. {
  338.     static ul cc[maxllen + 1];
  339.     static ul ret[maxllen + 1];
  340.     static ul temp[2943];
  341.     if (n < len) {
  342.         return s[n];
  343.     }
  344.     std::memcpy(cc, tcc, sizeof(ul) * (len + 1));
  345.     std::memset(ret, 0, sizeof(ul) * len);
  346.     ret[0] = 1;
  347.     ul dret = 0;
  348.     for (ull t = ull(1) << 63 - __builtin_clzll(n); t; t >>= 1) {
  349.         std::memset(temp, 0, sizeof(ul) * (dret + dret + 1));
  350.         for (ul i = 0; i <= dret; ++i) {
  351.             temp[i + i] = plus(temp[i + i], mul(ret[i], ret[i]));
  352.             for (ul j = i + 1; j <= dret; ++j) {
  353.                 ul tp = mul(ret[i], ret[j]);
  354.                 temp[i + j] = plus(temp[i + j], plus(tp, tp));
  355.             }
  356.         }
  357.         for (ul i = dret + dret; i >= len; --i) {
  358.             ul lambda = minus(0, temp[i]);
  359.             if (!lambda) {
  360.                 continue;
  361.             }
  362.             for (ul j = 0; j <= len; ++j) {
  363.                 temp[i - j] = plus(temp[i - j], mul(cc[j], lambda));
  364.             }
  365.         }
  366.         std::memcpy(ret, temp, sizeof(ul) * len);
  367.         dret = std::min(dret + dret, len - ul(1));
  368.         if (t & n) {
  369.             for (ul i = dret + 1; i; --i) {
  370.                 ret[i] = ret[i - 1];
  371.             }
  372.             ret[0] = 0;
  373.             ++dret;
  374.             if (dret == len) {
  375.                 ul lambda = minus(0, ret[len]);
  376.                 if (lambda) {
  377.                     for (ul i = 0; i <= len; ++i) {
  378.                         ret[len - i] = plus(ret[len - i], mul(cc[i], lambda));
  379.                     }
  380.                 }
  381.                 --dret;
  382.             }
  383.         }
  384.     }
  385.     ul out = 0;
  386.     for (ul i = 0; i != len; ++i) {
  387.         out = plus(out, mul(s[i], ret[i]));
  388.     }
  389.     return out;
  390. }
  392. ul div2(ul x)
  393. {
  394.     return (x & 1) ? (x + mod >> 1) : (x >> 1);
  395. }
  397. ul g(ul x)
  398. {
  399.     return div2(mul(x, plus(x, 1)));
  400. }
  402. ul ftaun(ull n)
  403. {
  404.     return minus(plus(g(ppow(2, n)), mul(8, g(ppow(2, n - 3)))), plus(mul(5, g(ppow(2, n - 2))), mul(4, g(mul(3, ppow(2, n - 4))))));
  405. }
  407. ul ftau(ull n)
  408. {
  409.     if (n == 1) {
  410.         return 1;
  411.     } else if (n == 2) {
  412.         return 4;
  413.     } else {
  414.         return plus(minus(g(ppow(2, n)), mul(2, plus(g(ppow(2, n - 1)), g(mul(3, ppow(2, n - 3)))))), mul(3, g(ppow(2, n - 2))));
  415.     }
  416. }
  418. ul fsigma(ull n)
  419. {
  420.     return minus(plus(g(mul(3, ppow(2, n - 2))), g(ppow(2, n - 2))), mul(2, g(ppow(2, n - 1))));
  421. }
  423. int main()
  424. {
  425.     ans[tau][0] = 1;
  426.     ans[tau][2] = 3;
  427.     ans[sigma][2] = 2;
  428.     ans[barsigma][2] = 2;
  429.     ans[bartau][2] = 2;
  430.     for (ul i = 3; i != maxllen; ++i) {
  431.         ans[tau][i] = plus(plus(ans[tau][i - 1], ans[sigma][i - 1]), ~i & 1);
  432.         ans[sigma][i] = plus(ans[tau][i - 1], ans[bartau][i - 1]);
  433.         ans[barsigma][i] = plus(ans[tau][i - 1], ans[bartau][i - 1]);
  434.         ans[bartau][i] = plus(plus(ans[barsigma][i - 1], ans[bartau][i - 1]), i & 1);
  435.     }
  436.     for (auto t : {tau, sigma, barsigma, bartau}) {
  437.         len[t] = bm(ans[t], cc[t], maxllen);
  438.     }
  439.     for (ul n = 0; n <= 3; ++n) {
  440.         for (ul i = 0; i != (1 << n); ++i) {
  441.             s[i] = (__builtin_popcount(i) & 1) + 'a';
  442.             s[i + 1] = 0;
  443.             for (ul j = 0; j <= i; ++j) {
  444.                 ++cnt[n][std::string(s + j)];
  445.             }
  446.         }
  447.         for (const auto& p : cnt[n]) {
  448.             ++cntcnt[n][p.second];
  449.         }
  450.     }
  451.     std::scanf("%u", &T);
  452.     for (ul Case = 1; Case <= T; ++Case) {
  453.         std::scanf("%llu%s", &n, s);
  454.         if (n <= 3) {
  455.             auto it = cnt[n].find(std::string(s));
  456.             if (it != cnt[n].end()) {
  457.                 std::printf("%u %u\n", it->second, cntcnt[n][it->second]);
  458.             } else {
  459.                 std::printf("-1\n");
  460.             }
  461.             continue;
  462.         }
  463.         state st;
  464.         ul pos = 0;
  465.         while (s[pos] && st.c != nst) {
  466.             onestep(pos, st);
  467.         }
  468.         if (st.c == nst) {
  469.             std::printf("-1\n");
  470.             continue;
  471.         }
  472.         ul out;
  473.         if (st.i != 0) {
  474.             out = linearrec(ans[st.c], cc[st.c], len[st.c], n - st.i);
  475.         } else if (st.c == tau) {
  476.             out = plus(linearrec(ans[tau], cc[tau], len[tau], n - 1), linearrec(ans[bartau], cc[bartau], len[bartau], n - 2));
  477.             out = plus(out, ~n & 1);
  478.         } else if (st.c == bartau) {
  479.             out = plus(linearrec(ans[bartau], cc[bartau], len[bartau], n - 1), linearrec(ans[tau], cc[tau], len[tau], n - 2));
  480.             out = plus(out, n & 1);
  481.         }
  482.         ul out2;
  483.         if (st.i == n) {
  484.             out2 = ftaun(n);
  485.         } else if (st.i == 0) {
  486.             out2 = 2;
  487.         } else {
  488.             out2 = 0;
  489.             for (auto t : {tau, bartau}) {
  490.                 if (linearrec(ans[t], cc[t], len[t], n - st.i) == out) {
  491.                     out2 = plus(out2, ftau(st.i));
  492.                 }
  493.             }
  494.             if (st.i != 1) {
  495.                 for (auto t : {sigma, barsigma}) {
  496.                     if (linearrec(ans[t], cc[t], len[t], n - st.i) == out) {
  497.                         out2 = plus(out2, fsigma(st.i));
  498.                     }
  499.                 }
  500.             }
  501.         }
  502.         std::printf("%u %u\n", out, out2);
  503.     }
  504.     return 0;
  505. }

B、Network Test 6878

　　给定一个无向图，要求拆成尽量少的森林的并。
　　首先想到这是一个拟阵划分问题，关于拟阵划分算法正确性的证明见https://chaoli.club/index.php/5645。论文中的叙述实际上等价于如下描述：
　　考虑现在已经有个独立集，新添加一个元素，能继续把加进已经有的独立集当且仅当能找到这样一条路线：（有可能是，不要求必须不同，但是必须不同），这条路径满足下列条件：必须在的圈中，必须独立。如果有这么条路线，就可以增广，如果没有说明必须新建独立集才能容下了。于是就可以广搜找增广路。
　　这样做的话每次增广访问独立集的次数能达到，再算上次增广，故总计，所以还要考虑新东西。论文中是针对更宽泛的情况，就是说，个拟阵之间不要求相同，但在相同的时候，每一次增广访问独立集的次数其实可以只到，考虑这样一件事：在同拟阵的背景下，如果存在一条增广路，则一定存在形如下方这样的增广路（用表示）。为什么呢，假设有一个别的形状的增广路，能强行把增广路改成这样的形式只要能证明如下命题即可：如果，是独立集，不独立且独立，则在的圈中至少有一条边满足独立。该命题的证明直接重复使用赖虹健《拟阵论》的（1.2.4）即可。于是现在只要能做到每次增广，每条边都只访问一次，那么时间可以在，表示单次对边访问的时间。于是我直接用重链剖分套treap用的时间把这道题糊过去了，但是实际上这道题存在的算法，由塔尖发明，我心情好了再说吧（连做两道有点硬的题，有点想休息一下了）。
　　

  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::mt19937 rnd;
  10. class treap {
  11. public:
  12.     class node {
  13.     public:
  14.         ul key = 0;
  15.         ul value = 0;
  16.         ul weight = 0;
  17.         ul lson = 0;
  18.         ul rson = 0;
  19.         ul fa = 0;
  20.         node()=default;
  21.         node(ul a, ul b): key(a), value(b), weight(rnd()) {}
  22.     };
  23.     std::vector<node> tree;
  24.     void clear() {
  25.         tree.resize(1);
  26.         tree[0].lson = 0;
  27.     }
  28.     void rotate(ul x) {
  29.         ul y = tree[x].fa;
  30.         if (tree[y].lson == x) {
  31.             tree[y].lson = tree[x].rson;
  32.             tree[x].rson = y;
  33.             tree[tree[y].lson].fa = y;
  34.         } else {
  35.             tree[y].rson = tree[x].lson;
  36.             tree[x].lson = y;
  37.             tree[tree[y].rson].fa = y;
  38.         }
  39.         tree[x].fa = tree[y].fa;
  40.         tree[y].fa = x;
  41.         if (tree[tree[x].fa].lson == y) {
  42.             tree[tree[x].fa].lson = x;
  43.         } else {
  44.             tree[tree[x].fa].rson = x;
  45.         }
  46.     }
  47.     void insert(ul a, ul b) {
  48.         if (!tree[0].lson) {
  49.             tree[0].lson = tree.size();
  50.             tree.push_back(node(a, b));
  51.             return;
  52.         }
  53.         ul c = tree[0].lson;
  54.         for ( ; ; ) {
  55.             if (a < tree[c].key) {
  56.                 if (tree[c].lson) {
  57.                     c = tree[c].lson;
  58.                 } else {
  59.                     tree[c].lson = tree.size();
  60.                     tree.push_back(node(a, b));
  61.                     tree.back().fa = c;
  62.                     break;
  63.                 }
  64.             } else if (a > tree[c].key) {
  65.                 if (tree[c].rson) {
  66.                     c = tree[c].rson;
  67.                 } else {
  68.                     tree[c].rson = tree.size();
  69.                     tree.push_back(node(a, b));
  70.                     tree.back().fa = c;
  71.                     break;
  72.                 }
  73.             } else {
  74.                 tree[c].value = b;
  75.                 return;
  76.             }
  77.         }
  78.         c = tree.size() - 1;
  79.         while (tree[c].fa && tree[tree[c].fa].weight < tree[c].weight) {
  80.             rotate(c);
  81.         }
  82.     }
  83.     ul lower_bound(ul a) {
  84.         ul c = tree[0].lson;
  85.         if (!c) {
  86.             return 0;
  87.         }
  88.         ul ret = 0;
  89.         for ( ; ; ) {
  90.             if (a > tree[c].key) {
  91.                 if (tree[c].rson) {
  92.                     c = tree[c].rson;
  93.                 } else {
  94.                     return ret;
  95.                 }
  96.             } else {
  97.                 ret = c;
  98.                 if (tree[c].lson) {
  99.                     c = tree[c].lson;
  100.                 } else {
  101.                     return ret;
  102.                 }
  103.             }
  104.         }
  105.     }
  106.     ul find(ul a) {
  107.         ul c = tree[0].lson;
  108.         if (!c) {
  109.             return 0;
  110.         }
  111.         for ( ; ; ) {
  112.             if (a > tree[c].key) {
  113.                 if (tree[c].rson) {
  114.                     c = tree[c].rson;
  115.                 } else {
  116.                     return 0;
  117.                 }
  118.             } else if (a < tree[c].key) {
  119.                 if (tree[c].lson) {
  120.                     c = tree[c].lson;
  121.                 } else {
  122.                     return 0;
  123.                 }
  124.             } else {
  125.                 return c;
  126.             }
  127.         }
  128.     }
  129.     ul next(ul c) {
  130.         if (tree[c].rson) {
  131.             c = tree[c].rson;
  132.             for ( ; ; ) {
  133.                 if (tree[c].lson) {
  134.                     c = tree[c].lson;
  135.                 } else {
  136.                     return c;
  137.                 }
  138.             }
  139.         } else {
  140.             ul k = tree[c].key;
  141.             for (c = tree[c].fa; ; c = tree[c].fa) {
  142.                 if (!c || tree[c].key > k) {
  143.                     return c;
  144.                 }
  145.             }
  146.         }
  147.     }
  148.     ul erase(ul c) {
  149.         ul ret = next(c);
  150.         for ( ; ; ) {
  151.             if (!tree[c].lson && !tree[c].rson) {
  152.                 if (tree[tree[c].fa].lson == c) {
  153.                     tree[tree[c].fa].lson = 0;
  154.                 } else {
  155.                     tree[tree[c].fa].rson = 0;
  156.                 }
  157.                 return ret;
  158.             } else if (!tree[c].lson) {
  159.                 rotate(tree[c].rson);
  160.             } else if (!tree[c].rson) {
  161.                 rotate(tree[c].lson);
  162.             } else {
  163.                 if (tree[tree[c].lson].weight > tree[tree[c].rson].weight) {
  164.                     rotate(tree[c].lson);
  165.                 } else {
  166.                     rotate(tree[c].rson);
  167.                 }
  168.             }
  169.         }
  170.     }
  171. };
  173. ul T;
  175. const ul maxn = 1000;
  176. const ul maxm = 2000;
  178. ul n, m;
  180. class edge_t {
  181. public:
  182.     ul u = 0;
  183.     ul v = 0;
  184.     ul nextforu = 0;
  185.     ul nextforv = 0;
  186.     ul& next(ul t) {
  187.         return t == u ? nextforu : nextforv;
  188.     }
  189.     ul next(ul t) const {
  190.         return t == u ? nextforu : nextforv;
  191.     }
  192.     ul to(ul t) const {
  193.         return t ^ u ^ v;
  194.     }
  195. };
  197. edge_t edge[maxm + 1];
  199. ul k;
  201. ul head[maxm + 1][maxn + 1];
  203. treap forest[maxm + 1];
  205. std::vector<ul> node[maxm + 1];
  207. ul ex[maxm + 1][maxn + 1];
  208. ul alfornode[maxm + 1][maxn + 1];
  209. ul tim = 0;
  210. ul timex[maxm + 1];
  212. ul depth[maxm + 1][maxn + 1];
  213. ul bigson[maxm + 1][maxn + 1];
  214. ul fa[maxm + 1][maxn + 1];
  215. ul hvhd[maxm + 1][maxn + 1];
  216. ul rootin[maxm + 1][maxn + 1];
  218. treap road[maxm + 1][maxn + 1];
  220. void addedge(ul from, ul eid, ul& head)
  221. {
  222.     edge[eid].next(from) = head;
  223.     head = eid;
  224. }
  226. void search(ul curr, ul prev, ul depth[], const ul head[], ul& sz, ul bigson[], ul fa[], ul alfornode[], ul rootin[])
  227. {
  228.     alfornode[curr] = tim;
  229.     depth[curr] = depth[prev] + 1;
  230.     sz = 1;
  231.     bigson[curr] = 0;
  232.     ul bignsz = 0;
  233.     for (ul eid = head[curr]; eid; eid = edge[eid].next(curr)) {
  234.         ul next = edge[eid].to(curr);
  235.         if (next == prev) {
  236.             continue;
  237.         }
  238.         rootin[next] = rootin[curr];
  239.         fa[next] = curr;
  240.         ul nsz;
  241.         search(next, curr, depth, head, nsz, bigson, fa, alfornode, rootin);
  242.         sz += nsz;
  243.         if (nsz > bignsz) {
  244.             bigson[curr] = next;
  245.             bignsz = nsz;
  246.         }
  247.     }
  248. }
  250. void search2(ul curr, ul prev, const ul depth[], const ul head[], const ul bigson[], ul hvhd[], treap road[])
  251. {
  252.     for (ul eid = head[curr]; eid; eid = edge[eid].next(curr)) {
  253.         ul next = edge[eid].to(curr);
  254.         if (next == prev) {
  255.             continue;
  256.         }
  257.         if (next == bigson[curr]) {
  258.             hvhd[next] = hvhd[curr];
  259.         } else {
  260.             hvhd[next] = next;
  261.             road[next].clear();
  262.         }
  263.         road[hvhd[next]].insert(depth[next], eid);
  264.         search2(next, curr, depth, head, bigson, hvhd, road);
  265.     }
  266. }
  268. std::deque<ul> queue;
  270. ul prev[maxm + 1];
  271. ul belong[maxm + 1];
  273. void lca(ul u, ul v, const ul depth[], const ul hvhd[], const ul fa[], treap road[], ul curr)
  274. {
  275.     while (hvhd[u] != hvhd[v]) {
  276.         if (depth[hvhd[u]] < depth[hvhd[v]]) {
  277.             std::swap(u, v);
  278.         }
  279.         ul l = depth[hvhd[u]];
  280.         ul r = depth[u];
  281.         treap& ro = road[hvhd[u]];
  282.         u = fa[hvhd[u]];
  283.         for (auto it = ro.lower_bound(l); it && ro.tree[it].key <= r; it = ro.erase(it)) {
  284.             queue.push_back(ro.tree[it].value);
  285.             prev[ro.tree[it].value] = curr;
  286.         }
  287.     }
  288.     if (depth[u] > depth[v]) {
  289.         std::swap(u, v);
  290.     }
  291.     ul l = depth[u] + 1;
  292.     ul r = depth[v];
  293.     treap& ro = road[hvhd[u]];
  294.     for (auto it = ro.lower_bound(l); it && ro.tree[it].key <= r; it = ro.erase(it)) {
  295.         queue.push_back(ro.tree[it].value);
  296.         prev[ro.tree[it].value] = curr;
  297.     }
  298. }
  300. int main()
  301. {
  302.     rnd.seed(std::time(0));
  303.     std::scanf("%u", &T);
  304.     for (ul Case = 1; Case <= T; ++Case) {
  305.         std::scanf("%u%u", &n, &m);
  306.         k = 0;
  307.         for (ul t = 1; t <= m; ++t) {
  308.             std::scanf("%u%u", &edge[t].u, &edge[t].v);
  309.             belong[t] = 0;
  310.             for (ul i = 1; i <= k; ++i) {
  311.                 node[i].resize(0);
  312.                 ++timex[i];
  313.                 for (ul it = forest[i].lower_bound(0); it; it = forest[i].next(it)) {
  314.                     ul eid = forest[i].tree[it].key;
  315.                     belong[eid] = i;
  316.                     ul u = edge[eid].u;
  317.                     ul v = edge[eid].v;
  318.                     if (ex[i][u] != timex[i]) {
  319.                         node[i].push_back(u);
  320.                         ex[i][u] = timex[i];
  321.                         head[i][u] = 0;
  322.                     }
  323.                     if (ex[i][v] != timex[i]) {
  324.                         node[i].push_back(v);
  325.                         ex[i][v] = timex[i];
  326.                         head[i][v] = 0;
  327.                     }
  328.                     addedge(u, eid, head[i][u]);
  329.                     addedge(v, eid, head[i][v]);
  330.                 }
  331.                 ++tim;
  332.                 for (ul root : node[i]) {
  333.                     if (alfornode[i][root] == tim) {
  334.                         continue;
  335.                     }
  336.                     ul sz = 0;
  337.                     rootin[i][root] = root;
  338.                     search(root, 0, depth[i], head[i], sz, bigson[i], fa[i], alfornode[i], rootin[i]);
  339.                     hvhd[i][root] = root;
  340.                     road[i][root].clear();
  341.                     search2(root, 0, depth[i], head[i], bigson[i], hvhd[i], road[i]);
  342.                 }
  343.             }
  344.             while (queue.size()) {
  345.                 queue.pop_front();
  346.             }
  347.             queue.push_back(t);
  348.             ul end = 0;
  349.             ul endprev = 0;
  350.             if (k) {
  351.                 while (queue.size() && !end) {
  352.                     ul curr = queue.front();
  353.                     queue.pop_front();
  354.                     ul u = edge[curr].u;
  355.                     ul v = edge[curr].v;
  356.                     ul i = belong[curr] % k + 1;
  357.                     if (ex[i][u] != timex[i] || ex[i][v] != timex[i] || rootin[i][u] != rootin[i][v]) {
  358.                         end = i;
  359.                         endprev = curr;
  360.                     } else {
  361.                         lca(u, v, depth[i], hvhd[i], fa[i], road[i], curr);
  362.                     }
  363.                 }
  364.             }
  365.             if (!end) {
  366.                 ++k;
  367.                 forest[k].clear();
  368.                 forest[k].insert(t, 0);
  369.             } else {
  370.                 for (ul a = end, b = endprev; ; ) {
  371.                     forest[a].insert(b, 0);
  372.                     if (belong[b]) {
  373.                         forest[belong[b]].erase(forest[belong[b]].find(b));
  374.                         a = belong[b];
  375.                         b = prev[b];
  376.                     } else {
  377.                         break;
  378.                     }
  379.                 }
  380.             }
  381.         }
  382.         std::printf("%u\n", k);
  383.     }
  384.     return 0;
  385. }

C、Mine Sweeper 6879

　　直接按照官方题解做就是，如下：
　　如果，直接构造为：X.X.X.X.的形式，长为
　　如果，设，于是图如下：

  1. XXXXXXXXXXXXXXXXXXXXXXXXX
  2. X.X.X.X.X.X.X.X.X.X.X.X.X
  3. XXXXXXXXXXXXXXXXXXXXXXXXX
  4. X.X.X.X.X.X.X.X.X.X.X.X.X
  5. XXXXXXXXXXXXXXXXXXXXXXXXX
  6. X.X.X.X.X.X.X.X.X.X.X.X.X
  7. XXXXXXXXXXXXXXXXXXXXXXXXX
  8. X.X.X.X.X.X.X.X.X.X.X.X.X
  9. XXXXXXXXXXXXXXXXXXXXXXXXX
  10. X.X.X.X.X.X.X.X.X.X.X.X.X
  11. XXXXXXXXXXXXXXXXXXXXXXXXX
  12. X.X.X.X.X.X.X.X.X.X.X.X.X
  13. XXXXXXXXXXXXXXXXXXXXXXXXX
  14. X.X.X.X.X.X.X.X.X.X.X.X.X
  15. XXXXXXXXXXXXXXXXXXXXXXXXX
  16. X.X.X.X.X.X.X.X.X.X.X.X.X
  17. XXXXXXXXXXXXXXXXXXXXXXXXX
  18. X.X.XXXXXXXXXXXXXXXXXXXXX
  19. XXXXXXXXXXXXXXXXXXXXXXXXX
  20. XXXXXXXXXXXXXXXXXXXXXXXXX
  21. XXXXXXXXXXXXXXXXXXXXXXXXX
  22. XXXXXXXXXXXXXXXXXXXXXXXXX
  23. XXXXXXXXXXXXXXXXXXXXXXXXX
  24. XXXXXXXXXXXXXXXXXXXXXXXXX
  25. XXXXXXXXXXXXXXXXXXX......
  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 s, T;
  10. void exgcd(li a, li b, li& x, li& y)
  11. {
  12.     if (b) {
  13.         exgcd(b, a % b, y, x);
  14.         y -= a / b * x;
  15.     } else {
  16.         x = 1;
  17.         y = 0;
  18.     }
  19. }
  21. li lower(li x, li y)
  22. {
  23.     return x < 0 ? (x - y + 1) / y : x / y;
  24. }
  26. int main()
  27. {
  28.     std::scanf("%u", &T);
  29.     for (ul Case = 1; Case <= T; ++Case) {
  30.         std::scanf("%u", &s);
  31.         if (s <= 24) {
  32.             std::printf("1 %u\n", s + 1);
  33.             for (ul i = 1; i <= s + 1; ++i) {
  34.                 std::putchar((i & 1) ? 'X' : '.');
  35.             }
  36.             std::putchar('\n');
  37.         } else {
  38.             li x, y;
  39.             exgcd(8, 3, x, y);
  40.             li a = li(s) * x;
  41.             li b = li(s) * y;
  42.             li k = lower(b, 8);
  43.             b -= 8 * k;
  44.             a += 3 * k;
  45.             std::printf("25 25\n");
  46.             for (ul i = 1; i <= 24; ++i) {
  47.                 for (ul j = 1; j <= 25; ++j) {
  48.                     if ((~i & ~j & 1) && a) {
  49.                         std::putchar('.');
  50.                         --a;
  51.                     } else {
  52.                         std::putchar('X');
  53.                     }
  54.                 }
  55.                 std::putchar('\n');
  56.             }
  57.             for (ul i = 1; i <= 25; ++i) {
  58.                 if (i <= 25 - b) {
  59.                     std::putchar('X');
  60.                 } else {
  61.                     std::putchar('.');
  62.                 }
  63.             }
  64.             std::putchar('\n');
  65.         }
  66.     }
  67.     return 0;
  68. }

D、Permutation Counting 6880

　　设表示长为的，满足序列前项要求的，由构成的，以结尾的排列有多少个。
　　于是可以直接对动态规划。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using ll = std::int64_t;
  5. using ull = std::uint64_t;
  6. using li = std::int32_t;
  8. const ul mod = 1e9 + 7;
  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. const ul maxn = 5000;
  22. ul ans[maxn + 1][maxn + 1];
  24. ul T;
  26. ul b[maxn];
  28. ul n;
  30. int main()
  31. {
  32.     std::scanf("%u", &T);
  33.     for (ul Case = 1; Case <= T; ++Case) {
  34.         std::scanf("%u", &n);
  35.         for (ul i = 1; i <= n - 1; ++i) {
  36.             std::scanf("%u", &b[i]);
  37.         }
  38.         ans[1][1] = 1;
  39.         for (ul x = 1; x <= n - 1; ++x) {
  40.             for (ul y = 1; y <= x + 1; ++y) {
  41.                 ans[x + 1][y] = 0;
  42.             }
  43.             if (b[x]) {
  44.                 for (ul y = 1; y <= x; ++y) {
  45.                     ans[x + 1][1] = plus(ans[x + 1][1], ans[x][y]);
  46.                     ans[x + 1][y + 1] = minus(ans[x + 1][y + 1], ans[x][y]);
  47.                 }
  48.             } else {
  49.                 for (ul y = 1; y <= x; ++y) {
  50.                     ans[x + 1][y + 1] = plus(ans[x + 1][y + 1], ans[x][y]);
  51.                 }
  52.             }
  53.             for (ul y = 1; y <= x + 1; ++y) {
  54.                 ans[x + 1][y] = plus(ans[x + 1][y], ans[x + 1][y - 1]);
  55.             }
  56.         }
  57.         ul out = 0;
  58.         for (ul y = 1; y <= n; ++y) {
  59.             out = plus(out, ans[n][y]);
  60.         }
  61.         std::printf("%u\n", out);
  62.     }
  63.     return 0;
  64. }

E、Tree Cutting 6881

常规点分治，注意，如果犯懒在边中间插点，在杭电会爆栈。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. ul n, k;
  12. const ul maxn = 3e5;
  14. class node_t {
  15. public:
  16.     ul rk = 0;
  17.     ul hd = 0;
  18. };
  20. node_t node[maxn + 1];
  22. class edge_t {
  23. public:
  24.     ul to = 0;
  25.     ul nex = 0;
  26. };
  28. edge_t edge[(maxn - 1) * 2 + 1];
  29. ul totedge;
  31. void addedge(ul a, ul b)
  32. {
  33.     ++totedge;
  34.     edge[totedge].to = b;
  35.     edge[totedge].nex = node[a].hd;
  36.     node[a].hd = totedge;
  37. }
  39. void getcen(ul curr, ul prev, ul totsz, ul& sz, ul& mnmxsz, ul& mnmxsznid)
  40. {
  41.     sz = 1;
  42.     ul mxsz = 0;
  43.     for (ul eid = node[curr].hd; eid; eid = edge[eid].nex) {
  44.         ul nex = edge[eid].to;
  45.         if (node[nex].rk) {
  46.             continue;
  47.         }
  48.         if (nex == prev) {
  49.             continue;
  50.         } else {
  51.             ul sonsz;
  52.             getcen(nex, curr, totsz, sonsz, mnmxsz, mnmxsznid);
  53.             mxsz = std::max(mxsz, sonsz);
  54.             sz += sonsz;
  55.         }
  56.     }
  57.     mxsz = std::max(mxsz, totsz - sz);
  58.     if (mnmxsz > mxsz) {
  59.         mnmxsz = mxsz;
  60.         mnmxsznid = curr;
  61.     }
  62. }
  64. void getsz(ul curr, ul prev, ul& sz)
  65. {
  66.     sz = 1;
  67.     for (ul eid = node[curr].hd; eid; eid = edge[eid].nex) {
  68.         ul nex = edge[eid].to;
  69.         if (node[nex].rk) {
  70.             continue;
  71.         }
  72.         if (nex == prev) {
  73.             continue;
  74.         } else {
  75.             ul sonsz;
  76.             getsz(nex, curr, sonsz);
  77.             sz += sonsz;
  78.         }
  79.     }
  80. }
  82. std::vector<ul> cnt[maxn + 1];
  83. std::vector<ul> sum;
  85. ul ans[maxn + 1];
  87. void search(ul curr, ul prev, ul rk, ul depth, std::vector<ul>& cnt)
  88. {
  89.     if (depth > k) {
  90.         return;
  91.     }
  92.     while (cnt.size() <= depth) {
  93.         cnt.push_back(0);
  94.     }
  95.     ++cnt[depth];
  96.     for (ul eid = node[curr].hd; eid; eid = edge[eid].nex) {
  97.         ul next = edge[eid].to;
  98.         if (next == prev || node[next].rk > rk) {
  99.             continue;
  100.         }
  101.         search(next, curr, rk, depth + 1, cnt);
  102.     }
  103. }
  105. ul query(const std::vector<ul>& v, ul t)
  106. {
  107.     return t < v.size() ? v[t] : v.back();
  108. }
  110. void update(ul curr, ul prev, ul rk, ul depth, const std::vector<ul>& cnt) {
  111.     if (depth > k) {
  112.         return;
  113.     }
  114.     ++ans[curr];
  115.     ans[curr] += query(sum, k - depth) - query(cnt, k - depth);
  116.     for (ul eid = node[curr].hd; eid; eid = edge[eid].nex) {
  117.         ul next = edge[eid].to;
  118.         if (next == prev || node[next].rk > rk) {
  119.             continue;
  120.         }
  121.         update(next, curr, rk, depth + 1, cnt);
  122.     }
  123. }
  125. ul fa[maxn + 1];
  127. void getfather(ul curr, ul prev)
  128. {
  129.     fa[curr] = prev;
  130.     for (ul eid = node[curr].hd; eid; eid = edge[eid].nex) {
  131.         ul next = edge[eid].to;
  132.         if (next == prev) {
  133.             continue;
  134.         }
  135.         getfather(next, curr);
  136.     }
  137. }
  139. void update1(ul curr, ul prev, ul rk, ul depth, const std::vector<ul>& cnt) {
  140.     if (depth > k) {
  141.         return;
  142.     }
  143.     ul id = (fa[curr] == prev) ? curr : prev;
  144.     ++ans[id];
  145.     ans[id] += query(sum, k - depth) - query(cnt, k - depth);
  146.     if (node[curr].rk > rk) {
  147.         return;
  148.     }
  149.     for (ul eid = node[curr].hd; eid; eid = edge[eid].nex) {
  150.         ul next = edge[eid].to;
  151.         if (next == prev) {
  152.             continue;
  153.         }
  154.         update1(next, curr, rk, depth + 1, cnt);
  155.     }
  156. }
  158. int main()
  159. {
  160.     std::scanf("%u", &T);
  161.     for (ul Case = 1; Case <= T; ++Case) {
  162.         std::scanf("%u%u", &n, &k);
  163.         totedge = 0;
  164.         for (ul i = 1; i <= n; ++i) {
  165.             node[i].hd = 0;
  166.             node[i].rk = 0;
  167.         }
  168.         for (ul i = 1; i <= n - 1; ++i) {
  169.             ul u, v;
  170.             u = i;
  171.             v = i + 1;
  172.             std::scanf("%u%u", &u, &v);
  173.             addedge(u, v);
  174.             addedge(v, u);
  175.         }
  176.         for (ul i = 1; i <= n; ++i) {
  177.             while (!node[i].rk) {
  178.                 ul sz;
  179.                 getsz(i, 0, sz);
  180.                 ul mnmxsz = sz, mnmxsznid;
  181.                 getcen(i, 0, sz, sz, mnmxsz, mnmxsznid);
  182.                 node[mnmxsznid].rk = sz;
  183.             }
  184.         }
  185.         std::memset(ans + 1, 0, sizeof(ul) * n);
  186.         if (~k & 1) {
  187.             k >>= 1;
  188.             for (ul i = 1; i <= n; ++i) {
  189.                 sum.resize(0);
  190.                 sum.resize(1);
  191.                 for (ul eid = node[i].hd; eid; eid = edge[eid].nex) {
  192.                     ul j = edge[eid].to;
  193.                     if (node[j].rk > node[i].rk) {
  194.                         continue;
  195.                     }
  196.                     cnt[j].resize(0);
  197.                     cnt[j].resize(1);
  198.                     search(j, i, node[i].rk, 1, cnt[j]);
  199.                     for (ul l = 0; l != cnt[j].size(); ++l) {
  200.                         while (sum.size() <= l) {
  201.                             sum.push_back(0);
  202.                         }
  203.                         sum[l] += cnt[j][l];
  204.                         if (l) {
  205.                             cnt[j][l] += cnt[j][l - 1];
  206.                         }
  207.                     }
  208.                 }
  209.                 for (ul j = 0; j != sum.size(); ++j) {
  210.                     if (j) {
  211.                         sum[j] += sum[j - 1];
  212.                     }
  213.                 }
  214.                 ++ans[i];
  215.                 ans[i] += query(sum, k);
  216.                 for (ul eid = node[i].hd; eid; eid = edge[eid].nex) {
  217.                     ul j = edge[eid].to;
  218.                     if (node[j].rk > node[i].rk) {
  219.                         continue;
  220.                     }
  221.                     update(j, i, node[i].rk, 1, cnt[j]);
  222.                 }
  223.             }
  224.         } else {
  225.             k = k + 1 >> 1;
  226.             getfather(1, 0);
  227.             for (ul i = 1; i <= n; ++i) {
  228.                 sum.resize(0);
  229.                 sum.resize(1);
  230.                 for (ul eid = node[i].hd; eid; eid = edge[eid].nex) {
  231.                     ul j = edge[eid].to;
  232.                     cnt[j].resize(0);
  233.                     cnt[j].resize(1);
  234.                     if (node[j].rk > node[i].rk) {
  235.                         continue;
  236.                     }
  237.                     search(j, i, node[i].rk, 1, cnt[j]);
  238.                     for (ul l = 0; l != cnt[j].size(); ++l) {
  239.                         while (sum.size() <= l) {
  240.                             sum.push_back(0);
  241.                         }
  242.                         sum[l] += cnt[j][l];
  243.                         if (l) {
  244.                             cnt[j][l] += cnt[j][l - 1];
  245.                         }
  246.                     }
  247.                 }
  248.                 for (ul j = 0; j != sum.size(); ++j) {
  249.                     if (j) {
  250.                         sum[j] += sum[j - 1];
  251.                     }
  252.                 }
  253.                 for (ul eid = node[i].hd; eid; eid = edge[eid].nex) {
  254.                     ul j = edge[eid].to;
  255.                     update1(j, i, node[i].rk, 1, cnt[j]);
  256.                 }
  257.             }
  258.         }
  259.         ul mx = 0;
  260.         for (ul i = 1; i <= n; ++i) {
  261.             mx = std::max(mx, ans[i]);
  262.         }
  263.         std::printf("%u\n", n - mx);
  264.     }
  265.     return 0;
  266. }

F、Divide and Conquer

　　第一条用极接近横线的直线把点分为两部分（按从小到大排序就行）；
　　第二条借助于连分数二分法找到即可。

  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 = 5e4;
  10. ul T;
  12. ul n;
  14. class vec {
  15. public:
  16.     ll x = 0;
  17.     ll y = 0;
  18.     vec()=default;
  19.     vec(ll a, ll b): x(a), y(b) {}
  20. };
  22. vec v[maxn + 1];
  24. class matrix {
  25. public:
  26.     ll xx = 1;
  27.     ll xy = 0;
  28.     ll yx = 0;
  29.     ll yy = 1;
  30.     matrix()=default;
  31.     matrix(ll a, ll b, ll c, ll d): xx(a), xy(b), yx(c), yy(d) {}
  32. };
  34. matrix operator*(const matrix& a, const matrix& b)
  35. {
  36.     return matrix(
  37.         a.xx * b.xx + a.xy * b.yx,
  38.         a.xx * b.xy + a.xy * b.yy,
  39.         a.yx * b.xx + a.yy * b.yx,
  40.         a.yx * b.xy + a.yy * b.yy
  41.     );
  42. }
  44. const ll inf = (ll(1) << 63) - 1;
  46. class cf {
  47. public:
  48.     matrix prev;
  49.     ll curr = 0;
  50.     cf()=default;
  51.     cf(ll t): curr(t) {}
  52. };
  54. void getmid(cf& l, cf& r, cf& mid)
  55. {
  56.     if (l.curr == inf) {
  57.         mid = r;
  58.         mid.curr *= 2;
  59.     } else if (r.curr == inf) {
  60.         mid = l;
  61.         mid.curr *= 2;
  62.     } else if (l.curr == r.curr + 1) {
  63.         l.prev = l.prev * matrix(r.curr, 1, 1, 0);
  64.         r.prev = r.prev * matrix(r.curr, 1, 1, 0);
  65.         l.curr = 1;
  66.         r.curr = inf;
  67.         getmid(l, r, mid);
  68.     } else if (r.curr == l.curr + 1) {
  69.         r.prev = r.prev * matrix(l.curr, 1, 1, 0);
  70.         l.prev = l.prev * matrix(l.curr, 1, 1, 0);
  71.         r.curr = 1;
  72.         l.curr = inf;
  73.         getmid(l, r, mid);
  74.     } else {
  75.         mid = l;
  76.         mid.curr = (l.curr + r.curr) / 2;
  77.     }
  78. }
  80. void getfrac(const cf& v, ll& a, ll& b)
  81. {
  82.     matrix tmp = v.prev * matrix(v.curr, 1, 1, 0);
  83.     a = tmp.xx;
  84.     b = tmp.yx;
  85. }
  87. ll operator*(const vec& a, const vec& b)
  88. {
  89.     return a.x * b.x + a.y * b.y;
  90. }
  92. void exgcd(ll a, ll b, ll& x, ll& y)
  93. {
  94.     if (b) {
  95.         exgcd(b, a % b, y, x);
  96.         y -= a / b * x;
  97.     } else {
  98.         x = 1;
  99.         y = 0;
  100.     }
  101. }
  103. int main()
  104. {
  105.     std::scanf("%u", &T);
  106.     for (ul Case = 1; Case <= T; ++Case) {
  107.         std::scanf("%u", &n);
  108.         for (ul i = 1; i <= n; ++i) {
  109.             std::scanf("%lld%lld", &v[i].x, &v[i].y);
  110.         }
  111.         std::sort(v + 1, v + n + 1, [](const vec& a, const vec& b){return a.y != b.y ? a.y < b.y : a.x < b.x;});
  112.         ul m = n >> 1;
  113.         if (v[m].y != v[m + 1].y) {
  114.             std::printf("-1000000000 %lld 1000000000 %lld\n", v[m + 1].y, v[m].y);
  115.         } else {
  116.             std::printf("%lld %lld %lld %lld\n", v[m].x - 10000000, v[m].y + 1, v[m + 1].x + 10000000, v[m].y - 1);
  117.         }
  118.         ul t = n >> 2;
  119.         cf l(-1e9), r(1e9);
  120.         cf mid;
  121.         vec dir;
  122.         while (true) {
  123.             getmid(l, r, mid);
  124.             getfrac(mid, dir.y, dir.x);
  125.             std::sort(v + 1, v + m + 1, [&](const vec& a, const vec& b){return a * dir < b * dir;});
  126.             std::sort(v + m + 1, v + n + 1, [&](const vec& a, const vec& b){return a * dir < b * dir;});
  127.             if (v[t + 1] * dir <= v[m + t] * dir) {
  128.                 r = mid;
  129.             } else if (v[m + t + 1] * dir <= v[t] * dir) {
  130.                 l = mid;
  131.             } else if (v[t + 1] * dir == v[m + t] * dir + 1) {
  132.                 r = mid;
  133.             } else if (v[m + t + 1] * dir == v[t] * dir + 1) {
  134.                 l = mid;
  135.             } else {
  136.                 break;
  137.             }
  138.         }
  139.         ll x, y;
  140.         if (dir.y >= 0) {
  141.             exgcd(dir.x, dir.y, x, y);
  142.         } else {
  143.             exgcd(dir.x, -dir.y, x, y);
  144.             y = -y;
  145.         }
  146.         vec tmp = v[m + t] * dir > v[t] * dir ? v[m + t] : v[t];
  147.         tmp.x += x;
  148.         tmp.y += y;
  149.         vec tmp2(tmp.x - dir.y, tmp.y + dir.x);
  150.         std::printf("%lld %lld %lld %lld\n", tmp.x, tmp.y, tmp2.x, tmp2.y);
  151.     }
  152.     return 0;
  153. }

G、Coin Game 6883

　　原题等价于问这样个物品的背包问题，其中个的价值为，体积为，令个的价值为，体积为。先将体积为和体积为的物品分别按价值从大到小排序，那么无论目标体积是多少，最优选项一定是体积为的物品列的某前缀和和体积为的物品列的某前缀和的合并。于是每次体积增大，只有两种可能性，一个是增加一个体积为一的，一个是去掉一个体积为一的再增加一个体积为二的。
　　

  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 = 5e6;
  10. ul n, m;
  12. ul a[maxn + 1];
  13. ul b[maxn + 1];
  15. constexpr int threshold = 10000000;
  16. unsigned long long k1, k2;
  18. unsigned long long xorShift128Plus() {
  19.     unsigned long long k3 = k1, k4 = k2;
  20.     k1 = k4;
  21.     k3 ^= (k3 << 23);
  22.     k2 = k3 ^ k4 ^(k3 >> 17) ^ (k4 >> 26);
  23.     return k2 + k4;
  24. }
  26. void gen(int n, unsigned long long _k1, unsigned long long _k2) {
  27.     k1 = _k1, k2 = _k2;
  28.     for (int i = 1; i <= n; i++) {
  29.         a[i] = xorShift128Plus() % threshold + 1;
  30.         b[i] = xorShift128Plus() % threshold + 1;
  31.     }
  32. }
  34. int main()
  35. {
  36.     while (std::scanf("%u%u%llu%llu", &n, &m, &k1, &k2) > 0) {
  37.         gen(n, k1, k2);
  38.         for (ul i = 1; i <= n; ++i) {
  39.             b[i] += a[i];
  40.         }
  41.         std::sort(a + 1, a + n + 1);
  42.         std::reverse(a + 1, a + n + 1);
  43.         std::sort(b + 1, b + n + 1);
  44.         std::reverse(b + 1, b + n + 1);
  45.         ul ia = 0, ib = 0;
  46.         ull sum = 0, ans = 0;
  47.         for (ul i = 1; i <= m; ++i) {
  48.             if (i > n + n + n) {
  49.             } else if (ia == n) {
  50.                 sum -= a[ia];
  51.                 --ia;
  52.                 ++ib;
  53.                 sum += b[ib];
  54.             } else if (ia == 0 || ib == n) {
  55.                 ++ia;
  56.                 sum += a[ia];
  57.             } else {
  58.                 ull s1 = sum + a[ia + 1];
  59.                 ull s2 = sum - a[ia] + b[ib + 1];
  60.                 if (s1 > s2) {
  61.                     sum = s1;
  62.                     ++ia;
  63.                 } else {
  64.                     sum = s2;
  65.                     --ia;
  66.                     ++ib;
  67.                 }
  68.             }
  69.             ans ^= sum;
  70.         }
  71.         std::printf("%llu\n", ans);
  72.     }
  73.     return 0;
  74. }

H、I do not know Graph Theory! 6884

　　本题需要用到竞赛图的这样一个性质：对任何的竞赛图，一定存在某个，满足可以将其点集分为这些组，其中所有，且每个都是一个强连通分量，并且对任何，和之间的所有边，一定是从到的，并且内部一定存在哈密顿圈。
　　关于这一点的证明，考虑下述构造方式：考虑一个点一个点添加，假设已经添加的点已经被整理成了上述结构，那么新来的点有以下几种可能性：
1、不存在从已有点到新来点的边，于是新来点独自作为一个新的强连通分量排在首位；
2、不存在从新来点到已有点的边，于是新来点独自作为一个新的强连通分量排在首位；
　　对于剩下的情况，用表示能到达新来点的强连通分量中编号最大的，用表示新来点能到达的强连通分量中编号最小的：
3、（此时必然），那么新来点独自作为一个新的强连通分量插入它俩之间；
4、，那么既然新来点既能到此分量又能被此分量到达，则一定存在一个合适的插入位置更新此分量的哈密顿圈；
5、，任意从中选一个新来点能一步到达的点，从它出发把中的边全部按照原哈密顿圈走一遍，再把中的点随便找个开头按照原哈密顿圈走一遍，最后任意从中选一个能一步到达新来点的点，从其之后那个点开始，按照原哈密顿圈走一遍，以之结束，最后在走到新来点。于是就成功吧中的点以及新来点重新组织为一个哈密顿圈，把这些强连通分量合并。

如上过程就是一个算法，于是考虑已经将输入的竞赛图整理为如上形式。现在如果，则无论如何不会强连通（特判）；如果且，那么一条边被改方向之后强连通当且仅当其是从到的；如果，那么原先强连通，由于已经有了一个哈密顿圈，改变圈外边的方向显然不会造成不强连通，现在考虑圈上的边，如果将其改变方向会使得不再强连通，则圈上一定存在某，满足圈上从到的所有点”和“圈上从到的所有点”之间的所有边（除了）都是从后者到前者的，于是枚举判断就是，需要做到对每个实现判断，这一点只要注意到，在重新对点标号之后，这只是个区间求和问题。

  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 T;
  11. const ul maxn = 5e3;
  13. ul n;
  15. char s[maxn + 1];
  17. ul edge[maxn + 1][maxn + 1];
  18. ul sum[maxn + 1][maxn + 1];
  19. ul ans[maxn + 1][maxn + 1];
  21. ul val[256];
  22. char rval[16];
  24. vul scc[maxn + 1];
  26. ul scccnt;
  28. std::vector<ul> tmp;
  30. ul id[maxn + 1];
  32. ul query(ul u, ul d, ul l, ul r)
  33. {
  34.     return sum[d][r] + sum[u - 1][l - 1] - sum[u - 1][r] - sum[d][l - 1];
  35. }
  37. int main()
  38. {
  39.     for (ul i = 0; i <= 9; ++i) {
  40.         val[i + '0'] = i;
  41.         rval[i] = i + '0';
  42.     }
  43.     for (ul i = 0; i <= 5; ++i) {
  44.         val[i + 'A'] = i + 10;
  45.         rval[i + 10] = i + 'A';
  46.     }
  47.     std::scanf("%u", &T);
  48.     for (ul Case = 1; Case <= T; ++Case) {
  49.         std::scanf("%u", &n);
  50.         for (ul i = 1; i <= n; ++i) {
  51.             for (ul j = 1; j <= n; ++j) {
  52.                 edge[i][j] = 0;
  53.             }
  54.         }
  55.         for (ul i = 1; i <= n - 1; ++i) {
  56.             std::scanf("%s", s + 1);
  57.             for (ul j = 1; s[j]; ++j) {
  58.                 ul v = val[s[j]];
  59.                 for (ul k = 0; k <= 3 && (j << 2) + k - 3 <= i; ++k) {
  60.                     if (v >> k & 1) {
  61.                         edge[i + 1][(j << 2) + k - 3] = 1;
  62.                     } else {
  63.                         edge[(j << 2) + k - 3][i + 1] = 1;
  64.                     }
  65.                 }
  66.             }
  67.         }
  68.         if (n == 2) {
  69.             std::printf("0\n");
  70.             continue;
  71.         }
  72.         scccnt = 0;
  73.         for (ul i = 1; i <= n; ++i) {
  74.             ul toi = 0, ito = 0;
  75.             for (ul j = 1; j <= scccnt; ++j) {
  76.                 for (ul k : scc[j]) {
  77.                     if (!ito && edge[i][k]) {
  78.                         ito = j;
  79.                     }
  80.                     if (edge[k][i]) {
  81.                         toi = j;
  82.                     }
  83.                 }
  84.             }
  85.             if (!ito) {
  86.                 ++scccnt;
  87.                 scc[scccnt].resize(0);
  88.                 scc[scccnt].push_back(i);
  89.             } else if (ito > toi) {
  90.                 ++scccnt;
  91.                 for (ul j = scccnt; j > ito; --j) {
  92.                     std::swap(scc[j - 1], scc[j]);
  93.                 }
  94.                 scc[ito].resize(0);
  95.                 scc[ito].push_back(i);
  96.             } else if (ito == toi) {
  97.                 if (edge[scc[toi].back()][i] && edge[i][scc[ito].front()]) {
  98.                     scc[ito].push_back(i);
  99.                 } else {
  100.                     tmp.resize(0);
  101.                     tmp.push_back(i);
  102.                     for (ul k = 1; k != scc[ito].size(); ++k) {
  103.                         if (edge[scc[toi][k - 1]][i] && edge[i][scc[ito][k]]) {
  104.                             for (ul j = k; j != scc[ito].size(); ++j) {
  105.                                 tmp.push_back(scc[ito][j]);
  106.                             }
  107.                             for (ul j = 0; j != k; ++j) {
  108.                                 tmp.push_back(scc[ito][j]);
  109.                             }
  110.                             std::swap(tmp, scc[ito]);
  111.                             break;
  112.                         }
  113.                     }
  114.                 }
  115.             } else {
  116.                 tmp.resize(0);
  117.                 tmp.push_back(i);
  118.                 for (ul k = 0; k != scc[ito].size(); ++k) {
  119.                     if (edge[i][scc[ito][k]]) {
  120.                         for (ul j = k; j != scc[ito].size(); ++j) {
  121.                             tmp.push_back(scc[ito][j]);
  122.                         }
  123.                         for (ul j = 0; j != k; ++j) {
  124.                             tmp.push_back(scc[ito][j]);
  125.                         }
  126.                         break;
  127.                     }
  128.                 }
  129.                 for (ul j = ito + 1; j < toi; ++j) {
  130.                     for (ul k : scc[j]) {
  131.                         tmp.push_back(k);
  132.                     }
  133.                 }
  134.                 for (ul k = 0; k != scc[toi].size(); ++k) {
  135.                     if (edge[scc[toi][k]][i]) {
  136.                         for (ul j = k + 1; j != scc[toi].size(); ++j) {
  137.                             tmp.push_back(scc[toi][j]);
  138.                         }
  139.                         for (ul j = 0; j <= k; ++j) {
  140.                             tmp.push_back(scc[toi][j]);
  141.                         }
  142.                         break;
  143.                     }
  144.                 }
  145.                 scccnt -= toi - ito;
  146.                 std::swap(scc[ito], tmp);
  147.                 for (ul j = ito + 1; j <= scccnt; ++j) {
  148.                     std::swap(scc[j], scc[j + toi - ito]);
  149.                 }
  150.             }
  151.         }
  152.         if (scccnt != 1) {
  153.             for (ul i = 1; i <= n; ++i) {
  154.                 for (ul j = 1; j <= n; ++j) {
  155.                     ans[i][j] = 0;
  156.                 }
  157.             }
  158.             for (ul k1 : scc[1]) {
  159.                 for (ul k2 : scc[scccnt]) {
  160.                     ans[k1][k2] = 1;
  161.                     ans[k2][k1] = 1;
  162.                 }
  163.             }
  164.         } else {
  165.             for (ul i = 1; i <= n; ++i) {
  166.                 for (ul j = 1; j <= n; ++j) {
  167.                     ans[i][j] = 1;
  168.                 }
  169.             }
  170.             for (ul i = 1; i <= n; ++i) {
  171.                 id[i] = scc[1][i - 1];
  172.             }
  173.             for (ul i = 1; i <= n; ++i) {
  174.                 for (ul j = 1; j <= n; ++j) {
  175.                     sum[i][j] = edge[id[i]][id[j]] + sum[i][j - 1];
  176.                 }
  177.             }
  178.             for (ul i = 1; i <= n; ++i) {
  179.                 for (ul j = 1; j <= n; ++j) {
  180.                     sum[j][i] += sum[j - 1][i];
  181.                 }
  182.             }
  183.             for (ul i = 1, j = 2; j <= n; ++i, ++j) {
  184.                 bool flag = true;
  185.                 for (ul s = j, t = j + 1; t <= n && flag; ++s, ++t) {
  186.                     ul tmp = query(j, s, t, n) + query(j, s, 1, i);
  187.                     if (tmp == (s - j + 1) * (n - t + 1 + i) - 1) {
  188.                         flag = false;
  189.                     }
  190.                 }
  191.                 if (flag) {
  192.                     ul s = n, t = 1;
  193.                     ul tmp = query(j, s, t, i);
  194.                     if (tmp == (s - j + 1) * (i - t + 1) - 1) {
  195.                         flag = false;
  196.                     }
  197.                 }
  198.                 for (ul s = 1, t = 2; t <= i && flag; ++s, ++t) {
  199.                     ul tmp = query(j, n, t, i) + query(1, s, t, i);
  200.                     if (tmp == (n - j + 1 + s) * (i - t + 1) - 1) {
  201.                         flag = false;
  202.                     }
  203.                 }
  204.                 if (!flag) {
  205.                     ans[id[i]][id[j]] = 0;
  206.                     ans[id[j]][id[i]] = 0;
  207.                 }
  208.             }
  209.             for (ul s = 1, t = 2; t <= n; ++s, ++t) {
  210.                 ul tmp = query(1, s, t, n);
  211.                 if (tmp == s * (n - t + 1) - 1) {
  212.                     ans[id[1]][id[n]] = 0;
  213.                     ans[id[n]][id[1]] = 0;
  214.                     break;
  215.                 }
  216.             }
  217.         }
  218.         for (ul i = 1; i <= n - 1; ++i) {
  219.             for (ul j = 1; (j << 2) - 3 <= i; ++j) {
  220.                 ul v = 0;
  221.                 for (ul k = 0; k <= 3 && (j << 2) + k - 3 <= i; ++k) {
  222.                     v |= ans[i + 1][(j << 2) + k - 3] << k;
  223.                 }
  224.                 std::putchar(rval[v]);
  225.             }
  226.             std::putchar('\n');
  227.         }
  228.     }
  229.     return 0;
  230. }

I、Photography 6885

　　根据题意可知是要最大化

其中，，，，，。把写在左侧只是方便书写，但是会造成右侧绝对值值过大，故实际需要把移到等号右侧。注意其实这就是求一个对称矩阵的最大特征值，直接解一个二次方程就是。
　　

  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>;
  8. using lf = double;
  9. using llf = long double;
  11. ul T;
  13. ul n;
  14. const ul maxn = 1e6;
  15. ul p;
  17. ll x[maxn + 1], y[maxn + 1];
  19. ll X1,Y1,X2,Y2,Z;
  21. llf sqr(llf x)
  22. {
  23.     return x * x;
  24. }
  26. llf mysqrt(llf x)
  27. {
  28.     return std::sqrt(std::max(llf(0), x));
  29. }
  31. llf calc(llf a, llf b, llf c)
  32. {
  33.     return mysqrt((a + c + mysqrt(sqr(a + c) - llf(4) * (a * c - b * b))) / llf(2));
  34. }
  36. int main()
  37. {
  38.     std::scanf("%u", &T);
  39.     for (ul Case = 1; Case <= T; ++Case) {
  40.         std::scanf("%u", &n);
  41.         p = 0;
  42.         X1 = X2 = Y1 = Y2 = Z = 0;
  43.         for (ul i = 1; i <= n; ++i) {
  44.             ul q;
  45.             std::scanf("%u", &q);
  46.             if (q == 1) {
  47.                 std::scanf("%lld%lld", &x[i], &y[i]);
  48.                 X1 += x[i];
  49.                 X2 += x[i] * x[i];
  50.                 Y1 += y[i];
  51.                 Y2 += y[i] * y[i];
  52.                 Z += x[i] * y[i];
  53.                 ++p;
  54.             } else {
  55.                 ul t;
  56.                 std::scanf("%u", &t);
  57.                 X1 -= x[t];
  58.                 X2 -= x[t] * x[t];
  59.                 Y1 -= y[t];
  60.                 Y2 -= y[t] * y[t];
  61.                 Z -= x[t] * y[t];
  62.                 --p;
  63.             }
  64.             lf tmp = calc(llf(2) * (llf(X2) / llf(p) - sqr(llf(X1) / llf(p))), llf(2) * (llf(Z) / llf(p) - (llf(X1) / llf(p)) * (llf(Y1) / llf(p))), llf(2) * (llf(Y2) / llf(p) - sqr(llf(Y1) / llf(p))));
  65.             std::printf("%.20lf\n", tmp);
  66.         }
  67.     }
  68.     return 0;
  69. }

J、Tic-Tac-Toe-Nim 6886

AB二人一开始必然选择不同行不同列的两个格子拿完，否则B立即就输了。将与AB二人所拿两格同行或同列的格子编号为，另一格编号为，于是现在问题变为，谁先使得中任何一堆石子空掉，谁就输了，其他情况均不会立即输。于是现在该游戏等价于大小为的一般抓石子游戏。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  5. ul T;
  7. ul v[3][3];
  9. int main()
  10. {
  11.     std::scanf("%u", &T);
  12.     for (ul Case = 1; Case <= T; ++Case) {
  13.         for (ul i = 0; i != 3; ++i) {
  14.             for (ul j = 0; j != 3; ++j) {
  15.                 std::scanf("%u", &v[i][j]);
  16.             }
  17.         }
  18.         ul ans = 0;
  19.         for (ul ai = 0; ai != 3; ++ai) {
  20.             for (ul aj = 0; aj != 3; ++aj) {
  21.                 bool flag = true;
  22.                 for (ul bi = 0; bi != 3 && flag; ++bi) {
  23.                     if (bi == ai) {
  24.                         continue;
  25.                     }
  26.                     for (ul bj = 0; bj != 3 && flag; ++bj) {
  27.                         if (bj == aj) {
  28.                             continue;
  29.                         }
  30.                         ul t = 0;
  31.                         for (ul ci = 0; ci != 3; ++ci) {
  32.                             for (ul cj = 0; cj != 3; ++cj) {
  33.                                 if (ci == ai && cj == aj) {
  34.                                     continue;
  35.                                 }
  36.                                 if (ci == bi && cj == bj) {
  37.                                     continue;
  38.                                 }
  39.                                 if (ci != ai && cj != aj && ci != bi && cj != bj) {
  40.                                     t ^= v[ci][cj];
  41.                                 } else {
  42.                                     t ^= v[ci][cj] - 1;
  43.                                 }
  44.                             }
  45.                         }
  46.                         if (!t) {
  47.                             flag = false;
  48.                         }
  49.                     }
  50.                 }
  51.                 if (flag) {
  52.                     ++ans;
  53.                 }
  54.             }
  55.         }
  56.         std::printf("%u\n", ans);
  57.     }
  58.     return 0;
  59. }

K、Task Scheduler 6887

只要证明且时：


即证明

现在记为，为，于是可知关于的增减如下：在单调递减，在单调递增，且相应相等点满足，所以实际等价于证明，其中。
现在考虑证明不等式
只要证明是关于的严格凹函数即可。只要证明
是严格凹函数即可，这显然是个严格凹函数，证毕。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  5. ul T;
  7. const ul maxn = 100;
  9. ul n, m, k;
  11. class worker {
  12. public:
  13.     ul id = 0;
  14.     ul cnt = 0;
  15. };
  17. bool operator<(const worker& a, const worker& b)
  18. {
  19.     return a.cnt != b.cnt ? a.cnt > b.cnt : a.id < b.id;
  20. }
  22. worker t[maxn + 1];
  24. int main()
  25. {
  26.     std::scanf("%u", &T);
  27.     for (ul Case = 1; Case <= T; ++Case) {
  28.         std::scanf("%u%u%u", &n, &m, &k);
  29.         for (ul i = 1; i <= n; ++i) {
  30.             std::scanf("%u", &t[i].cnt);
  31.             t[i].id = i;
  32.         }
  33.         if (k > 0) {
  34.             std::sort(t + 1, t + n + 1);
  35.         }
  36.         for (ul i = 1; i <= n; ++i) {
  37.             if (i != 1) {
  38.                 std::putchar(' ');
  39.             }
  40.             std::printf("%u", t[i].id);
  41.         }
  42.         std::putchar('\n');
  43.     }
  44.     return 0;
  45. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注