首页 > ACM题库 > HDU-杭电 > hdu 3800 Centeur待解决[解题报告]C++
2015
04-13

hdu 3800 Centeur待解决[解题报告]C++

Centeur

问题描述 :

The aliens in Centaurus a star reach the earth on Dec. 21th in 2012, and they are fairly smart. Before creating a friendly relationship with the human beings, they make a request that the intelligence of human must be tested. Upon their will, an earth citizen is asked to play the testing game with their boss, and rules of the game are as follows:
Given a row of bulbs whose total number is n, and the bulbs are numbered 1 to n from left to right, and each bulb has two states, named turned-on and turned-off. With the citizen from earth starts first, two players make their operations by turns. Every operation they make must meet the conditions:
Choose a bulb which is now on, then turn it off, and we assume this bulb is numbered p;
Choose a bulb and change its state(if on, then turn off, else, turn on), and suppose it is numbered q, which should meet the request of q <= p/2.

In addition, the step 2 is not a must.
And the one cannot move loses.
Eventually, the smart earth citizen wins this test soon.

However, another question is asked by an evil alien: Supposing there are turned-on bulbs in some sections at the beginning, and the other states can be decided by the citizen from earth. With this fixed rules, and the alien goes first, then how many original states will make the citizen from earth win the game?

输入:

Line 1: a single integer t(1<=t<=30), which refers to the number of cases;
And for each case, the first line contains two integers n m(1<=n<=263-1,0<=m<=1000), and in the following m lines, each line has two integers:s t(1<=s<=t<=n), which means that the bulbs numbered from s to t (include s and t)are turned-on originally;
Attention, these sections may be overlapped.

输出:

Line 1: a single integer t(1<=t<=30), which refers to the number of cases;
And for each case, the first line contains two integers n m(1<=n<=263-1,0<=m<=1000), and in the following m lines, each line has two integers:s t(1<=s<=t<=n), which means that the bulbs numbered from s to t (include s and t)are turned-on originally;
Attention, these sections may be overlapped.

样例输入:

2
1 1
1 1
3 0

样例输出:

0
2
Hint
When n = 3 , m = 0, there are two kinds of original states guaranteeing the winner of the earth citizen (From left to right, the bulbs are numbered 1 to n, and o refers to the turned-on bulbs, And * refers to the turned-off): *** ooo


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  3. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。