Warning: session_start(): open(/tmp/sess_56b4653a0fb874dedc77944d811f16b9, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/8/8fe637ac40e9dfa91f93fbcd08d065e4.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
===== 团队 =====
2020.05.03 [[2019-2020taipei-hsinchu|2019-2020 ICPC Asia Taipei-Hsinchu Regional Contest]] ''pro: 11/11/13'' ''rk: 9/488''
===== 个人 =====
==== zzh ====
2020.05.06 [[2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_639_div._1|Codeforces Round 639 (Div. 1)]] ''pro:6/6'' **DONE**
补题：
2020.04.15 [[2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_635_div._1|Codeforces Round 635 (Div. 1)]] ''pro:6/7''
==== pmxm ====
==== jsh ====
* 5/2 - Codeforces Round #393 (Div. 1): ''pro: 4/6''
* 5/4 - AtCoder Beginner Contest 165: ''pro: 6/6''
* 5/5 - 杂题 1000、1800，6 题一小时: ''pro: 6/6''
* 5/6 - Codeforces Round #639 (Div. 1): ''pro:4/6''
* 5/7 - Codeforces Round #613 (Div. 2): ''pro:5/6''
详细：[[.:jiangshenghu:2020.05.01-2020.05.07 周报]]
===== 本周推荐 =====
==== zzh ====
[[2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_635_div._1#e_chiori_and_doll_picking|Codeforces Round 635 (Div. 1): E. Chiori and Doll Picking]]
很新颖的 Xor-Walsh-Hadamard 变换（并不需要 Fast）题，不过根本想不到。
[[2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_639_div._1#e_train_tracks|Codeforces Round 639 (Div. 1): E. Train Tracks]]
cf 上难得一见的码农题，有兴趣可以练练码力。
[[2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_639_div._1#f_piet_s_palette|Codeforces Round 639 (Div. 1): F. Piet’s Palette]]
非常有趣的线性代数构造题。
==== pmxm ====
==== jsh ====
=== Codeforces Round #393 (Div. 1): D. Bacterial Melee ===
[[https://codeforces.com/contest/759/problem/D|题目链接]]
== 题意 ==
给一个字符串，字符可以把相邻的字符变得和自己一样，随便进行这样的操作若干次，问最后有多少种不同的字符串。
== 题解 ==
会发现最终的字符串中，字符的顺序应当和给定的字符串中字符的顺序一样，只不过给定的字符串有的字符跳过去了（吞没了）。
问题就可以视为，每次插一个字符，该字符可以作为后缀出现 $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)$。