问题描述:

传统的Nim游戏是这样的:有一些火柴堆,每堆都有若干根火柴(不同堆的火柴数量可以不同)。两个游戏者轮流操作,每次可以选一个火柴堆拿走若干根火柴。可以只拿一根,也可以拿走整堆火柴,但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。

本题的游戏稍微有些不同:在第一个回合中,第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿,但不可以全部拿走。第二回合也一样,第二个游戏者也有这样一次机会。从第三个回合(又轮到第一个游戏者)开始,规则和Nim游戏一样。

如果你先拿,怎样才能保证获胜?如果可以获胜的话,还要让第一回合拿的火柴总数尽量小。

输入:

第一行为整数$k$。即火柴堆数。第二行包含$k$个不超过$10^9$的正整数,即各堆的火柴个数 ($k<=100$)

输出:

输出第一回合拿的火柴数目的最小值。如果不能保证取胜,输出-1

思路:

如果已经弄清了NIM游戏的话,那么这道题应该也不难想到。

根据结论,如果要先手必胜,显然应该满足第三回合时所有堆的火柴数异或和大于0。既然这样,第一回合取完后所有堆的火柴数都应该线性无关。如果有一组数它们线性相关的话,它们的异或和就应该为0,那么这样第二回合就可以只留下这一组数,这样就先手比败了。

因此我们就可以直接求出这些数的线性基。还有一点就是题目要求拿的数目最小,所以我们就希望线性基里面的元素和最大。根据贪心,我们先将它们从大到小排个序就好了。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 10005
#define LL long long
using namespace std;

int n;
LL ans, sum, a[MAXN], base[MAXN];

bool CMP(LL x, LL y) {return x>y;}

bool insert(LL x)
{
    for(int i=31; i>=0; i--)
    {
        if(!(x>>i)) continue;
        if(!base[i]) {base[i]=x; return true;}
        x^=base[i];
    }
    return false;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    sort(a+1, a+n+1, CMP);
    for(int i=1; i<=n; i++)
    {
        if(insert(a[i])) ans+=a[i];
        sum+=a[i];
    }
    printf("%lld\n", sum-ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注