QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#290790 | #5065. Beautiful String | PolyBee# | WA | 2135ms | 4404kb | C++14 | 2.4kb | 2023-12-25 14:59:26 | 2023-12-25 14:59:27 |
Judging History
answer
#include <bits/stdc++.h>
#define M1(x) x=x-x/19260817*19260817
#define M2(x) x=x-x/2003110537*2003110537
using namespace std;
long long h1[5005], p1[5005];
long long h2[5005], p2[5005];
long long sml[5005];
char s[5005];
int n;
bool eq(int l, int r, int z, int y){
long long x1 = h1[r] - h1[l-1] * p1[r-l+1];
long long y1 = h1[y] - h1[z-1] * p1[y-z+1];
long long x2 = h2[r] - h2[l-1] * p2[r-l+1];
long long y2 = h2[y] - h2[z-1] * p2[y-z+1];
M1(x1);
M1(y1);
M2(x2);
M2(y2);
if(x1 < 0) x1 += 19260817;
if(y1 < 0) y1 += 19260817;
if(x2 < 0) x2 += 2003110537;
if(y2 < 0) y2 += 2003110537;
if(x1 == y1 && x2 == y2){
return true;
}
else return false;
}
map<pair<int,int>, int> sum;
pair<int,int> cal(int l, int r){
long long x1 = h1[r] - h1[l-1] * p1[r-l+1];
long long x2 = h2[r] - h2[l-1] * p2[r-l+1];
M1(x1);
M2(x2);
if(x1 < 0) x1 += 19260817;
if(x2 < 0) x2 += 2003110537;
return {(int)x1, (int)x2};
}
int main()
{
int T;
scanf("%d", &T);
p1[0] = p2[0] = 1;
for(int i = 1; i <= 5000; i++){
p1[i] = p1[i-1] * 233;
M1(p1[i]);
p2[i] = p2[i-1] * 157;
M2(p2[i]);
}
while(T--){
scanf("%s", s+1);
n = strlen(s+1);
int ans = 0;
for(int i = 1; i <= n; i++){
h1[i] = h1[i-1] * 233 + s[i];
M1(h1[i]);
//cout<<h1[i]<<" "<<p1[i]<<endl;
h2[i] = h2[i-1] * 157 + s[i];
M2(h2[i]);
}
for(int len = 1; len <= n; len++){
for(int l = n-2*len; l >= 1; l--){
pair<int,int> lst = cal(l+1+len, l+len*2);
sum[lst]++;
pair<int,int> nw = cal(l, l+len-1);
//cout<<l<<" - "<<l+len-1<<" : "<<l+1+len<<" "<<l+len*2<<endl;
//cout<<lst.first<<" "<<lst.second<<endl;
//cout<<nw.first<<" "<<nw.second<<endl;
ans += sum[nw] * sml[l];
//cout<<sum[nw]<<" ? "<<sml[l]<<endl;
//cout<<endl;
if(eq(l, l+len-1, l+len, l+2*len-1)){
sml[l+len]++;
}
}
sum.clear();
}
printf("%d\n", ans);
ans = 0;
sum.clear();
for(int i = 0; i <= n; i++)
sml[i] = 0;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3904kb
input:
2 114514 0000000
output:
1 3
result:
ok 2 number(s): "1 3"
Test #2:
score: 0
Accepted
time: 1878ms
memory: 4404kb
input:
11 79380 2483905227 37902399703986576270 39991723655814713848046032694137883815354365954917 5541883522667841718787744915558298207485830622522715211018760095628594390563630840464643840093757297 56530485554219245862513973750218715585679416120445975390556326891488719311495909340757506478400624741858999...
output:
0 0 0 2 4 20 119 113 1086 2128 15166
result:
ok 11 numbers
Test #3:
score: 0
Accepted
time: 56ms
memory: 3984kb
input:
50 11111111111111111111111111111111111111121111111111111111111111111111111111111112111111111121111111111211111121211121111111111111111111111111111211121111111111111111111111111111111111111111111111111112 111111111111111111111111111111111111111111111121111121111111111111111111111111111111111111111111...
output:
779344 799116 716078 723215 1197647 403357 652134 625671 414294 942493 390998 793444 612061 507395 473508 836065 461623 374925 539333 592574 676408 610940 463761 490048 995917 595830 424894 332669 596834 655095 521489 1032050 697420 752056 406316 360973 1180943 948628 478572 1026603 711224 429752 49...
result:
ok 50 numbers
Test #4:
score: 0
Accepted
time: 70ms
memory: 4028kb
input:
50 11211121122222111222111111222112111221112111121112221111111121211111212211212122112212221221112112221221112211211112121222112221211122112211112111112112211121222111222212211121111111112111112121111122 112112121211212111212221221222211211121212221111112122121211112221221121121112111221211112122121...
output:
7499 6375 7041 7889 6622 6804 8695 8795 7018 8387 8910 8019 8223 8820 7324 7144 8035 9941 7073 7373 7427 7280 6946 8204 7931 6769 7050 9268 7682 8232 7797 7356 7012 8967 7469 6869 11728 6562 7604 8840 7885 8658 7006 8156 10694 6716 6121 7499 7456 7981
result:
ok 50 numbers
Test #5:
score: -100
Wrong Answer
time: 2135ms
memory: 4120kb
input:
15 111111111111111111111111111111111111111111111111111111111111121111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111111111111111111...
output:
-1978378306 -142299245 56298360 -345762305 -1742858749 769356532 1523854696 892430452 1907882095 -1489234842 236758666 714533246 1101820191 -360214600 1788248324
result:
wrong answer 1st numbers differ - expected: '6611556286', found: '-1978378306'