首页 > ACM题库 > HDU-杭电 > HDU 4421-Bit Magic-图-[解题报告]HOJ
2015
07-16

HDU 4421-Bit Magic-图-[解题报告]HOJ

Bit Magic

问题描述 :

Yesterday, my teacher taught me about bit operators: and (&), or (|), xor (^). I generated a number table a[N], and wrote a program to calculate the matrix table b[N][N] using three kinds of bit operator. I thought my achievement would get teacher’s attention.
The key function is the code showed below.
Alice and Bob

There is no doubt that my teacher raised lots of interests in my work and was surprised to my talented programming skills. After deeply thinking, he came up with another problem: if we have the matrix table b[N][N] at first, can you check whether corresponding number table a[N] exists?

输入:

There are multiple test cases.
For each test case, the first line contains an integer N, indicating the size of the matrix. (1 <= N <= 500).
The next N lines, each line contains N integers, the jth integer in ith line indicating the element b[i][j] of matrix. (0 <= b[i][j] <= 2 31 – 1)

输出:

There are multiple test cases.
For each test case, the first line contains an integer N, indicating the size of the matrix. (1 <= N <= 500).
The next N lines, each line contains N integers, the jth integer in ith line indicating the element b[i][j] of matrix. (0 <= b[i][j] <= 2 31 – 1)

样例输入:

2
0 4
4 0
3
0 1 24
1 0 86
24 86 0

样例输出:

YES
NO

2012长春现场赛的题

正解要枚举32个bit,每次做2sat判断是否矛盾

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 510
#define NN 1010
#define M 3000100
using namespace std;
int n,b[N][N];

int head[NN],cnt,scc,top,Index;
int dfn[NN],low[NN],instack[NN],sstack[NN],belong[NN];
struct Edge{
    int v,next;
}edge[M];

void addedge(int u,int v){
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

void init(){
    memset(head,-1,sizeof(head));
    memset(instack,0,sizeof(instack));
    memset(dfn,0,sizeof(dfn));
    cnt=Index=top=scc=0;
}

void tarjan(int u){
    dfn[u]=low[u]=++Index;
    sstack[++top]=u;
    instack[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(dfn[v]==0){
            tarjan(v);
            low[u]=min(low[v],low[u]);
        }
        else if(instack[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        scc++;
        while(1){
            int tmp=sstack[top--];
            instack[tmp]=0;
            belong[tmp]=scc;
            if(tmp==u)break;
        }
    }
}

int main(){
    int i,j,k;
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                scanf("%d",&b[i][j]);
        int tem=n;
        bool ok=1;
        for(k=0;k<31;k++){
            init();
            for(i=0;i<n;i++)
                for(j=i+1;j<n;j++){
                    if(i%2==1 && j%2==1){
                        if(b[i][j] & (1<<k)){
                            addedge(i,j+tem);
                            addedge(j,i+tem);
                        }
                        else{
                            addedge(i+tem,i);
                            addedge(j+tem,j);
                        }
                    }
                    else if(i%2==0 && j%2==0){
                        if(b[i][j] & (1<<k)){
                            addedge(i,i+tem);
                            addedge(j,j+tem);
                        }
                        else{
                            addedge(i+tem,j);
                            addedge(j+tem,i);
                        }
                    }
                    else{
                        if(b[i][j] & (1<<k)){
                            addedge(i,j+tem);
                            addedge(i+tem,j);
                            addedge(j,i+tem);
                            addedge(j+tem,i);
                        }
                        else{
                            addedge(i,j);
                            addedge(i+tem,j+tem);
                            addedge(j,i);
                            addedge(j+tem,i+tem);
                        }
                    }
                }
            for(i=0;i<tem*2;i++)
                if(!dfn[i])
                    tarjan(i);
            bool flag=1;
            for(i=0;i<tem;i++)
                if(belong[i]==belong[i+tem]){
                    flag=0;
                    break;
                }
            if(flag==0){
                ok=0;break;
            }
        }
        if(ok) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/waitfor_/article/details/8694370


,