算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

    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 西月弦 阅读(595) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理