2023SDCPC｜Apr.6 CUC2024区域赛重现#7

The 13th Shandong ICPC Provincial Collegiate Programming Contest

ID	Difficulty	Topic	Status
A	⭐	Implementation, Greedy	0:10:36
B			(-1)
C
D	⭐⭐	Binary Search, Greedy	1:17:06
E	⭐⭐⭐	Math, Number theory, Implementation	(Upsolved)
F
G	⭐	Implementation, Greedy	0:46:48
H
I	⭐	Implementation	0:48:18 (+1)
J
K
L	⭐⭐	Constructive algorithms, Implementation	1:36:02
M	⭐⭐	Computational Geometry	(-1) (Upsolved)

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. Puzzle: Sashigane

• 题意 正方形黑白棋盘中有惟一黑格，用 L 型覆盖白格，给出覆盖方案。

• 思路 从黑色格子开始，每次操作向外包一层 L，形成更大的正方形，直至覆盖完毕。

• void eachT() {
      int n = read(), x = read(), y = read();
      int dy = 1, dx = 1;
      printf("Yes\n%d\n", n - 1);
      for (int i = 1; i < n; ++i) {
          if (x == n) dx = -1, x -= i - 1;
          if (y == n) dy = -1, y -= i - 1;
          x += dx;
          y += dy;
          printf("%d %d %d %d\n", x, y, -i * dx, -i * dy);
      }
  }

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. ↩︎ ↩︎