2020-2021:teams:intrepidsword:2020.05.01-2020.05.07_周报
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2020.05.01-2020.05.07_周报 [2020/05/09 01:52] admin fix |
2020-2021:teams:intrepidsword:2020.05.01-2020.05.07_周报 [2020/05/16 22:22] (当前版本) chielo [jsh] |
||
|---|---|---|---|
| 行 16: | 行 16: | ||
| ==== jsh ==== | ==== 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_周报]] | + | 详细：[[.:jiangshenghu:2020.05.01-2020.05.07 周报]] |
| 行 40: | 行 45: | ||
| ==== jsh ==== | ==== jsh ==== | ||
| - | [[https://codeforces.com/contest/759/problem/D|Codeforces Round #393 (Div. 1): D. Bacterial Melee]] | + | === Codeforces Round #393 (Div. 1): D. Bacterial Melee === |
| + | [[https://codeforces.com/contest/759/problem/D|题目链接]] | ||
| - | 题意： | + | == 题意 == |
| 给一个字符串，字符可以把相邻的字符变得和自己一样，随便进行这样的操作若干次，问最后有多少种不同的字符串。 | 给一个字符串，字符可以把相邻的字符变得和自己一样，随便进行这样的操作若干次，问最后有多少种不同的字符串。 | ||
| - | 题解： | + | == 题解 == |
| 会发现最终的字符串中，字符的顺序应当和给定的字符串中字符的顺序一样，只不过给定的字符串有的字符跳过去了（吞没了）。 | 会发现最终的字符串中，字符的顺序应当和给定的字符串中字符的顺序一样，只不过给定的字符串有的字符跳过去了（吞没了）。 | ||
| 行 53: | 行 59: | ||
| 那我们可以记 $f(c, i)$ 为以字符 $c$ 作为最后一个字符的情况下，长度为 $i$ 的字符串有多少种。 | 那我们可以记 $f(c, i)$ 为以字符 $c$ 作为最后一个字符的情况下，长度为 $i$ 的字符串有多少种。 | ||
| 记当前插入的字符是 $u$，那么 $f$ 只有 $f(u, *)$ 被改变了，值变为 $f(u, i) \gets \sum_{v \ne u}{\sum_{j < i} f(v, j)}$。 | 记当前插入的字符是 $u$，那么 $f$ 只有 $f(u, *)$ 被改变了，值变为 $f(u, i) \gets \sum_{v \ne u}{\sum_{j < i} f(v, j)}$。 | ||
| - | 再记一下 $f(i, *)$ 的前缀和，就可以每次以 $\mathcal{O}(n)$ 的时间复杂度更新 $f$。 | + | 再记一下 $f(*, i)$ 的前缀和 $S(i)$，就可以每次以 $\mathcal{O}(n)$ 的时间复杂度更新 $f$。 |
| 答案是 $\sum_{u}{f(u, n)}$。总时间复杂度 $\mathcal{O}(n^2)$。 | 答案是 $\sum_{u}{f(u, n)}$。总时间复杂度 $\mathcal{O}(n^2)$。 | ||
2020-2021/teams/intrepidsword/2020.05.01-2020.05.07_周报.1588960367.txt.gz · 最后更改: 2020/05/09 01:52 由 admin
