2014
03-23

Switch lights

lxhgww is playing a game with his computer Deep Blue.
The game is played on a matrix containing lights. At first, some lights are on, while others are off. lxhgww and Deep Blue take turns to switch the lights. For each step, the player should choose a rectangle in the matrix: (x1 , y1) , (x1 , y2) , (x2 , y1) , (x2 , y2) , (x1<=x2,y1<=y2, the light at (x2, y2) should be on) and change the lights’ status on the four vertex of the rectangle, namely on to off, and off to on. The player turns all the lights off wins the game. Notice the rectangle is possibly degenerated to line or even a single cell so that the player may also switch two or one besides four lights in a move.
Deep Blue’s strategy is perfect, if it has a chance to win, never will it lose. Does lxhgww have a chance to win if he takes the first step?

The first line is an integer T(T<=100) indicating the case number.
Each case has one integers n (n<= 1000 ), the number of on-lights at the beginning of the game.
Then come n lines, each line has two integers, xi , yi, (1<=xi<=10000, 1<=yi<=10000) , so light at (xi, yi) is on at first. (No two lights at the same position)

The first line is an integer T(T<=100) indicating the case number.
Each case has one integers n (n<= 1000 ), the number of on-lights at the beginning of the game.
Then come n lines, each line has two integers, xi , yi, (1<=xi<=10000, 1<=yi<=10000) , so light at (xi, yi) is on at first. (No two lights at the same position)

2
2
1 2
2 1
2
1 1
2 2

Don't waste your time.
Have a try, lxhgww.

#include<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
#define ll __int64
using namespace std;
int f[20][20];
int nim(int x,int y);
int _nim(int x,int y){
if(!x||!y)return 1<<x+y;
int &F=f[x][y];
if(F!=-1)return F;
int ret=1,e=1;
for(int i=0;i<16;++i)
if(((x^y)>>i)&1)e*=1<<(1<<i);
else if((x>>i)&1)ret=nim(ret,3*(1<<(1<<i))/2);
return F=nim(ret,e);
}
int nim(int x,int y){
if(x<2||y<2)return x*y;
int ret=0;
for(int i=0;i<16;++i)
if((x>>i)&1)
for(int j=0;j<16;++j)
if((y>>j)&1)
ret^=_nim(i,j);
return ret;
}
int main()
{
int t,x,y,n,res;
memset(f,-1,sizeof(f));
scanf("%d",&t);
while(t--){
scanf("%d",&n);
res=0;
while(n--){
scanf("%d%d",&x,&y);
res^=nim(x,y);
}
if(res) puts("Have a try, lxhgww.");
}
return 0;
}

View Code

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。

2. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测

3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks