bzoj 3105: [cqoi2013]新Nim游戏博弈论+贪心（拟阵）+线性基题意分析代码

118 阅读 0 评论 78 点赞

我是靠谱客的博主谦让网络，这篇文章主要介绍bzoj 3105: [cqoi2013]新Nim游戏博弈论+贪心（拟阵）+线性基题意分析代码，现在分享给大家，希望可以做个参考。

题意

传统的Nim游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。
本题的游戏稍微有些不同：在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和Nim游戏一样。
如果你先拿，怎样才能保证获胜？如果可以获胜的话，还要让第一回合拿的火柴总数尽量小。
k<=100

分析

今天好惨啊，打球的时候脚扭到了，现在从课室走到机房要走20分钟，真的爽到不行……

这篇题解写的很详细了

首先必须了解传统的Nim游戏
也就是说如果a[1]^a[2]^…^a[n]!=0则先手有必胜策略。
那么对于这题，现在我们需要找一个极大线性无关组（也就是其中的任意元素都不能表示为其中若干个元素的异或值），那么答案就是总权值减去极大线性无关组的总权值。

那么现在要怎么找线性无关组呢？我们可以证明这是一个拟阵（关于拟阵的介绍请点这里），那么就可以用贪心从大到小来找，然后用线性基来维护即可（关于线性基的介绍请点这里）

这题的代码虽然只有一丢丢，但为了做出这题我去学了传统Nim游戏、线性基还有拟阵（还没完全理解），可以说是收获颇丰啊。

代码

复制代码

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
36
37
38
39
40
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define N 105
#define ll long long
using namespace std;

int n,bin[35],a[N],ins[N];

int main()
{
    bin[0]=1;
    for (int i=1;i<=30;i++)
        bin[i]=bin[i-1]*2;
    scanf("%d",&n);
    ll ans=0;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        ans+=a[i];
    }
    sort(a+1,a+n+1);
    for (int i=n;i>=1;i--)
    {
        int x=a[i];
        for (int j=30;j>=0;j--)
            if (a[i]&bin[j])
                if (!ins[j])
                {
                    ins[j]=a[i];
                    break;
                }
                else a[i]^=ins[j];
            if (a[i]) ans-=x;
    }
    printf("%lld",ans);
    return 0;
}