对联

NC233102. 对联

描述

林间朝露，云顶晚霞。

正所谓
ac自动机fail树上建可持久化线段树
后缀自动机next指针dag图上求sg函数

小红和紫准备玩一个游戏。她们拿到了一个只包含小写字母的字符串 $s$ 。两人轮流将一个小写字母添加到一个新串t的结尾，必须保证t时刻都是s的一个子序列。谁先无法操作则输掉游戏。t初始是一个空串。小红先手添加，假设两人都足够聪明，请问谁最终能获得胜利？

子序列的定义：若一个字符串 $a$ 删除部分字符（也可以不删）后得到字符串 $b$ ，那么称 $b$ 是 $a$ 的子序列。

输入描述

一个只包含小写字母字符串 
字符串长度不超过

输出描述

如果小红获得胜利，则输出 "kou"
否则输出 "yukari"

示例1

输入:

aba

输出:

yukari

说明:

无论小红第一个添加的是'a'还是'b'，紫在后面添加一个'a'即可获得胜利。

示例2

输入:

aaa

输出:

kou

说明:

小红第一个添加'a' ，紫再添加'a' ，小红添加'a' 。此时紫无法操作。所以小红获胜。

示例3

输入:

aa

输出:

yukari

说明:

小红第一个添加'a' ，紫再添加'a' 。小红无法操作，紫获胜。

示例4

输入:

ab

输出:

kou

说明:

若小红先添加'a'则必败。但小红可以先添加 'b' ，这样紫就无法操作了，小红获胜。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 9ms, 内存消耗: 816K, 提交时间: 2022-01-31 21:12:34

#include<iostream> 
int main(){std::string s;std::cin>>s;int i,j=s.size()-1;for(i=j-1;i>=0;i--)if(s[i]==s[j])j=i-1,i=j;puts(j==-1?"yukari":"kou");}

Python3 解法, 执行用时: 141ms, 内存消耗: 5132K, 提交时间: 2022-02-06 15:22:49

s,i,j=input(),0,1
while j<len(s):
    if s[i] == s[j]:
        i=j+1
        j=i
    j+=1
print('yukari'if i==len(s)else'kou')

详情