XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#23253 #1134. ddd的回文串 Accepted 100 644 ms 10644 K C++ 11 / 1.9 K docriz🦆 2020-02-16 14:14:15
显示原始代码 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;

int n, m, k, T;
char s[MAXN];
int dis[50][50], minCost[50][50];
int sum[30][MAXN];

int getL(int x) {
    int res = -1;
    res = max(res, x - k + 1);
    if (x <= k)
        res = max(res, 1 + k - x);
    return res;
}

int getR(int x) {
    int res = n + 1;
    res = min(res, x + k - 1);
    if (x >= n - k + 1)
        res = min(res, 2 * n - k + 1 - x);
    return res;
}

int getNewPos(int x) {
    if (x % 2)
        return (x + 1) / 2;
    else
        return (n + 1) / 2 + x / 2;
}

int main() {
    scanf("%d %d %d %d", &n, &m, &k, &T);
    scanf("%s", s + 1);
    for (int i = 1; i <= 26; i++) {
        for (int j = 1; j <= 26; j++) {
            minCost[i][j] = INT_MAX / 2;
            if (i == j)
                dis[i][j] = 0;
            else
                dis[i][j] = T;
        }
    }
    for (int i = 1; i <= m; i++) {
        char ch1[3], ch2[3];
        int c;
        scanf("%s %s %d", ch1, ch2, &c);
        int v1 = ch1[0] - 'a' + 1;
        int v2 = ch2[0] - 'a' + 1;
        dis[v1][v2] = min(dis[v1][v2], c);
    }
    for (int k = 1; k <= 26; k++) {
        for (int i = 1; i <= 26; i++) {
            for (int j = 1; j <= 26; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    for (int i = 1; i <= 26; i++) {
        for (int j = 1; j <= 26; j++) {
            for (int k = 1; k <= 26; k++) {
                minCost[i][j] = min(minCost[i][j], dis[i][k] + dis[j][k]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        sum[s[i] - 'a' + 1][getNewPos(i)]++;
    }
    for (int j = 1; j <= 26; j++) {
        for (int i = 1; i <= n; i++) {
            sum[j][i] += sum[j][i - 1];
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int l = getL(i), r = getR(i);
        l = getNewPos(l), r = getNewPos(r);
        for (int j = 1; j <= 26; j++) {
            int cnt = sum[j][r] - sum[j][l - 1];
            ans += 1LL * cnt * minCost[s[i] - 'a' + 1][j];
        }
    }
    printf("%lld\n", ans / 2);
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：17 ms
内存：644 KiB

输入文件（01.in） 

1869 93998 900 368136851
aoyqashhquraeakciklzxikmassmpwlgaoaqzegwoakganffabaesiiqsiexupmeamzreaadtsm
<1307330 bytes omitted>

答案文件（01.out） 

235658071517

用户输出 

235658071517

系统信息 

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

输入文件（02.in） 

1974 98954 968 854839460
vimioksqdackekoiogisymgukwkmbmzvwmzgqoscqnpmzqsgaeyynxojyakemeakcqwczceneyq
<1376323 bytes omitted>

答案文件（02.out） 

225166532417

用户输出 

225166532417

系统信息 

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

输入文件（03.in） 

1890 90296 900 379213088
iqbiiepvmvelcknexeylwonjpynywravcqacaetkyzkccteawoaueqwgeucolcuoetsgumibmmg
<1256103 bytes omitted>

答案文件（03.out） 

257365236272

用户输出 

257365236272

系统信息 

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

输入文件（04.in） 

1867 98533 913 379089763
qmbhosqejvcnwloltoamiuzmzgizcyujgdqkuailfmknnsyumwpygneybdgonyxqsynesgeoeso
<1370183 bytes omitted>

答案文件（04.out） 

167645870596

用户输出 

167645870596

系统信息 

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

输入文件（05.in） 

1971 95944 947 812056313
kwoeuyjoceseuqbgfeascwmpamynqmgafnowkhuqsmojotkswsshacsieaukaqwedfcgsmidmme
<1334566 bytes omitted>

答案文件（05.out） 

199103971214

用户输出 

199103971214

系统信息 

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

输入文件（06.in） 

1809 94391 901 913811389
gmuozeaxqigaxzoiekiopsjkmwklskarxcadkoxqiculgifwaikmqdmaswuwkhzawpicepmupiq
<1312733 bytes omitted>

答案文件（06.out） 

245828151524

用户输出 

245828151524

系统信息 

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

输入文件（07.in） 

96275 94290 46452 21716561
aotvefmmaszastfwmktmeokiqjfsbiargmhtybkwwniqywqayywmeocemeacwrsakqqqmqnny
<1405742 bytes omitted>

答案文件（07.out） 

669440109451668

用户输出 

669440109451668

系统信息 

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

输入文件（08.in） 

99039 90167 45356 432557883
sxaufacaqcyywskiauamomyknwickqmcgaretyuoabetekacggbaaxeumuimoxaetcacuoqk
<1351226 bytes omitted>

答案文件（08.out） 

645817074484703

用户输出 

645817074484703

系统信息 

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

输入文件（09.in） 

91199 97743 45072 913975116
wvpfsqnaogagamamswyhmuweafagvaxqiksgmkpwaicuzaujunenzdnhoicwygmodaatygnm
<1448730 bytes omitted>

答案文件（09.out） 

506803744711132

用户输出 

506803744711132

系统信息 

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

输入文件（10.in） 

99108 95604 47408 636114061
iwiaiggkuwnakugunakmccuvsgyfwiwccyeukkmedmqabdxlmmktrdixwzqivmwmeusjkois
<1426935 bytes omitted>

答案文件（10.out） 

582014501328894

用户输出 

582014501328894

系统信息 

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

输入文件（11.in） 

91278 95295 45439 257640309
aakpiahfmscdwpemgrgaudoaoawinqadeagvwnsrkaywdmkvsajayskhmaffztywiyqiokol
<1414883 bytes omitted>

答案文件（11.out） 

442083747025033

用户输出 

442083747025033

系统信息 

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

输入文件（12.in） 

96636 94520 46300 357047255
vrntaamcuauwuqyykaybtkrlwnjwpfgoaoumszduzoowiwvppmfefmuoxauastcxicqfaeha
<1409214 bytes omitted>

答案文件（12.out） 

558344083111282

用户输出 

558344083111282

系统信息 

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

输入文件（13.in） 

91079 90668 45420 576653687
wezoeujyagmumepihcofomaiawgvilngqmaikcaasycqrynzaoyqjudygjxuhwmngunawlyw
<1350290 bytes omitted>

答案文件（13.out） 

538789922907646

用户输出 

538789922907646

系统信息 

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

输入文件（14.in） 

93891 97160 46627 796794884
guugmceolylqvyooaaymecapunxqqtmkcxevmoofwuyfemiaawsmmgqkmkidapcneiakrthn
<1443449 bytes omitted>

答案文件（14.out） 

469006808697808

用户输出 

469006808697808

系统信息 

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

输入文件（15.in） 

95017 92640 46777 259673790
fjsgoxgoywwuanadqopbkapxnsgertagmeogsgawwqqscsovzjqtakoiuucrlansiyfpirwj
<1381464 bytes omitted>

答案文件（15.out） 

437550575218548

用户输出 

437550575218548

系统信息 

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

输入文件（16.in） 

92540 96663 45586 392541641
aaaaedaivgvgnaikgeipgoxvcvmxtyamuawaicwnmomskcguiadgbarlgkazkfsaraoytkmy
<1434823 bytes omitted>

答案文件（16.out） 

503992149083265

用户输出 

503992149083265

系统信息 

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

输入文件（17.in） 

97373 93795 47953 463547353
cyllysjenhgpygsakncoaisdyaaqjqwvuwrvlglyiqnncleogoqicweiaexibraomnbeaqkc
<1400168 bytes omitted>

答案文件（17.out） 

987280699937697

用户输出 

987280699937697

系统信息 

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

输入文件（18.in） 

96183 91174 47474 413948014
xacdikjckmifayuikmneohqmqybqxaassekygwqeqqktjyiihmxaocqacgqswqfoqnaayoim
<1362412 bytes omitted>

答案文件（18.out） 

692996779148754

用户输出 

692996779148754

系统信息 

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

输入文件（19.in） 

97842 94434 48193 889116164
uwhyaauecxflqoyhwnfqicpqjktktagguhkciyokwovdmmagdmaiinyrikoikycvuaqiyiay
<1409658 bytes omitted>

答案文件（19.out） 

752717899660312

用户输出 

752717899660312

系统信息 

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

输入文件（20.in） 

97147 90973 45744 962244475
wdmazcyiqupksfkupypxyaknazgahuoekgkykciaqibownkghaiyndjgywgcatwwcpwysorc
<1360532 bytes omitted>

答案文件（20.out） 

929003800841297

用户输出 

929003800841297

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.