XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#23853 #1134. ddd的回文串 Accepted 100 378 ms 2644 K C++ 17 / 2.2 K Leohh 2020-02-20 14:54:03
显示原始代码 
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1000005
#define MAX_A 205
#define INF 0x3f3f3f3f3f3f3f3fLL
#define int long long

using namespace std;

int n, m, K, T, ans = 0;
int c[2][MAX_A];
int f[MAX_A][MAX_A];
int g[MAX_A][MAX_A];
char s[MAX_N];
bool vis[MAX_N];

signed main() {
    scanf("%lld%lld%lld%lld%s", &n, &m, &K, &T, s + 1);
    char cx[4], cy[4];
    int x;
    memset(f, 0x3f, sizeof(f));
    for (int i = 'a'; i <= 'z'; i++) {
        f[i][i] = 0;
    }
    for (int i = 1; i <= m; i++) {
        scanf("%s%s%lld", cx, cy, &x);
        f[cx[0]][cy[0]] = min(f[cx[0]][cy[0]], x);
    }
    for (int k = 'a'; k <= 'z'; k++) {
        for (int i = 'a'; i <= 'z'; i++) {
            for (int j = 'a'; j <= 'z'; j++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
    memset(g, 0x3f, sizeof(g));
    for (int i = 'a'; i <= 'z'; i++) {
        for (int j = 'a'; j <= 'z'; j++) {
            for (int k = 'a'; k <= 'z'; k++) {
                g[i][j] = min(g[i][j], f[i][k] + f[j][k]);
            }
        }
    }
    int pos = K, las = n;
    for (int i = 1; i <= n; i++) {
        // cout << "i = " << i << endl;
        if (i + K - 1 <= n) {
            if (!vis[i + K - 1]) {
                c[(i + K - 1) & 1][s[i + K - 1]]++, vis[i + K - 1] = true;
                // cout << "+nxt = " << i + K - 1 << endl;
            }
        }
        if (i < pos) {
            if (!vis[pos]) {
                // cout << "+pos = " << pos << endl;
                c[pos & 1][s[pos]]++, vis[pos] = true;
            }
            pos--;
        } else {
            if (vis[i]) {
                c[i & 1][s[i]]--, vis[i] = false;
                // cout << "-self" << endl;
            }
        }
        while (2 * n - K + 1 - i < las) {
            if (vis[las]) {
                c[las & 1][s[las]]--, vis[las] = false;
            }
            las--;
        }
        int id = (i + K - 1) & 1, res = 0;
        for (int j = 'a'; j <= 'z'; j++) {
            res += c[id][j] * min(T, g[s[i]][j]);
        }
        ans += res;
        // cout << "res = " << res << endl;
    }
    printf("%lld\n", ans);
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：16 ms
内存：960 KiB

输入文件（01.in） 

1869 93998 900 368136851
aoyqashhquraeakciklzxikmassmpwlgaoaqzegwoakganffabaesiiqsiexupmeamzreaadtsm
<1307330 bytes omitted>

答案文件（01.out） 

235658071517

用户输出 

235658071517

系统信息 

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

输入文件（02.in） 

1974 98954 968 854839460
vimioksqdackekoiogisymgukwkmbmzvwmzgqoscqnpmzqsgaeyynxojyakemeakcqwczceneyq
<1376323 bytes omitted>

答案文件（02.out） 

225166532417

用户输出 

225166532417

系统信息 

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

输入文件（03.in） 

1890 90296 900 379213088
iqbiiepvmvelcknexeylwonjpynywravcqacaetkyzkccteawoaueqwgeucolcuoetsgumibmmg
<1256103 bytes omitted>

答案文件（03.out） 

257365236272

用户输出 

257365236272

系统信息 

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

输入文件（04.in） 

1867 98533 913 379089763
qmbhosqejvcnwloltoamiuzmzgizcyujgdqkuailfmknnsyumwpygneybdgonyxqsynesgeoeso
<1370183 bytes omitted>

答案文件（04.out） 

167645870596

用户输出 

167645870596

系统信息 

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

输入文件（05.in） 

1971 95944 947 812056313
kwoeuyjoceseuqbgfeascwmpamynqmgafnowkhuqsmojotkswsshacsieaukaqwedfcgsmidmme
<1334566 bytes omitted>

答案文件（05.out） 

199103971214

用户输出 

199103971214

系统信息 

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

输入文件（06.in） 

1809 94391 901 913811389
gmuozeaxqigaxzoiekiopsjkmwklskarxcadkoxqiculgifwaikmqdmaswuwkhzawpicepmupiq
<1312733 bytes omitted>

答案文件（06.out） 

245828151524

用户输出 

245828151524

系统信息 

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

输入文件（07.in） 

96275 94290 46452 21716561
aotvefmmaszastfwmktmeokiqjfsbiargmhtybkwwniqywqayywmeocemeacwrsakqqqmqnny
<1405742 bytes omitted>

答案文件（07.out） 

669440109451668

用户输出 

669440109451668

系统信息 

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

输入文件（08.in） 

99039 90167 45356 432557883
sxaufacaqcyywskiauamomyknwickqmcgaretyuoabetekacggbaaxeumuimoxaetcacuoqk
<1351226 bytes omitted>

答案文件（08.out） 

645817074484703

用户输出 

645817074484703

系统信息 

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

输入文件（09.in） 

91199 97743 45072 913975116
wvpfsqnaogagamamswyhmuweafagvaxqiksgmkpwaicuzaujunenzdnhoicwygmodaatygnm
<1448730 bytes omitted>

答案文件（09.out） 

506803744711132

用户输出 

506803744711132

系统信息 

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

输入文件（10.in） 

99108 95604 47408 636114061
iwiaiggkuwnakugunakmccuvsgyfwiwccyeukkmedmqabdxlmmktrdixwzqivmwmeusjkois
<1426935 bytes omitted>

答案文件（10.out） 

582014501328894

用户输出 

582014501328894

系统信息 

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

输入文件（11.in） 

91278 95295 45439 257640309
aakpiahfmscdwpemgrgaudoaoawinqadeagvwnsrkaywdmkvsajayskhmaffztywiyqiokol
<1414883 bytes omitted>

答案文件（11.out） 

442083747025033

用户输出 

442083747025033

系统信息 

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

输入文件（12.in） 

96636 94520 46300 357047255
vrntaamcuauwuqyykaybtkrlwnjwpfgoaoumszduzoowiwvppmfefmuoxauastcxicqfaeha
<1409214 bytes omitted>

答案文件（12.out） 

558344083111282

用户输出 

558344083111282

系统信息 

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

输入文件（13.in） 

91079 90668 45420 576653687
wezoeujyagmumepihcofomaiawgvilngqmaikcaasycqrynzaoyqjudygjxuhwmngunawlyw
<1350290 bytes omitted>

答案文件（13.out） 

538789922907646

用户输出 

538789922907646

系统信息 

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

输入文件（14.in） 

93891 97160 46627 796794884
guugmceolylqvyooaaymecapunxqqtmkcxevmoofwuyfemiaawsmmgqkmkidapcneiakrthn
<1443449 bytes omitted>

答案文件（14.out） 

469006808697808

用户输出 

469006808697808

系统信息 

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

输入文件（15.in） 

95017 92640 46777 259673790
fjsgoxgoywwuanadqopbkapxnsgertagmeogsgawwqqscsovzjqtakoiuucrlansiyfpirwj
<1381464 bytes omitted>

答案文件（15.out） 

437550575218548

用户输出 

437550575218548

系统信息 

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

输入文件（16.in） 

92540 96663 45586 392541641
aaaaedaivgvgnaikgeipgoxvcvmxtyamuawaicwnmomskcguiadgbarlgkazkfsaraoytkmy
<1434823 bytes omitted>

答案文件（16.out） 

503992149083265

用户输出 

503992149083265

系统信息 

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

输入文件（17.in） 

97373 93795 47953 463547353
cyllysjenhgpygsakncoaisdyaaqjqwvuwrvlglyiqnncleogoqicweiaexibraomnbeaqkc
<1400168 bytes omitted>

答案文件（17.out） 

987280699937697

用户输出 

987280699937697

系统信息 

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

输入文件（18.in） 

96183 91174 47474 413948014
xacdikjckmifayuikmneohqmqybqxaassekygwqeqqktjyiihmxaocqacgqswqfoqnaayoim
<1362412 bytes omitted>

答案文件（18.out） 

692996779148754

用户输出 

692996779148754

系统信息 

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

输入文件（19.in） 

97842 94434 48193 889116164
uwhyaauecxflqoyhwnfqicpqjktktagguhkciyokwovdmmagdmaiinyrikoikycvuaqiyiay
<1409658 bytes omitted>

答案文件（19.out） 

752717899660312

用户输出 

752717899660312

系统信息 

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

输入文件（20.in） 

97147 90973 45744 962244475
wdmazcyiqupksfkupypxyaknazgahuoekgkykciaqibownkghaiyndjgywgcatwwcpwysorc
<1360532 bytes omitted>

答案文件（20.out） 

929003800841297

用户输出 

929003800841297

系统信息 

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

输入文件（21.in） 

989735 98203 479644 37494034
qdcazspekqznsyrajdcaeecpiqemdqoagaagehegeaatuszaqacuqavocagaacjikgfmaak
<2353574 bytes omitted>

答案文件（21.out） 

45679331478884622

用户输出 

45679331478884622

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.