Playing with String

博主： admin
发布时间：2021 年 02 月 28 日
325次浏览
1 条评论
315字数
分类：蓝桥杯

# Playing with String

## 题目

资源限制

时间限制：1.0s  内存限制：256.0MB

问题描述

两个小哥正在玩一个游戏。
　　两个小哥轮流行动，不能操作的人输。
　　游戏开始前裁判买老师会在方格纸上写下一个字符串，每个格子包含一个字母。
　　比如字符串"abacaba"长这样：
![](https://blog.super0.xyz/usr/uploads/2021/02/302768937.png)
　　一个小哥的操作分这么几步：
　　1.这个小哥选择一张纸，我们称上面写着的字符串为t。注意一开始时只有一张可选纸。
　　2.这个小哥选择一个i(1<=i<=|t|)使得存在一个正整数k(0<i-k,i+k<=|t|)满足t[i-1]=t[i+1] and t[i-2]=t[i+2] ... t[i-k]=t[i+k]
　　3.这个小哥以把这张纸的第i个字母的两侧撕开使得这张纸分成3份:t[1~i-1],t[i~i],t[i+1,|t|]如下图：

![](https://blog.super0.xyz/usr/uploads/2021/02/3331334311.png)
　　假如两个小哥都身经百战，使用最优策略，你需要确定胜者是谁。假如先行动的人胜，那么你还需要输出可以帮助这个小哥获胜的第一步行动选择的位置。如果有多个输出最小的那个。

输入格式

仅一行包含买老师选择的字符串s。只包含小写字母。

输出格式

假如后手获胜输出"Second"，否则第一行输出"First"，第二行输出最小的可行策略。

样例输入

abacaba

样例输出

First
2

数据规模和约定

对于25%的数据1<=|s|<=10
　　对于50%的数据1<=|s|<=100
　　对于75%的数据1<=|s|<=1000
　　对于100%的数据1<=|s|<=5000

## 题目分析

分析可知题目满足下列条件:

* 二人的有限且无平局游戏
* 双方拥有完全的资讯且游戏不牵涉运气因素
* 双方可采取的行动是相同的
* 双方的目的相同
* 走最后一步者胜利

很容易联想到SG数，什么是SG数可以参考下面的文章

<div class="inner-content" >
<p class="inser-title">Sprague-Grundy定理</p>
<div class="inster-summary text-muted">
Sprague-Grundy定理问题引入初始时有一个由 + 组成的字符串，例如 ++++++ 。游戏双方轮流进行如...
</div>
</div>
</a>

</div>

</div>

根据 SG 数的定义，一个状态的 SG 数是组成这个状态的各个相互独立的子状态的 SG 数的异或值，状态的 SG 数大于 0 代表胜态；小于 0 代表败态。

而如何划分各个相互独立的子状态成为这道题的重点。

题目的意思是每次从一个回文中心断开，若仅仅分为左右两个子状态，并且递归地求子状态的SG数，势必会超时。

因而需要将母状态分解为更多个相互独立的子状态。倘若不仔细划分，那么代表子状态的各个字符串可能各不相同，进而需要单独求取各个 SG 数。理想情况是各个子状态的 SG 数相互之间有联系，这样便可以节省时间。如何达到呢？试想一串连续的字符串，这个字符串除了首尾每一位都是回文中心，姑且称这样的串为 S 串，例如 `dfhdabababababcfg` 就是一个 S 串，无论从 S 串的哪个回文中心切开，两个子串依旧是 S 串，比如上面的 S 串：

| pos  |     part1      | len1 |     part2     | len2 |
| :--: | :------------: | :--: | :-----------: | :--: |
|  1   |     dfhda      |  0   | a`bababa`bcfg |  6   |
|  2   |     dfhdab     |  0   | b`ababa`bcfg  |  5   |
|  3   |   dfhda`b`a    |  1   |  a`baba`bcfg  |  4   |
|  4   |   dfhda`ba`b   |  2   |  b`aba`bcfg   |  3   |
|  5   |  dfhda`bab`a   |  3   |   a`ba`bcfg   |  2   |
|  6   |  dfhda`baba`b  |  4   |   b`a`bcfg    |  1   |
|  7   | dfhda`babab`a  |  5   |     abcfg     |  0   |
|  8   | dfhda`bababa`b |  6   |     bcfg      |  0   |

如果用 $sg(n)$ 表示长度为回文中心长度为 $n$ 的 S 串的 SG 数，那么当 $n\geq3$ 时：
$$
sg(n)=mex(\{sg(0)\oplus sg(n-2)\}\cup\{sg(k)\oplus sg(n-3-k)|k=0,...,\lfloor\frac{n-1}2\rfloor\})
$$

显然 S 串的 SG 数仅与回文中心的长度有关，并且可以通过自底向上的动态规划求出。

求一个非 S 串的 SG 数，只需要将这个串划分为若干个相互独立的 S 串，再将其 SG数异或即可。

## 代码

### C++

```cpp
#include<iostream>
#include<string>
using namespace std;

#define N 5004

//sg[i]代表回文中心长度为i的S串的SG数
int sg[N];

bool mex[16];

string s;

void init() {
	sg[0] = 0;
	sg[1] = 1;
	sg[2] = 1;
	//动态规划，自底向上求各个sg值
	for (int i = 3; i < N; ++i) {
		fill(mex, mex + 16, 0);//mex初始化为全0
		mex[sg[0] ^ sg[i - 2]] = 1;
		for (int k = 0; k < (i - 1) / 2; ++k)
			mex[sg[k] ^ sg[i - 3 - k]] = 1;
		int j = 0;
		while (mex[j])++j;
		sg[i] = j;
	}
}

//获取串s[l:r]的SG数
int getsg(int l, int r) {
	int ans = 0;
	int i = l + 1;
	//分解成一个个S串
	//s[l:r]的SG数就是各个S串的异或值
	while (i < r - 1) {
		if (s[i - 1] == s[i + 1]) {
			int now = 1;
			++i;
			while (i < r - 1 && s[i - 1] == s[i + 1]) {
				++now;
				++i;
			}
			ans ^= sg[now];
		}
		++i;
	}
	return ans;
}

int main() {
	init();
	cin >> s;
	int n = s.length();
	int index = 0;
	for (int i = 1; i < n - 1; ++i)
		if (s[i - 1] == s[i + 1] && (getsg(0, i) ^ getsg(i + 1, n)) == 0) {
			index = i + 1;
			break;
		}
	
	if (index)
		cout << "First\n" << index;
	else
		cout << "Second";
}
```

### Python

```python
N = 5004
sg = [0]*N
sg[0] = 0
sg[1] = 1
sg[2] = 1

for i in range(3, N):
    z = [0]*16
    z[sg[0]^sg[i-2]] = 1
    for k in range(int((i-1)/2)):
        z[sg[k]^sg[i-3-k]] = 1
    sg[i] = z.index(0)

s = input()
n = len(s)

def getsg(l, r):
    ans = 0
    i = l+1
    while i < r-1:
        if s[i-1] == s[i+1]:
            now = 1
            i += 1
            print(s)
            while i < r-1 and s[i-1] == s[i+1]:
                now += 1
                i += 1
            ans ^= sg[now]
        i += 1
    return ans

index = -1
for i in range(1, n-1):
    if s[i-1] == s[i+1] and getsg(0,i)^getsg(i+1,n)==0:
        index = i+1
        break

if index>0:
    print("First")
    print(index)
else:
    print("Second")

```

![][1]
同样的思路，C++满分而Python超时。

[1]: https://blog.super0.xyz/usr/uploads/2021/02/510367339.png

最后修改：2021 年 03 月 04 日 06 : 08 PM

如果觉得我的文章对你有用，请随意赞赏