QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#744311#7780. Dark LaTeX vs. Light LaTeXSuhyRE 1ms3760kbC++172.5kb2024-11-13 21:30:052024-11-13 21:30:10

Judging History

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

  • [2024-11-25 20:53:52]
  • hack成功,自动添加数据
  • (/hack/1258)
  • [2024-11-13 21:30:10]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3760kb
  • [2024-11-13 21:30:05]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll

using namespace std;

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

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

int f[maxn], cnt[maxn];
//babaa
void wok(int dlt)
{
    for(int i = 2; i < n; i ++)
    {
        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];
        int l = i + dlt - n + 1;
        int r = dlt;
        if(l > 1) 
        {
            //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 ++)
        {
            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] = pwb2[0] = 1;
    for(int i = 1; i <= max(n, m); i ++)
    {
        pwb1[i] = 1ll * pwb1[i - 1] * b1;
    }
    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 ++)
        {
            ull hsh1 = ps1[i] - ps1[j - 1] * pwb1[(i - j + 1)];
            ans += mp1[hsh1];
        }
    }
    cout<<ans<<endl;
}

詳細信息

Test #1:

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

input:

abab
ab

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

abab
abaaab

output:

29

result:

ok 1 number(s): "29"

Test #3:

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

input:

abcd
abcde

output:

10

result:

ok 1 number(s): "10"

Test #4:

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

input:

aaba
ba

output:

6

result:

ok 1 number(s): "6"

Test #5:

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

input:

babababaaabbaabababbbaabbbababbaaaaa
aaaabbaababbab

output:

1161

result:

ok 1 number(s): "1161"

Test #6:

score: -100
Runtime Error

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:


result: