Description

牛客练习赛 17 F 【玩游戏】:Link

给定两个串 S 和 T,|S| >= |T|。alice 和 bob 轮流操作串 S,bob 先手。
对于每次操作,alice 或 bob 会选择删掉 S 的第一位或最后一位。当操作以后的串的长度等于 |T| 时,游戏停止。如果停止时的串=T,则 alice 获胜,否则 bob 获胜。问在 alice 和 bob 均采取最优策略的情况下,谁赢?

数据范围:
1 <= |S| <= |T| <= 500000,S和T均由小写字母构成
字符串总长度 <= 1000000
数据组数 <= 1000

Hint

博弈类型的题目,还是需要仔细分析的。

Analysis

bob 先手,他想要让最后的串不等于 T。
既然起始字符串是 S,终止字符串是 T,则要删去 |S|-|T| 个字符(为了方便,下面设 k=|S|-|T|)。

由于这个游戏的条件设定使得后手处于劣势,我们尝试从后手的角度分析……

首先我们知道:如果字符串等于 T 可以满足,最终字符串肯定在起始字符串中间或者中间偏左一个字符或者偏右一个字符。如不然,先手肯定可以率先把这个最终字符串取掉,就没有与 T 相等的可能了。
所以在上述条件满足情况下,后手的最优策略肯定是对称取字符:即对方取左自己就取右,对方取右自己就取左。因为后手要保证左边取了的字符和右边取了的字符数量之差不大于 1,否则和前面一样,先手肯定可以率先把这个最终字符串取掉,就没有与 T 相等的可能了。
知道了这两个“大体策略”,我们只需要对临终状态分析了。

接下来就是最终取到中间,奇偶的问题。分奇偶讨论:

很多题解都说要用 KMP,其实并不需要,只要进行 $\Theta (N)$ 的一次字符串比较即可。

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>

using namespace std;
#define int long long

const int maxlen=1e6+5;
int T;
int len1,len2;
char s[maxlen],t[maxlen];

inline bool check(int x){
    for (int i=0;i<len2;i++) if (x+i>=len1 || s[x+i]!=t[i]) return false;
    return true;
}

signed main(){
    scanf("%lld",&T);
    while (T--){
        scanf("%s%s",s,t);
        len1=strlen(s);
        len2=strlen(t);
        if (len1==len2&&check(0)) {printf("Alice\n");continue;}
        bool ans;
        if ((len1-len2)&1) ans=check((len1-len2)/2)&&check((len1-len2)/2+1);
        else ans=check((len1-len2)/2)||(check((len1-len2)/2-1)&&check((len1-len2)/2+1));
        if (ans) printf("Alice\n"); else printf("Bob\n");
    }
    return 0;
}