CSU 2056 a simple game （正反进行KMP）超级好题！！！

时间：2024-06-06 21:05:32

Description

这一天，小A和小B在玩一个游戏，他俩每人都有一个整数，然后两人轮流对他们的整数进行操作，每次在下列两个操作任选一个：
（1）对整数进行翻转，如1234翻转成4321 ，1200翻转成21
（2）将整数除以10，如1234/10=123，1/10=0
当操作过程中出现a==b时，则小A就赢了，而操作一直进行下去或不能使a==b则算小B赢。
现在小A求助于你，想让你帮他在知道两人的整数时小A能不能赢，假设每次都是小A先手，并且两人都是采取最优策略

Input

首先输入T（T <= 100），表示有T组数据，然后接下来有T行，每行有两个整数a,b（0 <= a,b < 10100000)

Output

有T行，当小A赢了则输出"Yes",否则输出"No"

Sample Input

4

1234 123

123 321

1234 12345

123 123

Sample Output

Yes

Yes

No

Yes

Hint

Source

Author

wsf

分析：

每次都是A先手，且两个人每次都是采取的最优策略！！！

所有他们采取的都是对自己有利的策略

这句话需要好好理解

两个人都只可以操作自己的数

两个操作一个是翻转，一个是除以10

一开始需要将二者的后导0全部去掉

是因为后导0都可以通过除10或者翻转消去，没有意义

便于进行kmp，所以需要消去

很奇妙

还有影响匹配

先拿着B当作模板串，A当作文本串进行KMP匹配，然后将B翻转，然后再将翻转后的B当做模板串，A当作文本串进行KMP

为什么B需要翻转然后再进行一个KMP呢？

因为有翻转操作呀

只要这两个KMP中有一次匹配成功了，那么A是可以赢的，输出yes

注意：

1.一开始去除后导0的时候，需要保证串的长度至少大于1

比如输入的一个串是0的话，你消去了这仅有的1个0，你还怎么比较啊

2.翻转操作便捷函数：reverse（moban,moban+l)!!!!,超级方便有木有

code：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<memory>

#include<algorithm>

using namespace std;

#define max_v 1234567

char moban[max_v];

char wenben[max_v];

int next1[max_v];

int sum;

int flag;

void getnext(char s[],int m)

{

    next1[]=;

    next1[]=;

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

    {

        int j=next1[i];

        while(j&&s[i]!=s[j])

            j=next1[j];

        if(s[i]==s[j])

            next1[i+]=j+;

        else

            next1[i+]=;

    }

}

void kmp(char ss[],char s[],int n,int m)

{

    getnext(s,m);

    int j=;

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

    {

        while(j&&s[j]!=ss[i])

            j=next1[j];

        if(s[j]==ss[i])

            j++;

        if(j==m)

        {

            flag=;

        }

    }

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%s%s",wenben,moban);

        flag=;

        int L=strlen(wenben);

        int l=strlen(moban);

        while(wenben[L-]==''&&L>)

            wenben[L--]='\0';

        while(moban[l-]==''&&l>)

            moban[l--]='\0';

        kmp(wenben,moban,L,l);

        reverse(moban,moban+l);

        kmp(wenben,moban,L,l);

        if(flag)

            printf("Yes\n");

        else

            printf("No\n");

    }

    return ;

}

相关文章