【题目链接】
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3656
【题目大意】
假设已经知道一个数组a[N],那么用一下函数生成一个矩阵b:
void calculate(int a[N], int b[N][N]) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i == j) b[i][j] = 0;
else if (i % 2 == 1 && j % 2 == 1) b[i][j] = a[i] | a[j];
else if (i % 2 == 0 && j % 2 == 0) b[i][j] = a[i] & a[j];
else b[i][j] = a[i] ^ a[j];
}
}
}
现在已知一个矩阵b,问存不存在一个数组a能转换为矩阵b?
【分析】
这题其实就是 POJ 3678 Katu Puzzle 的加强版。
poj3678每个数字只能选择0或者1,相当与一个二进制只有1位的整数。
而这题每个数字的范围是0 ≤ b[i][j] ≤ 2 ^ 31 - 1, 相当于是二进制有31位的整数,那么只要枚举二进制位,分别对每个二进制为进行2-SAT判断即可!
【代码】
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long int64;
const int MAXN = 610;
const int VN = MAXN*62;
const int EN = 2000010;
int n;
int mat[MAXN][MAXN];
struct Graph{
int size;
int head[VN];
struct Edge{
int v, next;
}E[EN];
void init(){
size = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v){
E[size].v = v;
E[size].next = head[u];
head[u] = size++;
}
}g;
class Two_Sat{
public:
bool check(const Graph&g, const int n){
scc(g, n);
for(int i=0; i<n; ++i)
if(belong[i*2] == belong[i*2+1])
return false;
return true;
}
private:
void tarjan(const Graph&g, const int u){
int v;
DFN[u] = low[u] = ++idx;
sta[top++] = u;
instack[u] = true;
for(int e=g.head[u]; e!=-1; e=g.E[e].next){
v = g.E[e].v;
if(DFN[v] == -1){
tarjan(g, v);
low[u] = min(low[u], low[v]);
}else if(instack[v]){
low[u] = min(low[u], DFN[v]);
}
}
if(low[u] == DFN[u]){
++bcnt;
do{
v = sta[--top];
instack[v] = false;
belong[v] = bcnt;
}while(u != v);
}
}
void scc(const Graph& g, const int n){
top = idx = bcnt = 0;
memset(DFN, -1, sizeof(DFN));
memset(instack, 0, sizeof(instack));
for(int i=0; i<2*n; ++i)
if(DFN[i] == -1)
tarjan(g, i);
}
private:
int top, idx, bcnt;
int DFN[VN];
int low[VN];
int sta[VN];
int belong[VN];
bool instack[VN];
}sat;
bool ok(){
for(int i=0; i<n; ++i){
if(mat[i][i] != 0) return false;
for(int j=i+1; j<n; ++j)
if(mat[i][j] != mat[j][i])
return false;
}
return true;
}
bool judge(){
// 枚举二进制位
for(int k=0; k<31; ++k){
g.init();
for(int i=0; i<n; ++i){
for(int j=i+1; j<n; ++j){
int u=i, v=j, w=(mat[i][j]>>k)&1;
if(i%2==0 && j%2==0){
if(w){
g.addEdge(u*2, v*2+1), g.addEdge(v*2, u*2+1); //0, 0
g.addEdge(u*2, v*2), g.addEdge(v*2+1, u*2+1); // 0, 1
g.addEdge(u*2+1, v*2+1), g.addEdge(v*2, u*2); // 1, 0
}else{
g.addEdge(u*2+1, v*2), g.addEdge(v*2+1, u*2); // 1, 1
}
}else if(i%2==1 && j%2==1){
if(w){
g.addEdge(u*2, v*2+1), g.addEdge(v*2, u*2+1); //0, 0
}else{
g.addEdge(u*2, v*2), g.addEdge(v*2+1, u*2+1); // 0, 1
g.addEdge(u*2+1, v*2+1), g.addEdge(v*2, u*2); // 1, 0
g.addEdge(u*2+1, v*2), g.addEdge(v*2+1, u*2); // 1, 1
}
}else{ // XOR
if(w){
g.addEdge(u*2, v*2+1), g.addEdge(v*2, u*2+1); //0, 0
g.addEdge(u*2+1, v*2), g.addEdge(v*2+1, u*2); // 1, 1
}else{
g.addEdge(u*2, v*2), g.addEdge(v*2+1, u*2+1); // 0, 1
g.addEdge(u*2+1, v*2+1), g.addEdge(v*2, u*2); // 1, 0
}
}
}
}
if(!sat.check(g, n)) return false;
}
return true;
}
int main(){
while(~scanf("%d", &n)){
g.init();
bool flag = true;
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
scanf("%d", &mat[i][j]);
if(!ok()){
puts("NO");
continue;
}
if(judge()) puts("YES");
else puts("NO");
}
return 0;
}
分享到:
相关推荐
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 2247 Magic Trick.md
zoj 3212 K-Nice.md
zoj 1140-zju 2433 简单题的部分答案 都是可以正确通过的,简洁易懂
zoj 2561 Order-Preserving Codes.md
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
ZOJ完全解题报告,喜欢ACM的同学,欢迎下载
zoj 3590 -3+1.md
Problem Arrangement zoj 3777
ZOJ题目答案源码
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
zoj1027解题指南和代码,还不错,是学校培训给的。