#294 (div.2) D.A and B and Interesting Substring
2. 문제 풀이 방향: 본 문 제 는 s 에서 다음 조건 을 만족 시 키 는 문자열 을 찾 아야 합 니 다. (i) i + 1 ~ j - 1 의 문자열 가중치 의 합 은 0 입 니 다.(ii)s[i]==s[j]；권한 문자열 을 처리 하 는 일반적인 해법 은 접두사 와.그러나 나의 최초의 알고리즘 은 효율 이 매우 낮 았 다. 먼저 앞의 i 문자 의 권 리 를 구 했다.26 글자 가 나 오 는 위 치 를 vector 에 순서대로 저장 합 니 다.그 다음 에 0 ~ len 에서 각 위치의 문자 s [i] 를 차례대로 매 거 하고 다음 에 나타 나 는 위 치 를 매 거 한 다음 에 이 단락 의 문자열 이 조건 에 만족 하 는 지 계산 합 니 다 (1).이 알고리즘 은 6 조 데이터 에서 TLE 입 니 다.어 쩔 수 없 이 새로운 해법 을 찾 을 수 밖 에 없다.
조건 에 따라 sum [i] = sum [j - 1] 을 알 수 있 습 니 다. j 위 를 스 캔 할 때 가중치 를 추가 하지 않 으 면 sum [i] = sum [j] 가 있 습 니 다.만약 에 우리 가 sum 값 을 s [i] 의 map 에 넣 어서 s [i] 로 끝 날 때 sum 의 출현 횟수 를 통계 하면 자연히 조건 을 만족 시 킬 수 있다 (2).따라서 새로운 알고리즘 은 26 비트 길이 의 맵 을 미리 열 어 이 문자 로 끝 나 는 하위 문자열 이 만 나 는 모든 sum 값 을 저장 하 는 것 이 어렵 지 않 습 니 다.처음부터 끝까지 s 를 스 캔 하면 모든 sum 값 이 나타 나 는 횟수 가 0 입 니 다. 매번 에 s [i] 의 끝 을 누적 하고 가중치 의 합 은 바로 sum (sum 은 일시 적 으로 s [i] 의 가중치) 의 하위 문자열 의 개수 입 니 다. 즉, m [s [i] [sum] 을 한 다음 에 s [i] 의 끝 에 있 는 sum 값 을 업데이트 한 다음 에 m [s [i]] [sum] 의 값 을 업데이트 합 니 다.자세 한 내용 은 코드 주석 참조.
3. 코드:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;
#define N 100000+10
int word[26];
char s[N];
int main()
{
//freopen("test.txt", "r", stdin);
long long cnt = 0,sum=0;
for (int i = 0; i < 26; i++)
scanf("%d", word + i);
scanf("%s", s);
int len = strlen(s);
map<long long, long long>m[26];
for (int i = 0; i < len; i++)
{
int x = s[i] - 'a';//s[i]
cnt += m[x][sum];// s[i] sum
sum += word[x];// sum ， s[i]
m[x][sum]++;// sum
}
cout << cnt << endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
비슷한 이름의 Attribute를 많이 만들어 삭제하는 Houdini사용 소프트웨어는 Houdini16.5입니다 배열에서는 애트리뷰트의 보간이 잘 동작하지 않는 것과 AttributeCreateSOP 노드에서 Size가 4를 넘는 애트리뷰트를 작성해도 값이 조작할 수 없어 의미가 없...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
