本文共 2702 字，大约阅读时间需要 9 分钟。
【题目链接】
【题目大意】
假设已经知道一个数组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？
【分析】
这题其实就是 的加强版。
poj3678每个数字只能选择0或者1，相当与一个二进制只有1位的整数。
而这题每个数字的范围是0 ≤ b[i][j] ≤ 2 ^ 31 - 1， 相当于是二进制有31位的整数，那么只要枚举二进制位，分别对每个二进制为进行2-SAT判断即可！
【代码】
#include #include #include 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 >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
转载地址：http://bpzni.baihongyu.com/