牛客练习赛 17 F 玩游戏 题解：神奇的博弈

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 相等的可能了。 知道了这两个“大体策略”，我们只需要对临终状态分析了。

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

• 假设 k 是奇数：那么最后一步肯定是先手操作，也就是不想让两字符串相等的人。后手的最优操作是，先手怎么取，后手就从另一端对称取。那么最后要让字符串相等，必须让以下两种情况都满足，这样最后一步才无论怎么取都会相等；否则就不会相等：
  • 左边取了 [k/2] 个，右边取了 [k/2]+1 个，最后的字符串等于 T；
  • 左边取了 [k/2]+1 个，右边取了 [k/2] 个，最后的字符串等于 T；
• 假设 k 是偶数：最后一步后手操作，后手赢又有几种情况：
  • 左边和右边都取了 [k/2] 个，最后字符串等于 T；
  • 左边 [k/2]-1 个，右边 [k/2]+1 个，最后的字符串等于 T；并且左边 [k/2]+1 右边 [k/2]-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;
}