ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共277篇）

luoguP4112 [HEOI2015]最短不公共子串 SAM,序列自动机，广搜BFS

luoguP4112 [HEOI2015]最短不公共子串链接 luogu loj 思路子串可以用后缀自动机，子序列可以用序列自动机。序列自动机是啥，就是能访问到所有子序列的自动机。每个点记录下一个字母最近出现的位置。不过我这里构造是\(O(n^2)\)。然后进行bfs进行广搜就行了...

后缀自动机序列自动机广搜

2019-07-14

0 623

luogu P4248 [AHOI2013]差异 SAM

luogu P4248 [AHOI2013]差异链接 luogu 思路 \(\sum\limits_{1<=i<j<=n}{{len}(T_i)+{len}(T_j)-2*{lcp}(T_i,T_j)}\) =\(\sum\limits_{1<=i<j<...

后缀自动机

2019-07-14

0 595

cf1191 解题报告

cf1191 解题报告 A-简单模拟脑内算出来让计算机输出 #include <bits/stdc++.h> #define ll long long using namespace std; int main() { int x; cin>>x; ...

CF

2019-07-13

0 542

luogu P3975 [TJOI2015]弦论 SAM

luogu P3975 [TJOI2015]弦论链接 bzoj 思路建出sam。子串算多个的，统计preant tree的子树大小，否则就是大小为1 然后再统计sam的节点能走到多少串。然后就可以在sam的贪心的走了。代码 #include <bits/stdc++.h&...

后缀自动机

2019-07-13

0 681

bzoj3676 [Apio2014]回文串卡常+SAM+树上倍增

bzoj3676 [Apio2014]回文串 SAM+树上倍增链接 bzoj luogu 思路根据manacher可以知道，每次暴力扩展才有可能出现新的回文串。所以推出本质不同的回文串个数是O(n)级别的。每次查询一个串出现的个数。建立出parent树，一个串出现的个数就是对应pa...

后缀自动机树上倍增卡常

2019-07-13

0 708

cf1187解题报告

cf1187解题报告 cf A 去掉都有的,剩下的取最大值+1 #include <bits/stdc++.h> #define int long long using namespace std; signed main() { int T; cin>&g...

CF

2019-07-12

0 486

cf1189解题报告

cf1189div2解题报告 codeforces A 答案要不是一串要不就是去掉最后一个字母的两串 #include <bits/stdc++.h> #define ll long long using namespace std; const int N=107; int a...

CF

2019-07-10

0 556

luogu 2742 二维凸包

链接 luogu 模板一上下利用斜率求凸包然后合并。 #include <bits/stdc++.h> using namespace std; const int N=10005; const double eps=1e-10,inf=0x3f3f3f3f3f3f3f3f; ...

计算几何凸包

2019-06-13

0 590

luoguP1742 最小圆覆盖

最小圆覆盖首先没错，我是个蒟蒻。luogu 流程圆 C; for(i=1 to n) { if(P[i] 不在 C 内) { C = {P[i], 0}; for(j=1 to i-1) { if(P[j] 不在 C 内)...

最小圆覆盖

2019-06-12

0 640

bzoj4501 旅行

bzoj4501: 旅行链接 bzoj 思路我居然一上来就的去重边，***真可爱。如果没有修改的话就是一个拓扑dp。 \(f[u]=\sum\frac{f[v]+1}{numson}\) 修改的话a[i]表示这个边要不要。 \(f[u]=\frac{\sum (f[v]+1)*a[i]...

网络流分数规划最大权闭合子图

2019-06-10

0 537