QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#223938 | #6635. Strange Keyboard | fickle | AC ✓ | 662ms | 216632kb | C++20 | 2.6kb | 2023-10-22 22:11:01 | 2023-10-22 22:11:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int ll
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define SZ(a) (int(a.size()))
typedef long long ll;
typedef double db;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
#define log(...) fprintf(stderr, __VA_ARGS__)
std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }
const int N = 1000100;
int tr[N][26], co[N], tot;
void solve() {
int n, k;
cin >> n >> k;
set<int> lens;
vi cost(k, 1e18);
vector<vector<pii>> G(k);
cost[0] = 0;
vector<string> s(n);
for(int i = 0; i < n; i++) {
cin >> s[i];
lens.insert(SZ(s[i]));
}
string t;
cin >> t;
for(auto len : lens) {
for(int x = 0; x < k; x++) {
int y = x + len;
int w = y / k + 1;
y %= k;
G[y].pb(Mp(x, w));
}
}
priority_queue<pii> q;
q.push(Mp(0, 0));
while(SZ(q)) {
auto [dis, x] = q.top(); q.pop();
if(-dis != cost[x]) continue;
for(auto [y, w] : G[x])
if(cost[y] > cost[x] + w) {
cost[y] = cost[x] + w;
q.push(Mp(-cost[y], y));
}
}
// for(int i = 0; i < k; i++)
// cout << cost[i] << ' ';
// cout << '\n';
tot = -1;
auto newnode = [&]() {
tot++;
memset(tr[tot], 0, sizeof(tr[tot]));
co[tot] = 1e18;
return tot;
};
newnode();
auto ins = [&](string s) {
int nw = 0;
for(int i = 0; i < SZ(s); i++) {
if(!tr[nw][s[i] - 'a'])
tr[nw][s[i] - 'a'] = newnode();
nw = tr[nw][s[i] - 'a'];
co[nw] = min(co[nw], 1 + (SZ(s) - i - 1) / k + cost[(SZ(s) - i - 1) % k]);
}
};
for(int i = 0; i < n; i++) ins(s[i]);
vi f(SZ(t) + 1, 1e18);
f[0] = 0;
for(int i = 0; i < SZ(t); i++) {
int nw = 0;
for(int j = i; j < SZ(t); j++) {
if(!tr[nw][t[j] - 'a']) break;
nw = tr[nw][t[j] - 'a'];
f[j + 1] = min(f[j + 1], f[i] + co[nw]);
}
}
// for(int i = 0; i <= SZ(t); i++)
// cout << f[i] << ' ';
// cout << '\n';
cout << (f[SZ(t)] == 1e18 ? -1 : f[SZ(t)]) << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _; cin >> _; for(int cas = 1; cas <= _; cas++) solve();
cerr << "time: " << (db)clock()/CLOCKS_PER_SEC << "s\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5976kb
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: 96ms
memory: 148576kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 198ms
memory: 45980kb
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: 662ms
memory: 25944kb
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: 51ms
memory: 67888kb
input:
1 7 4864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205
result:
ok 1 number(s): "205"
Test #6:
score: 0
Accepted
time: 68ms
memory: 97716kb
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: 168ms
memory: 33832kb
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: 19ms
memory: 216632kb
input:
1 1 5000 abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
5023990000
result:
ok 1 number(s): "5023990000"
Test #9:
score: 0
Accepted
time: 21ms
memory: 62404kb
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: 22ms
memory: 64068kb
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