题目描述：
N(N<100)个带开关的灯泡排成一行，每个灯泡的开关可以转换自己，左边连续D个和右边连续D个灯泡的开关状态。现在给你每个灯泡的初始状态{Ai}，请问最少开关多少次能把所有的灯熄灭？
吐槽：
1.上来就往DP的思路想是什么水平...
2.本blog的第一个数学题目... mark~
思路分析：
首先在最后的解中，显然每个开关只能按一次。所以貌似可以状压DP？，但是由于开关可以控制后面的灯泡，所以100*2^30果断GG...
于是发现这个可以列出方程组，Xi表示开关i是否按下，Mij表示开关i是否可以控制灯泡j：
(M00*X0) XOR (M10*X1) XOR ... XOR (M0n-1*Xn-1) = A0
(M10*X0) XOR (M11*X1) XOR ... XOR (M1n-1*Xn-1) = A1
. . ... . . .
. . ... . . .
. . ... . . .
(Mj0*X0) XOR (Mj1*X1) XOR ... XOR (Mjn-1*Xn-1) = Aj
这个异或方程组怎么解呢？ 其实 A XOR B = (A + B) mod 2
可以看成是同余方程组，那么经典的解法就是
高斯-约当消元法了...
其实算的时候还是用XOR操作方便一些...
这个方程组的解有三种可能：
1. 无解： 判断消元后的系数矩阵是否存在 0 0 ... 0 1的情况，如果有输出impossible，否则一定有解。
2. 唯一解： 消去的过程中没有自由变量，即对消去每一列的过程都有主元可以选择，那么直接向前迭代求出唯一解~
3. 无穷解： 存在自由变量，这个时候需要对自由变量进行枚举，这个复杂度是指数级的，如果自由变量很少的话是ok的。那么如何估算自由变量呢？
矩阵的秩决定了自由变量的个数，不难发现这个矩阵是非常有特点的，从左到右画了一个很粗的斜线 :P ，如果n满足(n>2*D+1)的话，这个矩阵很明显是满秩的。
否则的话自由变量会在两行完全相同的情况下出现，显然这种情况下前n列都是1，这样的行最多会出现D+1次。枚举次数最多是2^(D+1)，这样就可以算了~
2和3是可以放在一起写的哦~
1 #include<iostream>
2 #include<cstdio>
3 #include<cassert>
4 using namespace std;
5 #define re(i,n) for(int i =0; i< n; i++)
6 #define re2(i,n) for(int i =0; i<= n; i++)
7 const int M = 105;
8 int gauss[M][M];
9 int hash[M] , solution[M], P[M], val[M];
10 template <typename T> inline
void chkmin(T &a,
const T b) {
if(a > b) a = b;}
11 int main(){
12 int t;
13 cin >> t;
14 while(t --){
15 int n,d;
16 scanf("%d%d",&n,&d);
17 re(i,n) {
18 scanf("%d",&gauss[i][n]);
19 }
20 int N = 0;
21 re(i,n) {
22 re(j,n) gauss[i][j] = 0;
23 int l = max(0, i - d);
24 int r = min(n-1, i + d);
25 for(
int j = l; j<= r; j++)
26 gauss[i][j] = 1;
27 }
28 re(i,n) P[i] = -1 , hash[i] = 0;
29 // re(i,n) {re2(j,n) cout << gauss[i][j] << " "; cout<<endl;} cout<<endl;
30 re(i,n) {
31 bool flag = 0;
32 re(j,n)
if(!hash[j] && gauss[j][i]){
33 P[i] = j;
34 flag = hash[j] = 1;
35 re(k,n)
if(!hash[k] && gauss[k][i])
36 for(
int x = i; x <= n; x++)
37 gauss[k][x] ^= gauss[j][x];
38 break;
39 }
40 if(!flag) val[N++] = i;
41 }
42 // re(i,n) {re2(j,n) cout << gauss[i][j] << " "; cout<<endl;} cout<<endl;
43 assert(N <=16);
44 bool s = 0;
int mask = 1 << N;
45 re(i,n) {
46 bool flag = 0;
47 re(j,n)
if(gauss[i][j]) flag = 1;
48 if(!flag && gauss[i][n]) { s = 1;
break; }
49 }
50 if(s) { puts("impossible");
continue; }
51 int ans = M;
52 re(i, mask){
53 int sum =0;
54 re(j,N) solution[ val[j] ] = (i & (1 << j)) != 0;
55 for(
int j =n-1 ; j >= 0; j--){
56 if(P[j] == -1)
continue;
57 assert(gauss[P[j]][j]);
58 solution[j] = gauss[P[j]][n];
59 for(
int k = n-1; k>j; k--)
60 solution[j] ^= solution[k] & gauss[P[j]][k];
61 }
62 re(j,n) sum += solution[j]!=0;
63 chkmin(ans,sum);
64 }
65 cout<<ans<<endl;
66 }
67 }
68 posted on 2012-04-27 18:26
西月弦 阅读(601)
评论(0) 编辑 收藏 引用 所属分类:
解题报告