2020.05.03 2019-2020 ICPC Asia Taipei-Hsinchu Regional Contest pro: 11/11/13
rk: 9/488
2020.05.06 Codeforces Round 639 (Div. 1) pro:6/6
DONE
补题:
2020.04.15 Codeforces Round 635 (Div. 1) pro:6/7
pro: 4/6
pro: 6/6
pro: 6/6
pro:4/6
pro:5/6
Codeforces Round 635 (Div. 1): E. Chiori and Doll Picking
很新颖的 Xor-Walsh-Hadamard 变换(并不需要 Fast)题,不过根本想不到。
Codeforces Round 639 (Div. 1): E. Train Tracks
cf 上难得一见的码农题,有兴趣可以练练码力。
Codeforces Round 639 (Div. 1): F. Piet’s Palette
非常有趣的线性代数构造题。
给一个字符串,字符可以把相邻的字符变得和自己一样,随便进行这样的操作若干次,问最后有多少种不同的字符串。
会发现最终的字符串中,字符的顺序应当和给定的字符串中字符的顺序一样,只不过给定的字符串有的字符跳过去了(吞没了)。 问题就可以视为,每次插一个字符,该字符可以作为后缀出现 $0, 1, \ldots$ 若干次,维护方案数。
那我们可以记 $f(c, i)$ 为以字符 $c$ 作为最后一个字符的情况下,长度为 $i$ 的字符串有多少种。 记当前插入的字符是 $u$,那么 $f$ 只有 $f(u, *)$ 被改变了,值变为 $f(u, i) \gets \sum_{v \ne u}{\sum_{j < i} f(v, j)}$。 再记一下 $f(*, i)$ 的前缀和 $S(i)$,就可以每次以 $\mathcal{O}(n)$ 的时间复杂度更新 $f$。
答案是 $\sum_{u}{f(u, n)}$。总时间复杂度 $\mathcal{O}(n^2)$。