CH0201費解的開關——二進制列舉

基礎知識

( a * b ) % m = ((a % m) * ( b % m )) % m
( a + b ) % m = ((a % m) + ( b % m )) % m
( a - b ) % m = ((a % m) - ( b % m )) % m

通常我們認爲 0x3f3f3f 來表示無窮大

memsert() 函數：初始化函數，將某一塊記憶體中的內容全部設定爲指定的值，結構體或陣列進行清零操作的一種最快方法 。

#include<string.h>
void *memset(void *s, int ch, size_t n);

memset解釋：將s中當前位置後面的n個位元組用ch替換並返回s

位運算

符號	意義
&	與運算：同爲1，則爲1
|	或運算：有1，則1
~	非運算
^	互斥或運算：不同爲1，相同爲0

練習題

快速冪

求 a 的 b 次方對 p 取模 ， 其中1 <= a , b , c <= 10^9。

#include<iostream> 

using namespace std;

int fun(int a, int b, int p)
{
	int ans = 1;
	
	for(; b; b = b >> 1)
	{
		if( b & 1){
			ans = (long long)(ans * a) % p;
		}
		a =(long long) (a * a) % p;
	}
	return ans;
	
}

int main()
{
	int a,b,p;
	cin>>a>>b>>p;
	cout<<fun(a,b,p);
}

快速乘

求 a * b 對 p 取模 ， 其中1 <= a , b , c <= 10^18。
與快速冪類似

在這裏插入程式碼片#include <iostream>

using namespace std;

int fun(int a, int b, int p)
{
	int ans = 0;
	
	while(b)
	{
		if(b & 1)
		{
			ans = (ans + a) % p; 
		}
		b = b >> 1;
		a = (a << 1) % p;
	}
	
	return ans;
	
}


int main()
{
	int a , b , p;
	cin>>a>>b>>p;
	
	cout<<fun(a,b,p);
}

CH0201 費解的開關

你玩過「拉燈」遊戲嗎？25盞燈排成一個5x5的方形。每一個燈都有一個開關，遊戲者可以改變它的狀態。每一步，遊戲者可以改變某一個燈的狀態。遊戲者改變一個燈的狀態會產生連鎖反應：和這個燈上下左右相鄰的燈也要相應地改變其狀態。

我們用數位「1」表示一盞開着的燈，用數位「0」表示關着的燈。下面 下麪這種狀態

10111
01101
10111
10000
11011

在改變了最左上角的燈的狀態後將變成：

01111
11101
10111
10000
11011

再改變它正中間的燈後狀態將變成：

01111
11001
11001
10100
11011

給定一些遊戲的初始狀態，編寫程式判斷遊戲者是否可能在6步以內使所有的燈都變亮。

輸入：
第一行有一個正整數n，代表數據中共有n個待解決的遊戲初始狀態。
以下若幹行數據分爲n組，每組數據有5行，每行5個字元。每組數據描述了一個遊戲的初始狀態。各組數據間用一個空行分隔。

輸出：
輸出數據一共有n行，每行有一個小於等於6的整數，它表示對於輸入數據中對應的遊戲狀態最少需要幾步才能 纔能使所有燈變亮。
對於某一個遊戲初始狀態，若6步以內無法使所有燈變亮，請輸出「-1」。

樣例輸入：

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

樣例輸出：

3
2
-1

思路：
首先先明確兩個問題：

1.對於一個開關，我們按下的次數以及按它周圍的開關對它所造成的影響，其實就兩種情況，改變狀態或者不變。顯然偶數次就是不變。所以對於每個開關，我們最多按下一次。

2.如果我們確定了第一行中有那幾個開關按下，那第一行的狀態也就確定了。對於第一行還關着的燈，我們只能通過它的下一行的同一列的開關來改變。這樣當我們把第一行的燈全部變亮的時候，第二行的狀態也就確定了。這樣遞推把前四行的燈全部變亮。對於最後一行，如果還有燈關着，那我們就不可能把所有燈開啓。

第一行燈只有5個，那我可以用二進制列舉第一行的所有情況。

程式碼：

#include <iostream>
#include <cstring>
using namespace std;

int a[6];
int aa[6];
char s[6];
int ans;

void dj(int x, int y){
	aa[x] ^= (1 << y);
	if(x != 1) aa[x-1] ^= (1 << y);
	if(x != 5) aa[x+1] ^= (1 << y);
	if(y != 4) aa[x] ^= (1 << (y+1) ) ;
	if(y != 0) aa[x] ^= (1 << (y-1) ); 
}

void bp(int p){
	int k = 0;
	memcpy(aa, a, sizeof(a));
	
	for(int i = 0; i < 5; i++){
		if(!((p >> i) & 1)){
			dj(1,i);
			if(++k >= ans ) return ;
		}
	}
	
	for(int x = 1; x <= 4; x++){
		for(int y = 0; y <= 4; y++){
			if(!((aa[x] >> y) & 1)){
				dj(x+1,y);
				if(++k >= ans) return ;
			}
		}
	}
	if(aa[5] == 31) ans = k;
}

void fun(){
	memset(a, 0, sizeof(a));
	ans = 7;
	for(int i = 1; i < 6; i++){
		cin>>(s+1);
		for(int j = 1; j < 6; j++ ){
			a[i] = (a[i] << 1) + (s[j] - '0');
		}
	}
	for(int p = 0; p < (1 << 5); p++) bp(p);
	
	if(ans == 7) cout<<"-1"<<endl;
	else cout<<ans<<endl;
} 

int main(){
	int n;
	cin>>n;
	while(n--) fun();
	return 0;
}