QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207139#6635. Strange KeyboardFamiglistmoAC ✓270ms141208kbC++142.2kb2023-10-08 10:05:442023-10-08 10:05:45

Judging History

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

  • [2023-10-08 10:05:45]
  • 评测
  • 测评结果:AC
  • 用时:270ms
  • 内存:141208kb
  • [2023-10-08 10:05:44]
  • 提交

answer

#include<bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N = 1e6 + 6;
const int K = 5005;

string s[N], t;
map<int, int> cost;
int ch[N][26], dis[K], mn[N];
int T, n, k, m, siz;
ll f[K];

void insert(string s) {
    int p = 1;
    for(auto c : s) {
        int &to = ch[p][c - 'a'];
        if(!to) to = ++ siz;
        p = to;
    }
}
inline int add(int a, int b) { return a + b >= k ? a + b - k : a + b; }

void solve() {
    for(int i = 1; i <= siz; ++ i)
        memset(ch[i], 0, sizeof(ch[i]));
    siz = 1, cost.clear();

    cin >> n >> k;
    for(int i = 1; i <= n; ++ i) {
        cin >> s[i], insert(s[i]);
        int len = s[i].size(), l = len % k;
        if(l == 0) continue;
        if(cost.find(l) == cost.end())
            cost[l] = len / k + 1;
        else cost[l] = min(cost[l], len / k + 1);
    }
    cin >> t, m = t.size();

    memset(dis, 127, (k + 5) << 2), dis[0] = 0;
    for(auto edge : cost) 
        for(int j = 0, lim = __gcd(k, edge.fi); j < lim; ++ j)
            for(int cur = j, cnt = 0, nex; cnt < 2; cnt += cur == j)
                nex = add(cur, edge.fi), dis[nex] = min(dis[nex], dis[cur] + edge.se + (cur > nex)), cur = nex;

    // for(int i = 0; i < k; ++ i)
        // cout << dis[i] << " "; cout << endl;

    memset(mn, 127, (siz + 5) << 2);
    for(int i = 1; i <= n; ++ i) {
        int p = 1, len = s[i].size();
        for(int j = 0; j < len; ++ j) {
            p = ch[p][s[i][j] - 'a'];
            int t = ((j + 1 - len) % k + k) % k;
			mn[p] = min(mn[p], dis[t] + (t + len - j - 1) / k);
        }
    }
    // for(int i = 1; i <= siz; ++ i)
    //     cout << mn[i] << " " ; cout << endl;

    memset(f, 127, (m + 5) << 3), f[0] = 0;
    for(int i = 0; i <= m; ++ i)
        for(int j = i + 1, p = 1; j <= m; ++ j) {
            p = ch[p][t[j - 1] - 'a'];
            if(!p) break;
            if(!(mn[p] >> 29))
                f[j] = min(f[j], f[i] + mn[p] + 1);
        }
    if(f[m] >> 60) cout << "-1\n";
    else cout << f[m] << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while(T --) solve();    
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 6ms
memory: 36108kb

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: 34ms
memory: 38316kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 96ms
memory: 37152kb

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: 270ms
memory: 35648kb

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: 63ms
memory: 67468kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205

result:

ok 1 number(s): "205"

Test #6:

score: 0
Accepted
time: 40ms
memory: 63572kb

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: 59ms
memory: 39516kb

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: 36ms
memory: 141208kb

input:

1
1 5000
abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

5023990000

result:

ok 1 number(s): "5023990000"

Test #9:

score: 0
Accepted
time: 49ms
memory: 63000kb

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: 28ms
memory: 64624kb

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