07-30 02:22 阅读 194

2021暑假 HDU中超第四场 1004

Display Substring

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1055 Accepted Submission(s): 212

题意

给一个字符串，告知每个小写字母对应的价值，求价值和第k名的子串

Sample Input

25 5ababc3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 15 15ababc3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output

4-1

考场思路：

求第k小子串，那么构建后缀自动机

根据传统算法搞（记录SAM上每个节点出发能到达的节点数），突然意识到不对劲

这里的第k小是指权值和第k小，而不是字典序

不能像传统算法那样，依据第一位转移

补题：

题目不要求输出子串是什么，只需要输出第k大子串的权值

可以考虑二分答案，假设 w 为答案，然后需要check是否有k个子串权值小于等于 w

先回顾一下SAM的性质：

每个节点代表一个等价类，其父节点包含的最大子串为AAA

则这个节点包含形如 XXXAAA，XXAAA，XAAA的子串

我们要计算每个节点中有多少子串的权值是大于 w 的，并且同一个节点中的子串都连续

权值和显然单调，可以对每个节点再二分，利用前缀和计算答案

check复杂度 O(nlogn) ，总复杂度 O(nlognlogn)

#include <bits/stdc++.h>#include <vector>using namespace std;#define ll long long#define fff(x,y,z) for(int x=y;x<=z;x++)#ifdef ACM_LOCALconst int maxn = 100005;#elseconst int maxn = 100005;#endifint mode=1e9+7;void swap(int &a, int &b){int ins=a;a=b;b=ins;}struct node{
    int ch[29];    int fa, len, cnt;    int fir;    void clear(){        for(int i=0;i<28;i++) ch[i] = 0;
        fa = len = fir = 0;
    }
}sam[2*maxn];int n; ll k;string s;int tot, lst;int val[28], sum[maxn];void expend(int c){    int cur = ++tot;    int p = lst;
    lst = cur;
    sam[cur].len = sam[p].len+1;
    sam[cur].cnt = 1;
    sam[cur].fir = sam[cur].len;    while(!sam[p].ch[c]){
        sam[p].ch[c] = cur;
        p = sam[p].fa;        if(p == -1){
            sam[cur].fa = 0;            return;
        }
    }    int q = sam[p].ch[c];    if(sam[p].len+1 == sam[q].len){
        sam[cur].fa = q;
    }else{        int clo = ++tot;
        sam[clo] = sam[q];
        sam[clo].len = sam[p].len+1;
        sam[clo].fir = sam[q].fir;
        sam[clo].cnt = 0;
        sam[q].fa = clo;
        sam[cur].fa = clo;        while(p != -1 && sam[p].ch[c] == q){
            sam[p].ch[c] = clo;
            p = sam[p].fa;
        }
    }
}void init(){    for(int i=0;i<n*2+5;i++) sam[i].clear();
    sam[0].len = 0;
    sam[0].fa = -1;
    sam[0].cnt = 0;
    tot = 0;
    lst = 0;
}bool check(int w, ll k){    //if (numof x<=w) >= k
    ll res = 0;    for(int i=1;i<=tot;i++){        int fs = sam[i].fir;//endpos
        int l = fs - sam[i].len + 1, r = fs - sam[sam[i].fa].len, mid;        while(l < r){
            mid = (l+r)/2;            if(sum[fs] - sum[mid-1] <= w){
                r = mid;
            }else{
                l = mid+1;
            }
        }        if(sum[fs] - sum[l-1] <= w) res += fs - sam[sam[i].fa].len - l + 1;
    }    return res >= k;
}void solve(){    cin >> n >> k;    cin >> s;    for(int i=0;i<26;i++) cin >> val[i];    for(int i=1;i<=n;i++) sum[i] = sum[i-1] + val[s[i-1] - 'a'];

    init();    for(int i=0;i<n;i++) expend(s[i] - 'a');    int l = 0, r = sum[n], mid;    while(l < r){
        mid = (l+r)/2;        if(check(mid, k)){
            r = mid;
        }else{
            l = mid+1;
        }
    }    if(check(l, k)) cout << l << '\n';    else cout << "-1\n";

}signed main() {#ifdef ACM_LOCAL
    freopen("x.txt","r",stdin);#endif

    ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    int T = 1;    cin>>T;    while(T--){
        solve();
    }    return 0;
}

来源https://www.cnblogs.com/tyin/p/15078242.html

2021暑假 HDU中超 第四场 1004