2017 CCPC 하 얼 빈 A: Palindrome (manacher + 나무 모양 배열)
1985 단어 선분 트 리 or 트 리 배열
제목:
꼬치 s 를 드 리 겠 습 니 다. 만족 S [i] = S [2n - i] = S [2n + i - 2] (1 ≤ i ≤ n) 의 슈퍼 답문 서브 꼬치 가 몇 개 있 습 니까?
문제 풀이:
p [i] 를 i 문 자 를 중심 으로 하 는 답장 문자열 반경 - 1
그럼 문 제 를 자세히 분석 해 보면 두 가지 점 (i, j) 이 j - i < = min (p [i], p [j]) 을 만족 시 키 면 j 와 i 는 슈퍼 답장 문자열 의 두 중심 이다.
이 모든 문 제 는 얼마나 많은 쌍 (i, j) 이 j - i < = min (p [i], p [j] 를 만족 시 키 는 지 를 구 하 는 것 이다.
매 거 i 가 p [i] 를 반경 으로 공헌 하 는 것 을 고려 하면 분명히 공헌 은 반경 내의 j - i < = p [j] 를 만족 시 키 는 j 의 개수 이 고, 항목 을 옮 기 면 p [j] - j > = - i 이다
그래서 선령 p [j] = p [j] - j, 그 다음 에 큰 것 부터 작은 것 까지 p [] 를 배열 에 추가 하고 트 리 배열 로 이미 가입 한 p [] 의 개 수 를 통계 하면 됩 니 다.
//2017CCPC --A
#include
#include
#include
#include
using namespace std;
#define LL long long
vector G[500005];
int n, p[1000010], tre[500005];
char s[500010], str[1000010];
int Query(int x)
{
int ans = 0;
while(x)
{
ans += tre[x];
x -= x&-x;
}
return ans;
}
void Update(int x, int val)
{
while(x<=n)
{
tre[x] += val;
x += x&-x;
}
}
int main(void)
{
LL ans;
int T, i, j, k, mx, id;
scanf("%d", &T);
while(T--)
{
scanf("%s", s);
n = strlen(s);
str[0] = '$';
str[1] = '#';
for(i=0;i<=n-1;i++)
{
k = (i+1)*2;
str[k] = s[i];
str[k+1] = '#';
}
n = k+1;
str[n+1] = 0;
mx = 0;
for(i=1;i<=n;i++)
{
p[i] = 1;
if(mx>i)
p[i] = min(p[2*id-i], mx-i+1);
while(str[i+p[i]]==str[i-p[i]])
p[i]++;
if(p[i]+i-1>mx)
{
mx = p[i]+i-1;
id = i;
}
}
k = 1;
for(i=2;i<=n;i+=2)
{
p[k] = k+1-p[i]/2;
G[k+1-p[i]/2].push_back(k);
k += 1;
}
n = k-1;
ans = 0;
for(i=1;i<=n;i++)
{
for(j=0;j 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
선분 트 리 기초 작업 - 단점 또는 구간 업데이트 + 조회문제 개술: 먼저 하나의 숫자 n 을 입력 하면 한 반 에 n 명 이 있다 는 것 을 나타 낸다. 처음에 모든 사람 이 손 에 사탕 이 하나 있 었 다. 그 다음 에 하나의 수 m 를 입력 하고 m 번 조작 을 한다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
