ComplexPug

未归档

做题记录(1)

/ 注册

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

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 597

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 452

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 507

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 415

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

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

网络流最小点覆盖

2019-02-18

0 633

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

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

网络流最小点覆盖

2019-02-18

0 525

P2860 [USACO06JAN]冗余路径Redundant Paths tarjan

题目链接 https://www.luogu.org/problemnew/show/P2860 思路缩点，之后就成了个树一般的东西了然后（叶子节点+1）/2就是答案，好像贪心的样子，lmc好像讲过诶 cpp #include <iostream> #include <c...

tarjan 树

2019-02-18

0 613

4514: [Sdoi2016]数字配对费用流

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=4514 思路 EK直接贪心做 <0的时候加上剩余返回二分图a->b的时候把b->a也连接上最后除2 整除和贪心可只知道它是对的代码 #include <...

费用流二分贪心

2019-02-18

0 477

P4137 Rmq Problem / mex

目录链接思路线段树莫队链接 https://www.luogu.org/problemnew/show/P4137 思路做了好几次，每次都得想一会，再记录一下可持久化权值线段树区间出现存最小的下标然后线段树上二...

莫队可持久化线段树卡常

2019-02-18

0 518

SP10707 COT2 - Count on a tree II 莫队

链接 https://vjudge.net/problem/SPOJ-COT2 https://www.luogu.org/problemnew/show/SP10707 思路 dfs欧拉序转化为普通莫队（并不算树上莫队，不过也可做) 好神仙啊，原来欧拉序是可以求任意两点的点，不过要加lca。...

莫队 dfs序

2019-02-16

0 556