| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 8/13 | O | O | O | . | O | . | O | O | . | . | O | O | . |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
密码：buaa
A
题目描述
问长度为$n$，给定的$m$个字符串都为$a$的连续子串的字符串$a$有多少种。
$1\leq n\leq 25,0\leq m\leq 10$
解题思路
看到$n,m$很小（$1<<10=1024$），很容易想到建立$AC$自动机进行
爆搜记忆化搜索。AC代码
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
typedef long long ll;
using namespace std;
char a[25];
int n,m,trie[N][26],fail[N],sign[N],tot;
void add(int x){
int now=0,i;
for(i=0;a[i];i++){
int p=a[i]-'a';
if(!trie[now][p])trie[now][p]=++tot;
now=trie[now][p];
}
sign[now]|=1<<x;
}
queue<int>Q;
void build(){
int i,pos;
for(i=0;i<26;i++)if(trie[0][i])Q.push(trie[0][i]);
while(!Q.empty()){
pos=Q.front();Q.pop();
for(i=0;i<26;i++){
if(trie[pos][i]){
fail[trie[pos][i]]=trie[fail[pos]][i];
Q.push(trie[pos][i]);
sign[trie[pos][i]]|=sign[fail[trie[pos][i]]];
}else trie[pos][i]=trie[fail[pos]][i];
}
}
}
ll f[27][N][1030];//f[len][pos][state]
ll dp(int len,int state,int pos){
ll &ans=f[len][pos][state];
if(~ans)return ans;
if(len==n)return ans=state==(1<<m)-1;
int i;
ans=0;
for(i=0;i<26;i++)
ans+=dp(len+1,state|sign[trie[pos][i]],trie[pos][i]);
return ans;
}
char out[30];
void print(int len,int state,int pos){
if(len==n){
fwrite(out,sizeof(out[0]),n,stdout);
puts("");
return;
}
int i;
for(i=0;i<26;i++){
out[len]=i+'a';
if(f[len+1][trie[pos][i]][state|sign[trie[pos][i]]]>0)
print(len+1,state|sign[trie[pos][i]],trie[pos][i]);
}
}
int main(){
int i,t=0;
while(~scanf("%d%d",&n,&m)&&(n|m)){
t++;
memset(trie,0,sizeof(trie));
memset(fail,0,sizeof(fail));
memset(f,-1,sizeof(f));
memset(sign,0,sizeof(sign));
tot=0;
for(i=0;i<m;i++)scanf("%s",a),add(i);
build();
ll ans=dp(0,0,0);
printf("Case %d: %lld suspects\n",t,ans);
if(ans<=42)print(0,0,0);
}
return 0;
}
B
题目描述
给定一个字符串的马拉车$len$数组和后缀数组$sa$，求还原字典序最小的原串。
解题思路
主要思路是，把每一个排名的数值视为一个点，具有相同的字符的多个位置用并查集缩成一个点，不等的之间连接边（这里从对应字符大的点到小的点连边）。有一点有趣的性质是，$sa$数组所对应的字符必然是单调不减的，于是可以设法找出每一个断点的位置。
所以根据马拉车$len$数组模仿跑一边马拉车，缩点连边，最后用$sa$数组进一步求出解。
这题的麻烦之处就在于各种地方不存在的判断。
具体的实现过程：
设$suffix(x)$为$s[x…n]$。
$Case 1$：
$s[sa[i]]\leq s[sa[i+1]]$，而当等号不可能成立时必然有$rk[sa[i]+1]>rk[sa[i+1]+1]$，此时需要连接$i+1,i$。
$Case 2$：
跑马拉车回文串时，每次仍然只向外扩展未知字符并缩点。可以证明的是，这样保证了线性的复杂度，而并不会影响解的正确性。
每次向外扩展的时候，把左右两点缩成一点。
扩展完之后，把左右两点连边，并注意扩展的位置的合理性。
$Case 3$：
最后从$rk$低到高填字符，并延必需边寻找最小可用字符，并判断点所处集合的合理性。
AC代码-人傻自带大常数，4792ms
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
typedef long long ll;
using namespace std;
int sa[N],rk[N],len[N<<1];
char s[N];
int hd[N],cnt,f[N];
int find(int x){return x==f[x]?f[x]:f[x]=find(f[x]);}
struct Edge{
int e,n;
}e[N<<2];
void add(int a,int b){e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;}
inline void scan(int &x){
register int ch;
while((ch=getchar())<'0'||ch>'9');
for(x=ch-'0';(ch=getchar())>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch-'0'));
}
int n,mr,mid;
int solve(){
mr=1;
int i,j,k,l,r,now,u,v;
for(i=2;i<=n<<1;i++){
if(mr>i)now=min(mr-i,len[(mid<<1)-i]+1);
else now=0;
if(now>len[i]+1||i-len[i]<1||i+len[i]>(n<<1|1))return 0;
l=i-now;r=i+now;
for(;now<=len[i];now++,l--,r++){
if((l&1)||l>=r)continue;
u=rk[l>>1],v=rk[r>>1];
if(u>v)u^=v^=u^=v;
u=find(u),v=find(v);
while(u<v){
for(j=hd[u];j;j=e[j].n)if(u<e[j].e)return 0;
v=f[v]=find(v-1);
}
}
if(l>=2&&r<=n<<1&&(l&1)==0){
u=rk[l>>1],v=rk[r>>1];
if(u>v)add(u,v);
else add(v,u);
}else if(l&1)return 0;
if(mr<i+now)mr=i+now,mid=i;
}
char mn='a',cur;
for(i=1;i<=n;i++){
cur=mn;
j=i+1;
while(j<=n&&find(i)==find(j))j++;
for(k=i;k<j;k++){
for(l=hd[k];l;l=e[l].n){
if(cur<=s[sa[e[l].e]])cur=s[sa[e[l].e]]+1;
if(find(e[l].e)==find(i))return 0;
}
}
if(cur>'z')return 0;
while(i<j)s[sa[i++]]=cur;
mn=cur;i--;
}
s[n+1]='\0';
return 1;
}
int main(){
int i,T,cas=0;
scan(T);
while(T--){
cnt=0;
scan(n);
memset(hd,0,sizeof(int)*(n+1));
for(i=1;i<=n;i++){
scan(sa[i]);sa[i]++;
rk[sa[i]]=i;
f[i]=i;
}
rk[n+1]=-1;
for(i=2;i<=n;i++)if(rk[sa[i-1]+1]>rk[sa[i]+1])add(i,i-1);
len[0]=-1;len[1]=len[n<<1|1]=0;
for(i=2;i<=n<<1;i++)scan(len[i]);
printf("Case #%d: ",++cas);
if(solve())printf("%s\n",s+1);
else printf("Wrong calculation!\n");
}
return 0;
}
然后看到$tls$也是这么做的，但是才跑了$500ms$，$%%%$
AC代码-tls,502ms
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
const int maxn=100010,maxs=26;
int t,n,sa[maxn],rk[maxn],ma[maxn<<1],tot,lnk[maxn],fa[maxn];
char str[maxn];
struct Edge{
int nxt,v;
}e[maxn<<2];
inline void scan(int &x){
register int ch;
while((ch=getchar())<'0'||ch>'9');
for(x=ch-'0';(ch=getchar())>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch-'0'));
}
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
scan(t);
for(int Case=1;Case<=t;++Case){
scan(n);
tot=0;
memset(lnk,-1,n*sizeof(int));
for(int i=0;i<n;++i){
scan(sa[i]);
rk[sa[i]]=i;
fa[i]=i;
}
rk[n]=-1;
for(int i=1;i<n;++i)
if(rk[sa[i-1]+1]>rk[sa[i]+1]){
e[tot]=(Edge){lnk[i],i-1};
lnk[i]=tot++;
}
ma[0]=-1;
ma[1]=ma[n<<1|1]=0;
for(int i=2;i<=n<<1;++i)
scan(ma[i]);
bool flag=1;
for(int i=2,mx=1,id=1;i<=n<<1&&flag;++i){
int cur=mx>i?std::min(mx-i,ma[(id<<1)-i]+1):0,pL,pR;
flag&=cur<=ma[i]+1&&i-ma[i]>0&&i+ma[i]<n+1<<1;
for(pL=i-cur,pR=i+cur;cur<=ma[i]&&flag;++cur,--pL,++pR)
if((~pL&1)&&pL<pR){
int u=rk[(pL>>1)-1],v=rk[(pR>>1)-1];
if(u>v)
std::swap(u,v);
for(u=find(u),v=find(v);u<v&&flag;v=find(v)){
for(int it=lnk[v];it!=-1&&flag;it=e[it].nxt)
flag&=e[it].v<u;
fa[v]=find(v-1);
}
}
if((flag&=(~pL&1))&&pL>=2&&pR<=n<<1){
pL=rk[(pL>>1)-1];
pR=rk[(pR>>1)-1];
if(pL>pR)
std::swap(pL,pR);
e[tot]=(Edge){lnk[pR],pL};
lnk[pR]=tot++;
}
if(mx<i+cur){
mx=i+cur;
id=i;
}
}
char last='a';
for(int i=0,j=0;i<n&&flag;i=j){
char cur=last;
for(++j;j<n&&find(i)==find(j);++j);
for(int k=i;k<j&&flag;++k)
for(int it=lnk[k];it!=-1&&flag;it=e[it].nxt)
if(find(e[it].v)==find(i))
flag=0;
else if(cur<=str[sa[e[it].v]])
cur=str[sa[e[it].v]]+1;
if(cur>'z')
flag=0;
else{
for( ;i<j;++i)
str[sa[i]]=cur;
last=cur;
}
}
str[n]='\0';
if(!flag)
printf("Case #%d: Wrong calculation!\n",Case);
else
printf("Case #%d: %s\n",Case,str);
}
return 0;
}
C
题目描述
如果一个长度为$n$的字符串$a$满足：对于任意$0< i\leq |n|$，$a_i$属于集合$S_i$，则其是一个合法的串。
给定字符串$a$，集合$S_i(1\leq i\leq n)$，按读入顺序输出$a$中所有合法的连续子串。
$1\leq n \leq 1000,|a|\leq 5\times 10^6$。
解题思路
看起来$|a|$比较大，似乎应当用一种比较快速、尽量能递推解决的算法解决。
构造一个$bitset$数组$b$，存放每一个元素$x$允许出现的位置$pos$，即对于每一个合法的位置，有$b[x][pos]=1$。
再构造一个$bitset$存储当前匹配状态$now$，每一次$now$左移$1$（代表开始匹配下一位），最低位设置成$1$（还未判断匹配情况），位运算进行匹配（与对应$b[x]$进行与运算），则如果$now$的第$n$位为$1$，就说明已经匹配成功，输出即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
char c[5000001],t;
bitset<1001>b[11],now;
int main(){
int i,n,k,a;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&k);
while(k--)scanf("%d",&a),b[a][i]=1;
}
scanf("%s",c);
for(i=0;c[i];i++){
((now<<=1).set(0))&=b[c[i]-'0'];
if(now[n-1])fwrite(c+i-n+1,sizeof(c[0]),n,stdout),putchar('\n');
}
return 0;
}
D
题目描述
解题思路
AC代码
2
E
题目描述
给一个长度$1\leq N\leq 5\times 10^5$的串。每次从头扯下来一个字符粘到尾端，进行$k$次这样的操作（$0\leq k<N$），输出每次操作后串中最长回文子串的长度。
解题思路
首先想到的办法是，建立一棵回文树，每次添加一个节点，并用一个堆保存当前回文串的位置、长度、回文树中的节点标号，每次被弹出堆的时候，沿$fail$边走并入堆。然而很不幸的是，这样无法保证时间复杂度，$26$个点只过了$18$个，剩下的都$T$掉了。
TLE代码
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using namespace std;
typedef struct node{
int xb,len,i;
bool operator<(const node&a)const{return len<a.len;}
}nd;
priority_queue<nd>Q;
int length;
struct PT{
int tr[N][M],fail[N],len[N];
int tot,s[N],n,last,i;
int newnode(int l){
for(i=0;i<M;i++)tr[tot][i]=0;
len[tot]=l;
return tot++;
}
void init(){
n=last=tot=0;
newnode(0);newnode(-1);
s[0]=-1;
fail[0]=1;
}
int getfail(int po,int p){
while(s[n-len[p]-1]!=s[n]||len[p]+2>length)p=fail[p];
return p;
}
void add(int po,int p){
s[++n]=p;
int cur;
cur=getfail(po,last);
last=fail[cur];
if(!tr[cur][p]){
int now=newnode(len[cur]+2),temp=getfail(po,fail[cur]);
fail[now]=tr[temp][p];
tr[cur][p]=now;
}
last=tr[cur][p];
Q.push((nd){tr[cur][p],len[tr[cur][p]],po});
}
}p;
char a[N];
int main(){
int i;
p.init();
scanf("%d",&length);
scanf("%s",a);
for(i=0;a[i];i++)
p.add(i,a[i]-'a');
for(i=0;a[i];i++){
nd t=Q.top();
printf("%d\n",Q.top().len);
p.add(i+length,a[i]-'a');
t=Q.top();
while(t.i-t.len<i){
Q.pop();
while(-p.len[p.fail[t.xb]]+t.i<i&&t.len>1)
t=(nd){p.fail[t.xb],p.len[p.fail[t.xb]],t.i};
if(t.len>1)Q.push((nd){p.fail[t.xb],p.len[p.fail[t.xb]],t.i});
if(Q.empty())break;
t=Q.top();
}
}
return 0;
}
过后，想到了一种暴力办法：直接复制串到串的后面，跑一遍马拉车，记录下以某个点为中心的奇数、偶数回文串的长度，分奇偶解决，解决的时候长度从大到小、位置从大到小枚举，记录只最靠后的超出范围的回文串的中心位置$full$，每次根据$full$和$set$中的合法答案更新答案即可。
发现从前往后一上来只能枚举到一半才能之后的保证每次的扩展合理，故反转字符串再跑一遍马拉车、分奇偶再解决一遍即可。
然后$A$了。
AC代码-12860ms
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
using namespace std;
typedef pair<int,int> ii;
char s[N],a[N<<1];
int n,odd[N],even[N],len[N<<1],ans[2][N];
void manacher(){
n<<=1;
memset(len,0,sizeof(len));
int m=n<<1,i,mr=0,mid;
for(i=0;i<=m;i+=2)a[i]='#';
for(i=0;i<n;i++)a[i*2+1]=s[i+1];
for(i=0;i<=m;i++){
if(i<mr)len[i]=min(len[2*mid-i],mr-i);
while(a[i+len[i]]&&a[i+len[i]]==a[i-len[i]])len[i]++;
if(i+len[i]>mr)mr=i+len[i],mid=i;
}
for(i=1;i<=n;i++)odd[i]=len[(i-1)*2+1]/2*2-1;
for(i=1;i<=n;i++)even[i-1]=len[(i-1)*2]/2*2;
n>>=1;
}
void solveOdd(int w){
int full=0,i;
set<ii>S;
for(i=1;i<=(n+1)/2;i++)S.insert({odd[i],i});
for(i=1;i<=n;i++){
while(S.size()){
int x=S.rbegin()->first,id=S.rbegin()->second;
if(id<i){
S.erase(*S.rbegin());
continue;
}
if(x>(id-i+1)*2-1){
full=max(full,id);
S.erase(*S.rbegin());
continue;
}
break;
}
if(S.size())ans[w][i]=max(ans[w][i],S.rbegin()->first);
if(full>=i)ans[w][i]=max(ans[w][i],(full-i+1)*2-1);
S.insert({odd[(n+1)/2+i],(n+1)/2+i});
}
}
int get(int p){return min(p,n-p)*2;}
void solveEven(int w){
int full=0,i;
set<ii>S;
for(i=1;i<=(n+1)/2;i++)S.insert({even[i],i});
for(i=1;i<=n;i++){
while(S.size()){
int x=S.rbegin()->first,id=S.rbegin()->second;
if(id<i){
S.erase(*S.rbegin());
continue;
}
int mx=get(id-i+1);
if(x>mx){
full=max(full,id);
S.erase(*S.rbegin());
continue;
}
break;
}
if(S.size())ans[w][i]=max(ans[w][i],S.rbegin()->first);
if(full>=i)ans[w][i]=max(ans[w][i],get(full-i+1));
S.insert({even[(n+1)/2+i],(n+1)/2+i});
}
}
int main(){
scanf("%d%s",&n,s+1);
int i;
for(i=1;i<=n;i++)s[i+n]=s[i];
manacher();solveOdd(0);solveEven(0);
reverse(s+1,s+n*2+1);
manacher();solveOdd(1);solveEven(1);
printf("%d\n",max(ans[0][1],ans[1][1]));
for(i=2;i<=n;i++)printf("%d\n",max(ans[0][i],ans[1][n+1-i+1]));
return 0;
}
似乎可以从头和尾分别加入和删除，过后学习一下再写写试试。
待补代码
2
顺便贴一下标程。
标程代码-2336ms
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
using namespace std;
const int MAXN=5e5,MAXX=MAXN<<1,MAXLEAVES=1<<19;
char S[MAXX+1];
int R[2][MAXX+1],fsize,T[2][MAXX+1];
void manacher(const int length,const int rx){
register int i,j,k;
int *table=R[rx];
for(i=j=0;i<length;i+=k,j=max(j-k,0)){
while(i-j>=0&&i+j+rx<length&&S[i-j]==S[i+j+rx])++j;
table[i]=j;
for(k=1;k<j&&table[i-k]!=table[i]-k;++k){
table[i+k]=min(table[i-k],table[i]-k);
}
}
}
int tree[(MAXLEAVES<<1)+1],rval,ileft,iright,leaves;
void update_tree(const int x,const int left,const int right){
if(ileft>right||iright<left){
return;
}
if(ileft<=left&&right<=iright){ //node completely inside the update interval
tree[x]=max(tree[x],rval);
} else{
int mid=(left+right)>>1;
update_tree(x<<1,left,mid);
update_tree((x<<1)+1,mid+1,right);
}
}
void adjust_and_gather(const int pos,const int parity){
int &ptr=R[parity][pos];
int diff=(ptr<<1)-(!parity)-fsize,lx,rx,flen;
if(diff>0){
diff+=(diff&1);
ptr-=diff>>1;
}
lx=pos-ptr+1;
rx=pos+ptr-(parity==0);
flen=(ptr<<1)-(!parity);
if((parity==0&&ptr>1)||(parity==1&&ptr>0)){
T[0][lx]=max(T[0][lx],flen);
T[1][rx]=max(T[1][rx],flen);
ileft=max(0,rx-fsize+1),iright=min(fsize-1,lx);
rval=flen;
update_tree(1,0,leaves-1);
}
}
inline void process_manacher_table(const int length){
for(register int i=0;i<length;++i){
adjust_and_gather(i,0);//odd length;
adjust_and_gather(i,1);//even length;
}
}
inline int read_tree(const int pos){
register int x=pos+leaves;
int result=1;
while(x){
result=max(result,tree[x]);
x>>=1;
}
return result;
}
inline void init_leaves(const int n){
leaves=1;
while(leaves<n){
leaves<<=1;
}
}
int main(){
int N,i,answer;
scanf("%d%s",&N,S);
memcpy(S+N,S,(N-1)*sizeof(char));
init_leaves(N);
fsize=N,N=(N<<1)-1;
manacher(N,0);//odd length;
manacher(N,1);//even length;
process_manacher_table(N);
for(i=1;i<N;++i){
T[0][i]=max(T[0][i],T[0][i-1]-2);
T[1][N-i-1]=max(T[1][N-i-1],T[1][N-i]-2);
}
for(i=0;i<fsize;++i){
answer=read_tree(i);
answer=max(answer,T[0][i]);
answer=max(answer,T[1][i+fsize-1]);
printf("%d\n",answer);
}
return 0;
}
F
题目描述
解题思路
AC代码
2
G
题目描述
定义一个$S$的真子串$T$为边界子串，当且仅当$T$为$S$的真前缀和真后缀，定义函数$P(l,r)$表示串$S[l,r]$的回文的边界子串个数。
给定一个串$S$（$|S|\leq 1e5$），求$\sum_{l\leq i\leq j\leq |S|}P(i,j)$。
解题思路
考虑每一种回文子串对答案的贡献，设其出现的次数为$cnt$，则其贡献为$\frac {(cnt+1)cnt}2$。
然后就变成回文树裸题了。注意$LL$！
AC代码
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
44
45
46
47
48
49
50
51
typedef long long ll;
ll ans,w=1000000007LL;
struct PAM{
int i,last,tot,n;
int tr[N][P],s[N];
int fail[N],len[N],cnt[N];
int newnode(int l){
for(i=0;i<P;i++)tr[tot][i]=0;
len[tot]=l;
cnt[tot]=0;
return tot++;
}
void init(){
last=tot=n=0;
newnode(0);newnode(-1);
s[0]=-1;
fail[0]=1;
}
int getfail(int p){
while(s[n-len[p]-1]!=s[n])p=fail[p];
return p;
}
void add(int x){
s[++n]=x;
int cur=getfail(last);
if(!tr[cur][x]){
int now=newnode(len[cur]+2);
fail[now]=tr[getfail(fail[cur])][x];
tr[cur][x]=now;
}
last=tr[cur][x];
cnt[last]++;
}
void count(){
for(i=tot-1;i>=0;i--)cnt[fail[i]]+=cnt[i];
}
}p;
char a[N];
int main(){
int i;
scanf("%s",a);
p.init();
for(i=0;a[i];i++)p.add(a[i]-'a');
p.count();
for(i=2;i<p.tot;i++)ans=(ans+1LL*p.cnt[i]*(p.cnt[i]-1)/2%w)%w;
printf("%lld",ans);
return 0;
}
H
题目描述
给$n$个长度小于$30$的小写字母字符串，选取任意两个（可以相同）字符串的任意前缀$a$和$b$，连接形成新的串$S=ab$。问本质不同的$S$共有多少种。
解题思路
显然，如果给定串为另一个给定串的前缀，则可以忽略掉它。所以先建立一棵$trie$树，考虑任意两个节点都代表一个前缀，答案初步定为$tot\times tot$（$tot$为$trie$节点数）。
然后考虑除重。假设$a,ab,bc,c$都为合理的前缀，则串$abc$可以由$a$和$bc$组成，亦可由$ab$和$c$组成。对于任意一个节点$i$对应的前缀$b$，假设当它作为$S$的后缀时的方案数为$t_i$，则答案数即为$tot\times tot-\sum_{i=1}^{tot}(t_i-1)$。
考虑如何求$t_i$，建立一棵$fail$树，根据$fail$树的性质：一个节点对应的串为（该节点子树大小个）前缀的后缀。于是在$fail$树上$dfs$算出子树大小，则$t_i=sum[rt]$（$rt$代表该串对应的最靠近根节点的节点）。
AC代码
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
typedef long long ll;
using namespace std;
int len[N],t[N][26],fail[N],sum[N],fa[N],tot;
char a[40];
void ins(){
int i,now=0,p;
for(i=0;a[i];i++){
p=a[i]-'a';
if(!t[now][p])
t[now][p]=++tot,len[tot]=len[now]+1,fa[tot]=now;
now=t[now][p];
}
}
queue<int>Q;
void build(){
int i,p;
for(i=0;i<26;i++)if(t[0][i])Q.push(t[0][i]);
while(!Q.empty()){
p=Q.front();Q.pop();
for(i=0;i<26;i++){
if(!t[p][i])t[p][i]=t[fail[p]][i];
else fail[t[p][i]]=t[fail[p]][i],Q.push(t[p][i]);
}
}
}
struct Edge{
int e,n;
}e[N];
int hd[N],cnt;
void add(int a,int b){
e[++cnt].e=b;
e[cnt].n=hd[a];
hd[a]=cnt;
}
void dfs(int p){
int i;
sum[p]=1;
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
dfs(q);
sum[p]+=sum[q];
}
}
int main(){
int i,n;
while(~scanf("%d",&n)&&n){
memset(len,0,sizeof(len));tot=0;
memset(sum,0,sizeof(sum));
memset(t,0,sizeof(t));
memset(fa,0,sizeof(fa));
memset(fail,0,sizeof(fail));
memset(hd,0,sizeof(hd));cnt=0;
for(i=0;i<n;i++)scanf("%s",a),ins();
build();
for(i=1;i<=tot;i++)add(fail[i],i);
dfs(0);
ll ans=1LL*tot*tot;
for(i=1;i<=tot;i++){
if(fail[i]){
int temp=len[fail[i]],now=i;
while(temp--)now=fa[now];
ans-=(sum[now]-1);
}
}
printf("%lld\n",ans);
}
return 0;
}
I
题目描述
解题思路
AC代码
2
J
题目描述
解题思路
AC代码
2
K
题目描述
定义一个串是好串，当且仅当它可以表示成$A+B+…+A+B+A$的形式，其中$A,B$可以为空，分别出现了$k+1$次和$k$次。
给定一个字符串$a(1\leq |a|\leq 10^6)$和$k(1\leq k\leq 10^6)$，求每一个前缀是否是好串。
解题思路
假设字符串$s$的前$i$位为$ABAB…ABA$，则显然，$AB…ABA$和$ABAB…A$可以匹配。
于是用$kmp$字符串匹配的思想自己匹配自己，有$|BA|=i-nxt[i]$。
如果$B$可以为空，也即$s$的前$i$位为$SS…S(共出现num=\frac i{|BA|}次)$，也即$i%|BA|==0$，则只需要满足分成恰好$k$段后的剩余段长度小于等于前面段长度（设新生成的前面段$|A|$为$SS…S(共出现\frac{num}k次)$，剩余段为$SS…S(共出现num%k次)$，则需要满足$\frac{num}k\geq num%k$）。
否则，同理可分析出要求为$\frac{num}k>num%k$。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n,k;
char a[N];
int nxt[N],ans[N];
int main(){
int i,j=0;
scanf("%d%d",&n,&k);
scanf("%s",a);
for(i=1;i<=n;i++){
while(j&&a[i]!=a[j])j=nxt[j];
if(a[i]==a[j])j++;
nxt[i+1]=j;
int r=i-nxt[i],num=i/r;
if(i%r)ans[i]=num/k>num%k;
else ans[i]=num/k>=num%k;
}
for(i=1;i<=n;i++)printf("%d",ans[i]);
return 0;
}
L
题目描述
给两个字符串$A,B(1\leq |A|,|B|\leq 2\times 10^5)$，求不同的公共回文子串$P,Q$个数，重复出现也要算入。
解题思路
使用两棵回文树，分别在偶数根和奇数根上同时深搜，把结果加起来即可。
刚学习回文树，感觉十分巧妙。大致说一下它的思路。
不同于$AC$自动机，回文树的建立基于对每一个回文串的中心向两端扩张，树上的每一个节点代表的是一种回文串，所以$fail$指针指向的是与当前节点具有最长公共回文后缀的串的树上的节点位置（不是字符位置！不是字符位置！）。最初状态只有两个树根，分别为奇数长度回文串的树根和偶数长度回文串的树根。每次添加一个节点$p$的时候，找到上一个节点$last$的最长回文后缀$S$，使得新形成的$pSp$为回文串。当然，如果找不到，那只能让$p$单独成为一个回文串。
用$len[i]$表示节点$i$代表的回文串长度，$cnt[i]$表示这个回文串出现的次数，剩下的就是在$fail$上面跳就好了。
AC代码
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
typedef long long ll;
struct PT{
int tr[N][26],fail[N],cnt[N]/*,num[N]*/,len[N];
int tot,s[N],n,last,i;
int newnode(int l){
for(i=0;i<26;i++)tr[tot][i]=0;
cnt[tot]=0;
len[tot]=l;
//num[tot]=l;
return tot++;
}
void init(){
n=last=tot=0;
newnode(0);newnode(-1);//建立两个树根
s[0]=-1;//奇数回文树树根len=-1
fail[0]=1;//奇数的fail指向偶数树根
}
int getfail(int p){
while(s[n-len[p]-1]!=s[n])p=fail[p];//找到最长的能构成回文串的节点
return p;
}
void add(int p){
s[++n]=p;
int cur=getfail(last);
if(!tr[cur][p]){
int now=newnode(len[cur]+2);//向两端扩张，长度+2
fail[now]=tr[getfail(fail[cur])][p];
tr[cur][p]=now;
//num[now]=num[fail[now]]+1;
}
last=tr[cur][p];
cnt[last]++;
}
void count(){
for(i=tot-1;i>=0;i--)cnt[fail[i]]+=cnt[i];
}
}p1,p2;
char a[N],b[N];
ll dfs(int a,int b){
ll ans=0;int i;
for(i=0;i<26;i++)
if(p1.tr[a][i]&&p2.tr[b][i])
ans+=1LL*p1.cnt[p1.tr[a][i]]*p2.cnt[p2.tr[b][i]]+dfs(p1.tr[a][i],p2.tr[b][i]);
return ans;
}
int main(){
int i,j,t;
scanf("%d",&t);
for(i=1;i<=t;i++){
p1.init();p2.init();
scanf("%s%s",a,b);
for(j=0;a[j];j++)p1.add(a[j]-'a');
for(j=0;b[j];j++)p2.add(b[j]-'a');
p1.count();p2.count();
printf("Case #%d: %lld\n",i,dfs(0,0)+dfs(1,1));
}
return 0;
}
M
题目描述
解题思路
AC代码
2