2020 Multi-University Training Contest 1

本文总阅读量次

7.20 卡字符串的杭电1

1004-Distinct Sub-palindromes

题意

计算具有最少回文子串且长度为 $n$ 的字符串数量

思路

  1. 当 $n=1$ 时，答案为 $26$
  2. 当 $n=2$ 时，答案为 $26^2$
  3. 当 $n>3$ 时，最少的回文子串数为 $3$ ，即 $abcabcabc$ 的循环，所以此时答案为 $26 * 25 * 24$
  4. 当 $n=3$ 时，虽然最少的回文子串数也为3，但此时不论子串内部怎么排，其最少回文子串数均为3，故此时的答案为 $26^3$

1011-Minimum Index

题意

给定一个串 $s$ ，求 $s$ 所有前缀的后缀序最小的下标的 $1112$ 进制值

思路

题解是用 $Lyndon$ 。作为一个乱搞选手，考虑乱搞（？）。

最初步的想法是：如果当前位比上一个的结果大，一直减到前面连续小的第一个，比如 $baaab$ 减到 $2$（下标 $1$ 开始）；如果当前位比之前的小，当前位一定是最优的；如果当前位和之前的一样，优先取当前位，参考 $aaa$ 。

需要记录位置，考虑双端队列的形式。如果当前位置较之前优，之前的就不需考虑；如果是连续的一段相同且最小的值，直接记录位置；遇到第一个不相同且较大的值时，一定是连续段的最前一个最优，往前更新。

$upd$ ：看了 $Lyndon$ 心态崩了，感觉其实差不多呜呜呜呜呜呜呜

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
char s[maxn];
int pos[maxn];
int solve(){
    scs(s+1); int len=strlen(s+1);
    int cur=0,ans=0,pow=1,pre=1;
    rep(i,1,len+1){
        pos[++cur]=i;
        while(cur>pre&&s[i]>s[i-(pos[cur]-pos[cur-1])]) cur--;
        while(cur>pre&&s[i]<s[i-(pos[pre+1]-pos[pre])]) pre++;
        // 其实核心就这两句qwq
        // 首先是每次都要处理的 到每一位都需要更新之前的状态
        // 有点难讲qwq 通过举例子来吧 比如aabaaab
        // 处理到第一个b时 减到前面连续小的第一个 当前答案为1
        // 处理到第二个b时 通过每次跳pos[cur]-pos[cur-1]来判断是否还在连续的状态
        ans+=1ll*pow*pos[cur]%mod;
        if(ans>=mod) ans-=mod;
        pow=1112ll*pow%mod;
    } return pf("%d\n",ans);
}
int main(){
    int _; sc(_); while(_--) solve();
}