大概平均两个星期一篇的样子？有点慢啊。

CF 888 D Almost Identity Permutations

对一个 $n\in [4, 1000]$ 排列，给定一个整数 $k\in [1, 4]$，表示排列中至少有 $n - k$ 个数的下标（从 1 开始）与自己相等。
给定 $n$ 和 $k$，求符合条件的排列个数。

从组合数上看，分情况考虑。$k = 0$ 时有一个；显然不存在 $k = 1$ 的情况；$k = 2$ 时可以挑出 $C_n^2$ 个数用于打乱（两个数只有一种打乱）；剩下两种情况类似。

但是注意：打乱必须是完全乱序的，否则选出 $k$ 个数打乱可能会退化到 $k - 1$ 的情况。所幸 $k\le 4$，挨个列举出完全乱序的个数即可。

CF 1493 C K-beautiful Strings

一个字符串是 k-漂亮的当且仅当各字符出现次数可被 $k$ 整除。
给定一个小写字符串 $s$ 和正整数 $k$。求不小于 $s$ 的最小 k-漂亮字符串。若不存在，输出 $-1$。
$1\le k \le |s|\le 10^5$

这题的 tag 是 2000。直接贴 tutorial 了。

显然，字符串的长度必须可以被 $k$ 整除，这样至少存在一个全 z 的串是符合条件的。而且，如果 $s$ 本身就符合条件，那就很轻松了。不然，我们从尾部向前修改以保证找到的结果递增。

一定会想到分字母统计出现次数。

从尾部开始枚举这样的位置 $p$：前缀不变，第 $p$ 位变大，是否存在符合条件的串。既然已经保证了大于原串，那么第 $p$ 位之后的后缀就应该尽量小，我们根据各字母在前缀中已经出现的次数来贪心即可。

对于每个在前缀中出现过的字母 $c$，它需要增加 $(k - count_c \% k) \% k$ 次出现来构成~~漂亮串~~。如果后缀可以容纳这些增加，那么就可以构造出一个解。关于后缀中多出来的部分长度，必定是 $k$ 的倍数，填上 a 即可。

这题需要注意的是：一旦确定了第一个更大的位置，后缀就只需要考虑凑齐倍数。

核心代码（不包含特判）：

for (int i = len - 1; i >= 0; --i) {
  // dispose the suffix count
  cnt[s[i] - 'a']--;
  for (int ch = s[i] - 'a' + 1; ch < 26; ++ch) {
    // add
    cnt[ch]++;
    // count chars needed to add
    int sum = 0;
    for (int ii = 0; ii < 26; ++ii) sum += (k - cnt[ii] % k) % k;
    // enough capacity
    if (sum <= len - 1 - i) {
      // add from tail to head
      int p = len - 1;
      // from a to z
      for (int ii = 25; ii >= 0; --ii) {
        int lim = (k - cnt[ii] % k) % k;
        while (p > i && lim > 0) {
          lim--;
          s[p--] = ii + 'a';
        }
      }
      // fill blanks
      while (p > i) {
        s[p--] = 'a';
      }
      // apply the iteration
      s[p] = ch + 'a';
      cout << s << endl;
      return;
    }
    // restore for next iteration
    cnt[ch]--;
  }
}

CF 1496 D Let’s Go Hiking

两个人（A 和 B）比赛爬山。山的地形可以用一串数 $p$ 来描述，每个数代表当前位置的高度。
每次移动，两人都只能向左或向右移动一个位置。此外，A 只能移动到严格小于当前高度的位置，B 只能移动到严格大于当前高度的位置。在自己的回合内无法移动的人判负。
A 先选择起始位置，B 后选，之后 A 先移动。
给定一串数，假设两人都采取最优策略，问 A 有几个起始位置可保证自己胜利。
$2\le n\le 10^5, 1\le p_i\le n$

比较繁的题。显然讨论的焦点应该放在最长的斜坡上。基于递增或递减对数列分块是比较常见的手法，记得在循环后处理最后一段。

首先考虑边界情况：当 A 选择斜坡的中间时，B 总能在下面卡住 A。

接着看最长坡的长度 $l$ （包含坡顶和坡底）和拥有这个长度的坡的数量 $c$。A 一定选择坡顶。

如果 $c > 2$，那么 B 也可以选到一个坡顶，则 A 必输
如果 $c = 1$，考虑这个坡的位置：
1. 在边上，则是边界情况
2. 不在边上，B 可以卡位。考虑另一侧较短坡的长度：
  1. 偶数，则 B 可以卡在和短坡底一样的高度
  2. 奇数，则 B 再往下卡一个位置
如果 $c = 2$，考虑 $l$ 的奇偶：
1. 偶数，必输
2. 奇数，A 只要向 B 在的那一侧移动即可

2019 EC Final M Value

对两个长 $n$ 的数列 $a$，$b$，设 $A\subset {1, 2, \cdots n}$，计算 $A$ 的分数如下：

分数初始为 $0$

$\forall i \in A$，得 $a_i$ 分

$\forall i, j \in A, i, j \ge 2$，若 $\exists k>1: i^k = j$，扣 $b_i$ 分

给定 $a$ 和 $b$，求最高的得分。
$1\le n\le 10^5, 1\le a_i, b_i\le 10^9$

底数不同的数是不会互相影响的，把底数相同的抽出来枚举即可。

HDOJ 1754 I Hate It

给定 $n$ 个数（编号从 1 开始）和 $m$ 次操作，操作有以下两种：

U a b：将编号 $a$ 的数更新为 $b$

Q a b：输出编号在 $[a, b]$ 的数的最大值

$1\le n\le 2\times 10^5, 0<m<5000$

线段树裸题。一般来说是：读数据，建树，查询/修改（lazy tag 或者 push up）。注意把区间设成左闭右开的时候会 TLE，而按照普遍使用的闭区间则不会。尽管左闭右开更美观一点。

Hello World.

题解 05

CF 888 D Almost Identity Permutations

CF 1493 C K-beautiful Strings

CF 1496 D Let’s Go Hiking

2019 EC Final M Value

HDOJ 1754 I Hate It