Summary of "reversal" problem in challenge Programming Competition

《 Challenge Programming Competition 》 And “ reverse ” The problem summary

Mengxin is writing a summary again
“ reverse ” The problem is 《 Challenge Programming Competition 》P150 Left and right ~

Refuse to ！ most ！ search ！ Cable ！

This kind of problem has the following characteristics ：
1. Mostly concentrated in one dimension / In two dimensions , The range of two-dimensional data is generally very small （ After all, you need some enumeration ）; It's for an interval / Invert several adjacent grids ;
2. Generally use search （dfs/bfs） It cannot be completed within the specified time （ Unless the data is too small ）;
3. Each grid has two states （ just / back ）, The reverse order of intervals has no effect on the final result ;
4. It is more than to reverse a lattice more than twice , So you just need to %2 You can know the result of inversion .

To borrow a word ：
“ The reverse method is a little like the ruler method , They all limit a range , Move forward , After the tail moves , We need to reduce the influence of the tail .”

Here are some classic topics ：
One dimensional inversion ：
Face The Right Way POJ - 3276
The Water Bowls POJ - 3185
Two dimensional inversion ：
Fliptile POJ - 3279
The Pilots Brothers’ refrigerator POJ - 2965
Flip Game POJ - 1753
EXTENDED LIGHTS OUT POJ - 1222

A. Face The Right Way POJ - 3276

tips: We can argue that , this “ Reverse continuous K Head ox ” Only according to The serial number is incremented The order of （ such as k = 3 , reverse 7 6 8 Three consecutive cows , It can be considered as 6 No. is the starting point , Continuous inversion 6 7 8 Three cows , The order has no effect ）. namely ： The problem is transformed into finding the set of intervals that need to be reversed .

For the end Insufficient k Head ox , To judge directly , No need to reverse （ Have not enough k A cow ）.

#include<cstdio>
#include<cstring>

const int maxn = 5005;
int book[maxn],flip[maxn],n,k,m,ans,reck;
char c;

int solve(int k){
    
	memset(flip,0,sizeof(flip));
	int sum = 0, res = 0;			//res Used to count the answers （ Number of reversals ）
	for(int i = 1; i <= n - k + 1; ++i){
    
		if((book[i] + sum) % 2 == 0)	flip[i] = 0;
		else	sum++, res++, flip[i] = 1;
		if(i - k >= 0)	sum -= flip[i - k + 1];	// Prepare for the next position 
	}
	for(int i = n - k + 2; i <= n; ++i){
    		// Direct judgment 
		if((book[i] + sum) % 2 != 0)	return -1;
		if(i - k >= 0)	sum -= flip[i - k + 1];
	}
	return res;
}

int main(){
    
	scanf("%d",&n); ans = 1e9;
	for(int i = 1; i <= n; ++i){
    
		getchar();
		scanf("%c",&c);
		book[i] = (c == 'B' ? 1 : 0);
	}
	for(k = 1; k <= n; ++k){
    
		int tmp = solve(k); 
		if(tmp != -1 && ans > tmp){
    
			ans = tmp;
			reck = k;
		}
	}
		
	printf("%d %d\n",reck,ans);
	return 0;
} 

B.The Water Bowls POJ - 3185

tips： Similar to the previous question , It just limits each time you reverse yourself and your neighbors 2 Lattice . You can do it directly , Don't use it like the last question sum Record .【 The only difference is , If it is both ends Lattice of , Can only reverse 2 individual ; The middle grid can be reversed 3 individual ,k Not a fixed value 】
Pay attention to the classified discussion ： The first lattice does not reverse / The first lattice is reversed .
We think , Start at the far left , When a grid is fixed , Only the latter grid can change him （ Because the one in front of him has been settled ）, Therefore, according to the current state of the grid Sole determination The number of inversions of the next lattice .

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int book[25],flip[25],minn,tmp[25];

void solve1(){
    		// The first lattice does not reverse 
	int cnt = 0;
	memcpy(tmp, book, sizeof(book));
	memset(flip, 0,sizeof(flip));
	for(int i = 2; i <= 20; ++i){
    
		if((flip[i - 1] + tmp[i - 1]) % 2 == 0)	continue;	// Whether the current grid is reversed , Depends on the state of the previous grid 
		else	flip[i]++, tmp[i + 1]++, cnt++;	// The current grid is reversed , Next grid   The state will also be affected , use tmp++ Express . The reason to use memcpy, Do not want to change the original data 
	}
	if((flip[20] + tmp[20]) % 2 == 0)
		minn = min(minn, cnt);
}

void solve2(){
    		// The first lattice is reversed 
	int cnt = 0;
	memset(flip, 0,sizeof(flip));
	memcpy(tmp, book, sizeof(book));
	flip[1] = 1, tmp[2]++, cnt++;
	for(int i = 2; i <= 20; ++i){
    
		if((flip[i - 1] + tmp[i - 1]) % 2 == 0)	continue;
		else	flip[i]++, tmp[i + 1]++, cnt++;
	}
	if((flip[20] + tmp[20]) % 2 == 0)
		minn = min(minn, cnt);
}

int main(){
    
	minn = 1e5;
	for(int i = 1; i <= 20; ++i)
		scanf("%d",&book[i]);
	solve1(); solve2();
	printf("%d",minn);
	return 0; 
} 

/* 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 */

It can also be used for reference A Writing method of questions , Twice （ The first element is changed / Don't change ）. Note that when modifying the last data , It can only be modified 2 individual , So judging is just judging the last one , Not from the second n-k+2 individual .
Another way of writing ：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 25;
int book[maxn],filp[maxn],n,k,minn;

int solve(int k){
    
	memset(filp,0,sizeof(filp));
	int sum = 0, res = 0;
	for(int i = 1; i <= n - 1; ++i){
    
		if((book[i] + sum) % 2 == 0)	filp[i] = 0;
		else	sum++, res++, filp[i] = 1;
		if(i - k >= 0)	sum -= filp[i - k + 1];
	}
	return (book[n] + sum) % 2 != 0	? -1 : res;
}

int main(){
    
	n = 20;
	for(int i = 1; i <= n; ++i)
		scanf("%d",&book[i]);
	int tmp1 = solve(3); 		//k = 3,  The first one does not reverse 
	book[1]++, book[2]++;		// The first reversal is equivalent to the number +1, The first 1、2 Data +1
	int tmp2 = solve(3) + 1;
	printf("%d",min(tmp1,tmp2));	
	return 0;
} 

C.Fliptile POJ - 3279

Very classic two-dimensional inversion . because n,m Up to 15, use dfs/bfs Must be TLE.
Each grid can change itself and up, down, left and right , So you can't do that like one-dimensional inversion （ Because it can change （1,1） You can also have （1,2） and （2,1）, There is only one way to change the leftmost bull in the last question , Because only one interval contains 1）.

We can Enumerate all reversals in the first row , After the reversal of the first line is determined , Only the next line can change the state of the previous line , And so on , Until the last line , Then check whether the last line is 0 that will do .

tips: State compression , Enumeration of collections in binary .

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

const int maxn = 20;
int n,m,book[maxn][maxn],flip[maxn][maxn],ans[maxn][maxn];
int dir[5][2] = {
    {
    1,0},{
    -1,0},{
    0,0},{
    0,1},{
    0,-1}};

int getcolor(int x, int y){
    
	int c = book[x][y];
	for(int k = 0; k < 5; ++k){
    
		int tx = x + dir[k][0], ty = y + dir[k][1];
		if(tx < 1 || ty < 1 || tx > m || ty > n)	continue;
		c += flip[tx][ty];
	}
	return c % 2;
}

int calc(){
    
	for(int i = 2; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			if(getcolor(i - 1, j))	flip[i][j] = 1;
	
	for(int j = 1; j <= n; ++j)
		if(getcolor(m, j))	return -1;
		
	int cnt = 0;
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			cnt += flip[i][j];
	return cnt;
}

void solve(){
    
	int res = -1;
	for(int s = 0; s < 1 << n; ++s){
    
		memset(flip, 0, sizeof(flip));
		for(int j = 1; j <= n; ++j)
			flip[1][j] = s >> (j - 1) & 1;
		int num = calc();
		if(num >= 0 && (res < 0 || res > num)){
    
			res = num;
			memcpy(ans, flip, sizeof(flip));
		}
	}
	if(res < 0)	printf("IMPOSSIBLE\n");
	else{
    
		for(int i = 1; i <= m; ++i)
			for(int j = 1; j <= n; ++j)
				printf("%d%c",ans[i][j], j == n ? '\n' : ' ');
	}
}

int main(){
    
	scanf("%d%d",&m,&n);
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			scanf("%d",&book[i][j]);
	solve();
	return 0;
}

D.Flip Game POJ - 1753
tips: Similar questions , It's just n = m = 4, The data range is greatly reduced , And “ Turn into the same side ” It can all be positive , It can also be all anti , It can be discussed in two categories .
The data range is too small, resulting in dfs You can go through , But it's better to reverse .

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int book[10][10],flip[10][10];
int dir[5][2] = {
    {
    1,0},{
    -1,0},{
    0,0},{
    0,1},{
    0,-1}};
char c;

int getcolor(int x ,int y){
    
	int c = book[x][y];
	for(int k = 0; k < 5; ++k){
    
		int tx = x + dir[k][0], ty = y + dir[k][1];
		if(tx < 1 || ty < 1 || tx > 4 || ty > 4)	continue;
		c += flip[tx][ty];
	}
	return c % 2;
}

int calc1(){
    
	for(int i = 2; i <= 4; ++i)
		for(int j = 1; j <= 4; ++j)
			if(getcolor(i - 1, j))	flip[i][j] = 1;
	
	for(int j = 1; j <= 4; ++j)
		if(getcolor(4, j))	return -1;
		
	int cnt = 0;
	for(int i = 1; i <= 4; ++i)
		for(int j = 1; j <= 4; ++j)
			cnt += flip[i][j];
	return cnt;
}

int calc2(){
    
	for(int i = 2; i <= 4; ++i)
		for(int j = 1; j <= 4; ++j)
			if(getcolor(i - 1, j) == 0)	flip[i][j] = 1;
	
	for(int j = 1; j <= 4; ++j)
		if(getcolor(4, j) == 0)	return -1;
		
	int cnt = 0;
	for(int i = 1; i <= 4; ++i)
		for(int j = 1; j <= 4; ++j)
			cnt += flip[i][j];
	return cnt;
}

void solve(){
    
	int res1 = -1, res2 = -1;
	for(int s = 0; s < 1 << 4; ++s){
    
		memset(flip, 0, sizeof(flip));
		for(int j = 1; j <= 4; ++j)
			flip[1][j] = s >> (j - 1) & 1;
		int num1 = calc1();
		if(num1 >= 0 && (res1 == -1 || res1 > num1))	res1 = num1;
	}
	for(int s = 0; s < 1 << 4; ++s){
    
		memset(flip, 0, sizeof(flip));
		for(int j = 1; j <= 4; ++j)
			flip[1][j] = s >> (j - 1) & 1;
		int num2 = calc2();
		if(num2 >= 0 && (res2 == -1 || res2 > num2))	res2 = num2;
	}
	if(res1 == -1 && res2 == -1)	printf("Impossible\n");
	else if(res1 == -1)	printf("%d",res2);
	else if(res2 == -1)	printf("%d",res1);
	else	printf("%d",min(res2, res1));
} 

int main(){
    
	for(int i = 1; i <= 4; ++i){
    
		for(int j = 1; j <= 4; ++j){
    
			scanf("%c",&c);
			book[i][j] = (c == 'b') ? 1 : 0;		//b yes 1
		}
		getchar();
	}
	solve();
	return 0;	
}

E.EXTENDED LIGHTS OUT POJ - 1222
tips: Same as 3279. Multi group input , And fixed m = 5, n = 6.

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

const int maxn = 10;
int t,n,m,book[maxn][maxn],flip[maxn][maxn],ans[maxn][maxn];
int dir[5][2] = {
    {
    1,0},{
    -1,0},{
    0,0},{
    0,1},{
    0,-1}};

int getcolor(int x, int y){
    
	int c = book[x][y];
	for(int k = 0; k < 5; ++k){
    
		int tx = x + dir[k][0], ty = y + dir[k][1];
		if(tx < 1 || ty < 1 || tx > m || ty > n)	continue;
		c += flip[tx][ty];
	}
	return c % 2;
}

int calc(){
    
	for(int i = 2; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			if(getcolor(i - 1, j))	flip[i][j] = 1;
	
	for(int j = 1; j <= n; ++j)
		if(getcolor(m, j))	return -1;
		
	int cnt = 0;
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			cnt += flip[i][j];
	return cnt;
}

void solve(){
    
	int res = -1;
	for(int s = 0; s < 1 << n; ++s){
    
		memset(flip, 0, sizeof(flip));
		for(int j = 1; j <= n; ++j)
			flip[1][j] = s >> (j - 1) & 1;
		int num = calc();
		if(num >= 0 && (res < 0 || res > num)){
    
			res = num;
			memcpy(ans, flip, sizeof(flip));
		}
	}
	if(res < 0)	printf("IMPOSSIBLE\n");
	else{
    
		for(int i = 1; i <= m; ++i)
			for(int j = 1; j <= n; ++j)
				printf("%d%c",ans[i][j], j == n ? '\n' : ' ');
	}
}

int main(){
    
	scanf("%d",&t);
	for(int x = 1; x <= t; ++x){
    
		m = 5, n = 6;
		for(int i = 1; i <= m; ++i)
			for(int j = 1; j <= n; ++j)
				scanf("%d",&book[i][j]);
		printf("PUZZLE #%d\n",x);
		solve();
	}
	return 0;
}

F.The Pilots Brothers’ refrigerator POJ - 2965

tips: A little bit different . The above two-dimensional inversion only changes itself and up, down, left and right , In addition to changing yourself , It will also change your line 、 All cells in the column . Fixed size 4*4.

An important discovery ： For example, the second in the first line is +, As long as the grid of the row and column where he is located is turned once , Will make the current + become - , But none of the other grids will change .（ prove ： The row of a grid / If the total number of inversions of the columns is even , The grid does not change ; Odd number , The grid is reversed . After the above operation , The number of reversals of the whole chessboard is odd except for this lattice （4 + 3 == 7）, Other positions are even . You can start to calculate ）
therefore , Find out + lattice , Just put all the grids in his row flip++, The final answer is all the grids (flip%2) Add up .

4*4 use dfs I can live , But using reverse thinking is obviously better than dfs Much faster .

#include<cstdio>
#include<utility>
#include<vector>
using namespace std;
 
int book[5][5], flip[5][5],ans;
char c;
vector<pair<int,int> > v;
vector<pair<int,int> > :: iterator it;

void change(int x, int y){
    
	for(int i = 1; i <= 4; ++i)	flip[x][i]++;
	for(int i = 1; i <= 4; ++i)	flip[i][y]++;
	flip[x][y]--;
}

int main(){
    
	for(int i = 1; i <= 4; ++i){
    
		for(int j = 1; j <= 4; ++j)
			scanf("%c",&c), book[i][j] = (c == '+') ? 1 : 0;
		getchar();
	}
	for(int i = 1; i <= 4; ++i){
    
		for(int j = 1; j <= 4; ++j){
    
			if(book[i][j])	change(i, j);
		}
	}
	for(int i = 1; i <= 4; ++i)
		for(int j = 1; j <= 4; ++j){
    
			ans += flip[i][j] % 2;
			if(flip[i][j] % 2)	v.push_back(make_pair(i, j)); 
		}
	printf("%d\n",ans);
	for(it = v.begin(); it != v.end(); ++it)
		printf("%d %d\n",it->first, it->second);
	return 0;
}