2020-2021:teams:acm_life_from_zero:8.8-8.14
2020/08/08-2020/08/14周报
团队训练
李元恺
题目
比赛
2020 年百度之星·程序设计大赛 - 复赛 rk:69 pros:3/6
Codeforces Round #664 (Div. 1) rk:131 pros:2/5
姜维翰
袁熙
比赛
本周推荐
李元恺
袁熙
cf1393E Twilight and Ancient Scroll
tag:hash,dp
题意：给n个词构成的串，词之间按字典序不降，可以选择对每个词进行一次操作：在某个字母后添加一个字母之后选择某个词。之后，选择一个词，撤销此操作。问操作后可能产生的串的不同版本数量
思路:考虑dp时，对相邻的两个词$S_1,S_2$，在题意的操作下分别产生$|S_1|+1，|S_2|+1$个子串。如果对子串排序后，对$S_2$的每个子串，可以二分找到合法的$S_1$的子串数量，完成转移。为了在转移时找到合法子串的数量，还需要对每个词hash一下。
comment:补之前的题（ 大概是常规的dp
姜维翰
2020-2021/teams/acm_life_from_zero/8.8-8.14.1597393749.txt.gz · 最后更改: 2020/08/14 16:29 由 kipple
