QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#260834#6635. Strange Keyboarducup-team1198#AC ✓246ms113812kbC++202.6kb2023-11-22 15:51:122023-11-22 15:51:13

Judging History

你现在查看的是最新测评结果

  • [2023-11-22 15:51:13]
  • 评测
  • 测评结果:AC
  • 用时:246ms
  • 内存:113812kb
  • [2023-11-22 15:51:12]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

const int MAXN = 1000100;
const long long INF = 1e18;
int go[MAXN][26];
long long cost[MAXN];
int nodes_cnt = 0;

int node() {
    fill(go[nodes_cnt], go[nodes_cnt] + 26, -1);
    cost[nodes_cnt] = INF;
    ++nodes_cnt;
    return nodes_cnt - 1;
}

void solve() {
    nodes_cnt = 0;
    node();

    int n, k;
    cin >> n >> k;
    vector<long long> dp(k, INF);
    vector<long long> min_len(k, INF);
    vector<string> lines(n);
    for (int i = 0; i < n; ++i) {
        cin >> lines[i];
        long long sz = lines[i].size();
        min_len[sz % k] = min(min_len[sz % k], sz);
        int cur = 0;
        for (char c : lines[i]) {
            if (go[cur][c - 'a'] == -1) {
                go[cur][c - 'a'] = node();
            }
            cur = go[cur][c - 'a'];
        }
    }

    // dp r

    vector<int> interesting;
    for (int i = 0; i < k; ++i) {
        if (min_len[i] != INF)
            interesting.emplace_back(i);
    }
    dp[0] = 0;
    set<pair<long long, int>> Q;
    Q.emplace(0ll, 0);
    while (!Q.empty()) {
        int mn = Q.begin()->second;
        Q.erase(Q.begin());
        for (int i : interesting) {
            long long extra_r = min_len[i] + mn;
            long long opt = dp[mn] + extra_r / k + 1;
            int nxt = mn + i;
            if (nxt >= k)
                nxt -= k;
            if (dp[nxt] > opt) {
                Q.erase(make_pair(dp[nxt], nxt));
                dp[nxt] = opt;
                Q.emplace(dp[nxt], nxt);
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        int cur = 0;
        for (int j = 0; j < lines[i].size(); ++j) {
            cur = go[cur][lines[i][j] - 'a'];
            int rest = lines[i].size() - j - 1;
            int tmp = (k - rest % k) % k;
            cost[cur] = min(cost[cur], (rest + tmp) / k + dp[tmp] + 1);
        }
    }

    string t;
    cin >> t;
    vector<long long> final_dp(t.size() + 1, INF);
    final_dp[0] = 0;
    for (int i = 0; i < t.size(); ++i) {
        int cur = 0;
        for (int j = 0; i + j < t.size(); ++j) {
            cur = go[cur][t[i + j] - 'a'];
            if (cur == -1)
                break;
            final_dp[i + j + 1] = min(final_dp[i + j + 1], final_dp[i] + cost[cur]);
        }
    }
    if (final_dp.back() == INF)
        cout << -1 << '\n';
    else
        cout << final_dp.back() << '\n';

}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5616kb

input:

2
2 3
defgh
abc
abcde
1 1
a
b

output:

3
-1

result:

ok 2 number(s): "3 -1"

Test #2:

score: 0
Accepted
time: 32ms
memory: 6836kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 73ms
memory: 6088kb

input:

10
446 4905
afigcjhcgagabbiccehjcjajigghgbjjadccicghggijjdfeciaccgheedjdhgfjdfdbgidbbdjaiehhceeehchhabhaideggjbjajgfgicfdggahhbjgdebccbgbiedhehaebdccdfdffaacjcfbgjeegbahhbgcdjigijajheidchbddicehhhjbeiaajgedhdcjiefdgdbjjfaegheeidieheecaicciaajbabiidcecefgiicccdidegeica
afigcjhcgagabbiccehjcjajigghgbj...

output:

3
2
2
11
6
5
1
1
1
1

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 246ms
memory: 5832kb

input:

100
140 4879
baabaababbababbaabababaaababbbabbbbbbabbababbbabbbbabbbbbbaabbbbbbbbabaabbbaabaabbbaabbabaabaabbbabbbababbbaabbabaaaaabbaaabbbabb
baa
baabaababbababbaabababaaababbbabbbbbbabbab
baabaababbababbaabababaaabab
baabaababbababbaabababaaababbbabbb
baabaababbababbaabababaaababbbabbbbbbabbababbb...

output:

1
1
1
1
3
1
1
1
1
1
1
3
2
1
1
1
2
1
1
2
1
1
1
1
1
1
1
1
1
4
3
2
1
2
1
1
1
1
1
2
1
1
1
3
1
1
1
2
1
1
1
2
3
1
1
1
2
1
1
1
1
1
1
1
1
3
2
3
1
3
1
1
2
1
2
3
2
1
1
1
3
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
2
1
4
1

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 46ms
memory: 38708kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205

result:

ok 1 number(s): "205"

Test #6:

score: 0
Accepted
time: 38ms
memory: 36544kb

input:

10
7 4923
baaabbabbbabbbbbabaabaabababbabbaaaabbaaabbbbabbaaababaaaaabaaabbabbbabbaaaabbaabbbaabbaaababaaababbabaababbaababbabaaabaabbaaabaaaababbabbabaabaabaabaabbbbaabaabbbaababbabbabaaaabbbaabbbaaaabaaaaababbaabaaaaababbbbaaaabbbaababbaabbabaabaaaaababaababaabaaaaabababababbabbbabababaaabaababbaa...

output:

4287
228
3671
549
129
372
475
534
336
288

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 72ms
memory: 12880kb

input:

100
7 4807
abbababaababbaabbabbaabaababbaaababaabaaabbaaaabababbbaabbaaabababbaabaabbaaaaabbbbaabbbaaabbbbabaabbbaaaaabbbaabbaaaabbaaababbaaabbbbabaabbababababbbabaaabaaaabbbbabbabbbbbaabaaabaababbabaaabbaabbabbabaaababbbabbabbbaababaabaaaabaaabbbbabbaabaababbbabbbbaaaabbabbbaabbaabbbbb
aaaaababaaab...

output:

45
32
11
4
2475
132
50
330
20
6
99
25
126
6
4
14
74
108
208
11
5
67
166
2822
178
1307
548
92
386
493
279
2415
255
262
567
215
46
113
31
651
17
4
8
21
12
100
69
152
15
55
521
146
11
13
181
-1
442
1839
2
5
31
26
122
696
280
77
1
839
11
273
7
178
421
228
6
6
82
116
1
-1
293
519
5
160
15
126
13
31
619
4...

result:

ok 100 numbers

Test #8:

score: 0
Accepted
time: 18ms
memory: 113812kb

input:

1
1 5000
abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

5023990000

result:

ok 1 number(s): "5023990000"

Test #9:

score: 0
Accepted
time: 33ms
memory: 37832kb

input:

1
100000 4817
acdcaaccca
cdbbbbabba
bcbccbcdbd
cdabaddaad
ddbdbabcac
dadadbbcba
aabcbbcabc
cdcadbbbda
dabacdbabd
dcbadbdabd
cdcbacbada
cadbbadbac
dbadbccdcd
babaddcdca
aaaddacccc
dabdcdadbb
abbbadbdaa
bcdbbacdaa
bcbcbddadb
bddaccbaba
baddadaaac
adbadbdaaa
cacbbbcdbc
abccdcacdb
abaacddbbc
acbbbcbcdc
...

output:

618356

result:

ok 1 number(s): "618356"

Test #10:

score: 0
Accepted
time: 26ms
memory: 35864kb

input:

10
3901 4952
srsofqyvrt
tazndzviuq
jcomfoxkiw
huzfqiecss
hhdtqpaohy
qcrokphbtf
xzkxssibix
hokmdpzydu
jreaeulsjt
vmxdsazajq
jawyofqbck
cwmzupygdm
rgsahqyxqt
kckgorfgvi
kcawvezmyb
mpcyhdifgn
xiwtmwttmp
mzknfqoifl
vbpvvdnqpy
anpdgjnbew
scekjovqpr
lzhfocjvld
oswjfhjdby
pmdbjddkpv
yjbnjcdtmc
gmpjgtpksa
r...

output:

904
208656
4560
30873
28272
5377
1326
93956
93720
282610

result:

ok 10 numbers