題意：
給定5*6 的燈的目標狀態（開始全暗），每按下一個燈就會把這個燈及這燈相鄰的4個燈狀態改變。
輸出一個按燈的方案使得由全暗變成輸入的狀態。
思路：
每盞燈都作為一個變量，
a1&x1 + a2&x2 + a3&x3 ··· a30&x30 = input[1][1]
能影響到某盞燈的系數是1，其他是0
實際上是
x4 + x5 + x3 + x10 = input[4]
但其他不相關的變量也要填充進方程，所以前面系數設置為0。
共5*6個變量，系數矩陣30*30,增廣矩陣 30*31.
回代時注意是系數和變量之間的符號是&
#include#include #include #include #include template inline bool rd(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if (x>9) pt(x / 10); putchar(x % 10 + '0'); } const double eps = 1e-8; typedef long long ll; using namespace std; int step[5][2], id[5][6]; int A[30][31], init[30][31]; int ans[30]; int Guass(int mat[][31], int row, int col){ int r, c, i, j; for (r = c = 0; r < row && c < col; r++, c++){ for (i = r; i < row; i++)if (mat[i][c]>0)break; if (i == row){ r--; continue; } if (i != r) for (j = c; j <= col; j++) swap(mat[i][j], mat[r][j]); for (i = r + 1; i < row; i++) if(mat[i][c]>0) for (j = c; j <= col; j++) mat[i][j] ^= mat[r][j]; } for (i = r; i < row; i++) if (mat[i][col] > 0)return 0; for (i = r - 1; i >= 0; i--) { ans[i] = mat[i][col]; for (j = i + 1; j < col; j++) ans[i] ^= (mat[i][j] && ans[j]); } return 1; } int main() { step[0][0] = 0; step[0][1] = 0; step[1][0] = 1; step[1][1] = 0; step[2][0] = 0; step[2][1] = 1; step[3][0] = -1; step[3][1] = 0; step[4][0] = 0; step[4][1] = -1; int now = 0; for (int i = 0; i < 5; i++)for (int j = 0; j < 6; j++)id[i][j] = now++; memset(init, 0, sizeof init); for (int i = 0; i < 5; i++)for (int j = 0; j < 6; j++){ for (int k = 0; k < 5; k++) { int x = i + step[k][0], y = j + step[k][1]; if (0 <= x&&x<5 && 0 <= y&&y<6)init[id[i][j]][id[x][y]] = 1; } } int T, Cas = 1; rd(T); while (T-->0){ for (int i = 0; i < 30; i++)for (int j = 0; j < 30; j++)A[i][j] = init[i][j]; for (int i = 0; i < 5; i++) for (int j = 0; j < 6; j++) rd(A[id[i][j]][now]); Guass(A, 30, 30); printf(PUZZLE #%d , Cas++); for (int i = 0, tmp = 0; i < 5; i++) for (int j = 0; j < 6; j++){ pt(ans[tmp++]); if (j == 5)puts(); else putchar(' '); } } return 0; }
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Queue;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
public class Main {
int[][] step = new int[5][2], id = new int[N][N];
int[][] A = new int[N][N], init = new int[N][N];
int[] ans = new int[N];
int Guass(int[][] mat, int row, int col){
int r, c, i, j;
for (r = c = 0; r < row && c < col; r++, c++){
for (i = r; i < row; i++)if (mat[i][c]>0)break;
if (i == row){ r--; continue; }
if (i != r)
for (j = c; j <= col; j++)
{int tmp = mat[i][j]; mat[i][j] = mat[r][j]; mat[r][j] = tmp;}
for (i = r + 1; i < row; i++)
if(mat[i][c]>0)
for (j = c; j <= col; j++) mat[i][j] ^= mat[r][j];
}
for (i = r; i < row; i++) if (mat[i][col] > 0)return 0;
for (i = r - 1; i >= 0; i--)
{
ans[i] = mat[i][col];
for (j = i + 1; j < col; j++)
ans[i] ^= (mat[i][j] & ans[j]);
}
return 1;
}
void work() throws Exception {
step[0][0] = 0; step[0][1] = 0;
step[1][0] = 1; step[1][1] = 0;
step[2][0] = 0; step[2][1] = 1;
step[3][0] = -1; step[3][1] = 0;
step[4][0] = 0; step[4][1] = -1;
int now = 0;
for(int i = 0; i < 5; i++)for(int j = 0; j < 6; j++)id[i][j] = now++;
for(int i = 0; i < N; i++)for(int j = 0; j < N; j++)init[i][j] = 0;
for(int i = 0; i < 5; i++)for(int j = 0; j < 6; j++){
for(int k = 0; k < 5; k++)
{
int x = i+step[k][0], y = j+step[k][1];
if(0<=x&&x<5&&0<=y&&y<6)init[id[i][j]][id[x][y]] = 1;
}
}
int T = Int(), Cas = 1;
while (T-->0){
for(int i = 0; i < N; i++)for(int j = 0; j < N; j++)A[i][j] = init[i][j];
for(int i = 0; i < 5; i++)
for(int j = 0; j < 6; j++)
A[id[i][j]][now] = Int();
Guass(A, now, now);
out.println(PUZZLE # + (Cas++));
for(int i = 0, tmp = 0; i < 5; i++)
for(int j = 0; j < 6; j++){
out.print(ans[tmp++]);
if(j==5)out.println(); else out.print( );
}
}
}
public static void main(String[] args) throws Exception {
Main wo = new Main();
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
// in = new BufferedReader(new InputStreamReader(new FileInputStream(new File(input.txt))));
// out = new PrintWriter(new File(output.txt));
wo.work();
out.close();
}
static int N = 56;
static int M = N * 2;
DecimalFormat df = new DecimalFormat(0.0000);
static int inf = (int) 1e9;
static long inf64 = (long) 1e18;
static double eps = 1e-8;
static double Pi = Math.PI;
static int mod = (int) 1e9 + 7;
private String Next() throws Exception {
while (str == null || !str.hasMoreElements())
str = new StringTokenizer(in.readLine());
return str.nextToken();
}
private int Int() throws Exception {
return Integer.parseInt(Next());
}
private long Long() throws Exception {
return Long.parseLong(Next());
}
private double Double() throws Exception {
return Double.parseDouble(Next());
}
StringTokenizer str;
static Scanner cin = new Scanner(System.in);
static BufferedReader in;
static PrintWriter out;
class Edge{
int from, to, dis, nex;
Edge(){}
Edge(int from, int to, int dis, int nex)
{
this.from = from; this.to = to; this.dis = dis; this.nex = nex;
}
}
Edge[] edge = new Edge[M<<1];
int[] head = new int[N]; int edgenum;
void init_edge(){ for(int i = 0; i < N; i++)head[i] = -1; edgenum = 0;}
void add(int u, int v, int dis){
edge[edgenum] = new Edge(u, v, dis, head[u]);
head[u] = edgenum++;
}
/*
*/
int upper_bound(int[] A, int l, int r, int val) {// upper_bound(A+l,A+r,val)-A;
int pos = r;
r--;
while (l <= r) {
int mid = (l + r) >> 1;
if (A[mid] <= val) {
l = mid + 1;
} else {
pos = mid;
r = mid - 1;
}
}
return pos;
}
int lower_bound(int[] A, int l, int r, int val) {// upper_bound(A+l,A+r,val)-A;
int pos = r;
r--;
while (l <= r) {
int mid = (l + r) >> 1;
if (A[mid] < val) {
l = mid + 1;
} else {
pos = mid;
r = mid - 1;
}
}
return pos;
}
int Pow(int x, int y) {
int ans = 1;
while (y > 0) {
if ((y & 1) > 0)
ans *= x;
y >>= 1;
x = x * x;
}
return ans;
}
double Pow(double x, int y) {
double ans = 1;
while (y > 0) {
if ((y & 1) > 0)
ans *= x;
y >>= 1;
x = x * x;
}
return ans;
}
int Pow_Mod(int x, int y, int mod) {
int ans = 1;
while (y > 0) {
if ((y & 1) > 0)
ans *= x;
ans %= mod;
y >>= 1;
x = x * x;
x %= mod;
}
return ans;
}
long Pow(long x, long y) {
long ans = 1;
while (y > 0) {
if ((y & 1) > 0)
ans *= x;
y >>= 1;
x = x * x;
}
return ans;
}
long Pow_Mod(long x, long y, long mod) {
long ans = 1;
while (y > 0) {
if ((y & 1) > 0)
ans *= x;
ans %= mod;
y >>= 1;
x = x * x;
x %= mod;
}
return ans;
}
int gcd(int x, int y) {
if (x > y) {
int tmp = x;
x = y;
y = tmp;
}
while (x > 0) {
y %= x;
int tmp = x;
x = y;
y = tmp;
}
return y;
}
int max(int x, int y) {
return x > y ? x : y;
}
int min(int x, int y) {
return x < y ? x : y;
}
double max(double x, double y) {
return x > y ? x : y;
}
double min(double x, double y) {
return x < y ? x : y;
}
long max(long x, long y) {
return x > y ? x : y;
}
long min(long x, long y) {
return x < y ? x : y;
}
int abs(int x) {
return x > 0 ? x : -x;
}
double abs(double x) {
return x > 0 ? x : -x;
}
long abs(long x) {
return x > 0 ? x : -x;
}
boolean zero(double x) {
return abs(x) < eps;
}
double sin(double x) {
return Math.sin(x);
}
double cos(double x) {
return Math.cos(x);
}
double tan(double x) {
return Math.tan(x);
}
double sqrt(double x) {
return Math.sqrt(x);
}
double fabs(double x){return x>0?x:-x;}
}
