QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#290104#5065. Beautiful StringRemakee#WA 208ms199180kbC++14967b2023-12-24 13:27:022023-12-24 13:27:03

Judging History

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

  • [2023-12-24 13:27:03]
  • 评测
  • 测评结果:WA
  • 用时:208ms
  • 内存:199180kb
  • [2023-12-24 13:27:02]
  • 提交

answer

// Skyqwq
#include <bits/stdc++.h>

using namespace std;

const int N = 5005;

typedef long long LL;

int n, f[N][N], g[N][N];

char s[N];

void clr() {
	for (int i = 0; i <= n + 1; i++)
		for (int j = 0; j <= n + 1; j++)
			f[i][j] = g[i][j] = 0;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
    	scanf("%s", s + 1);
    	n = strlen(s + 1);
    	for (int i = n; i; i--) {
    		for (int j = n; j; j--) {
    			if (s[i] == s[j])
    				f[i][j] = f[i + 1][j + 1] + 1;
    		}
    	}
    	for (int i = 1; i <= n; i++) {
    		for (int j = 1; j <= n; j++) {
    			if (i - j >= 1 && f[i - j][i] >= j)
    				g[i][j] = 1;
    			g[i][j] += g[i][j - 1];
    		}
    	}
    	LL ans = 0;
    	for (int i = 1; i <= n; i++) {
    		for (int j = i + 1; j <= n; j++) {
    			int u = min(f[i][j], j - i - 1);
    			ans += g[i][u - 1];
    		}
    	}
    	printf("%d\n", ans);
    	clr();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3716kb

input:

2
114514
0000000

output:

1
3

result:

ok 2 number(s): "1 3"

Test #2:

score: -100
Wrong Answer
time: 208ms
memory: 199180kb

input:

11
79380
2483905227
37902399703986576270
39991723655814713848046032694137883815354365954917
5541883522667841718787744915558298207485830622522715211018760095628594390563630840464643840093757297
56530485554219245862513973750218715585679416120445975390556326891488719311495909340757506478400624741858999...

output:

0
0
0
1
4
19
105
104
978
1932
13689

result:

wrong answer 4th numbers differ - expected: '2', found: '1'