CF 226 DIV2 B. Bear and Strings
3791 단어 codeforces
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
The bear has a string s = s1s2... s|s| (record |s| is the string's length), consisting of lowercase English letters. The bear wants to count the number of such pairs of indices i, j (1 ≤ i ≤ j ≤ |s|), that string x(i, j) = sisi + 1... sj contains at least one string "bear"as a substring.
String x(i, j) contains string "bear", if there is such index k (i ≤ k ≤ j - 3), that sk = b, sk + 1 = e, sk + 2 = a, sk + 3 = r.
Help the bear cope with the given problem.
Input
The first line contains a non-empty string s (1 ≤ |s| ≤ 5000). It is guaranteed that the string only consists of lowercase English letters.
Output
Print a single number — the answer to the problem.
Sample test(s)
input
bearbtear
output
6
input
bearaabearc
output
20
Note
In the first sample, the following pairs (i, j) match: (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9).
In the second sample, the following pairs (i, j) match: (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (2, 10), (2, 11), (3, 10), (3, 11), (4, 10), (4, 11), (5, 10), (5, 11), (6, 10), (6, 11), (7, 10), (7, 11).
이 문제를 내가 보자마자 가장 먼저 생각난 것은 용척이었다. 아쉽게도 용척에 대해 잘 알지 못해서 마지막에 막다른 골목으로 들어갔다
스스로 용척을 하면 틀릴 수 있는 이유:
A∪B∪C = A+B+C - A∩B - B∩C - C∩A +A∩B∩C
제가 하고 있는 건 C A예요. 분명히 안 빠졌어요.
오류 코드:
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<limits.h>
using namespace std;
int main()
{
char a[5555];
int t[5555];// bear
while(scanf("%s",&a)!=EOF)
{
int sum= 0;
int l= strlen(a);
for(int i= 0; i< l-3; i++)
if(a[i]=='b'&&a[i+1]=='e'&&a[i+2]=='a'&&a[i+3]=='r')
{
sum++;
t[sum]= i;
}
for(int i= 1; i<= sum; i++)
printf("%d ",t[i]);
printf("
");
__int64 ans= 0;
for(int i= 1; i<= sum; i++)
{
for(int j= 1; j+i-1<= sum; j++)
{
__int64 be= t[j]+1;
__int64 end= t[j+i-1] + 3;
// if(i==2)
// printf("%d %d
",be,end);
if(i%2)
{
ans+= be*(l- end);
//printf("%d %d %d
",i,j,be*(l-end));
printf("%d %d %d %d
",i,be,l-end,ans);
}
else
{
ans-= be*(l- end);
printf("%d %d %d %d
",i,be,l-end,ans);
}
}
}
printf("%I64d
",ans);
}
return 0;
}
사실 이 문제는 용납할 필요도 없이 그 중의 법칙만 찾아내면 된다
AC 코드:
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<limits.h>
using namespace std;
int main()
{
char ch[5555];
while(scanf("%s",&ch)!=EOF)
{
int l= strlen(ch);
int temp= 0;
__int64 ans= 0;
for(int i= 0; i< l-3; i++)
if(ch[i]=='b'&&ch[i+1]=='e'&&ch[i+2]=='a'&&ch[i+3]=='r')
{
ans+= (i+ 1- temp) * (l- i -3);
temp= i + 1;
}
printf("%I64d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.