洛谷P4301 [CQOI2013]新Nim游戏

P4301 [CQOI2013]新Nim游戏

题目描述

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

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

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

输入输出格式

输入格式：

第一行为整数k。即火柴堆数。

第二行包含k个不超过10^9的正整数，即各堆的火柴个数。

输出格式：

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

输入输出样例

输入样例#1：

6
5 5 6 6 5 5

输出样例#1：

说明

k<=100

sol：感觉这样的题属于写不出来类型。。。

首先可以看出先手应该是必胜的(如第一步取n-2堆)

要求是使得先手取完后下一步不管后手按要求怎么取，剩余数字异或和都不为0

并且尽量使得先手第一步取得少。。。

完全不知道上面那个怎么做到，去翻题解

线性基！！！（代码极短，适合ZZ选手）

题解是这样做上面写的那个操作的

从大到小排序,然后用线性基把可能异或和为0的取走,否则放进线性基中

/*
    易知先手应该是必胜的(如第一步取n-2堆)
    所以使得第一次新手取完后
    下一步不管后手按要求怎么取，剩余数字异或和都不为0
    从大到小排序,然后用线性基把可能异或和为0的取走,否则放进线性基中 
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=105;
int n,A[N],B[N];
map<int,bool>Map;
namespace  Xianxingji
{
    int Ji[35];
    inline void Insert(ll Num)
    {
        int i;
        for(i=31;~i;i--)
        {
            if((Num&(1<<i))==0) continue;
            if(!Ji[i]) {Ji[i]=Num; break;}
            Num^=Ji[i];
        }
        return;
    }
    inline bool Ask(int Num)
    {
        int i;
        for(i=31;~i;i--) if(Num&(1<<i))
        {
            if(!Ji[i]) break;
            Num^=Ji[i];
        }
        return (Num==0)?1:0;
    }
}
#define Xxj Xianxingji
int main()
{
    int i;
    ll ans=0;
    R(n);
    for(i=1;i<=n;i++)
    {
        R(A[i]);
        if(!Map[A[i]]) Map[A[i]]=1,B[++*B]=A[i];
        else ans+=1ll*A[i];
    }
    sort(B+1,B+*B+1);
    for(i=*B;i>=1;i--)
    {
        if(Xxj::Ask(B[i]))
        {
            ans+=1ll*B[i];
        }
        else Xxj::Insert(B[i]);
    }
    Wl(ans);
    return 0;
}
/*
input
6
5 5 6 6 5 5
output
21
*/

View Code