ComplexPug

分类

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

/ 注册

全部文章（共9篇）

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 503

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 595

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 448

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 578

hdu1814 Peaceful Commission 2-sat

hdu1814 Peaceful Commission 链接 emm，三个链接，三个都不同 loj随便做 hdu字典序最小 bzoj求合法方案数思路 loj是任意一组解，直接跑tarjan然后判。 hdu是求最小字典序的2-sat解，真的是码力弱的要死呀。只有O(N*M)的dfs复杂度能...

2-sat

2019-03-03

0 606

2-sat相关复习

2-sat相关复习 noi曾经考过，谁能说得准呢 sat问题通俗的sat问题表述一般是这样的：有很多个集合，每个集合里面有若干元素，现给出一些取元素的规则，要你判断是否可行，可行则给出一个可行方案。如果所有集合中，元素个数最多的集合有k个，那么我们就说这是一个k-sat问题。 k-sat是N...

2-sat

2019-03-03

0 542

# bzoj2215: [Poi2011]Conspiracy 2-sat

bzoj2215: [Poi2011]Conspiracy 2-sat 链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2215 思路一个点的属性为去当同谋者和后勤两种求出一种方案来很简单(只需要用简单的2-sat) 我们发现一条特...

2-sat

2019-03-07

0 511

AtCoder Regular Contest 069 F Flags 二分，2-sat，线段树优化建图

AtCoder Regular Contest 069 F Flags 二分，2-sat，线段树优化建图链接 AtCoder 大意在数轴上放上n个点，点i可能的位置有\(x_i\)或者\(y_i\) 思路首先最大值最小，考虑二分答案。如何check呢。只有两个坐标，考虑2-sa...

2-sat 线段树线段树优化建图二分二分答案

2019-05-01

0 672

3495: PA2010 Riddle 2-sat 前缀优化

3495: PA2010 Riddle 2-sat 前缀优化链接 bzoj 思路不想说啥了，看hwim的吧，我去睡觉了zZ。代码 /************************************************************** Problem:...

2-sat 前缀优化

2019-05-02

0 544