首页 > 代码库 > HDU 4421 Bit Magic(奇葩式解法)
HDU 4421 Bit Magic(奇葩式解法)
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=4421
题目大意：
给了你一段代码， 用一个数组的数 对其进行那段代码的处理，是可以得到一个矩阵
让你判断这个矩阵能否由一个数组转化而来。
思路： 既然每组数据可以得到，那么他肯定能消去。 我们用一个数组P[i][j] 保存 a[i]^a[j] 的值
a[i]^a[j] 我们可用 P[i][j] = P[i][j-1]^a[j-1]^a[j]
这样我们就可以找出所有 P[i][j] = a[i]^a[j] 的值
然后自己推出了个公式
(a^b)&(a&b) == 0
(a^b)&(~(a|b)) == 0
(a^b)^(a^b) == 0
然后 用所有找出来的值进行计算 当所有值 为 0 则 满足
#include<stdio.h>#include<stdlib.h>#include<math.h>#include<queue>#include<string.h>#include<iostream>#include<vector>using namespace std;#define maxn 560__int64 map[maxn][maxn];__int64 P[maxn][maxn], n;bool Judge(){ __int64 i, j, sum; for(i = 0; i<n; i++) { if(map[i][i]) return 0; for(j = 0; j<i; j++) { sum = map[i][j] ^ map[j][i]; if(sum) return 0; } } memset(P,0,sizeof(P)); for(i = 0; i < n; i++) { P[i][i] = 0; for(j=i+1; j <= n; j++) P[i][j] = P[i][j-1]^map[j-1][j]; } for(i = 0; i<n; i++) { for(j = i+1; j<n; j++) { if(i%2 == 0 && j%2 == 0)//(a^b)&(a&b) sum = P[i][j]&(map[i][j]); else if(i%2 == 1 && j%2 == 1)//(a^b)&(~(a|b)) sum = P[i][j]&(~map[i][j]); else//(a^b)^(a^b) sum = P[i][j]^map[i][j]; if(sum) return 0; } } return 1;}int main(){ int i, j; while(scanf("%I64d",&n) != EOF) { for(i = 0; i<n; i++) { for(j = 0; j<n; j++) scanf("%I64d",&map[i][j]); } if(Judge()) printf("YES\n"); else printf("NO\n"); } return 0;}
HDU 4421 Bit Magic(奇葩式解法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。