【贪心】取火柴游戏-布布扣-bubuko.com

题目描述

输入k及k个整数n1，n2，…，nk，表示有k堆火柴棒，第i堆火柴棒的根数为ni；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。

谁取走最后一根火柴为胜利者。

例如：k＝2，n₁＝n₂＝2，A代表你，P代表计算机，若决定A先取：

A：(2,2)→(1,2) {从一堆中取一根}

P：(1,2)→(1,1) {从另一堆中取一根}

A：(1,1)→(1,0)

P：(1,0)→ (0,0) {P胜利}

如果决定A后取：

P：(2,2)→(2,0)

A：(2,0)→ 0,0) {A胜利}

又如k＝3，n1=1，n2＝2，n3＝3，A决定后取：

P：(1,2,3)→(0,2,3)

A：(0,2,3)→(0,2,2)

A已将游戏归结为(2,2)的情况，不管P如何取A都必胜。

编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输

出第一次该如何取。如果是先取必败，则输出“lose”。

样例输出

4 3 3 6 5
分析：先求出所有元素的异或m，不为0，则必胜；m依次异或得到的值比这个元素小，则变成这个值即可；
代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include <ext/rope>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define vi vector<int>
#define pii pair<int,int>
#define mod 1000000007
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
const int maxn=1e5+10;
const int dis[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
using namespace std;
using namespace __gnu_cxx;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int n,m,a[maxn];
int main()
{
    int i,j,k,t;
    scanf("%d",&n);
    rep(i,0,n-1)scanf("%d",&a[i]),m^=a[i];
    if(!m)puts("lose");
    else
    {
        rep(i,0,n-1)
            if((m^a[i])<a[i]){
                printf("%d %d\n",a[i]-(m^a[i]),i+1);a[i]=m^a[i];
                break;
            }
        rep(i,0,n-1)printf("%d ",a[i]);
        printf("\n");
    }
    //system ("pause");
    return 0;
}

原文：http://www.cnblogs.com/dyzll/p/5696995.html

【贪心】取火柴游戏