|
/*================================================================================================*\
| Gauss消元算法求解開關(guān)燈問題
\*================================================================================================*/
開關(guān)問題：有N個相同的開關(guān)，每個開關(guān)都與某些開關(guān)有著聯(lián)系，每當(dāng)你打開或者關(guān)閉某個開關(guān)的時候，其他的與
此開關(guān)相關(guān)聯(lián)的開關(guān)也會相應(yīng)地發(fā)生變化，即這些相聯(lián)系的開關(guān)的狀態(tài)如果原來為開就變?yōu)殛P(guān)，如果為關(guān)就變?yōu)殚_。
對于這類問題，巧妙的運(yùn)用位運(yùn)算和gauss算法可以高效的解決。
----------------------------------------------------------------------------------------
開燈問題告訴N(N<=63)盞燈和M(M<=N)個開關(guān),每個開關(guān)可以控制K(K<=N)盞燈，給定N盞燈的初始狀態(tài)S和
要求通過開關(guān)控制得到的目標(biāo)狀態(tài)E，求可以達(dá)到目標(biāo)狀態(tài)的方案數(shù)。
----------------------------------------------------------------------------------------
簡單分析：對于每個開關(guān)，有按和不按兩種選擇（記為0/1）; 對于每盞燈有變和不變兩種情況（0/1）,如果初態(tài)和終態(tài)不一樣
，那么這盞燈是一定要變化的。由此我們就可以得到一個0/1的矩陣：讓N盞燈燈作為列向量，開關(guān)作為橫向量，把每盞燈是否變化
作為第M列（由0開始）這樣就得到一個N*(M+1)的矩陣,該矩陣有如下性質(zhì)：
1. 如果N = M ，那么矩陣為增廣矩陣。
2. 該矩陣相當(dāng)于方程組A * X = B,因此可以求其解。
1. 若方程組有唯一解，那么，N = M (逆命題：如果M = N ,那么方程組有唯一解 不成立)
2. 若方程組無實數(shù)解，那么，該方程不可以化成嚴(yán)格上三角形式（具體的證明見相關(guān)資料，這里不再證明）
3. 若方程組有多接，即存在自由變元，因為每個自由變元可以取0/1兩種情況，那么總共有2^m(m為變元數(shù))解
(也就是不影響最后結(jié)果的自由開關(guān)的數(shù)目）
下面是經(jīng)過驗證的代碼：
int getRow(int p, int q, int &row) {
for (int i = p; i < n; i++)
if (!zero(a[i][q])) return a[row=i][q];
return row=0;
}
void swapRow(int p, int row, int q) {
for (int k = q; k <= m; k++)
swap(a[p][k], a[row][k]);
}
i64 gauss() {
int i = -1, j = -1, k, p, q, ret, row;
while(++i < n && ++j < m) {
ret = getRow(i, j, row);
if (zero(ret)) { i--; continue;}
if (row != i) swapRow(i, row, j);
for (p = i+1; p < n; p++) if (a[p][j])
for (q = j; q <= m; q++)
a[p][q] ^= a[i][q];
}
for (k = i; k < n; k++) if(a[k][m]) return -1;
return (i64)1 << (m-i);
} //link: hdu3364 http://acm.hdu.edu.cn/showproblem.php?pid=3364
----------------------------------------------------------------------------------------
開關(guān)問題：有N個相同的開關(guān)，每個開關(guān)都與某些開關(guān)有著聯(lián)系，每當(dāng)你打開或者關(guān)閉某個開關(guān)的時候，
其他的與此開關(guān)相關(guān)聯(lián)的開關(guān)也會相應(yīng)地發(fā)生變化，即這些相聯(lián)系的開關(guān)的狀態(tài)如果原來為開就變?yōu)殛P(guān)，
果為關(guān)就變?yōu)殚_。求： 1. 方案數(shù)（自由變元的數(shù)目） 2. 給定一個最少的開關(guān)方案
----------------------------------------------------------------------------------------
這類問題是上面問題的一種簡化：
對于問題一、可以直接套用上面的公式（N=M）
對于問題二、如果構(gòu)造得到的方程組只有一個解，那么問題解決，這里主要討論一下多解，
存在自由變元的情況。如果存在自由變元，我們就要枚舉每個自由變元（0/1）然后比較選擇最小。
枚舉時間復(fù)雜度為2^m(m為自由變元的個數(shù))
下面是簡單的枚舉自由元的算法。
int gans(int a[][maxn+1]) {
int i, j, ret = a[n-1][n];
for (i = n-2; i >= 0; i--) {
for (j = i+1; j < n; j++)
a[i][n] ^= a[i][j] && a[j][n];
ret += b[i][n];
}
return ret;
}
void dfs(int p, int k) {
if (p == k) {
memcpy(b, a, sizeof(b));
int ret = gans(b);
if (ret < ans) ans = ret;
return;
}
a[p][n] = 1; dfs(p-1, k);
a[p][n] = 0; dfs(p-1, k);
}
int gauss() { //……代碼見上（n=m）……//
dfs(n-1, i-1);
return ans;
}
Link: pku_1222 http://162.105.81.212/JudgeOnline/problem?id=1222
pku_1681 http://162.105.81.212/JudgeOnline/problem?id=1681
pku_1753 http://162.105.81.212/JudgeOnline/problem?id=1753
pku_1830 http://162.105.81.212/JudgeOnline/problem?id=1830
pku_3185 http://162.105.81.212/JudgeOnline/problem?id=3185
hdu_2285 http://acm.hdu.edu.cn/showproblem.php?pid=2285
|