QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#114640 | #6635. Strange Keyboard | xaphoenix | AC ✓ | 948ms | 219156kb | C++14 | 3.1kb | 2023-06-22 18:07:58 | 2023-06-22 18:07:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define LC k<<1
#define RC k<<1|1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for (int i = a; i < n; i++)
#define repn(i,a,n) for (int i = a; i <= n; i++)
#define per(i,a,n) for (int i = (n) - 1; i >= a; i--)
#define pern(i,a,n) for (int i = n; i >= a; i--)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<double, double> PDD;
typedef pair<ull, ull> PUU;
typedef pair<LL, LL> PLL;
const int N = 1100000;
const int M = 1100000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = 1e18;
const double eps = 1e-9;
mt19937_64 Rand((unsigned long long)new char);
#define rand Rand
int T, n, m, k, pp[N], len[N], cp[N];
string s[N], t;
LL f[N], dis[N];
vector<PIL> g[N];
vector<int> tmp;
int ch[M][26], pos, rt;
LL val[M];
int newnode() {
pos++;
memset(ch[pos], 0, sizeof(ch[pos]));
val[pos] = INF;
return pos;
}
LL dp[N];
priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL,int>>> q;
void dijkstra(int st) {
rep(i, 0, k) dis[i] = INF, pp[i] = 0;
dis[st] = 0;
q.push(mp(0, st));
while (!q.empty()) {
int now = q.top().se; q.pop();
if (pp[now]) continue;
pp[now] = 1;
for (auto p: g[now]) {
int y = p.fi;
LL w = p.se;
if (dis[now] + w < dis[y]) dis[y] = dis[now] + w, q.push(mp(dis[y], y));
}
}
}
int main() {
IO;
cin >> T;
while (T--) {
cin >> n >> k;
rep(i, 0, k) f[i] = INF, pp[i] = cp[i] = 0, g[i].clear();
tmp.clear();
repn(i, 1, n) {
cin >> s[i];
len[i] = s[i].size();
f[len[i] % k] = min(f[len[i] % k], (LL)len[i]);
if (!cp[len[i] % k]) cp[len[i] % k] = 1, tmp.pb(len[i] % k);
}
cin >> t;
m = t.size();
rep(i, 0, k) {
for (auto j: tmp) {
int w = f[j] / k + 1, tgt = (i + j) % k;
if (i > tgt) w++;
g[tgt].pb(mp(i, w));
}
}
dijkstra(0);
/*
rep(i, 0, k) dis[i] = INF, pp[i] = 0;
dis[0] = 0;
while (1) {
LL mn = INF;
int pos = -1;
rep(i, 0, k) if (!pp[i] && dis[i] < mn) mn = dis[i], pos = i;
if (pos == -1) break;
pp[pos] = 1;
for (auto p: g[pos]) {
int y = p.fi;
LL w = p.se;
dis[y] = min(dis[y], dis[pos] + w);
}
}
*/
pos = 0;
rt = newnode();
repn(i, 1, n) {
int cur = rt;
rep(j, 0, len[i]) {
int p = s[i][j] - 'a';
if (ch[cur][p]) cur = ch[cur][p];
else cur = ch[cur][p] = newnode();
int left = len[i] - j - 1;
val[cur] = min(val[cur], dis[left % k] + left / k + 1);
}
}
repn(i, 1, m) dp[i] = INF;
dp[0] = 0;
rep(i, 0, m) {
int cur = rt;
repn(j, i + 1, m) {
int p = t[j - 1] - 'a';
cur = ch[cur][p];
if (cur == 0) break;
dp[j] = min(dp[j], dp[i] + val[cur]);
}
}
if (dp[m] == INF) cout << "-1\n";
else cout << dp[m] << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 12ms
memory: 79212kb
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: 124ms
memory: 219156kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 317ms
memory: 115684kb
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: 948ms
memory: 99332kb
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: 53ms
memory: 107340kb
input:
1 7 4864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205
result:
ok 1 number(s): "205"
Test #6:
score: 0
Accepted
time: 99ms
memory: 148660kb
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: 146ms
memory: 101368kb
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: 22ms
memory: 186632kb
input:
1 1 5000 abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
5023990000
result:
ok 1 number(s): "5023990000"
Test #9:
score: 0
Accepted
time: 28ms
memory: 106212kb
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: 108164kb
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