题目
- 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，两个人玩游戏. 每次任选一堆，首先拿掉至少一个石头,然后移动任意个石子到任意堆中. 谁不能移动了，谁就输了…
输入格式
Each line of input has integers 0 < n <= 100000, followed by n positive integers denoting the initial piles.
输出格式
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.
输入样例
3 2 1 3
输出样例
first player
题解
博弈论的题目总是很神(shao)奇(nao)。。。。
但想清楚总是很简单
①根据博弈的套路，当石子堆两两配对，后手猥琐模仿先手，先手必败
②根据本题特点，石子可以拿取后自由移动；
1、若为奇数，一定不是两两配对，那么先手就可以取掉一点并移动使得堆数-1且两两配对
2、若为偶数，且不两两配对，那么先手可以通过一定操作使得两两配对
综上：只要一开始不是两两配对，先手必胜，否则必败
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline int RD(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57) {
if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}return out * flag;
}
int A[maxn],n;
int main(){n = RD();if (n & 1) {
puts("first player"); return 0;}REP(i,n){A[i] = RD();if (i % 2 == 0 && A[i] != A[i - 1]) {
puts("first player"); return 0;}}puts("second player");return 0;
}