題目描述：
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
西月弦 閱讀(611)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告