ComplexPug

未归档

做题记录(1)

/ 注册

全部文章 / 未归档（共273篇）

luoguP4721 【模板】分治 FFT

P4721 【模板】分治 FFT 链接 luogu 题目描述给定长度为 \(n-1\) 的数组 \(g[1],g[2],..,g[n-1]\)，求 \(f[0],f[1],..,f[n-1]\)，其中 \[f[i]=\sum_{j=1}^if[i-j]g[j]\] 边界为 \(f[0]=1...

ntt 分治

2019-07-18

1 848

[Cqoi2016]K远点对 K-Dtree

4520: [Cqoi2016]K远点对链接 bzoj 思路用K-Dtree求点的最远距离。求的时候顺便维护一个大小为2k的小根堆。不知道为啥一定会对。代码 #include <bits/stdc++.h> #define ll long long #define ...

k-dtree

2019-07-17

0 795

[SDOI2010]捉迷藏 K-Dtree

[SDOI2010]捉迷藏链接 luogu 思路 k-dtree模板题代码 #include <bits/stdc++.h> #define ls (t[u].ch[0]) #define rs (t[u].ch[1]) #define cmin(a,b) (a>b...

k-dtree

2019-07-17

0 656

NOI2019 回家路线 DP

「NOI2019」回家路线链接 loj 思路 f[i][j]第i个点，时间为j，暴力转移复杂度O(m*t),好像正解是斜率优化，出题人太不小心了233 代码 #include <bits/stdc++.h> using namespace std; const int N...

DP

2019-07-17

0 706

bzoj4066: 简单题 K-Dtree

bzoj4066: 简单题链接 bzoj 思路强制在线。k-dtree。卡常啊。空间开1e6就T了。代码 #include <bits/stdc++.h> #define my_min(a,b) (a<b?a:a=b) #define my_max(a,b) (...

k-dtree

2019-07-17

0 666

luoguP4169 [Violet]天使玩偶/SJY摆棋子 K-Dtree

P4169 [Violet]天使玩偶/SJY摆棋子链接 luogu 思路 luogu以前用CDQ一直过不去。 bzoj还是卡时过去的。今天终于用k-dtree给过了。代码 #include <bits/stdc++.h> using namespace std; con...

k-dtree

2019-07-16

0 875

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