QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#734934#9522. A Simple String ProblemwinsunAC ✓539ms79668kbC++144.0kb2024-11-11 16:07:282024-11-11 16:07:29

Judging History

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

  • [2024-11-11 16:07:29]
  • 评测
  • 测评结果:AC
  • 用时:539ms
  • 内存:79668kb
  • [2024-11-11 16:07:28]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <utility>
#define fi first
#define se second

using namespace std;
typedef long long LL;

template <typename Tp> inline void read(Tp& x) {
    char ch; bool op = 0; x = 0;
    do ch = getchar(), op |= ch == '-'; while (ch < '0' || ch > '9');
    do x = (x<<3)+(x<<1)+(ch&15), ch = getchar(); while (ch >= '0' && ch <= '9');
    if (op) x = -x;
}

bool Mst;

const int MAXN = 4e5+5;

int lg[MAXN];

class SA {
private:
    int sa[MAXN], rk[MAXN], cnt[MAXN], tmp[MAXN];
    int st[MAXN][20];
    int n, m;
    void rsort() {
        for (int i = 1; i <= m; ++i) cnt[i] = 0;
        for (int i = 1; i <= n; ++i) ++cnt[rk[i]];
        for (int i = 1; i <= m; ++i) cnt[i] += cnt[i-1];
        for (int i = n; i; --i) sa[cnt[rk[tmp[i]]]--] = tmp[i];
    }
public:
    char str[MAXN];
    void calc() {
        n = strlen(str + 1), m = 127;
//        puts(str + 1);
        for (int i = 1; i <= n; ++i) rk[i] = str[i], tmp[i] = n-i+1;
        rsort();
        for (int k = 1; k == 1 || m < n; k <<= 1) {
            int x = 0;
            for (int i = 1; i <= k; ++i) tmp[++x] = n - i + 1;
            for (int i = 1; i <= n; ++i) if (sa[i] > k) tmp[++x] = sa[i] - k;
            rsort();
            for (int i = 1; i <= n; ++i) tmp[i] = rk[i];
            auto cmp = [&](int x, int y) {
                if (tmp[x] != tmp[y]) return 1;
                if (x + k <= n && y + k <= n) return int(tmp[x+k] != tmp[y+k]);
                return 1;
            };
            rk[sa[1]] = m = 1;
            for (int i = 2; i <= n; ++i) rk[sa[i]] = m += cmp(sa[i-1], sa[i]);
        } 
//        for (int i = 1; i <= n; ++i) printf("%d ", sa[i]); puts("");
        for (int i = 1, x = 0; i <= n; ++i) {
            if (rk[i] == 1) { st[rk[i]][0] = x = 0; continue; }
            if (x) --x;
            for (int j = sa[rk[i]-1]; i+x <= n && j+x <= n && str[i+x] == str[j+x]; ++x);
            st[rk[i]][0] = x;
        }
        for (int k = 1; 1 << k <= n; ++k) {
            for (int l = 1; l <= n - (1<<k) + 1; ++l) {
                st[l][k] = min(st[l][k-1], st[l+(1<<k-1)][k-1]);
            }
        }
    }
    
    int query(int x, int y) {
        if (rk[x] > rk[y]) swap(x, y);
        int l = rk[x] + 1, r = rk[y], len = r - l + 1, k = lg[len];
//        printf("%d %d %d\n", l, r, k);
        return min(st[l][k], st[r-(1<<k)+1][k]);
    }
} ori, rev;

int n;
char a[MAXN], b[MAXN];

int solve() {
    for (int k = n + 1 >> 1; k; --k) {
        for (int p = 1, q, lcp, lcs; p <= n - k + 1; p += k) {
            q = p + k;
            lcp = ori.query(p, q), lcs = rev.query(n-p+2, n-q+2);
            lcp += ori.query(p+lcp, n+1 +q+lcp);
//            printf("%d %d %d %d\n", p, q, lcp, lcs);
            if (lcp + lcs >= k) return k;
            lcp = ori.query(p, n+1 +q), lcs = rev.query(n-p+2, n+1 +n-q+2);
//            printf("%d %d %d %d\n", p, q, lcp, lcs);
            if (lcp + lcs >= k) return k;
            lcp = ori.query(n+1 +p, n+1 +q), lcs = rev.query(n+1 +n-p+2, n+1 +n-q+2);
            lcs += rev.query(n-p+2+lcs, n+1 +n-q+2+lcs);
//            printf("%d %d %d %d\n", p, q, lcp, lcs);
            if (lcp + lcs >= k) return k;
        }
    }
    return 0;
}

bool Med;

int main() {
    #ifndef ONLINE_JUDGE
    freopen("qoj9522.in", "r", stdin);
    freopen("qoj9522.out", "w", stdout);
    fprintf(stderr, "%.3lfMB\n", (&Mst - &Med) / 1048576.0);
    #endif
    lg[1] = 0;
    for (int i = 2; i <= 4e5+1; ++i) lg[i] = lg[i>>1] + 1;
    read(n), ++n, scanf("%s%s", a+1, b+2);
    a[n] = '#', b[1] = '@'; 
//    printf("%s %s\n", a+1, b+1); 
    for (int i = 1; i <= n; ++i) {
        ori.str[i] = a[i], ori.str[i+n+1] = b[i];
        rev.str[n-i+1] = a[i], rev.str[n-i+1+n+1] = b[i];
    }
    ori.str[n+1] = rev.str[n+1] = '$';
    ori.calc(), rev.calc();
    printf("%d\n", solve() << 1);
    return 0;
}

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

詳細信息

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 3ms
memory: 20172kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 247ms
memory: 79668kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 235ms
memory: 79284kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 247ms
memory: 79348kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 539ms
memory: 79284kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 209ms
memory: 79356kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 226ms
memory: 79372kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 377ms
memory: 79276kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 3ms
memory: 20784kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 3ms
memory: 19200kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 3ms
memory: 21584kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed