如果你使用电脑查看这个页面，可以使用 CTRL + SHIFT + L 启用深色模式.

A - Sakurako's Exam

首先将 2 两两匹配，剩余的不超过一个 2 和 1 匹配，最后判断 1 的数量是否充足并且为偶数即可.

时间复杂度 $O(1)$.

int main() {
  multiCase() {
    int a, b; cin >> a >> b;
    b %= 2;
    if (b == 1)
      a -= 2;
    Yes(a >= 0 && a % 2 == 0, "\\n");
  }
  return 0;
}

B - Square or Not

考虑到初始的正方形边长的平方应该恰好等于 $n$，那么得到边长后直接计算即可. 对于非正方形的情况也是容易的，因为 $n \times m\ (n > 2)$ 的好矩形的序列中全 $1$ 的最长前缀长度为 $m+1$，据此可以得到矩形的长宽信息.

时间复杂度 $O(n)$.

int main() {
  multiCase() {
    int n; string s; cin >> n >> s;
    int a = sqrt(n);
    if (a * a != n) {
      Yes(false, "\\n");
      continue;
    }
    int b = n / a;
    bool flg = true;
    for (int i = 0; i < a; i ++) {
      for (int j = 0; j < b; j ++) {
        int exp = (i == 0 || i == a - 1) || (j == 0 || j == b - 1);
        flg &= s[i * b + j] == '0' + exp;
      }
    }
    Yes(flg, "\\n");
  }
  return 0;
}

C - Longest Good Array

显然，将序列的第一个值设为 $l$ 是最优的. 随后考虑增量序列，可以发现，第 $i$ 个值恰好比第 $i-1$ 个值多 $i-1$ 时，序列的增长率可以达到最小，据此模拟构造即可.

时间复杂度 $O(\sqrt r)$.

int main() {
  multiCase() {
    int l, r; cin >> l >> r;
    if (l == r)
      puts("1");
    else {
      int ans = 2;
      int cur = l + 1, dif = 1;
      while (1) {
        ++ dif;
        cur += dif;
        if (cur > r)
          break;
        ++ ans;
      }
      printf("%d\\n", ans);
    }
  }
  return 0;
}

D - Sakurako's Hobby

我们在一个图上从 $i$ 向 $p_i$ 连一条有向边，那么这个图会形成若干个环. 根据题目定义，一个点可以到达的点正是这个点所在的环上的所有点，据此找到所有的环统计答案即可.

时间复杂度 $O(n)$.

int main() {
  multiCase() {
    int n; cin >> n;
    auto p = getv(n);
    string s; cin >> s;
    vector<bool> vis(n);
    vector<int> ans(n);
    for (int i = 0; i < n; i ++) if (!vis[i]) {
      vector<int> cur;
      int pos = i, num = 0;
      do {
        cur.push_back(pos);
        num += s[pos] == '0';
        vis[pos] = true;
        pos = p[pos] - 1;
      } while (!vis[pos]);
      for (auto e: cur)
        ans[e] = num;
    }
    write(ans, "%d ", "\\n");
  }
  return 0;
}

E - Alternating String

首先，考虑到只能删除一个字符，那么我们只能在 $n$ 是奇数时删除一个位置.

预处理函数 $f(ch, l, r, odd)$ 表示将 $[l,r]$ 中奇偶性等于 $odd$ 的部分全部替换成 $ch$ 所需的最少步数，这部分可以对每个字符维护一个前缀和数组做到. 随后考虑求出答案：