XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#23722 #1134. ddd的回文串 Accepted 100 1404 ms 202892 K C++ / 1.5 K 电类935-郑新宇 2020-02-16 20:56:36
显示原始代码 
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll mp[30][30], dis[30][30], n, m, k, T, z, sum[30][1000010];
char u, y, s[1000010];
ll getl(int x) {
    ll res = -1;
    res = max(res, x - k + 1);
    if (x <= k)
        res = max(res, 1 + k - x);  // x的左边不能提供k个长度
    // 1+k-x就是在k个长度下，x最左是k-x+1 对称性
    return res;
}
ll getr(int x) {
    ll res = n + 1;
    res = min(res, x + k - 1);
    if (x >= n - k + 1)
        res = min(res, n * 2 - k + 1 - x);
    return res;
}
int getNew(int x) {
    //奇数放在前，偶数放在后
    if (x & 1)
        return (x + 1) / 2;
    else
        return (n + 1) / 2 + x / 2;
}
int main() {
    //	freopen("in.txt","r",stdin);
    cin >> n >> m >> k >> T;
    cin >> s;
    for (int i = 1; i <= 26; i++)
        for (int j = 1; j <= 26; j++) mp[i][j] = T, dis[i][j] = 0x7f7f7f;
    for (int i = 1; i <= 26; i++) mp[i][i] = 0, dis[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        cin >> u >> y >> z;
        mp[u - 'a' + 1][y - 'a' + 1] = min(mp[u - 'a' + 1][y - 'a' + 1], z);
    }
    for (int k = 1; k <= 26; k++)
        for (int j = 1; j <= 26; j++)
            for (int i = 1; i <= 26; i++) mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
    for (int i = 1; i <= 26; i++)
        for (int j = 1; j <= 26; j++)
            for (int k = 1; k <= 26; k++) dis[i][j] = min(dis[i][j], mp[i][k] + mp[j][k]);

    for (int i = 1; i <= n; i++) sum[s[i - 1] - 'a' + 1][getNew(i)]++;
    //在i出现了多少 s[i]
    for (int i = 1; i <= 26; i++)
        for (int j = 1; j <= n; j++) sum[i][j] += sum[i][j - 1];
    //求前缀和
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int l = getNew(getl(i)), r = getNew(getr(i));
        for (int j = 1; j <= 26; j++) {
            ll cnt = sum[j][r] - sum[j][l - 1];
            ans += cnt * dis[s[i - 1] - 'a' + 1][j];
        }
    }
    cout << ans / 2;
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：40 ms
内存：1000 KiB

输入文件（01.in） 

1869 93998 900 368136851
aoyqashhquraeakciklzxikmassmpwlgaoaqzegwoakganffabaesiiqsiexupmeamzreaadtsm
<1307330 bytes omitted>

答案文件（01.out） 

235658071517

用户输出 

235658071517

系统信息 

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

输入文件（02.in） 

1974 98954 968 854839460
vimioksqdackekoiogisymgukwkmbmzvwmzgqoscqnpmzqsgaeyynxojyakemeakcqwczceneyq
<1376323 bytes omitted>

答案文件（02.out） 

225166532417

用户输出 

225166532417

系统信息 

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

输入文件（03.in） 

1890 90296 900 379213088
iqbiiepvmvelcknexeylwonjpynywravcqacaetkyzkccteawoaueqwgeucolcuoetsgumibmmg
<1256103 bytes omitted>

答案文件（03.out） 

257365236272

用户输出 

257365236272

系统信息 

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

输入文件（04.in） 

1867 98533 913 379089763
qmbhosqejvcnwloltoamiuzmzgizcyujgdqkuailfmknnsyumwpygneybdgonyxqsynesgeoeso
<1370183 bytes omitted>

答案文件（04.out） 

167645870596

用户输出 

167645870596

系统信息 

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

输入文件（05.in） 

1971 95944 947 812056313
kwoeuyjoceseuqbgfeascwmpamynqmgafnowkhuqsmojotkswsshacsieaukaqwedfcgsmidmme
<1334566 bytes omitted>

答案文件（05.out） 

199103971214

用户输出 

199103971214

系统信息 

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

输入文件（06.in） 

1809 94391 901 913811389
gmuozeaxqigaxzoiekiopsjkmwklskarxcadkoxqiculgifwaikmqdmaswuwkhzawpicepmupiq
<1312733 bytes omitted>

答案文件（06.out） 

245828151524

用户输出 

245828151524

系统信息 

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

输入文件（07.in） 

96275 94290 46452 21716561
aotvefmmaszastfwmktmeokiqjfsbiargmhtybkwwniqywqayywmeocemeacwrsakqqqmqnny
<1405742 bytes omitted>

答案文件（07.out） 

669440109451668

用户输出 

669440109451668

系统信息 

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

输入文件（08.in） 

99039 90167 45356 432557883
sxaufacaqcyywskiauamomyknwickqmcgaretyuoabetekacggbaaxeumuimoxaetcacuoqk
<1351226 bytes omitted>

答案文件（08.out） 

645817074484703

用户输出 

645817074484703

系统信息 

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

输入文件（09.in） 

91199 97743 45072 913975116
wvpfsqnaogagamamswyhmuweafagvaxqiksgmkpwaicuzaujunenzdnhoicwygmodaatygnm
<1448730 bytes omitted>

答案文件（09.out） 

506803744711132

用户输出 

506803744711132

系统信息 

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

输入文件（10.in） 

99108 95604 47408 636114061
iwiaiggkuwnakugunakmccuvsgyfwiwccyeukkmedmqabdxlmmktrdixwzqivmwmeusjkois
<1426935 bytes omitted>

答案文件（10.out） 

582014501328894

用户输出 

582014501328894

系统信息 

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

输入文件（11.in） 

91278 95295 45439 257640309
aakpiahfmscdwpemgrgaudoaoawinqadeagvwnsrkaywdmkvsajayskhmaffztywiyqiokol
<1414883 bytes omitted>

答案文件（11.out） 

442083747025033

用户输出 

442083747025033

系统信息 

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

输入文件（12.in） 

96636 94520 46300 357047255
vrntaamcuauwuqyykaybtkrlwnjwpfgoaoumszduzoowiwvppmfefmuoxauastcxicqfaeha
<1409214 bytes omitted>

答案文件（12.out） 

558344083111282

用户输出 

558344083111282

系统信息 

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

输入文件（13.in） 

91079 90668 45420 576653687
wezoeujyagmumepihcofomaiawgvilngqmaikcaasycqrynzaoyqjudygjxuhwmngunawlyw
<1350290 bytes omitted>

答案文件（13.out） 

538789922907646

用户输出 

538789922907646

系统信息 

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

输入文件（14.in） 

93891 97160 46627 796794884
guugmceolylqvyooaaymecapunxqqtmkcxevmoofwuyfemiaawsmmgqkmkidapcneiakrthn
<1443449 bytes omitted>

答案文件（14.out） 

469006808697808

用户输出 

469006808697808

系统信息 

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

输入文件（15.in） 

95017 92640 46777 259673790
fjsgoxgoywwuanadqopbkapxnsgertagmeogsgawwqqscsovzjqtakoiuucrlansiyfpirwj
<1381464 bytes omitted>

答案文件（15.out） 

437550575218548

用户输出 

437550575218548

系统信息 

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

输入文件（16.in） 

92540 96663 45586 392541641
aaaaedaivgvgnaikgeipgoxvcvmxtyamuawaicwnmomskcguiadgbarlgkazkfsaraoytkmy
<1434823 bytes omitted>

答案文件（16.out） 

503992149083265

用户输出 

503992149083265

系统信息 

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

输入文件（17.in） 

97373 93795 47953 463547353
cyllysjenhgpygsakncoaisdyaaqjqwvuwrvlglyiqnncleogoqicweiaexibraomnbeaqkc
<1400168 bytes omitted>

答案文件（17.out） 

987280699937697

用户输出 

987280699937697

系统信息 

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

输入文件（18.in） 

96183 91174 47474 413948014
xacdikjckmifayuikmneohqmqybqxaassekygwqeqqktjyiihmxaocqacgqswqfoqnaayoim
<1362412 bytes omitted>

答案文件（18.out） 

692996779148754

用户输出 

692996779148754

系统信息 

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

输入文件（19.in） 

97842 94434 48193 889116164
uwhyaauecxflqoyhwnfqicpqjktktagguhkciyokwovdmmagdmaiinyrikoikycvuaqiyiay
<1409658 bytes omitted>

答案文件（19.out） 

752717899660312

用户输出 

752717899660312

系统信息 

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

输入文件（20.in） 

97147 90973 45744 962244475
wdmazcyiqupksfkupypxyaknazgahuoekgkykciaqibownkghaiyndjgywgcatwwcpwysorc
<1360532 bytes omitted>

答案文件（20.out） 

929003800841297

用户输出 

929003800841297

系统信息 

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

输入文件（21.in） 

989735 98203 479644 37494034
qdcazspekqznsyrajdcaeecpiqemdqoagaagehegeaatuszaqacuqavocagaacjikgfmaak
<2353574 bytes omitted>

答案文件（21.out） 

45679331478884622

用户输出 

45679331478884622

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.