Part1.題型基本條件及思路

一般地說，當一個動作能導致兩個即以上的變化（例如摁開關能打開燈或關閉燈），就稱之為開關燈問題。
設計數學模型：容斥原理

----------

Part2.專題疑難突破~~（有內味了）~~

兩個思路：

>1.有規律時尋找規律
>2.無規律時進行模擬

----------

通式：令i為按開關的次數,$0$為關著的燈，$1$為開著的燈
1. 若此燈初始狀態為0，i%2==1時此燈被打開，i%2==0時此燈仍然關閉
2. 若此燈初始狀態為1，i%2==1時此燈被關閉，i%2==0時此燈仍然為開

----------

#Part3.一些例子

>eg1（尋找規律）:
?

題目描述
假設有 NN 盞燈（NN 為不大于 5000 的正整數），從 1 到 N 按順序依次編號，初始時全部處于開啟狀態；第一個人（1 號）將燈全部關閉，第二個人（2 號）將編號為 2 的倍數的燈打開，第三個人（3 號）將編號為 3 的倍數的燈做相反處理（即，將打開的燈關閉，將關閉的燈打開）。依照編號遞增順序，以后的人都和 3 號一樣，將凡是自己編號倍數的燈做相反處理。問當第 N 個人操作完之后，有哪些燈是關閉著的？

輸入格式
輸入為一行，一個整數 N，為燈的數量。

輸出格式
輸出為一行，按順序輸出關著的燈的編號。編號與編號之間間隔一個空格。

思考過后，發現規律：
只有完全平方數的因數個數為奇數，其余數都是偶數，而按動偶數次下也就相當于沒按了，所以最后還是亮的（因為一開始燈也都是亮的），那么最后關著的燈就是這些編號為完全平方數的燈。
我們只需一個循環輸出 1 到 n 之間的完全平方數，整個代碼時間復雜度只有
?
>代碼實現：
?

#include<iostream> using namespace std; int main(){int n;cin>>n;for(int i=1;i*i<=n;i++)cout<<i*i<<" ";return 0; }

>eg1習題訓練:
?

題目描述
首先所有的燈都是關的，編號為 1 的人走過來，把是 1 的倍數的燈全部打開，編號為 2 的人把是 2 的倍數的燈全部關上，編號為 3 的人又把是 3 的倍數的燈開的關上，關的開起來……直到第 N 個人為止。

給定 N，求 N 輪之后，還有哪幾盞是開著的。

輸入格式
一個數 N，表示燈的個數和操作的輪數。

輸出格式
若干數，表示開著的電燈編號。

看過題目后，不難發現，這和eg1完全一樣，讀者不妨思考過后再往下看

>代碼實現（這不和eg1一樣么）：

#include<iostream> using namespace std; int main() {int n;cin>>n;for(int i=1;i*i<=n;i++)cout<<i*i<<" ";return 0; }

>eg2（模擬）：

題目描述
有一個由按鈕組成的矩陣，其中每行有 6 個按鈕，共 5 行。每個按鈕的位置上有一盞燈。當按下一個按鈕后，該按鈕以及周圍位置(上邊、下邊、左邊、右邊)的燈都會改變一次。即，如果燈原來是點亮的，就會被熄滅；如果燈原來是熄滅的，則會被點亮。在矩陣角上的按鈕改變 3 盞燈的狀態；在矩陣邊上的按鈕改變 4 盞燈的狀態；其他的按鈕改變 5 盞燈的狀態。

?

在上圖中，左邊矩陣中用 X 標記的按鈕表示被按下，右邊的矩陣表示燈狀態的改變。對矩陣中的每盞燈設置一個初始狀態。請你按按鈕，直至每一盞等都熄滅。與一盞燈毗鄰的多個按鈕被按下時，一個操作會抵消另一次操作的結果。在下圖中，第 2 行第 3、5 列的按鈕都被按下，因此第 2 行、第 4 列的燈的狀態就不改變。

?

請你寫一個程序，確定需要按下哪些按鈕，恰好使得所有的燈都熄滅。根據上面的規則，我們知道 1) 第 2 次按下同一個按鈕時，將抵消第 1 次按下時所產生的結果。因此，每個按鈕最多只需要按下一次；

2) 各個按鈕被按下的順序對最終的結果沒有影響；

3) 對第 1 行中每盞點亮的燈，按下第 2 行對應的按鈕，就可以熄滅第 1 行的全部燈。如此重復下去，可以熄滅第 1、2、3、4 行的全部燈。同樣，按下第 1、2、3、4、5 列的按鈕，可以熄滅前 5 列的燈。

輸入格式
5 行組成，每一行包括 6 個數字（ 0 或 1 ）。相鄰兩個數字之間用單個空格隔開。0 表示燈的初始狀態是熄滅的，1 表示燈的初始狀態是點亮的。

?

#include<memory> #include<string> #include<cstring> #include<iostream> using namespace std;int GetBit(char c, int i) { //取c的第i位return ( c >> i ) & 1; }void SetBit(char & c, int i, int v) { //設置c的第i位設為vif ( v ) c |= ( 1 << i);else c &= ~( 1 << i); }void Flip(char & c, int i) { //將c的第i位取反c ^= ( 1 << i); }void OutputResult(int t, char result[]) { //輸出結果for ( int i = 0; i < 5; ++i ) {for ( int j = 0; j < 6; ++j ) {cout << GetBit(result[i], j);if ( j < 5 ) cout << " ";}cout << endl;} }int main() {char oriLights[5]; //最初燈矩陣，一個字節表示一盞燈char lights[5]; //不停變化的燈矩陣char result[5]; //結果開關矩陣char switchs; //某一行的開關狀態int T;//cin >> T;//輸入T表示有T組測試數據T = 1;for ( int t = 1; t <= T; ++ t) {memset(oriLights, 0, sizeof(oriLights));for ( int i = 0; i < 5; i ++ ) { //讀入最初燈狀態for ( int j = 0; j < 6; j ++ ) {int s;cin >> s;SetBit(oriLights[i], j, s);}}for ( int n = 0; n < 64; ++n ) { //遍歷首行開關的64種操作memcpy(lights, oriLights, sizeof(oriLights));switchs = n; //先假定第0行的開關需要的操作方案for ( int i = 0; i < 5; ++i ) {result[i] = switchs; //保存第i行開關的操作方案for ( int j = 0; j < 6; ++j ) { //根據方案修改第i行的燈if ( GetBit(switchs, j)) {//switchs的第j個位等于1表示需要按下第i行第j個按鈕，等于0表示不需要按下該按鈕if ( j > 0) Flip(lights[i], j - 1); //改左燈Flip(lights[i], j); //改開關位置的燈if ( j < 5 ) Flip(lights[i], j + 1); //改右燈}}if ( i < 4 ) lights[i + 1] ^= switchs; //改下一行的燈switchs = lights[i]; //第i+1行開關的操作方案由第i行燈的狀態決定}if ( lights[4] == 0 ) {OutputResult(t, result);break;}}}return 0; }

So that's all~see you~

總結

以上是生活随笔為你收集整理的经典问题总结——开关灯问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。