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;
}

白书P368页:禁止字符串

这道题属于字符串上的DP之单字符串的情况

题目大意:考虑仅仅由’A’,’G’,’C’, ‘T’组成的DNA串,给定一个长度为k的字符串S。计算所有长度为n,却不包含S的字符串的个数,输出结果需要模10009

限制条件:

1 ≤ k ≤ 100
1 ≤ n ≤ 10000

解题思路:

最简单的想法就是暴力枚举,对于一个长度为n的字符串,其中每个字符的可能性为4个,那么这样的话,总共需要枚举4^n种情况,这样绝对会TLE的

所以,与其我们将所有情况都枚举出来,然后去判断这些情况下的字符串是否含有S。不如我们直接在搜索(也就是从字符串头到尾进行4种情况的枚举)并在串最后添加字符时,直接判断添加后的串的最后k个字符是否为S就好了。这样一来,最后k个字符前面的字符都不予考虑了,因为他们对于后面的搜索都没有影响了。我们可以得到一个以剩余字符的个数和最后k – 1个字符的状态进行动态规划。

但是这样一来,还是有n*4^{k-1}种情况,复杂度并没有缩减多少。

但是实际上可以进行等价状态的归并,为啥,其实很多状态都是一样的,比如s=’ATG’的话,实际上’TAT’与’SAT’这两种情况是等价的,因为我们只需要考虑后面的两位AT就好了,前面的都不需要考虑了。因此可以发现,其实所有等价的情况归并后,每种情况都是s的前缀。因为我们可以s的前缀长度作为状态,包含0 … k-1,当然前缀长度为k的话,就是禁止字符串了,这种情况需要跳过。

也就是说,状态i等于前缀长度

这些做完了后,我们可以定义

dp[i][j]表示,字符串长度为i且以状态j结尾的合法数。

因此,最后的结果就是Σdp[n][j]其中j为所有可能的前缀长度,也就是0…k-1

状态转移方程就是:

dp[t][next[i][j]]+=dp[t-1][i]其中next[i][j]就是状态i后面加上字符j的下一个状态

这个是很显然的,DP的精髓就是状态转移方程,这个状态等于所有可以转移到这个状态之和

那么这时我们就是要处理一下next[i][j]了

next[i][j]表示当前状态i添加了字符j后将要转移到的状态。

为了方便起见,暂时不考虑模10009的限制条件

解题代码:

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
const int MAX_K = 107;
const int MAX_N = 1e4+7;
const char* AGCT = "AGCT";
int n, k;
string str;
// next[i][j]: 状态为i时,加上字符j,转移到状态next[i][j]
// dp[i][j]: 长度为i的字符串,以状态结尾的所有合法种数
int nxt[MAX_K][4];
int dp[MAX_N][MAX_K];
void cal_next(const int &k, const string &str) {
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < 4; j++) {
            string next_str = str.substr(0, i) + AGCT[j];
            while (next_str != str.substr(0, next_str.size())) {
                next_str = next_str.substr(1);
            }
            nxt[i][j] = next_str.size();
        }
    }
}
int cnt_num(const int &n, const int k) {
    dp[0][0] = 1; //长度为0,匹配串为0的话,算是合法的一种情况的
    for (int t = 1; t <= n; t++) {
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < 4; j++) {
                if (nxt[i][j] == k) continue;
                dp[t][nxt[i][j]] += dp[t - 1][i];
            }
        }
    }
    int res = 0;
    for (int i = 0; i < k; i++) {
        res += dp[n][i];
    }
    return res;
}
int main() {
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &k);
    cin >> str;
    cal_next(k, str);
    printf("%d\n", cnt_num(n, k));
    return 0;
}