2021暑假 HDU中超 第四场 1004

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

2
5 5
ababc
3 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
5 15
ababc
3 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 
#include 
using namespace std;
#define ll long long
#define fff(x,y,z) for(int x=y;x<=z;x++)
#ifdef ACM_LOCAL
const int maxn = 100005;
#else
const int maxn = 100005;
#endif
int 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= 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>T;
    while(T--){
        solve();
    }
    return 0;
}