首页 > ACM题库 > HDU-杭电 > HDU 3404-Switch lights-博弈论-[解题报告]HOJ
2014
03-23

HDU 3404-Switch lights-博弈论-[解题报告]HOJ

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.

主要是求NIM积!!!

代码如下:

 

Switch lights

#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.");
        else puts("Don't waste your time.");
    }
    return 0;
}

View Code

 

 

参考:http://www.cnblogs.com/xin-hua/archive/2013/09/03/3298737.html


  1. 羞辱想玩出ge不仅要潜入,还要潜行,尽量不杀人。这游戏可以一人不杀通关,包括那几个刺杀目标都可以触发支线用非致命手段解决。

  2. 美国还有共产党,只是现在跟随者寥寥无几。还有,你提的所有问题都是初中阶段的入门问题,自己看书学习去吧,这样能加深印象。

  3. 美国还有共产党,只是现在跟随者寥寥无几。还有,你提的所有问题都是初中阶段的入门问题,自己看书学习去吧,这样能加深印象。

  4. 美国还有共产党,只是现在跟随者寥寥无几。还有,你提的所有问题都是初中阶段的入门问题,自己看书学习去吧,这样能加深印象。

  5. 美国还有共产党,只是现在跟随者寥寥无几。还有,你提的所有问题都是初中阶段的入门问题,自己看书学习去吧,这样能加深印象。

  6. 美国还有共产党,只是现在跟随者寥寥无几。还有,你提的所有问题都是初中阶段的入门问题,自己看书学习去吧,这样能加深印象。

  7. 美国还有共产党,只是现在跟随者寥寥无几。还有,你提的所有问题都是初中阶段的入门问题,自己看书学习去吧,这样能加深印象。

  8. 哎呀呀我就是干这个的呢,好口怕啊,其实做久了有时候自己都不会注意,自己也经历过几次差点被卷到,总之还是很危险的呢

  9. 哎呀呀我就是干这个的呢,好口怕啊,其实做久了有时候自己都不会注意,自己也经历过几次差点被卷到,总之还是很危险的呢

  10. 哎呀呀我就是干这个的呢,好口怕啊,其实做久了有时候自己都不会注意,自己也经历过几次差点被卷到,总之还是很危险的呢

  11. 哎呀呀我就是干这个的呢,好口怕啊,其实做久了有时候自己都不会注意,自己也经历过几次差点被卷到,总之还是很危险的呢

  12. 哎呀呀我就是干这个的呢,好口怕啊,其实做久了有时候自己都不会注意,自己也经历过几次差点被卷到,总之还是很危险的呢

  13. 哎呀呀我就是干这个的呢,好口怕啊,其实做久了有时候自己都不会注意,自己也经历过几次差点被卷到,总之还是很危险的呢

  14. 哎呀呀我就是干这个的呢,好口怕啊,其实做久了有时候自己都不会注意,自己也经历过几次差点被卷到,总之还是很危险的呢

  15. 哎呀呀我就是干这个的呢,好口怕啊,其实做久了有时候自己都不会注意,自己也经历过几次差点被卷到,总之还是很危险的呢

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

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

  18. 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