「BZOJ1982」[SPOJ 2021] Moving Pebbles
Description
2021. Moving Pebbles Two players play the following game. At the beginning of the game they start with n (1<=n<=100000) piles of stones. At each step of the game, the player chooses a pile and remove at least one stone from this pile and move zero or more stones from this pile to any other pile that still has stones. A player loses if he has no more possible moves. Given the initial piles, determine who wins: the first player, or the second player, if both play perfectly. 给你N堆Stone，两个人玩游戏. 每次任选一堆，首先拿掉至少一个石头,然后移动任意个石子到任意堆中. 谁不能移动了，谁就输了…
Input
Each line of input has integers 0 < n <= 100000, followed by n positive integers denoting the initial piles.
Output
For each line of input, output “first player” if first player can force a win, or “second player”, if the second player can force a win.
Sample Input
3 2 1 3
Sample Output
first player
题解
博弈论，因为这个游戏显然不同游戏之间会互相影响……不能用sg
所以推结论，容易发现n为奇数的时候，先手必胜
n为偶数的时候，先将石头排好序
后手必胜当且仅当对于所有i，第2i-1堆石头和第2i堆的数目相等
证明略
注意输入数据的石头数目非常坑……需要高精度
不过输入数据比较弱……
没有排序就能ac
|
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 34 35 |
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; int n; char ch[10001]; string s[100001]; bool cmp(string a,string b) { int la=a.length(),lb=b.length(); if(la==lb) { for(int i=0;i<la;i++) { if(a[i]==b[i])continue; return a[i]<b[i]; } } return la<lb; } int main() { scanf("%d",&n); if(n&1){printf("first player");return 0;} for(int i=1;i<=n;i++) { scanf("%s",ch);s[i]=ch; } //sort(s+1,s+n+1,cmp); for(int i=1;i<=n;i+=2) if(s[i]!=s[i+1]){printf("first player");return 0;} printf("second player"); return 0; } |
Subscribe
计数器 9774991
OI 课件=>
OI 课件=>