XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#100410 #1059. 1-07E. JM的模板题 Accepted 100 5063 ms 24924 K C++ 17 / 1.8 K 滴蜡熊 2023-07-22 23:28:14
显示原始代码 
#include <bits/stdc++.h>
using namespace std;

//进行一个oi-wiki的抄

const int N = 1000010;

char s[N];
// key1[i] = rk[id[i]]（作为基数排序的第一关键字数组）
int n, sa[N], rk[N], oldrk[N << 1], id[N], key1[N], cnt[N];

bool cmp(int x, int y, int w) { return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w]; }

char t[N];
int upper() {
    int l = 1, r = n;
    while (true) {
        // cout<<"s "<<l<<" "<<r<<endl;
        if (l == r) {
            return l;
        }
        int mid = (l + r) / 2;
        // cout<<"cmp "<<(t+1)<<" "<<(s+sa[mid])<<endl;
        if (strcmp(t + 1, s + sa[mid]) >= 0) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
}

int main() {
    int i, m = 127, p, w;

    scanf("%s", s + 1);
    n = strlen(s + 1);
    s[n + 1] = 126;
    n++;
    for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

    for (w = 1;; w <<= 1, m = p) {  // m=p 就是优化计数排序值域
        for (p = 0, i = n; i > n - w; --i) id[++p] = i;
        for (i = 1; i <= n; ++i)
            if (sa[i] > w)
                id[++p] = sa[i] - w;

        memset(cnt, 0, sizeof(cnt));
        for (i = 1; i <= n; ++i) ++cnt[key1[i] = rk[id[i]]];
        // 注意这里px[i] != i，因为rk没有更新，是上一轮的排名数组

        for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[key1[i]]--] = id[i];
        memcpy(oldrk + 1, rk + 1, n * sizeof(int));
        for (p = 0, i = 1; i <= n; ++i) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
        if (p == n) {
            break;
        }
    }

    // for (i = 1; i <= n; ++i) printf("%d ", sa[i]);

    int q;
    cin >> q;
    int cnt = 0;
    for (int i = 1; i <= q; ++i) {
        cin >> (t + 1);
        int a = upper();
        t[strlen(t + 1) + 1] = 126;
        int b = upper();
        cnt += b - a;
    }
    cout << cnt;

    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：140 ms
内存：24808 KiB

输入文件（1.in） 

ababaaabbbbbbbaabaaaaababababbaaabbaabaabaabaaabbaaababbbabbaababbaabbababbaabbaaabbabbbaaaabaabbbaa
<2000107 bytes omitted>

答案文件（1.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：104 ms
内存：24832 KiB

输入文件（2.in） 

bbaaaabaaaabbbbaaabbbbabbaaabaaabbbbbaaabababaabbbaaabbabaaaababaaabababbabaaababbbabbabababaaaababb
<2000107 bytes omitted>

答案文件（2.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：104 ms
内存：24692 KiB

输入文件（3.in） 

ababbbaaaababbababaaabbbbabbaabaabbaaababbabbbaaaaaabababbbbabaababaabaaaaaabbbabbabbbbbbbbabbababba
<2000107 bytes omitted>

答案文件（3.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：130 ms
内存：24824 KiB

输入文件（4.in） 

bbbbbabbaaabbaaabbabbbabbbabbabaaababbaaabaaabababbaaaabbaaabbbbbbbabbabaabbaabbabababaaaaababbabaaa
<2000107 bytes omitted>

答案文件（4.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：99 ms
内存：24692 KiB

输入文件（5.in） 

abaaaaaabbaaaaabaabaabbaaaaabbbbbaababbaaabbaaababbbbaaaaaaaaaaabaababbabbbbaaaaababbbbbbaabbbbabbab
<2000107 bytes omitted>

答案文件（5.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：133 ms
内存：24776 KiB

输入文件（6.in） 

babbbbbabbaabbbbabbbababbaaabaabaaabaabbaabbbabbbaaabbbabbbbbbbabbbabaabbbbabbbababaaaabbababaababaa
<2000107 bytes omitted>

答案文件（6.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：101 ms
内存：24692 KiB

输入文件（7.in） 

baaaaaaaaabaabbbbbbabababbaabaababbbaababbbbabaabababaabbabaabaabbaaaabaaabbabaabbbbbbabababbbbbbabb
<2000107 bytes omitted>

答案文件（7.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：149 ms
内存：24840 KiB

输入文件（8.in） 

baababbbbbbbbaaabbbbbbbbbabbaabbaaaaabababbbbbabbbababaaaaabababbbaababaaaabbbababababbaabbaabbabbab
<2000107 bytes omitted>

答案文件（8.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：152 ms
内存：24816 KiB

输入文件（9.in） 

abbbbaabbbbbaabbaaabaaabbbbabbbaaabbbbaaababbbbbbabbaaababaaaaaaabaabbbaaabbbaabbbabbbbabbbbbaababba
<2000107 bytes omitted>

答案文件（9.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：108 ms
内存：24704 KiB

输入文件（10.in） 

aaababbbaabbabaaaababbabaaabaabbaabbbbbbbaababbabbbaaababbaabbaaabbabababbaabaaabaaababaaaaaabbabbba
<2000107 bytes omitted>

答案文件（10.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：192 ms
内存：24792 KiB

输入文件（11.in） 

cbedbecbbaacaaedadbaaadebacdcdeaebdeaeccaeccedcddadcaeddadcedebeadeeebabeebadaeeccabaececebdabcdcbbe
<2199910 bytes omitted>

答案文件（11.out） 

10266

用户输出 

10266

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：228 ms
内存：24900 KiB

输入文件（12.in） 

caacebdeebebecebcabecedeccdcacaaadeddaddbebeddecaddcebdeaababaebadbbebacdabccdcbdbabdadaeccdecbcccde
<2199910 bytes omitted>

答案文件（12.out） 

10165

用户输出 

10165

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：199 ms
内存：24820 KiB

输入文件（13.in） 

ecacbcbaccbacdedebaebeabaaeabccbedaaceaaeabbbcbbacadbbadeceacbdbdebadcdabcdeeebaaedaaacacebbccecaddb
<2199910 bytes omitted>

答案文件（13.out） 

10003

用户输出 

10003

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：189 ms
内存：24692 KiB

输入文件（14.in） 

dbcdaaebbadbddcebebbbcaabebbadbaeddeadcccddedbabcdbdeebbebbbdaecdadedcaaabedcecbdcdbadbeabeaebcceccb
<2199910 bytes omitted>

答案文件（14.out） 

10297

用户输出 

10297

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：198 ms
内存：24808 KiB

输入文件（15.in） 

eddecaacdbacbedaaaecacecdaedbdcbcaeeddedaacbecbabcbababcbddbabbbaccebcbbecdadadcbeabbdadabbdecdeacee
<2199910 bytes omitted>

答案文件（15.out） 

10355

用户输出 

10355

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：197 ms
内存：24688 KiB

输入文件（16.in） 

cdacecdebdabeeedddadbdaabbdecaeaabebaaacdcccddebbeeaecdedcacbaabedccdececbdbbcdedbeaccbeaeeebdaaaceb
<2199910 bytes omitted>

答案文件（16.out） 

10238

用户输出 

10238

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：237 ms
内存：24768 KiB

输入文件（17.in） 

cddbdacadcdcdeebcbedaeaeaabbbedabecddeaecededdeddddeececadceabcdcbedeccbeeaccbccaeeddaecccbeaedebeba
<2199910 bytes omitted>

答案文件（17.out） 

10314

用户输出 

10314

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：199 ms
内存：24740 KiB

输入文件（18.in） 

ecdceedcbcbdbccbccbbeeeceeedcaaeebecceaaecacbacdcdebbceaecddacaadeeedbbeacdbdccccbeaebeaacbdcdecaacd
<2199910 bytes omitted>

答案文件（18.out） 

10392

用户输出 

10392

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：167 ms
内存：24704 KiB

输入文件（19.in） 

adeedbeeccaadcebededeadbbbddebdcbcabcbaaddaccdddddeebdeccdedbdbcccebcbdbbcbdcbeeacdbaaebdebadbdaecad
<2199910 bytes omitted>

答案文件（19.out） 

10195

用户输出 

10195

系统信息 

Exited with return code 0
测试点 #20
Accepted
得分：100
用时：183 ms
内存：24776 KiB

输入文件（20.in） 

abcacbdccbdaeebbccbbdadacaebceebdacbbcccebdcbacddbabaeccdbcbeeecddeddacabadbbbceeadbaabbcdeedeadcedd
<2199910 bytes omitted>

答案文件（20.out） 

10374

用户输出 

10374

系统信息 

Exited with return code 0
测试点 #21
Accepted
得分：100
用时：180 ms
内存：24800 KiB

输入文件（21.in） 

ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
<1502408 bytes omitted>

答案文件（21.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #22
Accepted
得分：100
用时：196 ms
内存：24924 KiB

输入文件（22.in） 

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>

答案文件（22.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #23
Accepted
得分：100
用时：191 ms
内存：24736 KiB

输入文件（23.in） 

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>

答案文件（23.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #24
Accepted
得分：100
用时：184 ms
内存：24776 KiB

输入文件（24.in） 

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
<1502408 bytes omitted>

答案文件（24.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #25
Accepted
得分：100
用时：176 ms
内存：24724 KiB

输入文件（25.in） 

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
<1502408 bytes omitted>

答案文件（25.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #26
Accepted
得分：100
用时：181 ms
内存：24816 KiB

输入文件（26.in） 

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
<1502408 bytes omitted>

答案文件（26.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #27
Accepted
得分：100
用时：199 ms
内存：24692 KiB

输入文件（27.in） 

kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
<1502408 bytes omitted>

答案文件（27.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #28
Accepted
得分：100
用时：175 ms
内存：24812 KiB

输入文件（28.in） 

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj
<1502408 bytes omitted>

答案文件（28.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #29
Accepted
得分：100
用时：189 ms
内存：24704 KiB

输入文件（29.in） 

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
<1502408 bytes omitted>

答案文件（29.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #30
Accepted
得分：100
用时：183 ms
内存：24700 KiB

输入文件（30.in） 

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
<1502408 bytes omitted>

答案文件（30.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ. | 鲁ICP备2020034929号