2018百度之星资格赛1002题-子串查询

【题目大意】

有多组测试样例。

每个样例给定一个字符串A[1, n],并给出q次询问[l, r]。

输出询问区间中,有多少个子串(非空)是所有非空子串中字典序最小的。

也就是说,加入询问区间为ABA,那么应该输出2,因为区间中最小字典序的子串是A,而A出现了两次。

【样例输入】

1
2 3
AB
1 1
1 2
2 2

【样例输出】

Case #1:
1
1
1

【简要分析】

首先想到最多有1e5次询问,最长的字符串可以达到1e5。也就是说,如果每次询问得到结果的复杂度为O(n)的话,也就是说整个算法复杂度为O(n^2),很大可能上会超时。

分析一下,有多少个最小字典序的子串。小心别被糊弄了,题目就是要求给定区间中最小的字符的个数。这里可以用反证法,倘若最小的子串长度大于等于2,那么它的第一个字符构成的子串一定小于这个最小子串,那么这个子串将不是最小的,矛盾,因此最小的子串一定是一个字符。

那么我们如何动态的求区间的最小值呢,倘若遍历一遍,那么复杂度一定是O(n),TLE在所难免。

我们很容易想到线段树是一个优秀的求区间最值、和的一种方法。

用线段树求区间最小值就不必赘述了。

关键是,如何知道这个最小值出现了几次。

我们不妨在每个区间维持一个长度为26的数组,记录下26个字母各自出现的次数,然后在线段树向上更新的时候逐位更新,这样就大功告成了~

【示例代码】

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define m (l + ((r - l) >> 1))
#define lson (k << 1), l, m
#define rson (k << 1 | 1), m + 1, r
using namespace std;
const int MAX = 1e5+7;
const int INF = 0x3f3f3f3f;
int T, n, q, ll, rr, kase = 0;
char ch[MAX];
int dat[MAX << 2], sum[MAX << 2][30];
void pushUp(int k) {
    dat[k] = min(dat[k << 1], dat[k << 1 | 1]);
    for (int i = 0; i < 26; i++) {
        sum[k][i] = sum[k << 1][i] + sum[k << 1 | 1][i];
    }
} 
void update(int L, int c, int k, int l, int r) {
    if (l == r) {
        dat[k] = c;
        sum[k][c]++;
        return;
    }
    if (L <= m) update(L, c, lson);
    else update(L, c, rson);
    pushUp(k);
}
int query_min(int L, int R, int k, int l, int r) {
    if (L <= l && r <= R) {
        return dat[k];
    }
    if (L > r || l > R) return INF;
    int res = min(query_min(L, R, lson), query_min(L, R, rson));
    return res;
}
int query_sum(int L, int R, int c, int k, int l, int r) {
    if (L <= l && r <= R) {
        return sum[k][c];
    } 
    if (L > r || l > R) return 0;
    int res = query_sum(L, R, c, lson) + query_sum(L, R, c, rson);
    return res;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &q);
        fill(dat, dat + (n << 2), INF);
        memset(sum, 0, sizeof(sum));
        getchar();
        for (int i = 0; i < n; i++) {
            scanf("%c", &ch[i]);
            update(i + 1, (int)(ch[i] - 'A'), 1, 1, n);
        }
        printf("Case #%d:\n", ++kase);
        while (q--) {
            scanf("%d%d", &ll, &rr);
            int minn = query_min(ll, rr, 1, 1, n);
            printf("%d\n", query_sum(ll, rr, minn, 1, 1, n));
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注