QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#400954#7780. Dark LaTeX vs. Light LaTeXucup-team228#AC ✓867ms424632kbC++203.5kb2024-04-27 19:04:042024-04-27 19:04:04

Judging History

你现在查看的是测评时间为 2024-04-27 19:04:04 的历史记录

  • [2024-11-25 21:11:59]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:585ms
  • 内存:493940kb
  • [2024-11-25 20:53:52]
  • hack成功,自动添加数据
  • (/hack/1258)
  • [2024-04-27 19:04:04]
  • 评测
  • 测评结果:100
  • 用时:867ms
  • 内存:424632kb
  • [2024-04-27 19:04:04]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> calc_pref_func(const string& s) {
    int n = s.size();
    vector<int> pref(n, 0);
    for (int i = 1, border = 0; i <= n - 1; i++) {
        while (s[border] != s[i] && border) {
            border = pref[border - 1];
        }
        if (s[border] == s[i]) {
            border++;
        }
        pref[i] = border;
    }
    return pref;
}

int add(int a, int b, int mod) {
    return a + b >= mod ? a + b - mod : a + b;
}

int mult(int a, int b, int mod) {
    return int(1ll * a * b % mod);
}

const int m1 = 1e9 + 123;
const int m2 = 1e9 + 321;

const int b1 = 321123;
const int b2 = 123321;

const int N = 5e3 + 10;
int cnt[N][N];
int lcp[N][N];
ll pref[N][N];
int lcp_st[N][N];

ll merge(ll h1, ll h2) {
    return (h1 << 31) | h2;
}

void calc_subs(const string& s, const string& t) {
    for (int i = 0; i <= s.size() + 2; i++) {
        for (int j = 0; j <= t.size() + 2; j++) {
            lcp_st[i][j] = 0;
        }
    }
    for (int i = int(s.size()) - 1; i >= 0; i--) {
        for (int j = int(t.size()) - 1; j >= 0; j--) {
            lcp_st[i][j] = s[i] == t[j] ? lcp_st[i + 1][j + 1] + 1 : 0;
        }
    }

    for (int i = 0; i <= s.size() + 2; i++) {
        for (int j = 0; j <= s.size() + 2; j++) {
            cnt[i][j] = 0;
        }
    }

    for (int i = 0; i < s.size(); i++) {
        for (int j = 0; j < t.size(); j++) {
            int k = min(lcp_st[i][j], int(s.size()) - i);
            cnt[i][i]++;
            cnt[i][i + k]--;
        }
        for (int j = i; j < s.size(); j++) {
            cnt[i][j] += cnt[i][j - 1];
        }
    }

    for (int j = 0; j < s.size(); j++) {
        for (int i = 0; i <= j; i++) {
            pref[i][j] = cnt[i][j];
            if (i) pref[i][j] += pref[i - 1][j];
        }
    }
}

ll calc(const string& s, const string& t) {
    calc_subs(s, t);
    for (int i = 0; i <= s.size() + 2; i++) {
        for (int j = 0; j <= s.size() + 2; j++) {
            lcp[i][j] = 0;
        }
    }
    for (int i = int(s.size()) - 1; i >= 0; i--) {
        for (int j = int(s.size()) - 1; j >= i; j--) {
            lcp[i][j] = s[i] == s[j] ? lcp[i + 1][j + 1] + 1 : 0;
        }
    }
    ll ans = 0;
    // cout << cnt[1][1] << " " << cnt[0][1] << " " << pref[1][1] << "\n";
    for (int i = 0; i < s.size(); i++) {
        for (int j = i; j < s.size(); j++) {
            int k = lcp[i][j + 1];
            k = min(k, j - i);
            // cout << i << " " << j << " " << k << " " << pref[i + k][j] << " " << (i == 0 ? 0 : pref[i - 1][j]) << "\n";
            ans += pref[i + k][j] - (i == 0 ? 0 : pref[i - 1][j]);
        }
    }
    // cout << "\n";
    return ans;
}

ll solve(string s, string t) {
    ll ans = 0;
    ans += calc(s, t);
    for (int i = 0; i < s.size(); i++) {
        for (int j = i; j < s.size(); j++) {
            ans -= cnt[i][j];
        }
    }
    reverse(s.begin(), s.end());
    reverse(t.begin(), t.end());
    ans += calc(t, s);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    string s, t;
    cin >> s >> t;
//     s = string(5000, 'a');
//     t = string(5000, 'a');
    cout << solve(s, t) << "\n";

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

input:

abab
ab

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

abab
abaaab

output:

29

result:

ok 1 number(s): "29"

Test #3:

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

input:

abcd
abcde

output:

10

result:

ok 1 number(s): "10"

Test #4:

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

input:

aaba
ba

output:

6

result:

ok 1 number(s): "6"

Test #5:

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

input:

babababaaabbaabababbbaabbbababbaaaaa
aaaabbaababbab

output:

1161

result:

ok 1 number(s): "1161"

Test #6:

score: 0
Accepted
time: 728ms
memory: 424632kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

78156256250000

result:

ok 1 number(s): "78156256250000"

Test #7:

score: 0
Accepted
time: 12ms
memory: 92424kb

input:

gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...

output:

60716448

result:

ok 1 number(s): "60716448"

Test #8:

score: 0
Accepted
time: 23ms
memory: 91888kb

input:

mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...

output:

60679828

result:

ok 1 number(s): "60679828"

Test #9:

score: 0
Accepted
time: 715ms
memory: 413992kb

input:

vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...

output:

2655796915

result:

ok 1 number(s): "2655796915"

Test #10:

score: 0
Accepted
time: 752ms
memory: 413964kb

input:

ttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdt...

output:

2652657341

result:

ok 1 number(s): "2652657341"

Test #11:

score: 0
Accepted
time: 729ms
memory: 413956kb

input:

uupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupu...

output:

2619083676

result:

ok 1 number(s): "2619083676"

Test #12:

score: 0
Accepted
time: 14ms
memory: 91728kb

input:

ggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxg...

output:

61227979

result:

ok 1 number(s): "61227979"

Test #13:

score: 0
Accepted
time: 216ms
memory: 210708kb

input:

cwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcw...

output:

834307544

result:

ok 1 number(s): "834307544"

Test #14:

score: 0
Accepted
time: 708ms
memory: 414016kb

input:

trtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtr...

output:

2663862697

result:

ok 1 number(s): "2663862697"

Test #15:

score: 0
Accepted
time: 16ms
memory: 92220kb

input:

gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

0

result:

ok 1 number(s): "0"

Test #16:

score: 0
Accepted
time: 815ms
memory: 414244kb

input:

igkkcgocckgoocioiiggcgkigoggkociciigokikkcogkoookkiioikockoigokigiiciikcokoockgiiiogicgkkgoiogcggcgckgikccgcckoocgggogiccgkgcoccckgiooiogckoioiioogiicogkckgiickooiockogkoikogkkociioigocoiioccggkigciigcckkggiccciiiggkcgggcokookogiokoccccgogkcigokkckccoccgkoogokogkcioockkikigokiikkkoikiigckkooioogioio...

output:

1707132

result:

ok 1 number(s): "1707132"

Test #17:

score: 0
Accepted
time: 16ms
memory: 89888kb

input:

jkkkjjjkjkkkjjjjkkkkkjjjjjjkjjjjkjjjkkkjkjkkkkjjkkjjjkjkjjjkkkkjkjjkkkkkkkjkkkjkkjkkjjkkjjkjjjkkkjkjjkjkjjjjkkjjjjjjkkjjjkkkjkjkkkkkjkjjkjjkkkkkkkkjkkkjjkjjkkkjkjjkjjkkjjkkkkkjjjjjjkjjjkkjkjjkjjjkjkkjkjkkkkjjkkjkkjkkkjkkkkkkkjkjjkkjkjjkjkkkkkkkjkkjkkkkjkjkkkkkkkjkkjjkjjjkjjkkkkjkjkkjjjjjkjkjjjjkjkkk...

output:

2954810

result:

ok 1 number(s): "2954810"

Test #18:

score: 0
Accepted
time: 19ms
memory: 77944kb

input:

juxqlncuflculraueufcupffalouceftcepluhuupphohougacfftcrouohhnxopoguocjlpqpgppuhllpsnllqnftprunnucfcucclcplxuatfxtnljnuxnhapanlrpuexuflusncrapcrqpoganppxlloougftptxutfcrgchspahqghstuuefntfuauohlxlenpujeupuucnljxuunanustpuppllelnjcupqppaorpexophphnaopsxajtonupocuuoffpuqagutpuntfloalhrffhlrltghulpuoqop...

output:

40401

result:

ok 1 number(s): "40401"

Test #19:

score: 0
Accepted
time: 820ms
memory: 414020kb

input:

lmvbtqzhgzztvlsvzdesvgefvzkqfbvszmqjsgthnmhtifhztvhihdvgeqmhvzzqmqjhdmmteshvjbgvsfzgkivmvggvzbvzlemnmqhvqfmkmvmqhfqeehqvkgsedzmgbheeielzqzqtfzzvvjfievbzhdkfivhksmzbegkzsilnzgnzbqeqtghdzljvvfedmkeivmnzznhfhekvzeqvvfvqzehdhvsmklbzhhfzdtzqlmhehqqvkbqmvlzvmlzmzdzdbvmmmzimmqvleggmzigqmivqzqhvkezgmjvvivvg...

output:

1421341

result:

ok 1 number(s): "1421341"

Test #20:

score: 0
Accepted
time: 16ms
memory: 90472kb

input:

cccfcccffcffffffcfffffccffffffcccffffcffccfcffcfcfffcfcffcfcfcccccccfcffcfccccccffcccfcccfcccccccffcffffffcfccffcccfcfccfcffcfffccffccfffffccfcffcffffffffccfffffffccffcfccfcfcfffccfffffccccfcfccfccfcfcfccccfcccffccccfcccfccccfcfcffcccffcfffcfcccccffccfcccccccfffcffcccccccccccccfcfcffcffcffcffcffcfcf...

output:

3118221

result:

ok 1 number(s): "3118221"

Test #21:

score: 0
Accepted
time: 867ms
memory: 413960kb

input:

srrsrssrrsssrsrsrsrrrrrssrrssrsrsssrrrrsssrrsrrrsrrrrssrsssrssrrrsrrsrsssssrrrrrrrrrrsrrssrsrrrrrsssrrrrsssrsrrsrsssrrrrrsrrssrrssrrrrsrrsrsrsrrrsrrrrssrrssssrsrrrrsrssrsrsssssssrsrrsrrrrrsrssssrrsssrsssrrrrsssssrsrrrsssrssrrrssrsrsssssrrrssrrrrrsssrrsrrsrrrssrrssrsrsrssssrssssrsrrrsrrssrsrsrsrsrsrr...

output:

75529025

result:

ok 1 number(s): "75529025"

Test #22:

score: 0
Accepted
time: 842ms
memory: 413908kb

input:

onpboooppuaeabbabzpoopnqpopnyrabrrpbyorlebzprboypaprrpabebdobozuborppyualtbzauprrobnrqbzuzrrbebotqulratlrobaoyztyrpqqroorbyledaropnnploroabtelydozdopabapqubynynubpybptpoopnyrolparqpaoooobbperyuezponoboyuaopbpqpporplbdrooozbybueyrpnpzodrroyarzbpzyprpdpzboaaobpppalllranutyaobbdptrpprzubdbryapbudylbqab...

output:

3326939

result:

ok 1 number(s): "3326939"

Test #23:

score: 0
Accepted
time: 17ms
memory: 88524kb

input:

etweelwwwwwtttweetleettetlwwlltwwettwtwwlttletlwtltwtwelltetteleelelwwttelwleweltewtwllltwweeelwtweweeweetltttwtelteltwtewteetwwtltwetlteettelwtewtlletlltllwtweewletwtwtleewttlellwwteettlwtttwteetwwltwttelltweetttwtelleleetwewlewewewtewtetttweteeweltltelwwlwltlletwlweelelwlwelelettwllwlewleteeteellw...

output:

547040

result:

ok 1 number(s): "547040"

Test #24:

score: 0
Accepted
time: 12ms
memory: 89976kb

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

38791844792

result:

ok 1 number(s): "38791844792"

Test #25:

score: 0
Accepted
time: 242ms
memory: 208256kb

input:

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

4804791846049

result:

ok 1 number(s): "4804791846049"

Test #26:

score: 0
Accepted
time: 771ms
memory: 413964kb

input:

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

output:

10043476749324

result:

ok 1 number(s): "10043476749324"

Test #27:

score: 0
Accepted
time: 500ms
memory: 332204kb

input:

yhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyh...

output:

269398620

result:

ok 1 number(s): "269398620"

Test #28:

score: 0
Accepted
time: 505ms
memory: 336832kb

input:

yhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyh...

output:

269769773

result:

ok 1 number(s): "269769773"

Test #29:

score: 0
Accepted
time: 524ms
memory: 336916kb

input:

baababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabba...

output:

287077563

result:

ok 1 number(s): "287077563"

Extra Test:

score: 0
Extra Test Passed