[THUPC2018]绿绿和串串 题解

题目链接

题目大意

​ 太长了,自己看原题面吧。

题目解法

​ 考虑dp求解。$f_i$ 表示位置 $i$ 是否合法,显然 $f_{|S|}=1$。然后考虑每个位置 $j$ 是否合法,如果把 $S[1…j]$这一段翻折过去能够匹配上$S[j…2j-1]$,并且 $f_{2j-1}$合法(或者已经翻折出去了,即 $2j-1> n$)的话,则 $f_i$合法。

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define maxn 6000100
#define mod 1000000007
typedef long long ll;
using namespace std;
int n;
int h1[maxn],h2[maxn],power1[maxn],power2[maxn];
char s[maxn];
int vis[maxn];
void init() {
std::memset(vis, 0, sizeof(vis));
power1[0]=power2[0]=1;
h1[0]=h2[0]=0;
for(int i=1; i<=n; i++){
h1[i]=((ll)h1[i-1]*11+s[i]-'0'+1)%mod;
power1[i]=(ll)power1[i-1]*11%mod;
h2[i]=((ll)h2[i-1]*11+s[n-i+1]-'0'+1)%mod;
}
}
int cal1(int l,int r){
return ((h1[r]-(ll)h1[l-1]*power1[r-l+1])%mod+mod)%mod;
}int cal2(int l,int r){
return ((h2[r]-(ll)h2[l-1]*power1[r-l+1])%mod+mod)%mod;
}

int solve() {
init(); vis[n]=1;
for (int i = n-1;i>=1; --i) {
int length=std::min(n-i, i-1);
if (cal1(i-length, i)==cal2(n-i-length+1, n-i+1)&&(i-1+i>=n||vis[i*2-1])) {
vis[i]=1;
}
}for (int i=1;i<=n;++i) {
if (vis[i]) printf("%d ", i);
}printf("\n");
} int main() {
int t; scanf("%d", &t);
while (t--) {
scanf("%s", s+1);
n = strlen(s+1);
solve();
}
}