[关闭]
@qq290637843 2020-12-06T01:38:46.000000Z 字数 20827 阅读 239

2020杭电第四场

A、Anti-AK Problem 6802

首先，将球单位化。
采用球极投影（注意，球极投影之后，圆可能变成圆，也可能变成直线，为了避免出现特殊情况，将在一开始随机换一个新的正交标架），来给球面上的点赋予新的坐标：

于是可知第一基本形式为
于是面积微元为
其为如下微分形式的外微分：
于是任何一个参数曲线（可能是反向的）所提供的贡献为
此积分作为不定积分等于：
注意不要直接就代值用减法，要把那些跳跃点挖掉。

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  11. using lf = double;
  12. using llf = long double;
  13. using dt = llf;
  15. std::mt19937 gen;
  16. std::normal_distribution<dt> d(dt(0), dt(1) / std::sqrt(dt(3)));
  18. dt mat[4][4];
  19. dt fromv[4];
  20. dt tov[4];
  22. ul T;
  23. ul n;
  24. dt R;
  25. dt r0;
  27. const dt pi = std::acos(dt(-1));
  29. const ul maxn = 5e3;
  31. class circ {
  32. public:
  33.     dt x = 0;
  34.     dt y = 0;
  35.     dt r = 0;
  36.     bool clock = false;
  37. };
  39. circ cs[maxn + 1];
  41. dt sqr(dt a)
  42. {
  43.     return a * a;
  44. }
  46. dt dir(dt x, dt y)
  47. {
  48.     return x > 0 ? (y >= 0 ? std::atan(y / x) : pi + pi + std::atan(y / x)) : (x < 0 ? pi + std::atan(y / x) : (y > 0 ? pi * dt(0.5) : pi * dt(1.5)));
  49. }
  51. dt tracos(dt a2, dt b2, dt c2)
  52. {
  53.     return std::acos(std::min(dt(1), std::max(dt(-1), (b2 + c2 - a2) / std::sqrt(4.0 * b2 * c2))));
  54. }
  56. std::vector<std::pair<dt, char>> stack;
  58. void push(std::vector<std::pair<dt, char>>& v, dt alpha, dt beta)
  59. {
  60.     if (alpha <= beta) {
  61.         while (beta > pi + pi) {
  62.             alpha -= pi + pi;
  63.             beta -= pi + pi;
  64.         }
  65.         if (alpha >= dt(0)) {
  66.             v.push_back(std::pair<dt, char>(alpha, '('));
  67.             v.push_back(std::pair<dt, char>(beta, ')'));
  68.         } else {
  69.             v.push_back(std::pair<dt, char>(alpha + pi + pi, '('));
  70.             v.push_back(std::pair<dt, char>(pi + pi, ')'));
  71.             v.push_back(std::pair<dt, char>(dt(0), '('));
  72.             v.push_back(std::pair<dt, char>(beta, ')'));
  73.         }
  74.     } else {
  75.         while (alpha > pi + pi) {
  76.             alpha -= pi + pi;
  77.             beta -= pi + pi;
  78.         }
  79.         if (beta >= dt(0)) {
  80.             v.push_back(std::pair<dt, char>(alpha, '('));
  81.             v.push_back(std::pair<dt, char>(beta, ')'));
  82.         } else {
  83.             v.push_back(std::pair<dt, char>(alpha, '('));
  84.             v.push_back(std::pair<dt, char>(dt(0), ')'));
  85.             v.push_back(std::pair<dt, char>(pi + pi, '('));
  86.             v.push_back(std::pair<dt, char>(beta + pi + pi, ')'));
  87.         }
  88.     }
  89. }
  91. dt f(dt t, dt x0, dt y0, dt r)
  92. {
  93.     dt sqrt2 = std::sqrt(dt(2));
  94.     dt sint = std::sin(t);
  95.     dt cost = std::cos(t);
  96.     dt r2 = r * r;
  97.     dt x2py2 = x0 * x0 + y0 * y0;
  98.     dt A = std::sqrt(r2 * r2 - 2 * r2 * (-4 + x2py2) + sqr(4 + x2py2));
  99.     dt B = std::sqrt(8 + 2 * sqr(r * sint + y0));
  100.     return t + 2 * (-4 + r2 - x2py2) * (std::atan((2 * r * y0 + (4 + r2 - 2 * r * x0 + x2py2) * std::tan(t / 2)) / A) + (t > pi ? pi : dt(0))) / A + 2 * sqrt2 * std::atan(sqrt2 * (x0 + r * cost) / B) * (y0 + r * sint) / B;
  101. }
  103. dt getans(dt x0, dt y0, dt r, dt a, dt b)
  104. {
  105.     if (a == b) {
  106.         return 0;
  107.     }
  108.     return f(b, x0, y0, r) - f(a, x0, y0, r);
  109. }
  111. dt in()
  112. {
  113.     lf tmp;
  114.     iss >> tmp;
  115.     return tmp;
  116. }
  118. int main()
  119. {
  120.     std::ios::sync_with_stdio(false);
  121.     std::cin.tie(0);
  122.     iss.tie(0);
  123.     oss.tie(0);
  124.     std::getline(std::cin, instr, char(0));
  125.     iss.str(instr);
  126.     gen.seed(std::time(0));
  127.     iss >> T;
  128.     for (ul Case = 1; Case <= T; ++Case) {
  129.         for (ul i = 1; i <= 3; ++i) {
  130.             for (ul j = 1; j <= 3; ++j) {
  131.                 mat[i][j] = d(gen);
  132.             }
  133.             for (ul j = 1; j < i; ++j) {
  134.                 dt s = 0;
  135.                 for (ul k = 1; k <= 3; ++k) {
  136.                     s += mat[i][k] * mat[j][k];
  137.                 }
  138.                 for (ul k = 1; k <= 3; ++k) {
  139.                     mat[i][k] -= mat[j][k] * s;
  140.                 }
  141.             }
  142.             dt s = 0;
  143.             for (ul j = 1; j <= 3; ++j) {
  144.                 s += mat[i][j] * mat[i][j];
  145.             }
  146.             s = std::sqrt(s);
  147.             for (ul j = 1; j <= 3; ++j) {
  148.                 mat[i][j] /= s;
  149.             }
  150.         }
  151.         iss >> n;
  152.         R = in();
  153.         r0 = in();
  154.         r0 /= R;
  155.         for (ul i = 1; i <= n; ++i) {
  156.             dt x, y, z, r;
  157.             fromv[1] = in();
  158.             fromv[2] = in();
  159.             fromv[3] = in();
  160.             r = in();
  161.             for (ul i = 1; i <= 3; ++i) {
  162.                 tov[i] = 0;
  163.                 for (ul j = 1; j <= 3; ++j) {
  164.                     tov[i] += fromv[j] * mat[j][i];
  165.                 }
  166.             }
  167.             x = tov[1] / R;
  168.             y = tov[2] / R;
  169.             z = tov[3] / R;
  170.             r /= R;
  171.             x *= dt(2) / (dt(1) - z);
  172.             y *= dt(2) / (dt(1) - z);
  173.             dt rxy = std::sqrt(x * x + y * y);
  174.             dt dis1 = dt(2) * std::atan(rxy * dt(0.5));
  175.             dt dis2 = dis1 - r;
  176.             dt dis3 = dis1 + r;
  177.             if (dis3 > pi) {
  178.                 cs[i].clock = true;
  179.                 dis3 -= pi + pi;
  180.                 dis2 = dt(2) * std::tan(dis2 * dt(0.5));
  181.                 dis3 = dt(2) * std::tan(dis3 * dt(0.5));
  182.                 dis1 = (dis2 + dis3) * dt(0.5);
  183.                 cs[i].x = x * dis1 / rxy;
  184.                 cs[i].y = y * dis1 / rxy;
  185.                 cs[i].r = (dis2 - dis3) * dt(0.5);
  186.             } else {
  187.                 cs[i].clock = false;
  188.                 dis2 = dt(2) * std::tan(dis2 * dt(0.5));
  189.                 dis3 = dt(2) * std::tan(dis3 * dt(0.5));
  190.                 dis1 = (dis2 + dis3) * dt(0.5);
  191.                 cs[i].x = x * dis1 / rxy;
  192.                 cs[i].y = y * dis1 / rxy;
  193.                 cs[i].r = (dis3 - dis2) * dt(0.5);
  194.             }
  195.         }
  196.         dt ans = 0;
  197.         bool flag = false;
  198.         for (ul i = 1; i <= n; ++i) {
  199.             if (cs[i].clock) {
  200.                 flag = true;
  201.             }
  202.             stack.resize(0);
  203.             for (ul j = 1; j <= n; ++j) {
  204.                 if (i == j) {
  205.                     continue;
  206.                 }
  207.                 if (cs[i].x == cs[j].x && cs[i].y == cs[j].y && cs[i].r == cs[j].r) {
  208.                     if (i > j && !cs[i].clock) {
  209.                         push(stack, dt(0), pi + pi);
  210.                         break;
  211.                     }
  212.                     if (i > j && cs[i].clock) {
  213.                         push(stack, pi + pi, dt(0));
  214.                         break;
  215.                     }
  216.                     continue;
  217.                 }
  218.                 if (sqr(cs[i].x - cs[j].x) + sqr(cs[i].y - cs[j].y) >= sqr(cs[i].r + cs[j].r)) {
  219.                     if (!cs[i].clock && cs[j].clock) {
  220.                         push(stack, dt(0), pi + pi);
  221.                         break;
  222.                     }
  223.                     continue;
  224.                 }
  225.                 if (sqr(cs[i].x - cs[j].x) + sqr(cs[i].y - cs[j].y) <= sqr(cs[i].r - cs[j].r)) {
  226.                     if (cs[i].r <= cs[j].r && !cs[i].clock && !cs[j].clock) {
  227.                         push(stack, dt(0), pi + pi);
  228.                         break;
  229.                     }
  230.                     if (cs[i].r >= cs[j].r && cs[i].clock && cs[j].clock) {
  231.                         push(stack, pi + pi, dt(0));
  232.                         break;
  233.                     }
  234.                     continue;
  235.                 }
  236.                 dt gamma = dir(cs[j].x - cs[i].x, cs[j].y - cs[i].y);
  237.                 dt theta = tracos(sqr(cs[j].r), sqr(cs[i].r), sqr(cs[i].x - cs[j].x) + sqr(cs[i].y - cs[j].y));
  238.                 dt alpha = gamma - theta;
  239.                 dt beta = gamma + theta;
  240.                 if (!cs[i].clock) {
  241.                     if (!cs[j].clock) {
  242.                         push(stack, alpha, beta);
  243.                     } else {
  244.                         push(stack, beta, alpha + pi + pi);
  245.                     }
  246.                 } else {
  247.                     if (!cs[j].clock) {
  248.                         push(stack, beta, alpha);
  249.                     } else {
  250.                         push(stack, alpha + pi + pi, beta);
  251.                     }
  252.                 }
  253.             }
  254.             if (!cs[i].clock) {
  255.                 std::sort(stack.begin(), stack.end(), [](const std::pair<dt, char>& a, const std::pair<dt, char>& b){return a.first != b.first ? a.first < b.first : a.second < b.second;});
  256.             } else {
  257.                 std::sort(stack.begin(), stack.end(), [](const std::pair<dt, char>& a, const std::pair<dt, char>& b){return a.first != b.first ? a.first > b.first : a.second < b.second;});
  258.             }
  259.             ul cnt = 0;
  260.             dt prev;
  261.             if (!cs[i].clock) {
  262.                 prev = 0;
  263.             } else {
  264.                 prev = pi + pi;
  265.             }
  266.             for (const auto &p : stack) {
  267.                 if (cnt == 0) {
  268.                     ans += getans(cs[i].x, cs[i].y, cs[i].r, prev, p.first);
  269.                 }
  270.                 if (p.second == '(') {
  271.                     ++cnt;
  272.                 } else {
  273.                     --cnt;
  274.                 }
  275.                 if (cnt == 0) {
  276.                     prev = p.first;
  277.                 }
  278.             }
  279.             if (!cs[i].clock) {
  280.                 ans += getans(cs[i].x, cs[i].y, cs[i].r, prev, pi + pi);
  281.             } else {
  282.                 ans += getans(cs[i].x, cs[i].y, cs[i].r, prev, 0);
  283.             }
  284.         }
  285.         if (flag) {
  286.             ans += pi + pi + pi + pi;
  287.         }
  288.         ans = ans + (pi + pi + pi + pi - ans) * getans(0, 0, dt(2) * std::tan(r0 * dt(0.5)), 0, pi + pi) / (pi + pi + pi + pi);
  289.         oss << std::fixed << std::setprecision(20) << lf(ans * R * R) << '\n';
  290.     }
  291.     std::cout << oss.str();
  292.     return 0;
  293. }

B、Blow up the Enemy 6803

简单题

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  11. using lf = double;
  13. ul T, n;
  15. int main()
  16. {
  17.     std::ios::sync_with_stdio(false);
  18.     std::cin.tie(0);
  19.     iss.tie(0);
  20.     oss.tie(0);
  21.     std::freopen("B.in", "r", stdin);
  22.     std::getline(std::cin, instr, char(0));
  23.     iss.str(instr);
  24.     iss >> T;
  25.     for (ul Case = 1; Case <= T; ++Case) {
  26.         iss >> n;
  27.         ul mn = 1e9;
  28.         ul cnt = 0;
  29.         for (ul i = 1; i <= n; ++i) {
  30.             ul a, d;
  31.             iss >> a >> d;
  32.             ul v = ((100 + a - 1) / a - 1) * d;
  33.             if (mn > v) {
  34.                 mn = v;
  35.                 cnt = 0;
  36.             }
  37.             if (mn == v) {
  38.                 ++cnt;
  39.             }
  40.         }
  41.         oss << std::fixed << std::setprecision(20) << lf(n + n - cnt) / lf(n << 1) << '\n';
  42.     }
  43.     std::freopen("out.txt", "w", stdout);
  44.     std::cout << oss.str();
  45.     return 0;
  46. }

C、Contest of Rope Pulling 6804

官方题解如下：
新建位图图像.png-223.4kB

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  11. using plili = std::pair<li, li>;
  12. using lf = double;
  14. std::mt19937_64 rnd;
  16. const ul maxn = 1e3;
  17. const ul maxm = 1e3;
  19. const ul maxa = 1000 * std::sqrt(std::acos(lf(-1)) * (maxn + maxm)) + 1;
  20. ul a;
  21. ul n, m;
  23. plili v[maxn + maxm + 1];
  25. ll ans[maxa + maxa + 1];
  27. ul T;
  29. int main()
  30. {
  31.     std::ios::sync_with_stdio(false);
  32.     std::cin.tie(0);
  33.     iss.tie(0);
  34.     oss.tie(0);
  35.     std::getline(std::cin, instr, char(0));
  36.     iss.str(instr);
  37.     rnd.seed(std::time(0));
  38.     iss >> T;
  39.     for (ul Case = 1; Case <= T; ++Case) {
  40.         iss >> n >> m;
  41.         a = 1000 * std::sqrt(std::acos(lf(-1)) * (n + m)) + 1;
  42.         for (ul i = 1; i <= n; ++i) {
  43.             iss >> v[i].first >> v[i].second;
  44.         }
  45.         for (ul i = n + 1; i <= n + m; ++i) {
  46.             iss >> v[i].first >> v[i].second;
  47.             v[i].first = -v[i].first;
  48.         }
  49.         for (ul i = n + m; i >= 1; --i) {
  50.             std::swap(v[i], v[rnd() % i + 1]);
  51.         }
  52.         for (ul i = 0; i <= a + a; ++i) {
  53.             ans[i] = -1e15;
  54.         }
  55.         ans[a] = 0;
  56.         for (ul i = 1; i <= n + m; ++i) {
  57.             if (v[i].first > 0) {
  58.                 for (ul j = a + a; j >= v[i].first; --j) {
  59.                     ans[j] = std::max(ans[j], ans[j - v[i].first] + v[i].second);
  60.                 }
  61.             } else {
  62.                 for (ul j = 0; j <= a + a + v[i].first; ++j) {
  63.                     ans[j] = std::max(ans[j], ans[j - v[i].first] + v[i].second);
  64.                 }
  65.             }
  66.         }
  67.         oss << ans[a] << '\n';
  68.     }
  69.     std::cout << oss.str();
  70.     return 0;
  71. }

D、Deliver the Cake 6805

简单题

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul maxn = 1e5;
  14. ul T;
  16. ul n, m, s, t, x;
  18. class edge_t {
  19. public:
  20.     ul to = 0;
  21.     ull len = 0;
  22.     edge_t()=default;
  23.     edge_t(ul a, ull b): to(a), len(b) {}
  24. };
  26. bool operator<(const edge_t& a, const edge_t& b)
  27. {
  28.     return a.len > b.len;
  29. }
  31. char type[maxn + 2];
  33. std::vector<edge_t> edge[maxn + maxn + 2 + 1];
  35. void connect2(ul a, ul b, ul d)
  36. {
  37.     edge[a].push_back(edge_t(b, d));
  38.     edge[b].push_back(edge_t(a, d));
  39. }
  41. void connect(ul a, ul b, ul d)
  42. {
  43.     if (type[a] != 'R') {
  44.         if (type[b] != 'R') {
  45.             connect2(a, b, d);
  46.         }
  47.         if (type[b] != 'L') {
  48.             connect2(a, b + n, d + x);
  49.         }
  50.     }
  51.     if (type[a] != 'L') {
  52.         if (type[b] != 'R') {
  53.             connect2(a + n, b, d + x);
  54.         }
  55.         if (type[b] != 'L') {
  56.             connect2(a + n, b + n, d);
  57.         }
  58.     }
  59. }
  61. std::priority_queue<edge_t> heap;
  63. ull dis[maxn + maxn + 2 + 1];
  65. int main()
  66. {
  67.     std::ios::sync_with_stdio(false);
  68.     std::cin.tie(0);
  69.     iss.tie(0);
  70.     oss.tie(0);
  71.     std::getline(std::cin, instr, char(0));
  72.     iss.str(instr);
  73.     iss >> T;
  74.     for (ul Case = 1; Case <= T; ++Case) {
  75.         iss >> n >> m >> s >> t >> x >> type + 1;
  76.         for (ul i = 1; i <= n + n + 2; ++i) {
  77.             edge[i].resize(0);
  78.             dis[i] = 1e18;
  79.         }
  80.         if (type[s] != 'R') {
  81.             connect2(n + n + 1, s, 0);
  82.         }
  83.         if (type[s] != 'L') {
  84.             connect2(n + n + 1, s + n, 0);
  85.         }
  86.         if (type[t] != 'R') {
  87.             connect2(n + n + 2, t, 0);
  88.         }
  89.         if (type[t] != 'L') {
  90.             connect2(n + n + 2, t + n, 0);
  91.         }
  92.         for (ul i = 1; i <= m; ++i) {
  93.             ul a, b, d;
  94.             iss >> a >> b >> d;
  95.             connect(a, b, d);
  96.         }
  97.         while (heap.size()) {
  98.             heap.pop();
  99.         }
  100.         heap.push(edge_t(n + n + 1, 0));
  101.         dis[n + n + 1] = 0;
  102.         while (true) {
  103.             auto curr = heap.top();
  104.             if (curr.to == n + n + 2) {
  105.                 oss << curr.len << '\n';
  106.                 break;
  107.             }
  108.             heap.pop();
  109.             if (curr.len > dis[curr.to]) {
  110.                 continue;
  111.             }
  112.             for (const auto& next : edge[curr.to]) {
  113.                 if (next.len + curr.len < dis[next.to]) {
  114.                     dis[next.to] = next.len + curr.len;
  115.                     heap.push(edge_t(next.to, next.len + curr.len));
  116.                 }
  117.             }
  118.         }
  119.     }
  120.     std::cout << oss.str();
  121.     return 0;
  122. }

E、Equal Sentences 6806

用表示长为的前缀所对应的答案，递推式很容易想到。

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. std::string curr, next;
  13. ul n, T;
  15. const ul mod = 1e9 + 7;
  17. ul plus(ul a, ul b)
  18. {
  19.     return a + b < mod ? a + b : a + b - mod;
  20. }
  22. int main()
  23. {
  24.     std::ios::sync_with_stdio(false);
  25.     std::cin.tie(0);
  26.     iss.tie(0);
  27.     oss.tie(0);
  28.     std::getline(std::cin, instr, char(0));
  29.     iss.str(instr);
  30.     iss >> T;
  31.     for (ul Case = 1; Case <= T; ++Case) {
  32.         iss >> n;
  33.         ul ansprev = 0;
  34.         ul anscurr = 1;
  35.         curr = "";
  36.         for (ul i = 1; i <= n; ++i) {
  37.             iss >> next;
  38.             ul ansnext;
  39.             if (curr != next) {
  40.                 ansnext = plus(ansprev, anscurr);
  41.             } else {
  42.                 ansnext = anscurr;
  43.             }
  44.             std::swap(curr, next);
  45.             ansprev = anscurr;
  46.             anscurr = ansnext;
  47.         }
  48.         oss << anscurr << '\n';
  49.     }
  50.     std::cout << oss.str();
  51.     return 0;
  52. }

F、Fake Photo 6807

现在考虑以时针走一圈的时长为“一单位时长”（也就是半天），以一圈的路程为“一单位路程”。那么可以分析得出如下结论：最优时刻一定形如或，所以我们只需要把表盘等分为份，然后每一个样例只考虑个有必要考虑的时间点即可。故总时间复杂度为

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  11. using lf = double;
  13. const ul mod = 43200 * 13 * 2;
  14. const ul halfmod = 43200 * 13;
  16. ul plus(ul a, ul b)
  17. {
  18.     return a + b < mod ? a + b : a + b - mod;
  19. }
  21. ul minus(ul a, ul b)
  22. {
  23.     return a < b ? a + mod - b : a - b;
  24. }
  26. ul T;
  27. ul n;
  29. std::vector<ul> hpos;
  30. std::vector<ul> mpos;
  32. std::vector<ul> ntch(43200 * 14);
  33. std::vector<ul> ntcm(43200 * 14);
  35. char s[10];
  37. ul minus(ul a, ul b, ul mod)
  38. {
  39.     return a < b ? a + mod - b : a - b;
  40. }
  42. ul plus(ul a, ul b, ul mod)
  43. {
  44.     return a + b < mod ? a + b : a + b - mod;
  45. }
  47. int main()
  48. {
  49.     std::ios::sync_with_stdio(false);
  50.     std::cin.tie(0);
  51.     iss.tie(0);
  52.     oss.tie(0);
  53.     std::getline(std::cin, instr, char(0));
  54.     iss.str(instr);
  55.     ntch.resize(0);
  56.     ntcm.resize(0);
  57.     for (ul i = 0; i != mod; ++i) {
  58.         if (i % 13 == 0 || i % 2 == 0) {
  59.             ntch.push_back(i);
  60.             ntcm.push_back(12 * i % mod);
  61.         }
  62.     }
  63.     iss >> T;
  64.     for (ul Case = 1; Case <= T; ++Case) {
  65.         iss >> n;
  66.         hpos.resize(0);
  67.         mpos.resize(0);
  68.         for (ul i = 1; i <= n; ++i) {
  69.             iss >> s + 1;
  70.             ul t = (((s[1] - '0') * 10 + s[2] - '0') * 60 + (s[4] - '0') * 10 + s[5] - '0') * 60 + (s[7] - '0') * 10 + s[8] - '0';
  71.             hpos.push_back(plus(t % 43200 * 26, halfmod));
  72.             mpos.push_back(plus(t * 12 % 43200 * 26, halfmod));
  73.         }
  74.         std::sort(hpos.begin(), hpos.end());
  75.         hpos.resize(std::unique(hpos.begin(), hpos.end()) - hpos.begin());
  76.         std::sort(mpos.begin(), mpos.end());
  77.         mpos.resize(std::unique(mpos.begin(), mpos.end()) - mpos.begin());
  78.         ul mx = 0;
  79.         ul ith = 0;
  80.         ul itm = 0;
  81.         for (ul i = 0; i != ntch.size(); ++i) {
  82.             mx = std::max(mx, std::min(std::min(minus(ntcm[i], mpos[minus(itm, 1, mpos.size())]), minus(mpos[itm], ntcm[i])), std::min(minus(ntch[i], hpos[minus(ith, 1, hpos.size())]), minus(hpos[ith], ntch[i]))));
  83.             if (ntch[i] == hpos[ith]) {
  84.                 ith = plus(ith, 1, hpos.size());
  85.             }
  86.             if (ntcm[i] == mpos[itm]) {
  87.                 itm = plus(itm, 1, mpos.size());
  88.             }
  89.         }
  90.         oss << std::fixed << ' ' << std::setprecision(20) << lf(360 * (halfmod - mx)) / lf(mod) << '\n';
  91.     }
  92.     std::cout << oss.str();
  93.     return 0;
  94. }

G、Go Running 6808

二分图最大匹配，HK算法，直接把下文当模板即可。

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul maxn = 1e5;
  14. ul T;
  15. ul n;
  17. li t, x;
  19. std::pair<li, li> ee[maxn + 1];
  21. li as[maxn + 1];
  22. li bs[maxn + 1];
  23. ul acnt, bcnt;
  25. std::vector<ul> edges[maxn + maxn + 1];
  27. ul match[maxn + maxn + 1];
  29. std::deque<ul> queue;
  31. ul dis[maxn + maxn + 1];
  33. const ul inf = 1e9;
  35. ul al[maxn + maxn + 1];
  37. ul altim;
  39. bool search(ul curr)
  40. {
  41.     al[curr] = altim;
  42.     if (dis[curr] == 1) {
  43.         return true;
  44.     }
  45.     if (curr <= acnt) {
  46.         ul next = match[curr];
  47.         if (altim == al[next] || dis[next] != dis[curr] - 1) {
  48.             return false;
  49.         }
  50.         if (search(next)) {
  51.             return true;
  52.         }
  53.     } else {
  54.         for (ul next : edges[curr]) {
  55.             if (altim == al[next] || dis[next] != dis[curr] - 1) {
  56.                 continue;
  57.             }
  58.             if (search(next)) {
  59.                 match[next] = curr;
  60.                 match[curr] = next;
  61.                 return true;
  62.             }
  63.         }
  64.     }
  65.     return false;
  66. }
  68. int main()
  69. {
  70.     std::ios::sync_with_stdio(false);
  71.     std::cin.tie(0);
  72.     iss.tie(0);
  73.     oss.tie(0);
  74.     std::getline(std::cin, instr, char(0));
  75.     iss.str(instr);
  76.     iss >> T;
  77.     for (ul Case = 1; Case <= T; ++Case) {
  78.         iss >> n;
  79.         for (ul i = 1; i <= n; ++i) {
  80.             iss >> t >> x;
  81.             ee[i].first = as[i] = t - x;
  82.             ee[i].second = bs[i] = t + x;
  83.         }
  84.         std::sort(as + 1, as + n + 1);
  85.         std::sort(bs + 1, bs + n + 1);
  86.         acnt = std::unique(as + 1, as + n + 1) - as - 1;
  87.         bcnt = std::unique(bs + 1, bs + n + 1) - bs - 1;
  88.         for (ul i = 1; i <= acnt + bcnt; ++i) {
  89.             edges[i].resize(0);
  90.             match[i] = 0;
  91.         }
  92.         for (ul i = 1; i <= n; ++i) {
  93.             ul a = std::lower_bound(as + 1, as + acnt + 1, ee[i].first) - as;
  94.             ul b = std::lower_bound(bs + 1, bs + bcnt + 1, ee[i].second) - bs;
  95.             edges[a].push_back(b + acnt);
  96.             edges[b + acnt].push_back(a);
  97.         }
  98.         ul ans = 0;
  99.         while (true) {
  100.             assert(queue.empty());
  101.             ul k = inf;
  102.             for (ul i = 1; i <= acnt; ++i) {
  103.                 if (!match[i]) {
  104.                     queue.push_back(i);
  105.                     dis[i] = 1;
  106.                 } else {
  107.                     dis[i] = inf;
  108.                 }
  109.             }
  110.             for (ul i = acnt + 1; i <= acnt + bcnt; ++i) {
  111.                 dis[i] = inf;
  112.             }
  113.             while (queue.size()) {
  114.                 ul curr = queue.front();
  115.                 queue.pop_front();
  116.                 if (dis[curr] == k) {
  117.                     continue;
  118.                 }
  119.                 if (curr <= acnt) {
  120.                     for (ul next : edges[curr]) {
  121.                         if (dis[next] != inf) {
  122.                             continue;
  123.                         }
  124.                         if (!match[next]) {
  125.                             if (k == inf) {
  126.                                 k = dis[curr] + 1;
  127.                             }
  128.                         }
  129.                         dis[next] = dis[curr] + 1;
  130.                         queue.push_back(next);
  131.                     }
  132.                 } else {
  133.                     ul next = match[curr];
  134.                     if (dis[next] != inf) {
  135.                         continue;
  136.                     }
  137.                     dis[next] = dis[curr] + 1;
  138.                     queue.push_back(next);
  139.                 }
  140.             }
  141.             if (k == inf) {
  142.                 break;
  143.             }
  144.             ++altim;
  145.             for (ul i = acnt + 1; i <= acnt + bcnt; ++i) {
  146.                 if (!match[i] && dis[i] == k) {
  147.                     ans += search(i);
  148.                 }
  149.             }
  150.         }
  151.         oss << ans << '\n';
  152.     }
  153.     std::cout << oss.str();
  154.     return 0;
  155. }

H、Head Maker 6809

随机几棵生成树，然后检查是否可行即可。

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using li = std::int32_t;
  8. using ul = std::uint32_t;
  9. using plili = std::pair<li, li>;
  10. using ppliliplili = std::pair<plili, plili>;
  11. using pulul = std::pair<ul, ul>;
  12. using pulpulul = std::pair<ul, pulul>;
  14. const ul maxn = 6;
  15. const ul maxm = 6;
  17. ul fa[maxn * maxm + 1];
  18. ul rk[maxn * maxm + 1];
  20. ul getfather(ul x)
  21. {
  22.     return x == fa[x] ? x : fa[x] = getfather(fa[x]);
  23. }
  25. bool connect(ul x, ul y)
  26. {
  27.     x = getfather(x);
  28.     y = getfather(y);
  29.     if (x == y) {
  30.         return false;
  31.     }
  32.     if (rk[x] < rk[y]) {
  33.         fa[x] = y;
  34.     } else if (rk[x] > rk[y]) {
  35.         fa[y] = x;
  36.     } else {
  37.         fa[x] = y;
  38.         ++rk[y];
  39.     }
  40.     return true;
  41. }
  43. class vec {
  44. public:
  45.     li x = 0;
  46.     li y = 0;
  47.     li z = 0;
  48.     vec()=default;
  49.     vec(li a, li b , li c): x(a), y(b), z(c) {}
  50. };
  52. vec operator+(const vec& a, const vec& b)
  53. {
  54.     return vec(a.x + b.x, a.y + b.y, a.z + b.z);
  55. }
  57. vec operator*(li a, const vec& b)
  58. {
  59.     return vec(a * b.x, a * b.y, a * b.z);
  60. }
  62. li operator*(const vec& a, const vec& b)
  63. {
  64.     return a.x * b.x + a.y * b.y + a.z * b.z;
  65. }
  67. vec operator^(const vec& a, const vec& b)
  68. {
  69.     return vec(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);
  70. }
  72. bool operator<(const vec& a, const vec& b)
  73. {
  74.     return a.x != b.x ? a.x < b.x : (a.y != b.y ? a.y < b.y : a.z < b.z);
  75. }
  77. bool operator==(const vec& a, const vec& b)
  78. {
  79.     return a.x == b.x && a.y == b.y && a.z == b.z;
  80. }
  82. bool operator!=(const vec& a, const vec& b)
  83. {
  84.     return !(a == b);
  85. }
  87. class mat {
  88. public:
  89.     vec x;
  90.     vec y;
  91.     vec z;
  92.     mat()=default;
  93.     mat(const vec& a, const vec& b, const vec& c): x(a), y(b), z(c) {}
  94. };
  96. vec operator*(const vec& a, const mat& b)
  97. {
  98.     return a.x * b.x + a.y * b.y + a.z * b.z;
  99. }
  101. mat operator*(const mat& a, const mat& b)
  102. {
  103.     return mat(a.x * b, a.y * b, a.z * b);
  104. }
  106. bool operator<(const mat& a, const mat& b)
  107. {
  108.     return a.x != b.x ? a.x < b.x : (a.y != b.y ? a.y < b.y : a.z < b.z);
  109. }
  111. bool operator==(const mat& a, const mat& b)
  112. {
  113.     return a.x == b.x && a.y == b.y && a.z == b.z;
  114. }
  116. std::vector<vec> dir = {vec(1, 0, 0), vec(0, 1, 0), vec(-1, 0, 0), vec(0, -1, 0), vec(0, 0, 1), vec(0, 0, -1)};
  117. std::vector<mat> state;
  119. std::map<mat, ul> stateid;
  120. std::map<vec, ul> dirid;
  122. std::vector<mat> rot = {
  123.     mat(
  124.         vec(0, 0, -1),
  125.         vec(0, 1, 0),
  126.         vec(1, 0, 0)
  127.     ),
  128.     mat(
  129.         vec(1, 0, 0),
  130.         vec(0, 0, -1),
  131.         vec(0, 1, 0)
  132.     ),
  133.     mat(
  134.         vec(0, 0, 1),
  135.         vec(0, 1, 0),
  136.         vec(-1, 0, 0)
  137.     ),
  138.     mat(
  139.         vec(1, 0, 0),
  140.         vec(0, 0, 1),
  141.         vec(0, -1, 0)
  142.     )
  143. };
  145. ul inv[24];
  146. ul bt[24];
  147. ul change[24][4];
  150. std::deque<pulul> queue;
  151. ul st[maxn * maxm + 1];
  153. bool ans = false;
  155. std::vector<pulpulul> e;
  157. std::vector<pulul> edge[maxn * maxm + 1];
  159. std::mt19937_64 rnd;
  161. ul vsz;
  163. void check() {
  164.     for (ul i = e.size(); i; --i) {
  165.         std::swap(e[rnd() % i], e[i - 1]);
  166.     }
  167.     for (ul i = 1; i <= vsz; ++i) {
  168.         fa[i] = i;
  169.         rk[i] = 0;
  170.         edge[i].resize(0);
  171.     }
  172.     for (auto a : e) {
  173.         if (connect(a.second.first, a.second.second)) {
  174.             edge[a.second.first].push_back(pulul(a.first, a.second.second));
  175.             edge[a.second.second].push_back(pulul(a.first ^ 2, a.second.first));
  176.         }
  177.     }
  178.     while (queue.size()) {
  179.         queue.pop_front();
  180.     }
  181.     queue.push_back(pulul(0, 1));
  182.     st[1] = 0;
  183.     ul set = 0;
  184.     while (queue.size()) {
  185.         auto p = queue.front();
  186.         queue.pop_front();
  187.         auto curr = p.second;
  188.         auto prev = p.first;
  189.         set |= 1 << bt[st[curr]];
  190.         if (set == (1 << 6) - 1) {
  191.             ans = true;
  192.             break;
  193.         }
  194.         for (auto a : edge[curr]) {
  195.             ul i = a.first;
  196.             ul next = a.second;
  197.             if (next == prev) {
  198.                 continue;
  199.             }
  200.             st[next] = change[st[curr]][i];
  201.             queue.push_back(pulul(curr, next));
  202.         }
  203.     }
  204. }
  206. ul T;
  208. ul n, m;
  210. std::map<plili, ul> v;
  212. char str[maxm + 2];
  214. int main() {
  215.     std::ios::sync_with_stdio(false);
  216.     std::cin.tie(0);
  217.     iss.tie(0);
  218.     oss.tie(0);
  219.     std::getline(std::cin, instr, char(0));
  220.     iss.str(instr);
  221.     rnd.seed(std::time(0));
  222.     for (ul i = 0; i != 6; ++i) {
  223.         dirid[dir[i]] = i;
  224.     }
  225.     for (auto x : dir) {
  226.         for (auto y : dir) {
  227.             if ((x ^ y) == vec(0, 0, 0)) {
  228.                 continue;
  229.             }
  230.             state.push_back(mat(x, y, x ^ y));
  231.         }
  232.     }
  233.     for (ul i = 0; i != 24; ++i) {
  234.         stateid[state[i]] = i;
  235.     }
  236.     for (ul i = 0; i != 24; ++i) {
  237.         for (ul j = 0; j != 24; ++j) {
  238.             if (state[i] * state[j] == mat(vec(1, 0, 0), vec(0, 1, 0), vec(0, 0, 1))) {
  239.                 inv[i] = j;
  240.             }
  241.         }
  242.         bt[i] = dirid[vec(0, 0, -1) * state[inv[i]]];
  243.     }
  244.     for (ul i = 0; i != 24; ++i) {
  245.         for (ul j = 0; j != 4; ++j) {
  246.             change[i][j] = stateid[state[i] * rot[j]];
  247.         }
  248.     }
  249.     iss >> T;
  250.     for (ul Case = 1; Case <= T; ++Case) {
  251.         iss >> n >> m;
  252.         v.clear();
  253.         vsz = 0;
  254.         for (ul i = 1; i <= n; ++i) {
  255.             iss >> str + 1;
  256.             for (ul j = 1; j <= m; ++j) {
  257.                 if (str[j] == '1') {
  258.                     ++vsz;
  259.                     v[plili(i, j)] = vsz;
  260.                 }
  261.             }
  262.         }
  263.         e.resize(0);
  264.         for (const auto& a : v) {
  265.             auto curr = a.first;
  266.             for (ul i = 0; i != 2; ++i) {
  267.                 auto next = plili(curr.first + dir[i].x, curr.second + dir[i].y);
  268.                 if (v.find(next) != v.end()) {
  269.                     e.push_back(pulpulul(i, pulul(a.second, v[next])));
  270.                 }
  271.             }
  272.         }
  273.         ans = false;
  274.         for (ul cnt = 0; cnt != 10; ++cnt) {
  275.             check();
  276.             if (ans) {
  277.                 oss << "Yes\n";
  278.                 break;
  279.             }
  280.         }
  281.         if (!ans) {
  282.             oss << "No\n";
  283.         }
  284.     }
  285.     std::cout << oss.str();
  286.     return 0;
  287. }

I、Imperative Meeting 6810

官方题解如下：
新建位图图像.png-179.5kB

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using li = std::int32_t;
  8. using ul = std::uint32_t;
  9. using ll = std::int64_t;
  10. using ull = std::uint64_t;
  12. const ul mod = 1e9 + 7;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < mod ? a + b : a + b - mod;
  17. }
  19. ul minus(ul a, ul b)
  20. {
  21.     return a < b ? a + mod - b : a - b;
  22. }
  24. ul mul(ul a, ul b)
  25. {
  26.     return ull(a) * ull(b) % mod;
  27. }
  29. void exgcd(li a, li b, li& x, li& y)
  30. {
  31.     if (b) {
  32.         exgcd(b, a % b, y, x);
  33.         y -= a / b * x;
  34.     } else {
  35.         x = 1;
  36.         y = 0;
  37.     }
  38. }
  40. ul inverse(ul a)
  41. {
  42.     li x, y;
  43.     exgcd(a, mod, x, y);
  44.     return x < 0 ? x + li(mod) : x;
  45. }
  47. const ul maxn = 1e6;
  48. ul n, m;
  50. ul T;
  52. ul f[maxn + 1];
  53. ul sz[maxn + 1];
  55. ul h[maxn + 1];
  57. ul fac[maxn + 1];
  58. ul fiv[maxn + 1];
  60. ul bi(ul a, ul b)
  61. {
  62.     return a >= b ? mul(fac[a], mul(fiv[a - b], fiv[b])) : ul(0);
  63. }
  65. int main() {
  66.     std::ios::sync_with_stdio(false);
  67.     std::cin.tie(0);
  68.     iss.tie(0);
  69.     oss.tie(0);
  70.     std::getline(std::cin, instr, char(0));
  71.     iss.str(instr);
  72.     fac[0] = 1;
  73.     for (ul i = 1; i <= maxn; ++i) {
  74.         fac[i] = mul(fac[i - 1], i);
  75.     }
  76.     fiv[maxn] = inverse(fac[maxn]);
  77.     for (ul i = maxn; i >= 1; --i) {
  78.         fiv[i - 1] = mul(fiv[i], i);
  79.     }
  80.     iss >> T;
  81.     for (ul Case = 1; Case <= T; ++Case) {
  82.         iss >> n >> m;
  83.         for (ul i = 2; i <= n; ++i) {
  84.             iss >> f[i];
  85.             sz[i] = 0;
  86.         }
  87.         for (ul i = n; i >= 2; --i) {
  88.             ++sz[i];
  89.             sz[f[i]] += sz[i];
  90.         }
  91.         sz[1] = n;
  92.         ul p = m - 1 >> 1;
  93.         if (p >= 1) {
  94.             h[1] = bi(n - 1, m - 1);
  95.             for (ul s = 2; s <= n; ++s) {
  96.                 h[s] = minus(h[s - 1], mul(bi(s - 2, p - 1), bi(n - s, m - p - 1)));
  97.             }
  98.         } else {
  99.             for (ul s = 1; s <= n; ++s) {
  100.                 h[s] = 0;
  101.             }
  102.         }
  103.         ul ans = 0;
  104.         for (ul i = 2; i <= n; ++i) {
  105.             ul s = sz[i];
  106.             ans = plus(plus(ans, plus(mul(s, h[s]), mul(n - s, h[n - s]))), (~m & 1) ? mul(mul(bi(s, m >> 1), bi(n - s, m >> 1)), m >> 1) : ul(0));
  107.         }
  108.         oss << ans << '\n';
  109.     }
  110.     std::cout << oss.str();
  111.     return 0;
  112. }

K、Kindergarten Physics 6812

傻逼题

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using li = std::int32_t;
  8. using ul = std::uint32_t;
  9. using ll = std::int64_t;
  10. using ull = std::uint64_t;
  12. ul T;
  14. int main() {
  15.     std::ios::sync_with_stdio(false);
  16.     std::cin.tie(0);
  17.     iss.tie(0);
  18.     oss.tie(0);
  19.     std::getline(std::cin, instr, char(0));
  20.     iss.str(instr);
  21.     iss >> T;
  22.     for (ul Case = 1; Case <= T; ++Case) {
  23.         ul a, b, d, t0;
  24.         iss >> a >> b >> d >> t0;
  25.         oss << d << '\n';
  26.     }
  27.     std::cout << oss.str();
  28.     return 0;
  29. }

L、Last Problem 6813

直接看代码

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  11. using plili = std::pair<li, li>;
  13. ul n;
  15. const ul maxn = 100;
  17. std::vector<plili> v[maxn + 1];
  19. int main()
  20. {
  21.     std::ios::sync_with_stdio(false);
  22.     std::cin.tie(0);
  23.     iss.tie(0);
  24.     oss.tie(0);
  25.     std::getline(std::cin, instr, char(0));
  26.     iss.str(instr);
  27.     iss >> n;
  28.     v[n].push_back(plili(0, 0));
  29.     for (ul i = n; i >= 1; --i) {
  30.         std::sort(v[i].begin(), v[i].end());
  31.         v[i].resize(std::unique(v[i].begin(), v[i].end()) - v[i].begin());
  32.         for (const auto& p : v[i]) {
  33.             if (i >= 1) {
  34.                 v[i - 1].push_back(plili(p.first - 1, p.second));
  35.             }
  36.             if (i >= 2) {
  37.                 v[i - 2].push_back(plili(p.first, p.second - 1));
  38.             }
  39.             if (i >= 3) {
  40.                 v[i - 3].push_back(plili(p.first, p.second + 1));
  41.             }
  42.             if (i >= 4) {
  43.                 v[i - 4].push_back(plili(p.first + 1, p.second));
  44.             }
  45.         }
  46.     }
  47.     for (ul i = 1; i <= n; ++i) {
  48.         for (const auto& p : v[i]) {
  49.             oss << p.first << ' ' << p.second << ' ' << i << '\n';
  50.         }
  51.     }
  52.     std::cout << oss.str();
  53.     return 0;
  54. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注