ACM 福建省省赛 D题 Game

红太狼 2022-06-12 12:21 210阅读 0赞

滴，集训第六天打卡。

今天做的是福建省省赛的重现赛...

可以说是打铁了一下午...

省赛的题目都很灵活啊..dota...lol..yys...

A了三题..感觉最后两题是可以做的但是没写出来...

这里贴D题 Game

Alice and Bob is playing a game.

Each of them has a number. Alice’s number is A, and Bob’s number is B.

Each turn, one player can do one of the following actions on his own number:

1. Flip: Flip the number. Suppose X = 123456 and after flip, X = 654321

2. Divide. X = X/10. Attention all the numbers are integer. For example X=123456 , after this action X become 12345（but not 12345.6）. 0/0=0.

Alice and Bob moves in turn, Alice moves first. Alice can only modify A, Bob can only modify B. If A=B after any player’s action, then Alice win. Otherwise the game keep going on!

Alice wants to win the game, but Bob will try his best to stop Alice.

Suppose Alice and Bob are clever enough, now Alice wants to know whether she can win the game in limited step or the game will never end.

## ![prodesc.gif][] Input ##

First line contains an integer T (1 ≤ T ≤ 10), represents there are T test cases.

For each test case: Two number A and B. 0<=A,B<=10^100000.

## ![prodesc.gif][] Output ##

For each test case, if Alice can win the game, output “Alice”. Otherwise output “Bob”.

## ![20170723110310394][]    ##

## ![prodesc.gif][] Hint ##

For the third sample, Alice flip his number and win the game.

For the last sample, A=B, so Alice win the game immediately even nobody take a move.

题目大意：Alice和Bob玩游戏，有两种操作，一种是翻转字符串，另一种是字符串/10，Alice只能操作第一个字符串，Bob只能操作第二个字符串，当两个字符串完全相同时，Alice获胜。输出获胜者。

我的思路：首先可以想到两种剪枝，当Bob的字符串比Alice的长或出现在Bob字符串中的数字并未出现在Alice字符串中时，Alice不可能获胜。剩下的可以用找子串的方式查找。将Bob的原字串和翻转后的字串在Alice中查找，若可以找到则Alice获胜。这里要将一种特殊情况另外处理，则Bob串为1个0时，不论Alice串是什么都可以获胜，因为/0到最后的结果也是0。

PS：这里找子串用的是KMP算法，其他会超时，将在下一篇博客详细介绍。

#include<stdio.h>
    #include<string.h>
    int f[100001];
    void init(char *b)
    {
        int i,j=0,lb=strlen(b);
        for (i=1;i<lb;i++)
        {
        	while(j&&b[i]!=b[j]) 
    		j=f[j];
            if(b[i]==b[j]) 
      		j++;
         	f[i+1]=j;
        }
    }
    int kmp(char *a,char *b)
    {
    	memset(f,0,sizeof(f));
    	init(b);
        int i,j=0,la=strlen(a),lb=strlen(b);
        for(i=0;i<la;i++)
        {
            while(j&&a[i]!=b[j]) 
    		j=f[j];
            if(a[i]==b[j]) 
    		j++;
            if(j==lb)
    		return i-j+1;
        }
        return -1;
    }
    int main()
    {
    	int  t,i;
    	char m[100001],n[100001],n1[100001];
    	scanf("%d",&t);
    	while(t--){
    		scanf("%s%s",m,n);
    		int lm=strlen(m);
    		int ln=strlen(n);
    		if(ln==1&&n[0]=='0')
    		{
    			puts("Alice");
    			continue;
    		}
    		if(lm<ln)
    		{
    			puts("Bob");
    			continue;
    		}
    		for(i=0;i<ln;i++)
    			n1[i]=n[ln-i-1];
    		n1[ln]='\0';
    		int x=kmp(m,n);
    		int y=kmp(m,n1);
    		if(x==-1&&y==-1)
    		puts("Bob");
    		else 
    		puts("Alice");
    	}
    }

[prodesc.gif]: http://acm.fzu.edu.cn/image/prodesc.gif
[20170723110310394]: /images/20220612/9949f2ed29334a30a3f4b42425de9763.png