QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#754831#7780. Dark LaTeX vs. Light LaTeXSuhyTL 618ms16588kbC++112.7kb2024-11-16 15:55:062024-11-16 15:55:08

Judging History

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

  • [2024-11-25 20:53:52]
  • hack成功,自动添加数据
  • (/hack/1258)
  • [2024-11-16 15:55:08]
  • 评测
  • 测评结果:TL
  • 用时:618ms
  • 内存:16588kb
  • [2024-11-16 15:55:06]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#pragma GCC optimize(3)

using namespace std;

const int maxn = 10004;
const int b1 = 31;
const int b2 = 37;

int n, m;
int s[maxn], t[maxn];
ull ps1[maxn], pt1[maxn];
unordered_map <ull, int> mp1;
ull pwb1[maxn];
ll ans;

int f[maxn], cnt[maxn];
//babaa
void wok(int dlt)
{
    for(int i = 2, l = 2 + dlt - n + 1, r = dlt; i < n; i ++, l ++)
    {
        int j = f[i - 1];
        while(j > 0 && (s[j + 1 + dlt] != s[i + dlt] || (i + dlt > n && (i + dlt - j <= n || j + dlt >= n))))
            j = f[j];
        if(s[j + 1 + dlt] == s[i + dlt])
            j ++;
        f[i] = j;
        cnt[i] = 0;
        if(j != 0) cnt[i] ++;
        cnt[i] += cnt[j];
        if(cnt[i] && l > 1 && r - l + 1 <= m) 
        {
            //cout<<l<<' '<<r<<' '<<cnt[i]<<' '<<i<<' '<<f[i]<<' '<<s[i + dlt]<<' '<<s[1 + dlt]<<' ';
            // for(int j = l; j <= r; j ++)
            //     putchar(s[j] + 'a' - 1);
            // cout<<endl;
            ans += cnt[i] * mp1[ps1[r] - ps1[l - 1] * pwb1[r - l + 1]];
            //cout<<ps1[r] - ps1[l - 1] * pwb1[r - l + 1]<<endl;
        }
    }
}

void work()
{
    mp1.clear();
    for(int i = 1; i <= m; i ++)
    {
        for(int j = 1; j <= i; j ++)
        {
            if(i - j + 1 <= n)
                mp1[pt1[i] - pt1[j - 1] * pwb1[(i - j + 1)]] ++;
        }
    }
    for(int i = 1; i <= n; i ++)
        s[i + n] = s[i]; 
    for(int i = 1; i < n; i ++)
    {
        wok(i);
    }
}

signed main()
{
    char c = getchar();
    while('a' <= c && c <= 'z')
        s[++ n] = c - 'a' + 1, c = getchar();
    while(!('a' <= c && c <= 'z'))
        c = getchar();
    while('a' <= c && c <= 'z')
        t[++ m] = c - 'a' + 1, c = getchar();
    for(int i = 1; i <= n; i ++)
    {
        ps1[i] = ps1[i - 1] * b1 + s[i];
    }
    for(int i = 1; i <= m; i ++)
    {
        pt1[i] = pt1[i - 1] * b1 + t[i];
    }
    pwb1[0] = 1;
    for(int i = 1; i <= max(n, m); i ++)
    {
        pwb1[i] = 1ll * pwb1[i - 1] * b1;
    }
    swap(n, m);
    for(int i = 1; i <= max(n, m); i ++)
    {
        swap(s[i], t[i]);
        swap(ps1[i], pt1[i]);
    }
    work();
    //cout<<"-----"<<endl;
    swap(n, m);
    for(int i = 1; i <= max(n, m); i ++)
    {
        swap(s[i], t[i]);
        swap(ps1[i], pt1[i]);
    }
    work();
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= i; j ++)
        {
            if(i - j + 1 <= m)
            {
                ull hsh1 = ps1[i] - ps1[j - 1] * pwb1[(i - j + 1)];
                ans += mp1[hsh1];
            }
        }
    }
    cout<<ans<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3864kb

input:

abab
ab

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

abab
abaaab

output:

29

result:

ok 1 number(s): "29"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

abcd
abcde

output:

10

result:

ok 1 number(s): "10"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

aaba
ba

output:

6

result:

ok 1 number(s): "6"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

babababaaabbaabababbbaabbbababbaaaaa
aaaabbaababbab

output:

1161

result:

ok 1 number(s): "1161"

Test #6:

score: 0
Accepted
time: 618ms
memory: 4264kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

78156256250000

result:

ok 1 number(s): "78156256250000"

Test #7:

score: 0
Accepted
time: 116ms
memory: 16152kb

input:

gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...

output:

60716448

result:

ok 1 number(s): "60716448"

Test #8:

score: 0
Accepted
time: 125ms
memory: 16588kb

input:

mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...

output:

60679828

result:

ok 1 number(s): "60679828"

Test #9:

score: -100
Time Limit Exceeded

input:

vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...

output:


result: