HDU problem 5635 LCP Array【思维】-白红宇

HDU problem 5635 LCP Array【思维】

阅读量：6208 次

发布时间：2019-06-21

本文共 2041 字，大约阅读时间需要 6 分钟。

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

输入描述

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取模的结果.

输入样例

16250260

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

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

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

#include #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  //#include 
                  
                   //#define LOACL#define space " "using namespace std;typedef long long LL;typedef __int64 Int;typedef pair
                   
                     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 <
                    
                     = 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

你可能感兴趣的文章