2022SYCPC｜Apr.30 CUC2024区域赛重现#10

The 2022 ICPC Asia Shenyang Regional Contest (The 1st Universal Cup, Stage 1: Shenyang)

ID	Difficulty	Topic	Status
A	⭐	Implementation, Greedy
B
C			0:34:09 (+1)
D	⭐⭐	Binary Search, Greedy	0:06:36
E	⭐⭐⭐	Math, Number theory, Implementation	(Upsolved)
F			3:21:40
G	⭐	Implementation, Greedy
H
I	⭐	Implementation	0:48:18 (+1)
J
K
L	⭐⭐	Math, Implementation, Brute Force	4:16:23 (+2)
M	⭐⭐	Computational Geometry

A. Orders

• 题意 每天可加工$k$ 个产品，在第$a_i$ 天消耗$b_i$ 个产品，判断是否有解。

• 思路$ka_i\geqslant\sum{b_i}$。

• void eachT() {
      int n = read(), k = read();
      vector<pair<int, int> > a(n);
      for (auto& i : a) i.f = read(), i.s = read();
      sort(a.begin(), a.end());
      ll sum = 0;
      for (auto i : a) {
          sum += i.s;
          if (1ll * i.f * k < sum) return void(printf("No\n"));
      }
      printf("Yes\n");
  }

B. Building Company

D. Fast and Fat

• 题意$n$ 个人分别有其$v_i$ 和$w_i$。每个人可选择背至多一个人，当$i$ 背着$j$ 时，若$w_i>w_j$， 则$v_i$ 不变，否则$v_i:=v_i - (w_j - w_i)$。求所有有未被背负的人中最小的$v$ 的最大值。

• 思路 二分答案为$x$。$v_i<x$ 的人必须被背起，对于$v_i\geqslant x$ 的人，希望背之后仍有$v_i\geqslant x$。依表达式$v_i:=(v_i+w_i) - w_j$ 知，贪心地选择让最大的$v_i+w_i$ 背最大的$w_j$，以此类推，是最优策略。

• void eachT() {
      int n = read();
      vector<pii> a;
      int l = 1e9, r = 1, mid = -1;
      for (int i = 0; i < n; i++) {
          int v = read(), w = read();
          a.push_back({ v,w });
          l = min(l, v); r = max(r, v);
      }
      auto half = [&](ll x) {
          vector<pii> top, back;
          for (auto i : a) {
              if (i.f < x) top.push_back(i);
              else back.push_back(i);
          }
          sort(top.begin(), top.end(), [&](pii n1, pii n2) { return n1.s > n2.s; });
          sort(back.begin(), back.end(), [&](pii n1, pii n2) { return n1.f + n1.s > n2.f + n2.s; });
          if (top.size() > back.size()) return 0;
          for (int i = 0; i < top.size(); ++i) {
              if (back[i].f - top[i].s + back[i].s < x) return 0;
          }
          return 1;
      };
      while (l <= r) { mid = l + r >> 1; if (half(mid)) l = mid + 1; else r = mid - 1; }
      printf("%d\n", r);
  }

E. Math Problem

• 题意 给定$n,k,m$，可任意多次花费$a$ 将$n$ 变为$kn + x ,~ 0 \leqslant x< k$，或花费$b$ 将$n$ 变为$\lfloor\frac nk\rfloor$，求将$n$ 变为$m$ 的 倍数(multiple) 的最小花费。

• 思路 两个操作对应$k$ 进制下的「补末位」和「删末位」操作。因操作方法不惟一，且位数很少，枚举删的位数。（止步于此，可能是被进制局限了） 继续枚举补的位数，虽然补的数无法确定，但它有一个范围，只要范围内存在$m$ 的倍数即保证有解。

  具体地说，对$n$ 进行$x$ 次乘法操作后的取值区间是$\left[nk^x,~ (n+1)k^x-1 \right]$。要判断区间$\left(l,r\right]$ 中是否存在$m$ 的倍数，只需判断$\lfloor\frac{l}{m}\rfloor < \lfloor\frac rm\rfloor$，或$l-(l\bmod m)+m \geqslant r$，等价于$(l\bmod m)+len \geqslant m$，使用后者的优势在于，避免了计算高次幂导致的溢出。

• void eachT() {
      ll n = read(), k = read(), m = read(), a = read(), b = read();
      ll ans = (ll)8e18;
      if (k == 1 && n % m) ans = -1;
      else for (ll bcnt = 0; ; bcnt += b) {
          ll l = n % m, len = 1;
          for (ll acnt = 0;; acnt += a) {
              if (l == 0 || l + len > m) { ans = min(ans, acnt + bcnt); break; }
              l *= k, len *= k, l %= m;
          }
          if (!n || !ans) break;
          n /= k;
      }
      printf("%lld\n", ans);
  }

G. Matching

• 题意 给定序列$a$，按 ^[1] 以下规则构造出一张无向图$G$：若$i - j = a_i - a_j$，则$G$ 中将存在一条连接节点$i$ 与$j$ 的无向边，其边权为$a_i + a_j$，求$G$ 中所有边的边权之和最大的 匹配(matching^[1:1]) 。

• 思路 以$a_i-i$ 为键存入 map，对每个 map 贪心地按边权从大到小选择偶数个。

• void eachT() {
      int n = read();
      map<int, vector<int> > mp;
      for (int i = 1; i <= n; ++i) {
          int x = read();
          mp[x - i].push_back(x);
      }
      ll ans = 0;
      for (auto [j, v] : mp) {
          sort(v.begin(), v.end(), greater<int>());
          for (int i = 1; i < v.size(); i += 2) {
              if (v[i] + v[i - 1] >= 0) ans += v[i] + v[i - 1];
          }
      }
      printf("%lld\n", ans);
  }

I. Three Dice

• 题意 能否掷出三只骰子，使得朝上的面的红色点数之和为$a$，黑色点数之和为$b$。

• 思路 循环枚举。

• void eachT() {
      int a = read(), b = read();
      int ta[] = { 0,1,0,0,1,0,0,0 };
      for (int i = 1; i <= 6; ++i)
          for (int j = 1; j <= 6; ++j)
              for (int k = 1; k <= 6; ++k) {
                  int sum[2] = { 0 };
                  sum[ta[i]] += i;
                  sum[ta[j]] += j;
                  sum[ta[k]] += k;
                  if (sum[1] == a && sum[0] == b)
                      return void(printf("Yes\n"));
              }
      printf("No\n");
  }

L. Tavern Chess

• 题意 模拟《炉石传说》，求双方获胜概率。

• 思路 模拟。注意概率需要「加权」，即在第一轮有一种情形获胜的概率与在第二轮有一种情形获胜的概率是不同的，后者需要将本轮的概率乘上上一轮为判别胜负的概率。

• int n, m;
  
  struct PROBABILITY {
      double a, b, t;
  };
  
  struct MINION {
      int a, h, w, die = 0;
      int dies;
  };
  
  PROBABILITY dfs(bool op, vector<MINION> a, vector<MINION> b, int ta = 0, int tb = 0) {
      PROBABILITY ans = { 0,0,0 };
  
      if (op) {
          int anum = ta;
          while (a[anum].die == 1) {
              anum = (anum + 1) % n;
          }
  
          for (int bnum = 0; bnum < b.size(); ++bnum) {
              if (b[bnum].die == 1) continue;
  
              vector<MINION> atmp = a, btmp = b;
              atmp[anum].h -= btmp[bnum].a;
              atmp[anum].w += 1;
              btmp[bnum].h -= atmp[anum].a;
  
              if (atmp[anum].h <= 0) {
                  atmp[anum].die = 1;
                  atmp[0].dies += 1;
              }
              if (btmp[bnum].h <= 0) {
                  btmp[bnum].die = 1;
                  btmp[0].dies += 1;
              }
  
              if (atmp[0].dies == n && btmp[0].dies == m) {
                  ans.t += 1.0;
              } else if (atmp[0].dies == n) {
                  ans.b += 1.0;
              } else if (btmp[0].dies == m) {
                  ans.a += 1.0;
              } else {
                  PROBABILITY tmp = dfs(op ^ 1, atmp, btmp, (anum + 1) % n, tb);
                  ans.a += tmp.a / (tmp.a + tmp.b + tmp.t);
                  ans.b += tmp.b / (tmp.a + tmp.b + tmp.t);
                  ans.t += tmp.t / (tmp.a + tmp.b + tmp.t);
              }
          }
  
  
  
      } else {
          int bnum = tb;
          while (b[bnum].die == 1) {
              bnum = (bnum + 1) % m;
          }
          for (int anum = 0; anum < a.size(); ++anum) {
              if (a[anum].die == 1) continue;
  
              vector<MINION> atmp = a, btmp = b;
              btmp[bnum].h -= atmp[anum].a;
              btmp[bnum].w += 1;
              atmp[anum].h -= btmp[bnum].a;
  
              if (atmp[anum].h <= 0) {
                  atmp[anum].die = 1;
                  atmp[0].dies += 1;
              }
              if (btmp[bnum].h <= 0) {
                  btmp[bnum].die = 1;
                  btmp[0].dies += 1;
              }
  
              if (atmp[0].dies == n && btmp[0].dies == m) {
                  ans.t += 1.0;
              } else if (atmp[0].dies == n) {
                  ans.b += 1.0;
              } else if (btmp[0].dies == m) {
                  ans.a += 1.0;
              } else {
                  PROBABILITY tmp = dfs(op ^ 1, atmp, btmp, ta, (bnum + 1) % m);
                  ans.a += tmp.a / (tmp.a + tmp.b + tmp.t);
                  ans.b += tmp.b / (tmp.a + tmp.b + tmp.t);
                  ans.t += tmp.t / (tmp.a + tmp.b + tmp.t);
              }
          }
      }
  
      return ans;
  }
  
  void eachT() {
      n = read(), m = read();
  
      vector<MINION> a(n), b(m);
      for (auto& i : a) i.a = i.h = read(), i.w = 0;
      for (auto& i : b) i.a = i.h = read(), i.w = 0;
  
      PROBABILITY ans;
      if (a.size() < b.size()) {
          ans = dfs(0, a, b);
      } else if (a.size() > b.size()) {
          ans = dfs(1, a, b);
      } else {
          ans = dfs(0, a, b);
          PROBABILITY tmp2 = dfs(1, a, b);
          ans.a += tmp2.a;
          ans.b += tmp2.b;
          ans.t += tmp2.t;
      }
      printf("%.12lf ", ans.a / (ans.a + ans.b + ans.t));
      printf("%.12lf ", ans.b / (ans.a + ans.b + ans.t));
      printf("%.12lf ", ans.t / (ans.a + ans.b + ans.t));
  }

• 变式 模拟《Super Auto Pets》，求在所有的排队情形中，双方获胜概率。

• int a_atk[maxN], a_hp[maxN], b_atk[maxN], b_hp[maxN];
  void eachT() {
      int n = read(), m = read();
      for (int i = 0; i < n; ++i) a_hp[i] = a_atk[i] = read();
      for (int j = 0; j < m; ++j) b_hp[j] = b_atk[j] = read();
  
      int alice = 0, bob = 0, tie = 0;
  
      std::sort(a_atk, a_atk + n);
      do {
          for (int bnum = 0; bnum < n; ++bnum) a_hp[bnum] = a_atk[bnum];
  
          std::sort(b_atk, b_atk + m);
          do {
              for (int j = 0; j < m; ++j) b_hp[j] = b_atk[j];
  
              int bnum = 0, j = 0;
              while (iLoveCUC) {
                  a_hp[bnum] -= b_atk[j];
                  b_hp[bnum] -= a_atk[j];
                  if (a_hp[bnum] <= 0) ++bnum;
                  if (b_hp[j] <= 0) ++j;
                  if (bnum == n && j == m) {
                      tie++;
                      break;
                  }
                  if (bnum == n) {
                      bob++;
                      break;
                  }
                  if (j == m) {
                      alice++;
                      break;
                  }
              }
  
          } while (std::next_permutation(b_atk, b_atk + m));
      } while (std::next_permutation(a_atk, a_atk + n));
  
      printf("%.12lf ", alice / (alice + bob + tie));
      printf("%.12lf ", bob / (alice + bob + tie));
      printf("%.12lf ", tie / (alice + bob + tie));
  }

M. Computational Geometry

• 题意 给定$n$ 个顶点的凸多边形$P$，需要选择$P$ 的三个顶点记为$A,B,C$（按逆时针顺序），且$B$ 沿逆时针方向到$C$ 之间恰有$k$ 条边。将由线段$AB,AC$，以及$B$ 和$C$ 之间的$k$ 条边围成的$k + 2$ 边形记作$Q$。 求$Q$ 可能的最大面积$S_Q$。

• 思路$S_Q=S_{B\dots C}+S_{\triangle ABC}$，枚举$B$，则$B,C$ 已经确定，$A$ 需取距离直线$BC$ 最远的点，用三分法解决 （赛时三分法的符号反了） ，时间复杂度$\Theta(n\log n)$。

• void eachT() {
      int n = read(), k = read();
      vector<pair<int, int> > pos(n);
      for (int i = 0; i < n; ++i) pos[i].f = read(), pos[i].s = read();
  
      auto getarea = [&](int i, int j, int k) {
          i %= n, j %= n, k %= n;
          ll x1 = pos[i].f, y1 = pos[i].s;
          ll x2 = pos[j].f, y2 = pos[j].s;
          ll x3 = pos[k].f, y3 = pos[k].s;
          ll _ans = x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2;
          return abs(_ans);
      };
  
      ll area = 0, ans = 0;
      for (int i = 0; i < k; ++i) area += getarea(0, i, i + 1);
  
      auto solve = [&](int a, int b) {
          ll _ans = 0;
          int lt = a, rt = b, lm = -1, rm = -1;
          while (lt + 2 < rt) {
              lm = (lt * 2 + rt) / 3, rm = (rt * 2 + lt) / 3;
              if (getarea(lm, a, b) < getarea(rm, a, b)) lt = lm;
              else rt = rm;
          }
          for (int tt = lt; tt <= rt; ++tt)
              _ans = max(_ans, getarea(a, b, tt));
          return _ans;
      };
  
      for (int i = 0; i <= n; ++i) {
          ans = max(ans, area + solve(i + k, i + n));
          area += getarea(i + k + 1, i, i + k);
          area -= getarea(i + k + 1, i, i + 1);
      }
  
      printf("%.9lf\n", ans * 0.5);
  }

• 评注一 亦可使用点到直线距离公式进行比较：

  int A, B, C;
  auto getkb = [&](int i, int j) {
      i %= n, j %= n;
      A = pos[i].s - pos[j].s;
      B = pos[j].f - pos[i].f;
      C = pos[i].f * pos[j].s - pos[j].f * pos[i].s;
  };
  
  auto getd = [&](int i) {
      i %= n;
      return A * pos[i].f + B * pos[i].s + C; // 无需 / sqrt(A*A + B*B)
  };

• 评注二 注意到$A$ 的位置是逆时针旋转的，可模拟这个过程以代替三分法，将时间复杂度优化到$\Theta(n)$。

---

1. A matching of an undirected graph means that we choose some edges from the graph such that any two edges have no common vertices. Specifically, not choosing any edge is also a matching. ↩︎ ↩︎