首页 > 其他分享 >POJ 1222(Gauss消元xor版)

POJ 1222(Gauss消元xor版)

时间:2022-10-25 11:02:08浏览次数:90  
标签:11 xor cout int return POJ 消元 include


EXTENDED LIGHTS OUT



Description



Lights Out就是下图的游戏,给你一个5*6的矩阵. 


POJ 1222(Gauss消元xor版)_数据


你的目标是把灯全关上. 



POJ 1222(Gauss消元xor版)_数据_02



0表示关,1表示开.


Input


第一行为数据组数T.


对于每组数据,输入1个5*6的矩阵.


Output


对于每组数据,输出一行 "PUZZLE #m".接下来为还原矩阵.


Sample Input


20 1 1 0 1 01 0 0 1 1 10 0 1 0 0 11 0 0 1 0 10 1 1 1 0 00 0 1 0 1 01 0 1 0 1 10 0 1 0 1 11 0 1 1 0 00 1 0 1 0 0


Sample Output


PUZZLE #11 0 1 0 0 11 1 0 1 0 10 0 1 0 1 11 0 0 1 0 00 1 0 0 0 0PUZZLE #21 0 0 1 1 11 1 0 0 0 00 0 0 1 0 01 1 0 1 0 11 0 1 1 0 1


Source


​Greater New York 2002​

Time Limit: 1000MS

 

Memory Limit: 10000K

Total Submissions: 5182

 

Accepted: 3403

就是Gauss消元的xor版本.

显然若 a1 xor a2 xor a3..=an

             b1 xor b2 xor b3..=bn

        则 (a1 xor b1) xor (a2 xor b2)..=an xor an

满足消元性质


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<functional>
using namespace std;
const int n=5,m=6;
bool inside(int x){return (x>=0)&&(x<31);}
struct E
{
int a[31];
int& operator[](int p){static int t;if (inside(p)) return a[p]; else return t;}
friend E operator^(E a,E b)
{
for (int i=0;i<31;i++) a[i]^=b[i];
return a;
}
};
struct M
{
E a[30];
E& operator[](int p){return a[p];}
M()
{
// memset(a,sizeof(a),0);
for (int i=0;i<30;i++)
for (int j=0;j<31;j++) a[i][j]=0;
for(int i=0;i<n*m;i++)
{
a[i][i]=a[i][i+6]=a[i][i-6]=1;
if (i%6) a[i][i-1]=1;
if (i%6<5) a[i][i+1]=1;

}
}
void gauss()
{
int i=0,j=0,n=30,m=31;
while (i<n&&j<m)
{
// print();
int maxi=i;
for(int k=i+1;k<n;k++) if (a[k][j]>a[maxi][j]) maxi=k;
if (a[maxi][j]!=0)
{
swap(a[maxi],a[i]);
for(int k=i+1;k<n;k++)
if (a[k][j]!=0) a[k]=a[k]^a[i];
}
i++;j++;
}
for(int i=28;i>=0;i--)
{
for(int j=i+1;j<30;j++) if (a[i][j]) {a[i][j]=0;a[i][30]^=a[j][30]; }
}
for (int i=0;i<30;i++)
{
cout<<a[i][30];
if (i%6==5) cout<<endl; else cout<<' ';
}
}
void print()
{
for (int i=0;i<30;i++)
{
for (int j=0;j<31;j++) cout<<a[i][j]<<' ';
cout<<endl;
}
cout<<"--------------------------------------------------\n";
system("pause");
}


}EM;
int main()
{
// freopen("poj1222.in","r",stdin);
int tt;
cin>>tt;
for(int t=1;t<=tt;t++)
{
EM=M();
for(int i=0;i<n*m;i++) cin>>EM[i][30];
cout<<"PUZZLE #"<<t<<endl;
EM.gauss();


}
return 0;
}





标签:11,xor,cout,int,return,POJ,消元,include
From: https://blog.51cto.com/u_15724837/5794159

相关文章

  • POJ 2398(二分点集)
    DefaultToyStorageDescription在长方形(x1,y1)(x2,y2)中有n块板(保证与上下边相交),和m个点。现给出板和点的位置,求拥有相同点数的区域数、  Inpu......
  • POJ 2318(点集二分)
    DefaultTOYSDescription在长方形(x1,y1)(x2,y2)中有n块板(保证与上下边相交),和m个点。现给出板和点的位置,求各区域点数、  Input......
  • BZOJ 3503([Cqoi2014]和谐矩阵-gauss消元)
    Description我们称一个由0和1组成的矩阵是和谐的,当且仅当每个元素都有偶数个相邻的1。一个元素相邻的元素包括它本身,及他上下左右的4个元素(如果存在)。给定矩阵的行数和......
  • POJ 1825/2279(Young/Mr. Young's Picture Permutations-杨氏矩阵和钩子公式)
    给出一个n行的矩阵,每一行有a[i]个数,总共有sum个数,要求每一个位置的数必须比上面的数和左面的数大,求总方案数.杨氏矩阵又叫杨氏图表,它是这样一个矩阵,满足条件:(1)如果格子......
  • ARC139F Many Xor Optimization Problems
    题意:给定\(n,m\),求\(n\)个\([0,2^m)\)的数的最大异或和的和。瞎扯:考虑线性基,考虑消元后的,显然唯一,最大异或和为基内所有数的异或和。考虑大小为\(k\)的基方案数为......
  • 【luogu AGC034F】RNG and XOR(FWT)
    RNGandXOR题目链接:luoguAGC034F题目大意给你一个长度为2^n的数组A。一开始有一个\(0\)数,然后每次你随机给它异或上0~2^n-1中的数,随机到\(i\)的概率跟Ai+1......
  • POJ 1201 Intervals 差分约束
    ​​http://poj.org/problem?id=1201​​TLE了很久,因为用了cin.....思路和其他差分约束差不多,​​http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html​​......
  • DFS练习: POJ1010 POJ1011 POJ1020 POJ1321 POJ1416 POJ1724
    POJ1010packagepoj1010;importjava.util.Arrays;importjava.util.Scanner;/***@Authorjinjun99*@DateCreatedin2022/10/418:11*@Description*@S......
  • DFS练习: POJ2362 POJ2676 POJ2698 POJ3083 POJ3411
    POJ2362packagepoj2362;importjava.util.Scanner;/***@Authorjinjun99*@DateCreatedin2022/10/513:22*@Description*用到了定序剪枝,遍历正方形的......
  • POJ 1389. Area of Simple Polygons 题解
    关于扫描线的介绍可以去看OIWiki。但那上面的参考代码并不好,下面给出了带注释的POJ1389题代码。/**Title:AreaofSimplePolygons*Source:POJ*URL:htt......