2020-2021:teams:acm_life_from_zero:8.22-8.28
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:acm_life_from_zero:8.22-8.28 [2020/08/28 10:19] lak [李元恺] |
2020-2021:teams:acm_life_from_zero:8.22-8.28 [2020/08/28 15:30] (当前版本) kipple [袁熙] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| ====== 李元恺 ====== | ====== 李元恺 ====== | ||
| + | 题目： | ||
| + | AGC047 BC | ||
| ====== 姜维翰 ====== | ====== 姜维翰 ====== | ||
| ===== 专题 ===== | ===== 专题 ===== | ||
| 行 33: | 行 34: | ||
| ===== 姜维翰 ===== | ===== 姜维翰 ===== | ||
| + | 链接：https://atcoder.jp/contests/agc047/tasks/agc047_b | ||
| + | agc047 b | ||
| + | |||
| + | 题意：给n个全小写的字符串，可以删除一个字符串中前两个字母中的任意一个，问这n个字符串中，有多少的字符串对，其中一个串经过任意次操作后可以变成另一个串 | ||
| + | |||
| + | 标签：字典树 | ||
| + | |||
| + | 题解：很显然，串S在经过多次操作后，相当于从S的前缀中选一个字母出来，与S剩下的部分拼在一起，也就是说，A想变成B，B去掉首字母之后必然是A的后缀，且B首字母在A去掉该后缀后的部分出现过 | ||
| + | |||
| + | 于是先把所有串的反串建一个trie，对一个串S1来说，一边从叶子向上走一边记录出现过哪些字母，如果到达一个节点p，当前出现过的字符集是Q，就看一下在p的后面接上Q中的字符能不能到达某个串S2的末端（因为插的是反串，所以对应的是串的首字母），能的话就说明S1能变成S2 | ||
| + | |||
| + | 评论：我就是菜.jpg，想到做法的时候已经来不及写了 | ||
| ===== 袁熙 ===== | ===== 袁熙 ===== | ||
| + | [[https://atcoder.jp/contests/abc176/tasks/abc176_f|abc176f brave chain]]\\ | ||
| + | |||
| + | 题意：长$3n(n<2000)$的数列$a,1\leq a_i \leq n$，每次操作可以从最左选5个任意排序并选出3个除去，若3个数相同得一分，直到最后剩下3个数。若他们也都相同，得一分。求可能的最大得分。\\ | ||
| + | |||
| + | tag:dp\\ | ||
| + | |||
| + | 题解：考虑dp(i,x,y)，表示进行第i次操作时，从5个数中留下了x,y 两个数后，已得分的最大值。直接dp状态数会很多，但发现在i和i+1时可能存在的x,y的状态差的不多，可以考虑滚动掉第一维。考虑对i和i+1时x,y变化进行讨论。若i+1时存在三个数相同，可以贪心地直接将这三个数删除；若$x_1,y_1$中有一个/两个数被更换为$x_2，y_2$；有一个数被更换时，$dp_{i+1}(x_1,y_2)$只需要从$dp_i(y_2,*)$更新，两个数都被更换时，仅更新$dp(x_2,y_2)$的最大值。这样每轮处理的状态数是$O(n)$的，复杂度$O(n^2)$\\ | ||
| + | |||
| + | comment:本周做的比较有意思的题 | ||
2020-2021/teams/acm_life_from_zero/8.22-8.28.1598581192.txt.gz · 最后更改: 2020/08/28 10:19 由 lak
