Codeforces Round #116 (Div. 2, ACM-ICPC Rules)

时间:2024-01-06 12:02:50

Codeforces Round #116 (Div. 2, ACM-ICPC Rules)

代码


A. Defragmentation

  • 按颜色分配\(1\)到\(\sum_{i=1}^{m}{n_i}\)位置,那么可以得到\(t_i\)表示位置\(i\)最后占据位置\(t_i\),-1表示该位置为空。
  • 那么会出现两种情况:
  1. \(t_1 \to t_2 \to \cdots \to \ {-1}\),即一条链,从后面往前覆盖。
  2. \(t_1 \to t_2 \to \cdots \to t_i \to t_1\),构成一条链,那么找到一个空位置,将其中一个值暂存在空位置上,变成一条链,最后再把暂存的值放到相应的位置上。

B. Divisibility Rules

  • \(2-type\):\[gcd(d, b, b^2, \cdots, b^k) = 1\]
  • \(3-type\):\[(b-1)\ mod\ d =0\]
  • \(11-type\):\[(b+1)\ mod\ d =0\]
  • \(6-type\):分解质因数,判断每种是否都能表示成前3种之一。

C. Letter

  • 枚举边界,统计前半部分大写字母个数,后半部分小写字母个数。

D. Name

  • 尽可能让前缀相等。
  • \(t\)是\(s\)的前缀情况特判。

E. Cubes

  • 统计每种颜色的位置。
  • 每种颜色单独做,维护左右边界,当操作次数超过k时缩小范围。

F. Mathematical Analysis Rocks!

  • \[p[a[i]] = b[i]\]