HDU Bit Magic (2-Sat)
程序员文章站
2022-06-02 17:30:30
...
- Bit Magic
- 题意
已知一位数组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<bits/stdc++.h>
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 printf
typedef pair<ll,ll> 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<int>st;
void Init(){
cnt=tot=scc_cnt=0;
for(int i=0;i<N*2;i++){
head[i]=-1;
dfn[i]=sccnum[i]=0;
}
while(!st.empty())
st.pop();
return ;
}
void built_map(int k){
int i,j;
for(i=0;i<N-1;i++){
for(j=i+1;j<N;j++){
int x=2*i;
int y=2*j;
if(b[i][j]&(1ll<<k)){//第k位是1
if(i%2==1&&j%2==1){// 或操作
add(x,y^1);
add(y,x^1);
}
else if(i%2==0&&j%2==0){// 与操作
add(x^1,y^1);
add(y^1,x^1);
}
else{// 异或操作
add(x,y^1);
add(x^1,y);
add(y,x^1);
add(y^1,x);
}
}
else{//第k位是0
if(i%2==1&&j%2==1){// 或操作
add(x,y);
add(y,x);
}
else if(i%2==0&&j%2==0){// 与操作
add(x^1,y);
add(y^1,x);
}
else{// 异或操作
add(x,y);
add(y,x);
add(x^1,y^1);
add(y^1,x^1);
}
}
}
}
return ;
}
void Tarjan(int u){
dfn[u]=low[u]=++tot;
st.push(u);
int i,j,v;
for(i=head[u];~i;i=edge[i].nex){
v=edge[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!sccnum[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
++scc_cnt;
while(!st.empty()){
v=st.top();
st.pop();
sccnum[v]=scc_cnt;
if(u==v)
break;
}
}
return ;
}
bool is_ok(){
int i,j,k;
for(k=0;k<31;k++){//枚举每一位是否有矛盾
Init();
built_map(k);
for(i=0;i<N*2;i++){
if(!dfn[i])
Tarjan(i);
}
for(i=0;i<N*2;i+=2){
if(sccnum[i]==sccnum[i^1])
return false;
}
}
return true;
}
bool is_pre(){
int i,j,k;
for(i=0;i<N;i++){
for(j=i;j<N;j++){
if(i==j&&b[i][j]!=0)
return false;
if(b[i][j]!=b[j][i])
return false;
}
}
return true;
}
int main()
{
// freopen(".../.txt","w",stdout);
// freopen(".../.txt","r",stdin);
// ios::sync_with_stdio(false);
int i,j,k;
while(~scf("%d",&N)){
for(i=0;i<N;i++){
for(j=0;j<N;j++)
scf("%lld",&b[i][j]);
}
if(!is_pre()){
puts("NO");
continue;
}
if(is_ok())
puts("YES");
else
puts("NO");
}
return 0;
}
上一篇: 骁龙855或成高通首款搭载NPU的芯片:AI时机已到?
下一篇: 百度霸屏之视频被动引流实操总结