用户工具

站点工具


2020-2021:teams:acm_life_from_zero:7.18-7.24

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:acm_life_from_zero:7.18-7.24 [2020/07/24 17:22]
lak [团队训练]
2020-2021:teams:acm_life_from_zero:7.18-7.24 [2020/07/24 17:27] (当前版本)
holmium [姜维翰]
行 67: 行 67:
 题意:给一个长为n的串S,求最长的字符串序列$S,​S_1,​..,​S_k$,​满足其中每一个串都在前一个串中出现至少2次\\ 题意:给一个长为n的串S,求最长的字符串序列$S,​S_1,​..,​S_k$,​满足其中每一个串都在前一个串中出现至少2次\\
 做法:比较容易想到的做法是在SAM的parent树上从根向下找出现次数>​2的点,但并不能满足父亲结点在儿子结点中出现至少两次的要求。 做法:比较容易想到的做法是在SAM的parent树上从根向下找出现次数>​2的点,但并不能满足父亲结点在儿子结点中出现至少两次的要求。
-需要用线段树维护一下串的特定范围上(parent树上结点的长度范围),各个点的endpos,来确定是否满足要求并转移+需要用线段树维护一下串的特定范围上(parent树上结点的长度范围),各个点的endpos,来确定是否满足要求并转移\\
 comment:似乎比较少见的SAM题 comment:似乎比较少见的SAM题
 ====== 姜维翰 ====== ====== 姜维翰 ======
 Codeforces 662C Binary Table\\ Codeforces 662C Binary Table\\
-n行m列(n=20,​m=1e5)的01阵,可以翻转任意行和列,问最少有多少1\\ +tag:​状压,FWT\\ 
-各列压成一个数之后合并,和所有的行状态做一个异或FWT\\ +题面:n行m列(n=20,​m=1e5)的01阵,可以翻转任意行和列,问最少有多少1\\ 
-最后计数一下就行了\\+题解:各列压成一个数之后合并,和所有的行状态做一个异或FWT最后计数一下就行了\\ 
 +comment:算是我找到的比较裸的FWT了,可以用来做个板子
2020-2021/teams/acm_life_from_zero/7.18-7.24.1595582577.txt.gz · 最后更改: 2020/07/24 17:22 由 lak