QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#108771#5440. P-P-PalindromezhanghaojieWA 185ms37064kbC++141.4kb2023-05-26 17:11:542023-05-26 17:12:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-26 17:12:20]
  • 评测
  • 测评结果:WA
  • 用时:185ms
  • 内存:37064kb
  • [2023-05-26 17:11:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10,P = 13331;
typedef long long LL;
typedef unsigned long long ULL;

struct Node
{
	int ch[26];
	int len,fail;
}tr[N];
char s[N];
int n,cnt,tot,las;
ULL p[N],h[N];
map<ULL,int> mp;
LL ans;

int new_node(int l)
{
	int p=++tot;
	memset(tr[p].ch,0,sizeof tr[p].ch);
	tr[p].fail=0;
	tr[p].len=l;
	return p;
}

void init()
{
	cnt=las=0;
	tot=-1;
	new_node(0);
	new_node(-1);
	tr[0].fail=1;
}

int find_fail(int x)
{
	while(s[cnt]!=s[cnt-tr[x].len-1]) x=tr[x].fail;
	return x;
}

void insert(int x)
{
	int now=find_fail(las);
	if(!tr[now].ch[x])
	{
		int p=new_node(tr[now].len+2);
		tr[p].fail=tr[find_fail(tr[now].fail)].ch[x];
		tr[now].ch[x]=p;
	}
	las=tr[now].ch[x];
}

ULL sr(int l,int r)
{
	return h[r]-h[l-1]*p[r-l+1];
}

int main()
{
	p[0]=1;
	for(int i=1;i<N;i++)
	p[i]=p[i-1]*P;
	int t;
	cin>>t;
	while(t--)
	{
		scanf("%s",s+1);
		n=strlen(s+1);
		init();
		for(int i=1;i<=n;i++)
		h[i]=h[i-1]*P+s[i];
		
		for(int i=1;i<=n;i++)
		{
			cnt++;
			insert(s[i]-'a');
			int len=tr[las].len,flen=tr[tr[las].fail].len;
			int diff=len-flen;
			if(len%diff!=0)
			diff=len;
			
			ULL tmp=sr(i-diff+1,i);
			if(!mp[tmp]) mp[tmp]=len/diff;
			else mp[tmp]=max(mp[tmp],len/diff);
		}
	}
	for(auto i:mp)
	ans+=1ll*i.second*i.second;
	cout<<ans<<endl;
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 13752kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 1ms
memory: 15716kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 1ms
memory: 13664kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 7ms
memory: 15664kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

score: 0
Accepted
time: 14ms
memory: 22340kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

score: 0
Accepted
time: 18ms
memory: 20328kb

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

score: 0
Accepted
time: 161ms
memory: 35076kb

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

133586

result:

ok 1 number(s): "133586"

Test #8:

score: 0
Accepted
time: 153ms
memory: 35684kb

input:

3
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbabab...

output:

118967

result:

ok 1 number(s): "118967"

Test #9:

score: 0
Accepted
time: 129ms
memory: 35292kb

input:

3
bbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabb...

output:

114444

result:

ok 1 number(s): "114444"

Test #10:

score: 0
Accepted
time: 185ms
memory: 31828kb

input:

3
abbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbabab...

output:

115321

result:

ok 1 number(s): "115321"

Test #11:

score: 0
Accepted
time: 158ms
memory: 37064kb

input:

3
azzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazaz...

output:

131825

result:

ok 1 number(s): "131825"

Test #12:

score: 0
Accepted
time: 15ms
memory: 16196kb

input:

3
yazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbyb...

output:

6

result:

ok 1 number(s): "6"

Test #13:

score: 0
Accepted
time: 9ms
memory: 16496kb

input:

3
azbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazby...

output:

6

result:

ok 1 number(s): "6"

Test #14:

score: 0
Accepted
time: 10ms
memory: 16156kb

input:

3
byazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyaz...

output:

6

result:

ok 1 number(s): "6"

Test #15:

score: -100
Wrong Answer
time: 56ms
memory: 33036kb

input:

1
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabba...

output:

70307

result:

wrong answer 1st numbers differ - expected: '113382', found: '70307'