「小奇模拟赛」小奇的自动机
「题目背景」
小奇在研究后缀自动机时遇到了一个难题。
「问题描述」
定义：如果字符串A是字符串B的后缀，那么称B是A的XQ串。
小奇有n个只包含小写字母的字符串，编号为1-n，表示为Si。
接下来对于每个串Si，小奇想知道：对于小奇拥有的n个字符串，所有是Si的XQ串的编号集合(包括i）中第Ki小的编号。
「输入格式」
第1行1个整数n。
接下来n行，第i+1行包括1个字符串Si。
再接下来n行，第n+1+i行的整数表示Ki。
「输出格式」
输出n行，第i行表示对Si的询问的答案。
「样例输入」
3
cd
abcd
bcd
2
3
1
「样例输出」
2
-1
2
「数据范围」
对于20%的数据 n<=500，字符串总长<=1000;
对于50%的数据 K=1;
对于100%的数据 n<=100000，字符串总长<=300000。
题解
本题来自胜利一中Vampire
20%的数据
直接暴力好了
50%的数据
把所有的串反过来建个trie，那么某个串的结束结点的子树里的串就是所有的以该串为后缀的串
这部分数据只要求查询子树内的最小编号，用线段树维护dfs序即可
100%的数据
把区间最值改成区间K大，把线段树换成主席树即可
「更简单的做法」
由于可以离线，那么区间最值就能直接在trie上dp，而区间K大可以用线段树合并自底向上查询
|
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 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 93 94 95 96 97 98 99 100 101 102 103 104 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define eps 1e-13 #define mod 10000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,L,cnt=1,seg; int K[300005]; char ch[300005]; int t[300005][26]; vector<int>que[300005]; int rt[300005],ans[300005]; int ls[1200005],rs[1200005],sum[1200005]; void insert(int &k,int l,int r,int val) { if(!k)k=++seg; if(l==r) { sum[k]++;return; } int mid=(l+r)>>1; if(val<=mid)insert(ls[k],l,mid,val); else insert(rs[k],mid+1,r,val); sum[k]=sum[ls[k]]+sum[rs[k]]; } int merge(int x,int y) { if(!x)return y; if(!y)return x; ls[x]=merge(ls[x],ls[y]); rs[x]=merge(rs[x],rs[y]); sum[x]=sum[ls[x]]+sum[rs[x]]; return x; } int query(int k,int l,int r,int rk) { if(rk>sum[k])return -1; if(l==r)return l; int mid=(l+r)>>1; if(sum[ls[k]]>=rk)return query(ls[k],l,mid,rk); else return query(rs[k],mid+1,r,rk-sum[ls[k]]); } void build(int id) { int now=1; int L=strlen(ch+1); for(int i=L;i;i--) { int p=ch[i]-'a'; if(!t[now][p])t[now][p]=++cnt; now=t[now][p]; } que[now].push_back(id); insert(rt[now],1,n,id); } void solve(int now) { for(int i=0;i<26;i++) if(t[now][i]) { solve(t[now][i]); rt[now]=merge(rt[now],rt[t[now][i]]); } for(int i=0;i<que[now].size();i++) { int Q=que[now][i]; ans[Q]=query(rt[now],1,n,K[Q]); } } int main() { freopen("sam.in","r",stdin); freopen("sam.out","w",stdout); n=read(); for(int i=1;i<=n;i++) { scanf("%s",ch+1); build(i); } for(int i=1;i<=n;i++) K[i]=read(); solve(1); for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; } |
Subscribe
计数器 9855140
OI 课件=>
OI 课件=>