[POJ 1222] EXTENDED LIGHTS OUT【高斯消元法】
Problem:
Time Limit: 1000MS | Memory Limit: 10000K |
Description


1. It does not matter what order the buttons are pressed.
2. If a button is pressed a second time, it exactly cancels the effect of the first press, so no button ever need be pressed more than once.
3. As illustrated in the second diagram, all the lights in the first row may be turned off, by pressing the corresponding buttons in the second row. By repeating this process in each row, all the lights in the first
four rows may be turned out. Similarly, by pressing buttons in columns 2, 3 ?, all lights in the first 5 columns may be turned off.
Write a program to solve the puzzle.
Input
Output
Sample Input
2 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 1 0 0
Sample Output
PUZZLE #1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 PUZZLE #2 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1
Source
Solution:
# 今天晚上开始放寒假啦啦啦啦啦啦啦~~~ #
本题可以巧妙地构造异或方程组,采用高斯消元法求解。
我们可以将 5 × 6 = 30 个开关作为未知数 x1 ~ x30。
由于同一个开关按两下等于没按,我们不妨假设 xi 的取值只能为 0 或 1。
我们可以将某盏灯的初始状态表示为对其有影响的开关按下情况的异或值,构造出 30 个方程。
只需要存该异或方程组的增广矩阵,跑一遍高斯消元即可求出一组解。
Code: O(Tn3) [356K, 0MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int T, pz[10][10]; int mat[35][35], ans[35]; inline void Gauss_xor(){ for(register int i = 1; i <= 30; i++){ int major; for(major = i; major <= 30; major++) if(mat[major][i]) break; for(register int j = i; j <= 31; j++) swap(mat[major][j], mat[i][j]); for(register int j = i + 1; j <= 30; j++) if(mat[j][i]) for(register int k = i; k <= 31; k++) mat[j][k] ^= mat[i][k]; } for(register int i = 30; i >= 1; i--){ ans[i] = mat[i][31]; for(register int j = i + 1; j <= 30; j++) if(mat[i][j]) ans[i] ^= ans[j]; } } int main(){ scanf("%d", &T); for(register int curT = 1; curT <= T; curT++){ for(register int i = 1; i <= 5; i++) for(register int j = 1; j <= 6; j++) scanf("%d", &pz[i][j]); memset(mat, 0, sizeof(mat)); for(register int i = 1; i <= 5; i++) for(register int j = 1; j <= 6; j++){ int sub = (i - 1) * 6 + j; mat[sub][sub] = 1; if(i > 1) mat[sub][sub - 6] = 1; if(i < 5) mat[sub][sub + 6] = 1; if(j > 1) mat[sub][sub - 1] = 1; if(j < 6) mat[sub][sub + 1] = 1; mat[sub][31] = pz[i][j]; } Gauss_xor(); printf("PUZZLE #%d\n", curT); for(register int i = 1; i <= 5; i++){ for(register int j = 1; j <= 6; j++){ if(j > 1) putchar(' '); printf("%d", ans[(i - 1) * 6 + j]); } putchar('\n'); } } return 0; }
发表评论