【POI2003/2004 stage I】

【原题在此】

Let us consider a game on a rectangular board m x 1 consisting of m elementary squares numbered successively from 1 to m. There are n pawns on the board, each on a distinct square. None of them occupies the square with number m. Each single move in the is the following action: the moving player picks a pawn from any occupied square chosen at will and places it on the first unoccupied square with a larger number. The two players make moves in turn. The one who puts a pawn on the last square, i.e. the square with a number m, wins.

In the case presented in the figure (m = 7), a player is allowed to move a pawn from square no. 2 to 4, from square no. 3 to 4 or from square no. 6 to 7. The latter ends the game.

We say a player's move is winning if after making it he can win the game, no matter what moves his opponent makes.

Task
Write a programme that:

reads the size of a board and the initial setup of pawns from the standard input,
determines the number of distinct winning moves the starting player may choose in the given initial situation,
writes the result to the standard output.

Input
The first line of the input contains two integers m and n (2 <= m <= 109, 1 <= n <= 106, n < m) separated by a single space. The second line contains n increasing numbers - these are the numbers of squares the pawns are set on. Numbers in the line are separated by single spaces.

Output
The first and only output line should contain the number of distinct winning moves possible for the starting player in the given initial situation.

Example
For the following input data:

5 2
1 3

the correct answer is:

For the following input data:

5 2
2 3

the correct answer is:

【题目翻译】

在一个有M个格子的长条上，从左到右编号1到M。一些格子上方有一些棋子，一个格子只能放一个棋子，第M格没有放棋子。两个人轮流操作，每次操作是选择一枚棋子往右放，放在它右边距离它最近的一个空格里。最先把棋子放在第M格的人胜利。问先手必胜的第一步策略一共有多少种？

上图中，当前玩家可以将2中的硬币移动到4，或3中的硬币到4，或6中的硬币到7。

【输入格式】

第一行输入m,n 。第二行n个数分别表示每一枚硬币所在的位置。

【输出格式】

进一行，保证先行者胜利的策略数。

分析:

　　目测这题我自己是想不出来的了，原来可以转化为阶梯模型，也是听了scy讲了才知道~~

（转自：http://blog.sina.com.cn/s/blog_51cea4040100h0ab.html）

　　感觉博主很厉害很厉害，同时也是萌萌哒~~于是这题就转成了我们熟悉的阶梯模型了。

　　然后我开始打代码，打完之后，我的内心：

　　&&￥￥%%#这题好坑好坑好坑啊，各种情况都要考虑到才行。把这题转换成阶梯模型之后，偶数阶的棋子并不是没有用的！！对方案有巨大贡献啊！！可以把偶数阶的扫下去相当于奇数阶的增加了！！还有各种特判，都晕了~（数据大的直接不管了，好麻烦~~）

　　呵呵~

代码在这里，数据大的过不了TAT：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 using namespace std;
 8 #define Maxn 10000100
 9 
10 int a[Maxn],c[Maxn];
11 bool b[Maxn];
12 
13 int main()
14 {
15     int m,n;
16     scanf("%d%d",&m,&n);
17     memset(b,0,sizeof(b));
18     for(int i=1;i<=n;i++)
19     {
20         scanf("%d",&a[i]);
21         b[a[i]]=1;
22     }
23     if(b[m-1]==1)
24     {
25         int i;
26         int sum=0;for(i=m-1;i>=1;i--) if(!b[i]) break;
27         printf("%d
",m-1-i);
28     }
29     else
30     {
31         memset(c,0,sizeof(c));
32         int sum=0,st;
33         for(st=m-2;b[st];st--);
34         for(int i=st;i>=1;i--)
35         {
36             if(b[i]==0) sum++;
37             else c[sum]++;
38         }
39         int ans=0;
40         for(int i=1;i<=sum;i+=2) ans^=c[i];
41         if(ans==0) printf("0
");
42         else
43         {
44             int mx=0;
45             for(int i=0;(1<<i)<=ans;i++)
46                 if((1<<i)&ans) mx=(1<<i);
47             int h=0;
48             for(int i=1;i<=sum;i+=2) 
49                 if(c[i]&mx) h++;
50             for(int i=2;i<=sum;i+=2)
51              if(((ans^c[i-1])-c[i-1])>=0&&c[i]>=((ans^c[i-1])-c[i-1])) h++;
52             printf("%d
",h);
53         }
54     }
55     return 0;
56 }

[POI2003/2004 stage I ]

2016-04-16 10:23:03