夢に僕らで帆を張って
来るべき日のために夜を超え

标签 2-SAT 下的文章

November 1, 2019

洛谷P4171/JSOI2010 满汉全席

题意略数据范围:$n \le 100,m \le 1000$题解容易想到这是一个$\text{2-SAT}$问题将每种材料拆成满/汉两种选择,分别为$i,i+n$,每个评审的要求可以看作“或”建图跑$\text{Tarjan}$,判断$i,i+n$是否在同一强连通分量里代码:#include<iostream> #include<cstdio> #include<...
September 26, 2019

CF1215F Radio Stations

题意有$n$个要求,要求电台$x_i$与$y_i$中至少选择$1$个共$p$个电台,满足一个电台的信号功率范围为$[l_i,r_i]$在$[1,M]$选择一个信号功率,要求满足选择的所有电台有$m$对电台不能同时选择判断是否能够满足,如果是,输出方案数据范围:$2 \le n,p,M,m \le 4 \cdot 10^5$题解对于至少选择一个和不能同时选择的要求,我们容易看出这是一个$2-S...