7.20 卡字符串的杭电1
1004-Distinct Sub-palindromes
题意
计算具有最少回文子串且长度为 $n$ 的字符串数量
思路
- 当 $n=1$ 时,答案为 $26$
- 当 $n=2$ 时,答案为 $26^2$
- 当 $n>3$ 时,最少的回文子串数为 $3$ ,即 $abcabcabc$ 的循环,所以此时答案为 $26 * 25 * 24$
- 当 $n=3$ 时,虽然最少的回文子串数也为3,但此时不论子串内部怎么排,其最少回文子串数均为3,故此时的答案为 $26^3$
1011-Minimum Index
题意
给定一个串 $s$ ,求 $s$ 所有前缀的后缀序最小的下标的 $1112$ 进制值
思路
题解是用 $Lyndon$ 。作为一个乱搞选手,考虑乱搞(?)。
最初步的想法是:如果当前位比上一个的结果大,一直减到前面连续小的第一个,比如 $baaab$ 减到 $2$(下标 $1$ 开始);如果当前位比之前的小,当前位一定是最优的;如果当前位和之前的一样,优先取当前位,参考 $aaa$ 。
需要记录位置,考虑双端队列的形式。如果当前位置较之前优,之前的就不需考虑;如果是连续的一段相同且最小的值,直接记录位置;遇到第一个不相同且较大的值时,一定是连续段的最前一个最优,往前更新。
$upd$ :看了 $Lyndon$ 心态崩了,感觉其实差不多呜呜呜呜呜呜呜
代码
1 |
|