HDU problem 5635 LCP Array【思维】

谁借莪１个温暖的怀抱￠ 2022-01-10 04:37 164阅读 0赞

LCP Array

Accepts: 131

Submissions: 1352

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

问题描述

s=s_{1}s_{2}...s_{n}s=s1s2...sn, 令\text{suff}_i =s_{i}s_{i+1}...s_{n}suffi=sisi+1...sn是ss第ii字符开头的后缀. Peter知道任意两个相邻的后缀的最长公共前缀a_i = \text{lcp}(\text{suff}_i, \text{suff}_{i+1}) \quad (1 \le i < nai=lcp(suffi,suffi+1)(1≤i<n). 现在给你数组aa, Peter有多少个仅包含小写字母的字符串满足这个数组. 答案也许会很大, 你只要输出对10^9 + 7109+7取模的结果即可.

输入描述

TT, 表示测试数据的组数. 对于每组数据: 第一行包含一个整数nn (2 \le n \le 10^5)2≤n≤105)表示字符串的长度. 第二行包含n - 1n−1个整数: a_1,a_2,...,a_{n-1}a1,a2,...,an−1 (0 \le a_i \le n)(0≤ai≤n). 所有数据中nn的和不超过10^6106.

输出描述

10^9+7109+7取模的结果.

输入样例

16250
    26
    0

题意： 给你一个含有N-1个元素的数组，数组对应一个长度为N的字符串，数组中的第i个数的含义为字符串中第i个开头的和第i+1个开头的字符串的子串的最大　　　　公共前缀的长度，现在让你推算数这个字符串有多少种情况。

先把数组处理下，对于i个长度为0的子串，它的颜色和他的后面的元素的字母不相同，标记下。如果长度不为0，它的首字母必定和下个字母相同，然后利用最大长度检查剩下的是否也相同，要是不相同，则这组数据出错了。

利用记录的字符串的信息扫一下，如果某个位置的字符和它的后面的相同，则他的情况和后面支付的一样，否则它有25种可能性。

#include <map>
    #include <set>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <iostream>
    #include <stack>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <cstdlib>
    //#include <bits/stdc++.h>
    //#define LOACL
    #define space " "
    using namespace std;
    typedef long long LL;
    typedef __int64 Int;
    typedef pair<int, int> PAI;
    const int INF = 0x3f3f3f3f;
    const double ESP = 1e-5;
    const double PI = acos(-1.0);
    const int MOD = 1e9 + 7;
    const int MAXN = 1e5 + 10;
    int ar[MAXN], clor[MAXN];
    int main() {
        int T, N;
        scanf("%d", &T);
        while (T--) {
            memset(clor, 0, sizeof(clor));
            scanf("%d", &N);
            for (int i = 0; i < N - 1; i++) scanf("%d", &ar[i]);
            clor[N - 1] = 1;
            int cnt = 2;
            bool flag = false;
            for (int i = N - 2; i >= 0; i--) {
                if (ar[i] != 0) {
                    clor[i] = clor[i + 1];
                    for (int j = 1; j <= ar[i]; j++) {
                        if (clor[i] != clor[i + j]) {flag = true; break;}
                    }
                    if (clor[i + ar[i] + 1] == clor[i]) {flag = true; break;}
                }
                else clor[i] = cnt++;
                if (flag) break;
            }
            Int ans = 26;
           // cout << "数据发生错误: " << flag <<endl;
            bool change = false;
            int temp = clor[N - 1];
            //for (int i = 0; i < N; i++) printf("第i个字母应该是%d\n", clor[i]);
            for (int i = N - 2; i >= 0; i--) {
                if (clor[i] != temp) {
                    ans *= 25;  temp = clor[i];
                    ans %= MOD;
                }
            }
            if (flag) printf("%d\n", 0);
            else printf("%I64d\n", ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/cniwoq/p/6770743.html