[HDU 5635 BestCoder Round 74(div2)A][욕심 폭력]LCP Array 인접 접미사 최대 동일 접두사 출력 문자열 방안 수
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1176 Accepted Submission(s): 328
Problem Description
Peter has a string
s=s1s2...sn , let
suffi=sisi+1...sn
be the suffix start with
i -th character of
s . Peter knows the lcp (longest common prefix) of each two adjacent suffixes which denotes as
ai=lcp(suffi,suffi+1)(1≤i
109+7 .
Input
There are multiple test cases. The first line of input contains an integer
T
indicating the number of test cases. For each test case:
The first line contains an integer
n
(
2≤n≤105)
-- the length of the string. The second line contains
n−1
integers:
a1,a2,...,an−1
(0≤ai≤n) .
The sum of values of
n
in all test cases doesn't exceed
106 .
Output
For each test case output one integer denoting the answer. The answer must be printed modulo
109+7 .
Sample Input
3
3
0 0
4
3 2 1
3
1 2
Sample Output
16250
26
0
Source
BestCoder Round #74 (div.2)
Recommend
wange2014
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 1e5+10, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
int n;
void datamaker()
{
freopen("c://test//input.in", "w", stdout);
casenum = 10000;
printf("%d
", casenum);
for (casei = 1; casei <= casenum; ++casei)
{
n = rand() % 10 + 2; printf("%d
", n);
for (int i = 1; i < n; ++i)printf("%d ", rand() % (n+2));
puts("");
}
}
int b[N];
int observe()
{
for (int i = 1; i < n; ++i)scanf("%d", &b[i]);
if (b[n - 1] != 0 && b[n - 1] != 1)return 0;
LL ans = b[1] == 0 ? 26 * 25 : 26;
for (int i = 2; i < n; ++i)
{
if (b[i - 1] != 0 && b[i] != b[i - 1] - 1)return 0;
if (b[i] == 0)ans = ans * 25 % Z;
}
return ans;
}
int solve()
{
int x;
LL ans = 26;
int stop = 0;//stop a[stop]!=a[stop+1]
for (int i = 1; i < n; ++i)
{
scanf("%d", &x);
if (stop < i) stop = i + x;
else if (stop != i + x)ans = 0;
if (x == 0)ans = ans * 25 % Z;
}
if (stop > n)ans = 0;
return ans;
}
int main()
{
//datamaker(); return 0;
//fre();
scanf("%d", &casenum);
for (casei = 1; casei <= casenum; ++casei)
{
scanf("%d", &n);
//printf("%d
", observe()); continue;
printf("%d
", solve());
}
return 0;
}
/*
【trick&& 】
1，
2，
【 】
， ， n（2<=n<=1e5）
， 。
【 】
【 】
=======================================
first thought
。
，
0，
0， 26-1
0，
========================================
WA.
， ， 。
a[i] a[i+1] b[]
b[] ——
x,x-1,x-2,...,2,1,0,0,...,0,0,y,y-1,y-2,...,2,1,0,...,1or0( 1 0)
b[]
【 && 】
O（n）
*/이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HPU - ACM 여름 훈련 2 주차 14 급 개인전: Problem D [욕심]Problem D Problem Description 그 러 고 보 니 해동 그룹 이 안팎 으로 어려움 을 겪 고 있 고 회사 의 원로 도 XHD 부부 만 남 았 다 고 한다.분명히 여러 해 동안 싸 운 상인 으로서...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
