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();
}