QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#290790#5065. Beautiful StringPolyBee#WA 2135ms4404kbC++142.4kb2023-12-25 14:59:262023-12-25 14:59:27

Judging History

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

  • [2023-12-25 14:59:27]
  • 评测
  • 测评结果:WA
  • 用时:2135ms
  • 内存:4404kb
  • [2023-12-25 14:59:26]
  • 提交

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'