ComplexPug

分类

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

/ 注册

全部文章（共277篇）

hdu1358 Period kmp求循环节

链接 http://acm.hdu.edu.cn/showproblem.php?pid=1358 思路当初shenben学长暑假讲过，当初太笨了，noip前几天才理解过来、、我也没啥好说的代码 #include <iostream> #include <cstdi...

kmp

2019-02-21

0 445

cf213E 线段树维护hash

链接 https://codeforces.com/contest/213/problem/E 题目大意给出两个排列a、b，长度分别为n、m，你需要计算有多少个x，使得\(a_1 + x; a_2 + x; a_3 + x、、、 a_n + x\) 是b 的子序列(不连续的那种)。思路...

线段树 hash

2019-02-21

0 545

bzoj2298: [HAOI2011]problem a DP

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2298 思路把一个人的话转化为区间的线段，显然是\([a_{i},n-b_{i}]\) 然后找最大的不相交，不覆盖的最多线段数量注意是有重复的数字，所以不是单纯的线段覆盖 f[i]=m...

DP

2019-02-21

0 536

loj#2305. 「NOI2017」游戏 2-sat

链接 https://loj.ac/problem/2305 https://www.luogu.org/problemnew/show/P3825 思路 3-sat神马的就不要想了，NP问题除去x每个点只有两种可能，2-sat x只有8个，\(3^n\)暴力枚举哪个不选 2-sat是对称性...

2-sat 暴力

2019-02-21

0 586

P4782 【模板】2-SAT 问题

https://www.luogu.org/problemnew/show/P4782 链接 https://www.luogu.org/problemnew/show/P4782 思路选a就必须选b 好像是要建反边，tarjan，tarjan的染色省去拓扑排序拓扑排序我也感觉跟贪心似的...

2-sat

2019-02-20

0 604

1823: [JSOI2010]满汉全席 2-sat

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1823 思路建图，缩点tarjan 判断impossible 代码 #include <bits/stdc++.h> using namespace std; const...

2-sat

2019-02-20

0 456

2199: [Usaco2011 Jan]奶牛议会 2-sat

链接 https://www.luogu.org/problemnew/show/P3007 https://www.lydsy.com/JudgeOnline/problem.php?id=2199 思路建图，缩点tarjan 判断impossible 之后就不是输出方案的套路了判断Y ...

2-sat

2019-02-20

0 516

P3899 [湖南集训]谈笑风生

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=3653 https://www.luogu.org/problemnew/show/P3899 思路三个点肯定在1到c的链上 a已经确定 1.b是a的祖先，答案就是(siz[u]-1...

线段树合并

2019-02-18

0 426

bzoj 1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场最小点覆盖

链接 1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场思路这就是个上一篇的稍微麻烦版(是变脸版，其实没麻烦) 用边长为1的模板覆盖地图上的没有长草的土地，不能覆盖草地每个点(x,y)只有选择x或者y才能被覆盖还是最小点覆盖，证明在上一篇横边和竖边得遍历一...

网络流最小点覆盖

2019-02-18

0 639

bzoj1741 [Usaco2005 nov]Asteroids 穿越小行星群最小点覆盖

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1741 思路消除所有的小行星每个点(x,y)只有选择x或者y才能被覆盖二分图最小点覆盖=最大流首先，最小顶点覆盖一定>=最大匹配，因为假设最大匹配为n，那么我们就得到...

网络流最小点覆盖

2019-02-18

0 532