[JZOJ 5912] [NOIP2018模拟10.18] VanUSee 解题报告（KMP+博弈）

题目链接：

https://jzoj.net/senior/#contest/show/2530/2

题目：

众所周知，cqf童鞋对哲学有着深入的理解和认识，并常常将哲学思想应用在实际生活中，例如锻炼摔角技术或者研究化(fa)学。
由于cqf童鞋哲学造诣太过高深，以至于影响到了pty，他们常常给在一块VanUSee。Van的都是一些像“装备回收交易自由”、“开局一条鲲进化全靠吞”、“今晚八点是兄弟就来肝”这样高端大气上档次的著名USee。
有一天他们决定Van一个亲民的USee来和大家分享他们的哲学心路历程
规则是这样的：
   “给定两个串S和T，|S| >= |T|。
   cqf和pty轮流操作串S，cqf先手。
   对于每次操作，cqf或pty会选择删掉S的第一位或最后一位。
   当操作以后的串的长度等于|T|时，游戏停止。
   如果停止时的串=T，则pty获胜，否则cqf获胜。”
   cqf和pty的哲学思维都很强，他们都能采取最优的策略来行动
   作为高级玩家的苏巴先生在一旁观战，他早已看穿了这个USee的本质，当两个串给出的那一瞬间胜负已分，然而不是所有围观者的水平都像苏巴先生那么高，其中也没有五年级的积分小哥，他们又想知道结果，于是围观者们找到了能预见一局围棋接下来40手的你。

题解：

我们简化状态，设当前左边取了l个，右边取了r个，状态定义为r-l

一开始状态为0，每次操作都让它+1或者-1。双方轮流操作，总共操作|S|-|T|次，显然最终状态的奇偶相同

考虑当|S|-|T|是奇数的时候，最后一次操作是先手做，它肯定往不是目标状态走，那么一个位置i在最后一次操作前是目标状态当且仅当它和它-1都是目标状态（目标状态指的是S中i-m+1~i这一段和T完全一样）

于是全部转化为|S|-|T|为偶数的情况

假如 0 是目标状态，那么显然后手会赢，因为无论先手往哪里走后手都可以把他拉回来

如果 0 不是，并且-2 和 2 不全是，那么先手一定会朝不是的那一边走，后手无论如何都没有办法将它拉回到是的那一边了

因此后手会赢当且仅当 0 是目标状态或者-2 和 2 都是目标状态否则都是先手赢

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=1e5+;

int t;

int nxt[N],goal[N<<],pos[N];

char a[N],b[N];

int main()

{

    freopen("vanusee.in","r",stdin);

    freopen("vanusee.out","w",stdout);

    scanf("%d",&t);

    while (t--)

    {

        scanf("%s",a+);

        int n=strlen(a+);

        scanf("%s",b+);

        int m=strlen(b+);

        memset(nxt,,sizeof(nxt));

        memset(goal,,sizeof(goal));

        memset(pos,,sizeof(pos));

        for (int i=,j=;i<=m;i++)

        {

            while (j&&b[j+]!=b[i]) j=nxt[j];

            if (b[j+]==b[i]) ++j;

            nxt[i]=j;

        }

        for (int i=,j=;i<=n;i++)

        {

            while (j&&(b[j+]!=a[i]||j==m)) j=nxt[j];

            if (b[j+]==a[i]) ++j;

            if (j==m) pos[i]=;

        }

        if ((n-m)&) for (int i=;i<=n;i++) goal[n+m-*i++n]=pos[i-]&pos[i];

        else for (int i=;i<=n;i++) goal[n+m-*i+n]=pos[i];

        if (goal[n]||(goal[n-]&&goal[n+])) puts("pty");

        else puts("cqf");

    }

    return ;

}

巴特西

[JZOJ 5912] [NOIP2018模拟10.18] VanUSee 解题报告（KMP+博弈）

题目链接：

题目：

题解：

最新文章

热门文章

巴特西

[JZOJ 5912] [NOIP2018模拟10.18] VanUSee 解题报告 （KMP+博弈）

题目链接：

题目：

题解：

最新文章

热门文章

[JZOJ 5912] [NOIP2018模拟10.18] VanUSee 解题报告（KMP+博弈）