XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#23963 #1134. ddd的回文串 Accepted 100 1221 ms 404452 K C++ 17 / 1.5 K q3540555 2020-03-02 21:43:55
显示原始代码 
#include <bits/stdc++.h>
using namespace std;
long long dis[35][35];
long long value[35][35];
long long cnt[2][35][1000005];
int n, m, k;
char s[1000005];
long long ans;
void work(int i) {
    for (int j = 1; j <= 26; ++j) {
        int l = max(k - i + 1, i), r = min(2 * n - k - i + 1, i + k - 1);
        int pos = ((k + 1) % 2 + i % 2) % 2;
        if (l > r)
            continue;
        ans += value[s[i] - 'a' + 1][j] * (cnt[pos][j][r] - cnt[pos][j][l - 1]);
    }
}
int main() {
    // freopen("01.in","r",stdin);
    ios::sync_with_stdio(false);
    long long t;
    cin >> n >> m >> k >> t;
    for (int i = 1; i <= 26; ++i)
        for (int j = 1; j <= 26; ++j) dis[i][j] = value[i][j] = 230584300921369392;
    for (int i = 1; i <= n; ++i) cin >> s[i];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= 26; ++j) cnt[0][j][i] = cnt[0][j][i - 1], cnt[1][j][i] = cnt[1][j][i - 1];
        ++cnt[i % 2][s[i] - 'a' + 1][i];
    }
    for (int i = 1; i <= m; ++i) {
        char x, y;
        long long c;
        cin >> x >> y >> c;
        dis[x - 'a' + 1][y - 'a' + 1] = min(dis[x - 'a' + 1][y - 'a' + 1], c);
    }
    for (int i = 1; i <= 26; ++i) dis[i][i] = 0;
    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][k] + dis[k][j], dis[i][j]);
    for (int i = 1; i <= 26; ++i)
        for (int j = 1; j <= 26; ++j)
            for (int k = 1; k <= 26; ++k) value[i][j] = min(t, min(value[i][j], dis[i][k] + dis[j][k]));
    for (int i = 1; i <= 26; ++i)
        for (int j = 1; j <= 26; ++j) value[i][j] = min(value[i][j], value[j][i]);
    for (int i = 1; i <= n; ++i) {
        int l = max(k - i + 1, i), r = min(2 * n - k - i + 1, i + k - 1);
        work(i);
    }
    //	for(int i=n-k+2;i<=n-k/2;++i)
    //	ans+=value[s[i]-'a'+1][s[2*n-k-i+1]-'a'+1];
    printf("%lld\n", ans);
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：16 ms
内存：1584 KiB

输入文件（01.in） 

1869 93998 900 368136851
aoyqashhquraeakciklzxikmassmpwlgaoaqzegwoakganffabaesiiqsiexupmeamzreaadtsm
<1307330 bytes omitted>

答案文件（01.out） 

235658071517

用户输出 

235658071517

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：19 ms
内存：1588 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
内存：1544 KiB

输入文件（03.in） 

1890 90296 900 379213088
iqbiiepvmvelcknexeylwonjpynywravcqacaetkyzkccteawoaueqwgeucolcuoetsgumibmmg
<1256103 bytes omitted>

答案文件（03.out） 

257365236272

用户输出 

257365236272

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：20 ms
内存：1556 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
内存：1600 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
内存：1504 KiB

输入文件（06.in） 

1809 94391 901 913811389
gmuozeaxqigaxzoiekiopsjkmwklskarxcadkoxqiculgifwaikmqdmaswuwkhzawpicepmupiq
<1312733 bytes omitted>

答案文件（06.out） 

245828151524

用户输出 

245828151524

系统信息 

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

输入文件（07.in） 

96275 94290 46452 21716561
aotvefmmaszastfwmktmeokiqjfsbiargmhtybkwwniqywqayywmeocemeacwrsakqqqmqnny
<1405742 bytes omitted>

答案文件（07.out） 

669440109451668

用户输出 

669440109451668

系统信息 

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

输入文件（08.in） 

99039 90167 45356 432557883
sxaufacaqcyywskiauamomyknwickqmcgaretyuoabetekacggbaaxeumuimoxaetcacuoqk
<1351226 bytes omitted>

答案文件（08.out） 

645817074484703

用户输出 

645817074484703

系统信息 

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

输入文件（09.in） 

91199 97743 45072 913975116
wvpfsqnaogagamamswyhmuweafagvaxqiksgmkpwaicuzaujunenzdnhoicwygmodaatygnm
<1448730 bytes omitted>

答案文件（09.out） 

506803744711132

用户输出 

506803744711132

系统信息 

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

输入文件（10.in） 

99108 95604 47408 636114061
iwiaiggkuwnakugunakmccuvsgyfwiwccyeukkmedmqabdxlmmktrdixwzqivmwmeusjkois
<1426935 bytes omitted>

答案文件（10.out） 

582014501328894

用户输出 

582014501328894

系统信息 

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

输入文件（11.in） 

91278 95295 45439 257640309
aakpiahfmscdwpemgrgaudoaoawinqadeagvwnsrkaywdmkvsajayskhmaffztywiyqiokol
<1414883 bytes omitted>

答案文件（11.out） 

442083747025033

用户输出 

442083747025033

系统信息 

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

输入文件（12.in） 

96636 94520 46300 357047255
vrntaamcuauwuqyykaybtkrlwnjwpfgoaoumszduzoowiwvppmfefmuoxauastcxicqfaeha
<1409214 bytes omitted>

答案文件（12.out） 

558344083111282

用户输出 

558344083111282

系统信息 

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

输入文件（13.in） 

91079 90668 45420 576653687
wezoeujyagmumepihcofomaiawgvilngqmaikcaasycqrynzaoyqjudygjxuhwmngunawlyw
<1350290 bytes omitted>

答案文件（13.out） 

538789922907646

用户输出 

538789922907646

系统信息 

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

输入文件（14.in） 

93891 97160 46627 796794884
guugmceolylqvyooaaymecapunxqqtmkcxevmoofwuyfemiaawsmmgqkmkidapcneiakrthn
<1443449 bytes omitted>

答案文件（14.out） 

469006808697808

用户输出 

469006808697808

系统信息 

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

输入文件（15.in） 

95017 92640 46777 259673790
fjsgoxgoywwuanadqopbkapxnsgertagmeogsgawwqqscsovzjqtakoiuucrlansiyfpirwj
<1381464 bytes omitted>

答案文件（15.out） 

437550575218548

用户输出 

437550575218548

系统信息 

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

输入文件（16.in） 

92540 96663 45586 392541641
aaaaedaivgvgnaikgeipgoxvcvmxtyamuawaicwnmomskcguiadgbarlgkazkfsaraoytkmy
<1434823 bytes omitted>

答案文件（16.out） 

503992149083265

用户输出 

503992149083265

系统信息 

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

输入文件（17.in） 

97373 93795 47953 463547353
cyllysjenhgpygsakncoaisdyaaqjqwvuwrvlglyiqnncleogoqicweiaexibraomnbeaqkc
<1400168 bytes omitted>

答案文件（17.out） 

987280699937697

用户输出 

987280699937697

系统信息 

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

输入文件（18.in） 

96183 91174 47474 413948014
xacdikjckmifayuikmneohqmqybqxaassekygwqeqqktjyiihmxaocqacgqswqfoqnaayoim
<1362412 bytes omitted>

答案文件（18.out） 

692996779148754

用户输出 

692996779148754

系统信息 

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

输入文件（19.in） 

97842 94434 48193 889116164
uwhyaauecxflqoyhwnfqicpqjktktagguhkciyokwovdmmagdmaiinyrikoikycvuaqiyiay
<1409658 bytes omitted>

答案文件（19.out） 

752717899660312

用户输出 

752717899660312

系统信息 

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

输入文件（20.in） 

97147 90973 45744 962244475
wdmazcyiqupksfkupypxyaknazgahuoekgkykciaqibownkghaiyndjgywgcatwwcpwysorc
<1360532 bytes omitted>

答案文件（20.out） 

929003800841297

用户输出 

929003800841297

系统信息 

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

输入文件（21.in） 

989735 98203 479644 37494034
qdcazspekqznsyrajdcaeecpiqemdqoagaagehegeaatuszaqacuqavocagaacjikgfmaak
<2353574 bytes omitted>

答案文件（21.out） 

45679331478884622

用户输出 

45679331478884622

系统信息 

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