QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#618755	#7814. 消消乐	crazy_monkey	100 ✓	183ms	29076kb	C++14	521b	2024-10-07 09:53:31	2024-10-07 09:53:37

Judging History

你现在查看的是最新测评结果

[2024-10-07 09:53:37]
评测

测评结果：100
用时：183ms
内存：29076kb

查看

[2024-10-07 09:53:31]
提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n;
char s[N];
int nxt[N];
long long dp[N];
int main()
{
	memset(nxt,-1,sizeof nxt);
	cin >> n;
	cin >> s+1;
	memset(dp,0,sizeof dp);
	long long ans=0;
	for(int i=2;i<=n;i++)
	{
		nxt[i]=i-1;
		while(s[i]!=s[nxt[i]]&&nxt[i]>=0)nxt[i]=nxt[nxt[i]]-1;
		if(nxt[i]<0)nxt[i]=-1;
	}
	for(int i=1;i<=n;i++)
	{
		if(nxt[i]-1>=0){
			dp[i]=dp[nxt[i]-1]+1;
		}
	}
	for(int i=1;i<=n;i++){
		ans+=dp[i];
	}
	cout << ans;
	return 0;
}

源文件, 语言: C++14

詳細信息

Pretests

Final Tests

Test #1:

score: 5

Accepted

time: 0ms

memory: 27316kb

input:

10
aaaaaaaaaa

output:

result:

ok single line: '25'

Test #2:

score: 5

Accepted

time: 0ms

memory: 26976kb

input:

10
ooooppuuhh

output:

result:

ok single line: '16'

Test #3:

score: 5

Accepted

time: 0ms

memory: 28236kb

input:

10
nnppkkppjj

output:

result:

ok single line: '16'

Test #4:

score: 5

Accepted

time: 0ms

memory: 28624kb

input:

10
vvcckkhhqq

output:

result:

ok single line: '15'

Test #5:

score: 5

Accepted

time: 0ms

memory: 27224kb

input:

10
llmmxxoopp

output:

result:

ok single line: '15'

Test #6:

score: 5

Accepted

time: 0ms

memory: 29040kb

input:

800
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjddzziiyyyyjjooppiivvppmmooppttnnbbmmaaqqvvkkllyyvvmmjjsswwxxccwweeeekkhhaakkvvffaaiieessmmiibbff...

output:

result:

ok single line: '38306'

Test #7:

score: 5

Accepted

time: 0ms

memory: 27312kb

input:

800
pffpgppguqqugllgwhhwxjjxpkkpxnnxlkklunnuxiixallayqqyccccjnnjnyynqccqqjjqtuutboobwddwfwwfgvvgwuuwpqqppttpyggysrrsgwwgeddexbbxbssbvbbvbeebweewwkkwwddwnoontddtcddcajjapffptcctkeekboobfjjfvaavpjjpriirlfflnazdsevmozgezlngnhktrllcgorjoollwtqylmmzxfeibnifcebsnnugzluzlizievzxfnlokzodymigextlmyltzbmptyjf...

output:

result:

ok single line: '27479'

Test #8:

score: 5

Accepted

time: 0ms

memory: 28036kb

input:

8000
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...

output:

result:

ok single line: '3820477'

Test #9:

score: 5

Accepted

time: 0ms

memory: 28944kb

input:

8000
neenbnnbvjjvddddommolrrlzttzqwwqlfflijjiaqqayaayihhiqmmqduudlzzlyzzyannatyytfiifbqqbroorcffcgjjgwhhwoqqopuupdjjdeqqewnnwvwwvpiiprqqrukkuhbbhsiisrqqrxvvxfmmfzkkzjlljimmiazzariirdvvdcuucpaapbaabbaabccccxqqxivvipttpqffqmggmzhhzdaadyxxyhccheddeaiianggnxjjxqssqfaafqllqskksfuufviivozzocwwcznnzfxxfnss...

output:

result:

ok single line: '2713693'

Test #10:

score: 5

Accepted

time: 0ms

memory: 28584kb

input:

8000
ivviurrukrrkaccafoofaxxaleelcyycsiisimmifvvfoeeodppdneenqjjqsccsguugonnoyiiymttmcjjcmkkmjwwjieeikeekdbbdolloyvvyolloxiixmaamfnnfzrrzqbbqweewvttvboobbeebcmmcsqqsiyyifddfyvvyvttvvddvejjeeeeeleellzzlzbbzcrrcobbowsswquuqozzoyqqyulluwvvwyxxyxllxwrrwgmmgeppecvvcsiisyvvyukkuyppyryyrhjjhthhtvssvvnnvnee...

output:

result:

ok single line: '2721590'

Test #11:

score: 5

Accepted

time: 0ms

memory: 28020kb

input:

200000
tdaatgfvypbdkxdlvttiuksoooxszoqnqvmtznizlqfstlenqrnmdpkmvhmzftporwzvlbpyplrvrkgrpvqxyjcwwpcinilarbaudodadcglszflkzvmmdahgqphqoueltddqlymwpvweslymviccsmhuezesmlwsswgznaofullpxciuezrbkxfnodiglhpyrfcjajyuqzfoxsysgeqrqmvtqysypgaivfetwhmgxngzdvavbkipanoopqftdmntwpxgaljiqrkppywfuspzfgljheckapftjqar...

output:

result:

ok single line: '8356'

Test #12:

score: 5

Accepted

time: 0ms

memory: 28320kb

input:

200000
nleqrvpkpopfbstnolidsxrfhivbwbbqbwxmvymzmnwozrbklbuwliccquzhpfjsbxlnkzewvjpjarqmwcpsvovxeynjrgdjxrauincbnjvokawliinjqqulwxxeztpbrotihuiyjjqsxxosragocxbpjmhquczgwfakfaojxslteazikjqkebpcrrggswjiyetkpyvjubhtoounhveftykvetuwqgpddicnarbsigpjytmhcymvapbmkforkaeccsuhmwiuljmvajlztzjghnohlmxnmdehfxnra...

output:

result:

ok single line: '8340'

Test #13:

score: 5

Accepted

time: 6ms

memory: 28200kb

input:

200000
abbabbbbbbaababaaabaaaababaaaaaabbababababbabbaaababbbbaabaabbbbbbababaabababbababaabbaabaaaabbbbbaabbbbaababbbabaaababbbbbbbbbbabbbabaabaabaababbbbbbabaabbbbbbbbbbaaabbbbabaabbaababaaabbabbaaabbbbbaaabababaababbaaabbbbababbbbbbaaaabaaaaaaabbbaabbaaaabbabbbbbaabbbbbbbabbaaaabaaabaabbaaaababbb...

output:

52315097

result:

ok single line: '52315097'

Test #14:

score: 5

Accepted

time: 5ms

memory: 28060kb

input:

200000
aaaababaaaaabbabababbbbabbbbababbabbaabaaabbabbaabaaaaaabaaaabbbbbbbabaabbabaabababbbaabbbbabbbbbaabaaaabaaaababaaaabbaaaaabbbabbbabbbbbbbaabbbabbaaabbbabaabaaaaaaaaababbaaabbbbaabaabbaaababbabbaabbbbaaababbbbbbbbbbbaabaaabbaaabaabbaaabbabaabbabbaabbbababbaaabaaaaaabbbbbbbabaabbabbaabaabaabaa...

output:

72221142

result:

ok single line: '72221142'

Test #15:

score: 5

Accepted

time: 10ms

memory: 27916kb

input:

200000
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

2395581278

result:

ok single line: '2395581278'

Test #16:

score: 5

Accepted

time: 10ms

memory: 27324kb

input:

200000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

2396621459

result:

ok single line: '2396621459'

Test #17:

score: 5

Accepted

time: 13ms

memory: 27300kb

input:

200000
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...

output:

2395864064

result:

ok single line: '2395864064'

Test #18:

score: 5

Accepted

time: 183ms

memory: 28984kb

input:

2000000
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

239586659381

result:

ok single line: '239586659381'

Test #19:

score: 5

Accepted

time: 180ms

memory: 28988kb

input:

2000000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

239687303822

result:

ok single line: '239687303822'

Test #20:

score: 5

Accepted

time: 180ms

memory: 29076kb

input:

2000000
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...

output:

239608981171

result:

ok single line: '239608981171'