2-sat – Tgotp-Blog

4945: [Noi2017]游戏

观察d的数据范围为8
然后考虑暴力枚举x的取值…
一开始我暴力令x = ‘a’ ,’b’,’c’则为3^n
但是发现其实因为最后每个位置只用一个取值,那么只要保证x能取’A’ ‘B’ ‘C’即可。
也就是x = ‘a’ ,’b’, 复杂度2^n
接下来容易发现是个2-sat问题…
建边以[......]

Read more

2199: [Usaco2011 Jan]奶牛议会

之前一直不知道2-sat怎么求方案数,然后现在 做了大概懂了。

就是不用tarjan,然后对于每一种状态枚举是否可行,也就是说对于一个方案成与不成立分别判断一次,如果都不行说明impossible,

然后剩下的脑补)

对于判断,就是说把这个点之后的必搭状态全部找出来,判断里面是[......]

Read more

BZOJ3495(PA2010)[Riddle]

2-sat

对于这道题。

前缀和优化。
即令 i + n 表示i所在的王国前 i所处的位置是否存在首都,那么如果 i 为首都,就要向前 i - 1 的位置不是首都的前缀连边,向前i个位置是首都的前缀连边

然后对于前i-1个是首都的前缀要向是首都的前缀连边,以及当前i点不是首都的情[......]

Read more

1997: [Hnoi2010]Planar

对于这道题,分析,对于已经有的回路构图,剩下的边,只有两种选择,圈内圈外,

手动模拟一下就可以发现:题目要求避免两线相交,那么只会存在在圈内的编号存在以下关系时满足:

( u[i] < u[j] && v[i] > u[j] && v[i] &[......]

Read more

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

2-sat模板题

观察发现,对于每一种食材只能选择一次,即如果你选择了一种菜,那么对于这菜所需食材的另外一种方式连向该人的另一种必需品。

这里我看hzwer的blog,感觉就有点问题,他这里是把该菜品连向另一菜品的另外一种形式,exm?难道说你就不能同时选择两种菜了么?

当然代码体[......]

Read more