SDOI2009

E&D

时间限制
1.00s
内存限制
125.00MB

题目描述

小 E 与小 W 进行一项名为 E&D 游戏。

游戏的规则如下:桌子上有 \(2n\) 堆石子,编号为 \(1 \sim 2n\) 。其中,为了方便起见,我们将第 \(2k-1\) 堆与第 \(2k\) 堆\((1 \le k \le n)\)视为同一组。第 \(i\) 堆的石子个数用一个正整数 \(S_i\) 表示。

一次分割操作指的是,从桌子上任取一堆石子,将其移走。然后分割它同一组的另一堆石子,从中取出若干个石子放在被移走的位置,组成新的一堆。操作完成后,所有堆的石子数必须保证大于 \(1\) 。显然,被分割的一堆的石子数至少要为 \(2\) 。两个人轮流进行分割操作。如果轮到某人进行操作时,所有堆的石子数均为 \(1\) ,则此时没有石子可以操作,判此人输掉比赛。

小 E 进行第一次分割。他想知道,是否存在某种策略使得他一定能战胜小 W。因此,他求助于小 F,也就是你,请你告诉他是否存在必胜策略。例如,假设初始时桌子上有 \(4\) 堆石子,数量分别为 \(1,2,3,1\) 。小 E 可以选择移走第 \(1\) 堆,然后将第 \(2\) 堆分割(只能分出 \(1\) 个石子)。接下来,小 W 只能选择移走第 \(4\) 堆,然后将第 \(3\) 堆分割为 \(1\) 和 \(2\) 。最后轮到小 E,他只能移走后两堆中数量为 \(1\) 的一堆,将另一堆分割为 \(1\) 和 \(1\) 。这样,轮到小 W 时,所有堆的数量均为 \(1\) ,则他输掉了比赛。故小 E 存在必胜策略。

输入格式

本题有多组数据。

第一行一个整数 \(T\),表示数据组数。

对于每组数据:

第一行一个整数 \(N\),表示桌子上共有 \(N\) 堆石子,这里的 \(N\) 即为题目描述中的 \(2n\) 。

第二行 \(N\) 个整数 \(S_{1 \dots N}\) 。

输出格式

对于每组数据,如果小 E 必胜,则一行一个字符串 YES,否则一行一个字符串 NO

输入输出样例

输入

2
4
1 2 3 1
6
1 1 1 1 1 1

输出

YES
NO

说明/提示

对于 \(20\%\) 的数据,\(N=2\) 。

对于另外 \(20\%\) 的数据,\(N \le 4,S_i \le 50\) 。

对于 \(100\%\) 的数据,\(1 \le T \le 20,1 \le N \le 2 \times 10^4\) 且 \(N\) 为偶数,\(1 \le S_i \le 2 \times 10^9\) 。

原题链接

P2148 [SDOI2009]E&D

题目大意

给定n对石子堆,每次操作针对一对石子堆:去掉一堆,将另外一堆石子进行分割,保证所有石子堆数量不为0

解题思路

博弈论,sg函数

  • sg定理
    SDOI2009 为ICG的状态,则: SDOI2009

nim游戏,N堆石子,单位是一对堆石子,可以先把所有单位的sg函数求出,然后再根据sg定理进而求出整堆石子的sg函数。
首先,\(sg(1,1)\)为必败点,即\(sg(1,1)=0\),设\(i=j+k\),则\(sg(i,……)=mex(sg(j,k))\)。
算起来比较,我们可以用bitset来简化操作,bitset每一位我们用来表示是否出现在mex集合里,如bitset表示的\(s(i)\),意思是所有\(j+k=i\)的sg函数,位数为\(1\)表示该位出现在mex集合里面。
复杂度过大,不过可以用来打表找规律~
打表代码:

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int sg[N][N];
//设i=j+k,由题意,sg[i,…]=mex(sg[k]),s[i]相当于sg函数的集合,不过每个数都用01表示,存储mex元素
bitset<101>s[N];
inline int mex(bitset<101> b)
{
    int i=0;
    while(b[i])i++;
    return i;
}
int main()
{
    for(int i=2;i<=101;i++)
        for(int j=1,k=i-1;k;j++,k--)
            s[i].set(sg[j][k]=mex(s[j]|s[k]));
    for(int i=1;i<=100;i++)
    {
        for(int j=1;j<=100;j++)
            cout<<sg[i][j]<<' ';
        puts("");
    }
    return 0;
}

打表结果:
SDOI2009iujie
根据打表结果,

  1. \(i \in 奇数,j \in 奇数\),有\(sg(i,j)=0\)
  2. \(sg(i,j)=sg(j,i)\)
  3. \(n\) 列和 \(2n\) 列有一定联系,对 \(j \in 偶数,\)有 \(sg(i,j)=sg(\frac{i-1}{2}+1,\frac{j}{2})+1\)
    可以递归求解
  • 算法复杂度:\(o(nlogn)\)

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,x,y;
inline int sg(int n,int m)
{
    if((n&1)&&(m&1))return 0;
    else if(!(m&1))return sg((n-1>>1)+1,m>>1)+1;
    else
        return sg(m,n);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int res=0;
        for(int i=0;i<n/2;i++)
        {
            scanf("%d%d",&x,&y);
            res^=sg(x,y);
        }
        puts(res?"YES":"NO");
    }
    return 0;
}



上一篇:题解CF1375D Replace by MEX


下一篇:求SG函数(两种方法)