【BZOJ-3895】取石子 记忆化搜索 + 博弈

时间：2021-09-17 06:59:15

3895: 取石子

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 263  Solved: 127
[Submit][Status][Discuss]

Description

Alice和Bob两个好朋含友又开始玩取石子了。游戏开始时，有N堆石子
排成一排，然后他们轮流操作（Alice先手），每次操作时从下面的规则中任选一个：
·从某堆石子中取走一个
·合并任意两堆石子
不能操作的人输。Alice想知道，她是否能有必胜策略。

Input

第一行输入T，表示数据组数。
对于每组测试数据，第一行读入N。
接下来N个正整数a1，a2…an，表示每堆石子的数量。

Output

对于每组测试数据，输出一行。
输出YES表示Alice有必胜策略，输出NO表示Alice没有必胜策略。

Sample Input

2
3
1 1 2
2
3 4
3
2 3 5

Sample Output

YES
NO
NO

HINT

100%的数据满足T<=100,  N<=50. ai<=1000

Source

Solution

结论+记忆化搜索

首先，手玩或者感受一下，很好发现：操作总数S=$\sum a_{i}+N-1.......(x>1)$

这样进一步发现，如果S为奇数，显然先手必胜

证明：

难以证明S为奇数先手必胜，考虑证明S为偶数先手必败；

首先如果只有一堆，为奇数，显然先手必胜；

1.如果先手选择合并两堆石子,那么每堆石子的个数依然大于1,x变为奇数.

2.如果先手选择从一堆石子数大于2的堆中拿走一枚石子,那么同上每堆石子个数依然大于1,x变为奇数。

3.如果先手选择从一堆石子数等于2的堆中拿走一枚石子,那么后手可以合并剩下的1枚石子到任意一个堆。那样x的奇偶性不变,每堆石子的个数依然大于

所以这样可以得到对于所有x>1的情况，那么考虑存在x=1的情况

可以分为4种情况考虑：

1.取走某个大小为1的堆中的石子.

2.将某个大小为1的堆和某个大小不为1的堆合并

3.合并两个大小为1的堆.

4.对大小不为1的堆进行合并或者取石子操作.

那么我们用OK[i][j]表示状态，表示仅有1颗石子的有i堆，多颗石子堆的总操作数为S

那么对于上述情况，显然可以利用记忆化搜索转移

考虑数据最大值并不大，所以可以通过所有数据。

Code

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int w=; char ch=getchar();

    while (ch<'' || ch>'') ch=getchar();

    while (ch>='' && ch<='') w=w*+ch-'',ch=getchar();

    return w;

}

#define MAXN 100

#define int register int

bool ok[][],visit[][];

inline bool DFS(int x,int y)

{

    if (!x) return y&;

    if (y==) return DFS(x+,);

    if (visit[x][y]) return ok[x][y];

    visit[x][y]=;

    if (x>= && y && !DFS(x-,y+)) {ok[x][y]=; return ;}

    if (x>= && !y && !DFS(x-,y+)) {ok[x][y]=; return ;}

    if (x && y && !DFS(x-,y+)) {ok[x][y]=; return ;}

    if (y && !DFS(x,y-)) {ok[x][y]=; return ;}

    if (x && !DFS(x-,y)) {ok[x][y]=; return ;}

    ok[x][y]=;

    return ;

}

main()

{

    int N,a[MAXN],T,sum;

    T=read();

    while (T--)

        {

            N=read();

            bool flag=;

            sum=;

            for (int i=; i<=N; i++)

                {

                    a[i]=read(),sum+=a[i];

                    if (a[i]==) flag=;

                }

            if (flag)

                if ((sum+N-)&) puts("YES"); else puts("NO");

            else

                {

                    int x=,y=;

                    for (int i=; i<=N; i++)

                        if (a[i]==) x+=a[i]; else y+=a[i]+;

                    if (DFS(x,max(y-,))) puts("YES"); else puts("NO");

                }

        }

//  return 0;

}

Sunshine学长的Day3T2....

测试的时候，手玩了好几组，发现了结论，于是随口和DCrusher大爷一说

被DCrusher大爷一顿教育

大爷教育我说，随便一个记搜就出来了，然后滚去用10分钟写了个记搜..

手残写错了一个地方，卡成了80.....BeiYu大爷标算卡成50...

DCrusher实力虐场Orz

相关文章