[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 F: qwb has a lot of Coins [nim]【博弈】

Tabris

CSDN博弈

发布于：2017年6月3日

次浏览

[原创]2017 年第 0 届浙江工业大学之江学院程序设计竞赛决赛 F: qwb has a lot of Coins [nim]【博弈】

2017-06-03 02:22:20 Tabris_ 阅读数：400

博客爬取于 2020-06-14 22:40:18
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849663

题目链接：http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=5
——————————————————————————————————————————
Problem F: qwb has a lot of Coins
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 699 Solved: 220
[Submit][Status][Web Board]
Description
qwb has a lot of coins. One day, he decides to play a game with his friend using these coins. He first puts some of his coins into M piles, each of which is composed of Ni (1<=i<=M) coins. Then, the two players play the coin game in turns. Every step, one can remove one or more coins from only one pile. The winner is the one who removes the last coin.
Then comes the question: How many different ways the first player can do that will ensure him win the game?
Input
Input contains multiple test cases till the end of file. Each test case starts with a number M (1 <= M<= 1000) meaning the number of piles. The next line contains M integers Ni (1 <= Ni <= 1e9, 1 <= i<= M) indicating the number of coins in pile i.
Output
For each case, put the method count in one line.
If the first player can win the game, the method count is the number of different ways that he can do to ensure him win the game, otherwise zero.
Sample Input
3
1 2 3
1
1
Sample Output
0
1
——————————————————————————————————————————
题意：就是问你 Nim 游戏先手第一步能赢的方案数

显然就是然你模拟下 Nim 游戏呗，如果第一步选当前堆能赢就 ++，

能赢就是这个堆的石子个数大于其他堆得石子个数异或和

简单 nim 游戏不解释

虽然给了 1000，但是这题是可以预处理前后缀异或和达到 O(n)的

附本题代码
——————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
 
# define abs(x) (((x)>0)?(x):-(x))
 
const int N = 3000+10;
const int MOD  = 1e8;
 
/******************************************/
 
int n;
int a[1111];
int pre[1111],suf[1111];
int main(){
    while(~scanf("%d",&n)){
        pre[0]=suf[n+1]=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            pre[i]=pre[i-1]^a[i];
        }
        for(int i=n;i;i--)
            suf[i]=suf[i+1]^a[i];
        int cnt=0;
        for(int i=1;i<=n;i++){
//            printf("%d : %d %d\n",i,a[i],(pre[i-1]^suf[i+1]));
            if(a[i]>(pre[i-1]^suf[i+1])) cnt++;
        }
        printf("%d\n",cnt);
    }
    return 0;
}
 

本页文档最后更新于：2021年5月16日

CSDN