题解

27 条题解

  • 2
    @ 2018-12-15 21:12:42

    自己想了半天,感觉是奇数必胜,偶数必败,然后成功WA,于是滚去看题解。
    后来依次想了一遍题解板块里头涉及到的判断方法
    第一种 判断是否全部异或为0
    反例 n=3 三堆石子分别为1 2 3.先手只要把它变成2 2 0就必胜了。
    第二种 判断n的奇偶性
    反例 n=2 两堆石子分别为1 2.先手只要把它变成1 1就必胜了
    然后看到了FlameH的证明 让我有了一个想法
    对于n为奇数的情况,去掉所有对子之后,剩下的石子堆数肯定是奇数,且互不相等。这时只要用FlameH的方法,令a[1]=0即可,于是先手必胜(即不论当前是否为奇异局势,先手都能一步将其变成奇异局势,同时让后手无法在一步之内保持局势奇异性不变)。
    而对于n为偶数的情况,如果去掉所有对子之后,如果剩下互不相等的偶数堆石子,先手依然能必胜,然而如果去掉所有对子之后,没有任何一堆棋子剩余(即当前局势为奇异局势),那么先手的任何操作都会让这个奇异局势变成非奇异局势,于是只有后手才能必胜。

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<vector>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    typedef long long ll;
    const int maxn=5000+5;
    const ll INF=0x3f3f3f3f3f3f3f3fll;
    int t,n;
    int main() {
        ios::sync_with_stdio(false);
        //freopen("校庆的娱乐.in","r",stdin);
        cin>>t;
        while(t--){
            cin>>n;
            int temp,x;
            cin>>temp;
            for(int i=2;i<=n;i++){
                cin>>x;
                temp^=x;
            }
            if(temp||n&1) cout<<"lolanv"<<endl;
            else cout<<"Wind"<<endl; //只有全是对子 才会让wind赢 
        }
    
        return 0;
    }
    
  • 1
    @ 2016-10-13 08:58:30

    首先楼下显然是错的 七年前@jacklv 在你的下面就已经给出反例了
    然后我讲一下先手在必胜情况下的操作方法

    首先如果堆数是偶数
    然后把石子数相等的堆"抓对子"去掉,先不考虑它们
    然后将所有n堆从小到大排序,记为a[]
    取最大的一堆a[n],使a[n]只剩下a[1]颗
    然后把a[2]补齐成a[3],a[4]补齐a[5]...a[n-2]补齐a[n-1]
    现在再把前面"抓对子"去掉的堆加进来
    这样堆里石子数两两相等,根据下面的题解,后面先手只要做和后手一样的操作就行

    下面证明a[n]里的石子一定够用
    上面的方法需要用到石子数是:
    a[1]+(a[3]-a[2])+(a[5]-a[4])+...+(a[n-1]-a[n-2])
    整理一下,相当于我们需要
    (a[1]-a[2])+(a[3]-a[4])+...(a[n-3]-a[n-2])+a[n-1]<=a[n]-1
    (右边a[n]-1是因为至少要拿掉一个石子)
    因为我们已经事先"抓对子",所以没有石子数相同的堆
    所以左边的每个括号都是负数,最后一个a[n-1]<=a[n]-1也是成立的

    如果堆数是奇数,就设a[1]=0,然后用上面的方法

  • 1
    @ 2009-06-14 13:36:28

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 56ms

    ├ 测试数据 09:答案正确... 88ms

    ├ 测试数据 10:答案正确... 181ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:325ms

    可惜没有秒杀,不过一次就AC了~

    其实捏,只需要判断是否有两两相同的情况就可以了~如果有,Wind胜~

  • 1
    @ 2007-10-24 21:37:29

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    其实很简单,模拟一下很快就能找到规律。

    首先,只有一堆时:明显,第一个人都拿了,先手必胜。

    其次,只有两堆时:

    如果有两堆一样的,谁先拿完第一堆,就会必败,所以,第二个人只要不先拿完第一堆,那么只能是第一个人去拿第一堆。(想想就知道为什么了)所以这种情况下,后手必胜。

    如果有两堆石子不一样多,那么第一个人第一次就可以让这两堆石子变成一样多,然后就和上面一样的了。所以先手必胜。

    如果有三堆:

    先拿完一堆,就和上一种情况一样了,所以第一个人第一次拿就能把三堆变成两堆一样的,所以先手必胜。

    如果有四堆:

    先手后手都不想首先拿完一堆,变成三对。我们就能想到两堆的情况,如果四堆中两两相等,后手就会必胜。

    于是:

    如果有奇数堆,先手必胜。

    如果有偶数堆,其中,如果两两相等,后手必胜,否则先手必胜。

    这样编程就容易了吧。

  • 0
    @ 2016-10-07 20:31:36

    石子数为x的一堆sg函数为 sg(x)=x

    所以先手必败当且仅当所有石子数异或和为0

  • 0
    @ 2015-12-17 13:34:10

    Wind ™是大写。。。。

  • 0
    @ 2013-12-07 17:09:15

    xor^^^^^

  • 0
    @ 2009-10-21 20:21:32

    楼上的不对吧,这个可以自由分配

    原来有1 2 3

    我取第三堆2个,将一个分到1堆中,则是

    2 2

    这样对方怎么取都先方胜啊

  • 0
    @ 2009-08-06 13:41:18

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 9ms

    ├ 测试数据 07:答案正确... 25ms

    ├ 测试数据 08:答案正确... 88ms

    ├ 测试数据 09:答案正确... 119ms

    ├ 测试数据 10:答案正确... 181ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:422ms

    真想直接秒杀一次……

  • 0
    @ 2009-08-06 13:02:37

    冒泡排序都过了。。。。。。

  • 0
    @ 2009-07-14 02:55:14

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 25ms

    ├ 测试数据 07:答案正确... 103ms

    ├ 测试数据 08:答案正确... 197ms

    ├ 测试数据 09:答案正确... 322ms

    ├ 测试数据 10:答案正确... 462ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:1109ms

    我汗!写程序时忘了voyagec2大牛的话,3次才AC

    #include "stdio.h"

    int a,b[6000],n,i,j;

    int check()

    {

    int i,j,x;

    x=0;

    for(i=1;i

  • 0
    @ 2009-03-19 19:19:38

    只有当有N DIV 2对相等的数时,WIND才能赢,是吧?

  • 0
    @ 2009-01-12 17:47:39

    为啥大家都秒杀而我用了那么长时间...

    我是快排的难道大家是用Hash?

  • 0
    @ 2009-08-27 21:20:40

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    过了快一年了,再回来看看这题解,唉...顺便怀念一下lolanv和Wind两位大牛

    x1 xor x2 xor x3...xor xn=0时先手必败

    program p1298;

    var n,k,i,j,t:integer;

    a:array[1..5000] of longint;

    begin

    readln(k);

    for i:=1 to k do

    begin

    readln(n);

    for j:=1 to n do read(a[j]);

    if n=1 then

    writeln('lolanv')

    else

    begin

    t:=a[1];

    for j:=1 to n-1 do t:=t xor a[j+1];

    if t=0 then writeln('Wind') else writeln('lolanv');

    end;

    end;

    end.

  • 0
    @ 2008-08-07 13:39:40

    下面的,你没做手脚!!!!

  • 0
    @ 2006-11-15 20:00:59

    只有一堆时先手必胜。

    有两堆时若两堆相等则后手只用和先手一样决策即可保证胜利,后手必胜。若不同则先手可以使其变成相等的两堆,先手必胜。

    有三堆时先手只用一次决策即可将其变成两堆相等的局面,先手必胜。

    有四堆时由于三堆必胜,无论先手后手都想逼对方取完其中一堆,而只有在四堆都为一颗时才会有人取完其中一堆,联系前面的结论可以发现,只有当四堆可以分成两两相等的两对时先手才会失败。

    分析到这里,题目好像已经有了一些眉目了,凭借归纳猜想,我们猜测必败态的条件为“堆数为偶数(不妨设为2N),并且可以分为两两相等的N对”。

    下面只需证明一下这个猜想。其实证明这样的猜想很简单,只用检验是否满足必败态的三条性质即可。

    首先,末状态为必败态,第一条性质符合。

    其次,可以证明任何一个胜态都有策略变成必败态(分奇数堆和偶数堆两种情况讨论)。

    最后,证明任何一个必败态都无法变成另一个必败态(比较简单)。

    由于篇幅关系,这里就不具体证明了,如果有兴趣可以自己试试∶P

      接下来的程序就相当简单了,只用判断一下即可。

  • 0
    @ 2006-11-15 13:35:52

    做完这题可以去看看1196

  • 0
    @ 2006-11-10 21:45:27

    没想到最后还是这么简单的判断,郁闷,我想了N天还没出来.经高人指点,竟然是...

  • 0
    @ 2006-11-09 20:53:10

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 05:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 06:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 07:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 08:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 09:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 10:答案错误... ├ 标准行输出

     ├ 错误行输出

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:30 有效耗时:0ms

    想不出来`\`\不想了

  • 0
    @ 2006-11-14 13:13:18

    这题应该自己想,认真想,用力想,死命想,然后就AC了

信息

ID
1298
难度
5
分类
博弈论 点击显示
标签
(无)
递交数
273
已通过
93
通过率
34%
被复制
8
上传者