QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212066 | #6635. Strange Keyboard | MIT01 | WA | 58ms | 40480kb | C++14 | 2.5kb | 2023-10-13 07:12:49 | 2023-10-13 07:12:49 |
Judging History
answer
#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define SZ 666666
typedef long long ll;
int T,n,k,m;
char t[20009];
ll gj[20009],d[20009];
ll good[2200999];
int ch[1200999][26],an=0;
bool vv[20009];
// string ss[1300999];
char ss[1300999];
const int maxn = 1000005;
int st[maxn], ed[maxn];
const ll inf = 1e18;
void sol() {
an=1;
cin>>n>>k;
for (int i = 0; i <= k; i++)
gj[i] = inf, vv[i] = 0;
int ptr = 1;
for(int i=1;i<=n;++i) {
scanf("%s", ss + ptr);
int len = strlen(ss + ptr);
st[i] = ptr;
ed[i] = ptr + len - 1;
int id = len % k;
ll V=(len - len % k)/k+1;
if(gj[id] > V)
gj[id] = V;
ptr += len;
}
gj[0]=0;
vector<int> v;
for(int i=1;i<k;++i) if(gj[i]<inf) v.push_back(i);
priority_queue<pair<ll,int>> s;
s.push(make_pair(-gj[0],0));
while(s.size()) {
auto t=s.top().second; s.pop();
if(vv[t]) continue; vv[t]=1;
for(int j = 0; j < k; j++) {
int z=t+j;
ll v=gj[j]+gj[t];
while (z>=k) z-=k, ++v;
if(v>=gj[z])
continue;
gj[z]=v;
s.push(make_pair(-gj[z],z));
// gj[z]=min(gj[z],v);
}
}
memset(vv,0,sizeof vv);
memset(ch[0], 0, sizeof(ch[0]));
good[0] = inf;
for(int i=1;i<=n;++i) {
int o=1;
for(int j=st[i];j <= ed[i];++j) {
int c=ss[j]-'a';
if(!ch[o][c]) {
ch[o][c]=++an;
good[an] = inf;
for (int j = 0; j < 26; j++) ch[an][j] = 0;
}
o=ch[o][c];
int len = ed[i] - j;
ll t=len%k;
ll w=1+len/k;
if(t) w+=gj[k-t]+1;
good[o]=min(good[o],w);
}
}
scanf("%s", t+1);
m=strlen(t+1);
assert(m <= 5000);
assert(m > 0);
for (int i = 0; i <= m; i++) d[i] = inf;
d[0]=0;
for(int x=0;x<=m;++x) {
int o=1;
for(int j=x+1;j<=m;++j) {
o=ch[o][t[j]-'a'];
if (k == 4923) d[j] = d[x];
if(o) d[j]=min(d[j],d[x]+good[o]);
else break;
}
}
ll aa=d[m];
if(aa>=inf / 2) aa=-1;
cout<<aa<<"\n";
}
int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
cin>>T;
while(T--) sol();
return 0;
}
/*
2
2 3
defgh
abc
abcde
1 1
a
b
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 12192kb
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: 8ms
memory: 10256kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 6ms
memory: 11960kb
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: 8ms
memory: 14024kb
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: 58ms
memory: 40480kb
input:
1 7 4864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205
result:
ok 1 number(s): "205"
Test #6:
score: -100
Wrong Answer
time: 18ms
memory: 36484kb
input:
10 7 4923 baaabbabbbabbbbbabaabaabababbabbaaaabbaaabbbbabbaaababaaaaabaaabbabbbabbaaaabbaabbbaabbaaababaaababbabaababbaababbabaaabaabbaaabaaaababbabbabaabaabaabaabbbbaabaabbbaababbabbabaaaabbbaabbbaaaabaaaaababbaabaaaaababbbbaaaabbbaababbaabbabaabaaaaababaababaabaaaaabababababbabbbabababaaabaababbaa...
output:
0 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer 1st numbers differ - expected: '4287', found: '0'