ComplexPug

未归档

做题记录(1)

/ 注册

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

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

cf1173 D. Nauuo and Circle

链接 [cf]http://codeforces.com/contest/1175/problem/F) 思路当1在1的位置做dp[i]为i的子树所有的方案。一条性质是i的子树所占圆上的位置一定一段连续的。那\(f[i]\)的方案就是$(son[i]+(i!=1))!\prod\limi...

DP

2019-06-09

0 610

bzoj3745: [Coci2015]Norma 分治，单调队列

链接 bzoj 思路首先\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{k=i}^{j}max(a_k)\)可以用单调队列求解。参见? 求解此题目，我们分治。计算\([l,mid]\)对\([mid+1,r]\)的贡献。我们...

分治前缀优化单调队列

2019-06-09

0 612

bzoj1176: [Balkan2007]Mokia cdq

链接 bzoj 思路 cdq入门题，拆成4个矩阵，然后cdq。代码 /************************************************************** Problem: 1176 User: gryz2016 Langu...

cdq

2019-06-09

0 517

luoguP3964 [TJOI2013]松鼠聚会

链接 luogu 思路切比雪夫距离有max，不好优化。但是我们能转化成曼哈顿距离，只需要 \((x,y)变成(\frac{x+y}{2},\frac{x-y}{2})\) 相反的曼哈顿距离转切比雪夫距离 \((x,y)=>(x+y,x-y)\) 详情见attack 剩下的就是sort...

2019-06-06

0 507