TheNumberGame

作者：欧阳思琦

关键词：子串 字符串匹配

题目简述

Manao 有一个整数$A$，他的朋友有一个整数$B$（$A,B$都是$10$进制数）。他们发明了一个游戏，两个人轮流操作，每个人每轮可以将他的数翻转或者除以$10$向下取整。如果不超过$1000$次操作（Manao的$500$次+朋友的$500$次）后两个数相等了，那么Manao赢，否则Manao输。

给你$A,B$，假设两个玩家都是采取最佳策略进行游戏，问Manao最后会赢还是会输。

$A,B \in [1, 10^9),且A和B的字符串表示中没有0$

算法

先给出结论：只要$B$或者$B$的翻转（记为$B'$）是$A$的一个子串，那么Manao赢，否则Manao输。

证明的话也很简单，因为$A$通过这两个操作（相当与只能在两边删除字符），能构成的只有$A$的子串或者子串的翻转。具体操作方法就是根据当前$B$的状态翻转删除，保持$B~or~B'$是$A$的子串即可（可以将$0$看成任意字符串的子串），因为字符串的长度只有$9$，$B$如果不变短就必定会有一个时刻$B~or~B'=A$，在$1000$步以内总是能够决出胜负的。

因为字符串长度很短，暴力$O(n^2)$或者KMP$O(n)$都是可以的。