本文共 1035 字，大约阅读时间需要 3 分钟。

• 题意
  已知一位数组a[]和二维数组b[][]满足以下关系
  
  给定数组b[][],问是否存在数组a[],如果存在，输出"YES",否则输出"NO"
  • 题解
    写的是2-Sat的专题，想了好久都没想到怎么和2-Sat扯上关系，后来看了题解，说是按位进行2-Sat,就知道要怎么做了。因为位数最多不超过31位i，我一开始想的是从数组b[][]中找到条件，对这31位综合起来只进行一次2-Sat,后来T掉了，但是想了想复杂度是不会T的，现在还想不明白。后来只好对每一位建图，对每一位进行一次2-Sat，如果有一位找出了矛盾，就直接NO了。
  • 代码

#pragma GCC optimize(2)#include
   
    using namespace std;typedef long long ll;typedef unsigned long ul;typedef unsigned long long ull;#define pi acos(-1.0)#define e exp(1.0)#define pb push_back#define mk make_pair#define fir first#define sec second#define scf scanf#define prf printftypedef pair
    
      pa;const int dir_4[4][2]={   -1,0,0,1,1,0,0,-1};const int dir_8[8][2]={   -1,-1,-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1};const ll INF=0x3f3f3f3f3f3f3f3f;const int MAX_N=520*2;struct node{   	int to,nex;}edge[1000000];int N,cnt,tot,scc_cnt,head[MAX_N],dfn[MAX_N],low[MAX_N],sccnum[MAX_N];int base;ll  b[520][520];void add(int u,int v){   	edge[cnt].to=v;	edge[cnt].nex=head[u];	head[u]=cnt++;	return ;}stack
     
      st;void Init(){   	cnt=tot=scc_cnt=0;	for(int i=0;i
     
    
   

转载地址：http://cpph.baihongyu.com/