【CSU-2056】解题报告（思维，KMP，去0）

原始题目

2056: a simple game

  • Time Limit: 1 Sec
  • Memory Limit: 128 Mb
  • Submitted: 412
  • Solved: 73

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，B的整数看作字符串，那两种操作就是反转，去尾。 - 两人都采取最优策略，考虑小A什么时候输，即B可以无限翻转而A永远不能将自己的串通过两种操作达到B字符串的状态。 - 那么当B的串或B反转后的串是A的子串时，A就是必赢的 - 考虑一些特殊情况。 - 由于末尾0的存在会在反转中自动去掉，所以要提前预处理一下，把末尾0去掉 - 正方各一次KMP即可。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//#include <bits/stdc++.h>
#include <cstdio> 
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <vector>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define PI acos((double)-1)
#define E exp(double(1))
#define K 1000000+9
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define ms(x,a) memset((x),(a),sizeof(a))
const int maxn=1e6+5;
int nt[maxn],nt2[maxn] ;
char a[maxn],b[maxn],b2[maxn];
int n,m;
//参数为模板串和next数组
//字符串均从下标0开始
void kmpGetNext(char *s,int *Next)
{
    Next[0]=0;
    int len=strlen(s);
    for(int i=1,j=0;i<len;i++)
    {
        while(j&&s[i]!=s[j]) j=Next[j];
        if(s[i]==s[j]) j++;
        Next[i+1]=j;
    }
//    Next[len]=0;
}
int kmp(char *ss,char *s,int *Next)
{
    kmpGetNext(s,Next);
//  调试输出Next数组
//	int len=strlen(s);
//	for(int i=0;i<=len;i++)
//		cout<<Next[i]<<" ";
//	cout<<endl; 

    int ans=0;
    int len1=strlen(ss);
    int len2=strlen(s);
    for(int i=0,j=0;i<len1;i++)
    {
        while(j&&ss[i]!=s[j])j=Next[j];
        if(ss[i]==s[j]) j++;
        if(j==len2){
        	return 1;
		}
           
    }
    return 0;
//	return ans;
}

int main(void)
{
//	ios::sync_with_stdio(false);
    int t;
    scanf("%d",&t); 
    while(t--)
    {
    	memset(nt,0,sizeof(nt));
    	memset(nt2,0,sizeof(nt2));
		scanf("%s",a);
    	scanf("%s",b);
    	int len1=strlen(a);
    	int len2=strlen(b);
    	while (a[len1-1] == '0'&&len1 > 1)
			a[--len1] = '\0';
		while (b[len2-1] == '0'&&len2 > 1)
			b[--len2] = '\0';
		rep(i,0,len2) b2[i]=b[len2-1-i];
		b2[len2]='\0';
		
//		printf("b1=  %s\nb2=  %s\n",b,b2);
		if(kmp(a,b,nt)||kmp(a,b2,nt2)) printf("Yes\n");
		else printf("No\n");
    }

    return 0;
}

收获与反思

  • 思维+KMP