【博弈论】春联

博客主页: https://blog.csdn.net/qq_50285142欢迎点赞⭐️收藏⭐️❤️关注❤️留言  如有错误，敬请指正 一看一温习，一码一收获

今天是2022年农历大年初一，祝大家虎年快乐！

非常遗憾2022农历新年以题解开局

题目链接：
https://ac.nowcoder.com/acm/contest/28335/E

红与紫两人玩游戏，游戏如下：
一个包含小写字母的字符串，红在一个空字符串末尾添加一个字母，要求形成的新字符串为给出字符串的子序列，然后紫选一个字母在该新字符串末尾添加，两个人轮流，直到不能操作则输。

两个人轮流玩游戏一般就是博弈论的题目。

博弈论就要想到sg函数，就要想到要讨论必胜与必败的情况。
必胜必败一般从后面开始倒推。
那么本题：
假设一个字符串：bcabcdebceac
选中最后一个字母必然是必胜状态（用[]表示）：bcabcdecea[c]

那么到前面最近的相同字母的区间为必败状态(用()表示)：bcabcde(cea)[c]

然后必败状态前面的字母必然为必胜状态：bcabcde[b](cea)[c]
依次类推：：bc[a](bcde)[b](cea)[c],因为前面的[a]必胜区间没有相同的a与其对应，注意bc不考虑作为必败区间

可以发现只要先手选择必胜区间，那么后手的选择一定在必败区间。

如何判断胜负：
只要看能形成区间的第一个字母在什么区间，如果在必胜区间，那么红胜；若在必败区间，则紫胜。

代码：
j代表必胜区间的下标
i是遍历必败区间的下标，当访问到有字母等于必胜区间的字母，j就开始变为i-1(前一个必胜区间的下标)

#include
using namespace std;
const int N = 1e5+5;

int main()
{
	string s;
	cin>>s;
	int j = s.size()-1;
	for(int i=j-1;i>=0;i--)
	{
		if(s[j] == s[i])
		{
			j = i - 1;
			i = j;
		}
	}
	if(j == -1) cout<<"yukarin";
	else cout<<"koun";
	return 0;
 } 

C++ STL详解，超全总结(快速入门STL) 李【期末复习】c++知识点大回顾，八篇文章让你永不破防（一）区间贡献问题习题详解