现实砖头

文章
5
资源
0
加入时间
2年10月24天

AtCoder Beginner Contest 209 E - Shiritori(博弈,图)

LINKTakahashi先手(叫做小TTT),Aoki后手(叫做小AAA)每个人轮流说一个单词,这个单词的前三个字母必须等于上一个单词的后三个字母现在问当小TTT说出的第一个单词为sis_isi​时,能否获得胜利??可以O(n2)O(n^2)O(n2)暴力枚举两点间是否有边,但是复杂度太高考虑每个单词只有前三个字母和后三个字母有用把前三个字母浓缩成一个点,后三个字母浓缩成一个点那么单词sis_isi​(设长度为lll)就表示能从{s1,s2,s3}\{s_1,s_2,s_3\}{s1​,s