andyli

题解 UVA1482 【Playing With Stones】
本题和$Nim$游戏不同,但也可以看做$n$个单堆游戏之和。遗憾的是,即使是单堆游戏,由于$a_i$的范围太大,也...
扫描右侧二维码阅读全文
20
2019/06

题解 UVA1482 【Playing With Stones】

本题和$Nim$游戏不同,但也可以看做$n$个单堆游戏之和。遗憾的是,即使是单堆游戏,由于$a_i$的范围太大,也不能按照定义递推出所有的$SG$函数。尽管如此,我们还是可以先写一个递推程序,看看$SG$函数有没有规律。代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
int SG[maxn];
bool vis[maxn];
int main()
{
    SG[1]=0;
    for (int i = 2; i <= 30; i++)
    {
        memset(vis, 0, sizeof(vis));
        for (int j = 1; j*2<=i; j++)
            vis[SG[i-j]]=true;
        for (int j = 0; ; j++)
            if (!vis[j]) 
            {
                SG[i]=j;
                break;
            }
        printf("%d ", SG[i]);
    }
    printf("\n");
    return 0;
}

打印出来的结果是:
1 0 2 1 3 0 4 2 5 1 6 3 7 0 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15.
我们发现,当$n$为偶数时,$SG(n)=n/2$,但$n$为奇数时似乎没什么规律。但当把$n$为偶数的值全部删除后得到的数列是 0 1 0 2 1 3 0 4 2 5 1 6 3 7...,和原数列是一样的。换句话说,当$n$为奇数时,$SG(n)=SG(n/2)$($n/2$向下取整)。
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL SG(LL x)
{
    return x & 1 ? SG(x >> 1) : (x>>1);
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        LL a, v = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%lld", &a);
            v ^=SG(a);
        }
        printf("%s\n", v ? "YES" : "NO");
    }
    return 0;
}
Last modification:June 25th, 2019 at 11:23 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment