【bzoj3998】弦论

  • 后缀自动机重修系列第二题

这题是后缀自动机的基础应用之一

首先构建$SAM$

每个子串对应了 $SAM$ 上的一条路径

我们考虑这个路径在SAM上某个状态 $p$ 停下：

  1. 若去重，则只有一种方案

  2. 若不去重，则有 $|right(p)|$ 种方案

记 $f[x]$ 表示从状态$x$ 向后走的不同的路径数

在 $SAM$ 上求 $K$ 大，逐个确定答案的每位字符即可

重点说一下我犯得低级错误吧

extend函数中又一个memcpy的过程，我打成了memcmp，结果一下午就进去了

其实这个问题可以通过GDB开警告解决

$ g++ -g 3998.cpp -Wall -o 3998.exe

这样就可以报错了

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 1000010
using namespace std;
int n,now(1),cnt(1),id[MAXN],c[MAXN],mx[MAXN],Right[MAXN],f[MAXN],parent[MAXN],tr[MAXN][27];
char ch[MAXN];
inline int read(){
    int x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
void extend(int x){
    int np=++cnt,p=now; Right[np]=1;
    mx[np]=mx[p]+1;  now=np;
    while(p&&!tr[p][x])  tr[p][x]=np,p=parent[p];
    if(!p) parent[np]=1;
    else{
        int q=tr[p][x];
        if(mx[q]==mx[p]+1)  parent[np]=q;
        else{
            int nq=++cnt; mx[nq]=mx[p]+1;
            memcpy(tr[nq],tr[q],sizeof(tr[q]));
            parent[nq]=parent[q]; parent[q]=parent[np]=nq;
            while(p&&tr[p][x]==q) tr[p][x]=nq,p=parent[p];
        }
    }
}
void topsort(){
    for(int i=1;i<=cnt;++i)  c[mx[i]]++;
    for(int i=1;i<=n;++i)    c[i]+=c[i-1];
    for(int i=1;i<=cnt;++i)  id[c[mx[i]]--]=i;
}
int main(){
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
    scanf("%s",ch+1);  n=strlen(ch+1);
    for(int i=1;i<=n;++i)  extend(ch[i]-'a');
    topsort();int opt=read(),len=read();
    for(int i=cnt;i;--i){
        if(opt==1) Right[parent[id[i]]]+=Right[id[i]];
        else Right[id[i]]=1;
    }
    Right[1]=0; now=1;
    for(int i=cnt;i;--i){
        f[id[i]]=Right[id[i]];
        for(int j=0;j<26;++j) f[id[i]]+=f[tr[id[i]][j]];
    }
    if(len>f[1])  {puts("-1"); return 0;}
    while(len>Right[now]){
        len-=Right[now];
        for(int i=0;i<26;++i)if(tr[now][i]){
            if(len<=f[tr[now][i]]){
                putchar('a'+i);
                now=tr[now][i]; break;
            }
            else len-=f[tr[now][i]];
        }
    }
    return 0;
}

附makedata程序

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<cmath>
#include<algorithm>
#define FILE "read"
using namespace std;
const int INF=(int)1e9;
int main(){
    freopen(FILE".in","w",stdout);
    srand(time(0));
    int n=500000;
    for(int i=1;i<=n;++i){
        putchar('a'+rand()%26);
    }
    printf("\n");
    printf("%d %lld",rand()%2,1LL*rand()*rand()%INF);
    return 0;
}

本文标题:【bzoj3998】弦论

文章作者:chty

发布时间:2017年03月08日 - 17时01分

最后更新:2018年03月02日 - 17时17分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
  1. 1. $ g++ -g 3998.cpp -Wall -o 3998.exe
,