QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#234238 | #6635. Strange Keyboard | ugly2333 | AC ✓ | 1335ms | 151904kb | C++20 | 1.6kb | 2023-11-01 15:04:26 | 2023-11-01 15:04:26 |
Judging History
answer
//Δ_E
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 1111111;
const int M = 26;
const int K = 5555;
const LL inf = 1e18;
int n,k,l,w,rt,c[N][M];
LL f[N],g[N],b[K],d[K],e[K],h[K];
char s[N],t[K];
vector<int> v,r;
int nw(){
w++;
memset(c[w],0,sizeof(c[w]));
g[w]=inf;
return w;
}
void ins(int&u,int i){
if(!u)
u=nw();
if(!s[i]){
g[u]=1;
v.push_back(u);
return;
}
ins(c[u][s[i]-'a'],i+1);
f[c[u][s[i]-'a']]=u;
}
int main(){
int T,i,j,o,x,u;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
for(i=0;i<k;i++)
b[i]=inf,d[i]=inf,e[i]=1;
w=0;
rt=nw();
v.clear();
for(i=1;i<=n;i++){
scanf("%s",s+1);
ins(rt,1);
x=strlen(s+1);
b[x%k]=min(b[x%k],(LL)x);
}
r.clear();
for(j=0;j<k;j++)
if(b[j]<inf)
r.push_back(j);
d[0]=0;
for(i=1;i<=k;i++){
o=-1;
LL xx=inf+1;
for(j=0;j<k;j++)
if(e[j]&&xx>d[j])
xx=d[j],o=j;
if(xx>=inf)
break;
e[o]=0;
for(u=0;u<r.size();u++){
j=r[u];
x=(o+j)%k;
d[x]=min(d[x],d[o]+(o+b[j])/k+1);
}
}
reverse(d+1,d+k);
for(i=1;i<k;i++)
d[i]++;
for(i=0;i<v.size();i++)
for(x=v[i],j=0;x;x=f[x],j++)
if(d[j%k]<inf)
g[x]=min(g[x],g[v[i]]+d[j%k]+j/k);
scanf("%s",t+1);
l=strlen(t+1);
for(i=0;i<=l;i++)
h[i]=inf;
h[0]=0;
for(i=0;i<l;i++)
if(h[i]<inf)
for(j=i,x=rt;j<=l&&x;j++,x=c[x][t[j]-'a'])
if(g[x]<inf)
h[j]=min(h[j],h[i]+g[x]);
printf("%lld\n",h[l]>=inf?-1:h[l]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9964kb
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: 49ms
memory: 8276kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 208ms
memory: 8244kb
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: 1335ms
memory: 10068kb
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: 75ms
memory: 51328kb
input:
1 7 4864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205
result:
ok 1 number(s): "205"
Test #6:
score: 0
Accepted
time: 163ms
memory: 38300kb
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: 1201ms
memory: 12888kb
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: 40ms
memory: 151904kb
input:
1 1 5000 abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
5023990000
result:
ok 1 number(s): "5023990000"
Test #9:
score: 0
Accepted
time: 39ms
memory: 36884kb
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: 130ms
memory: 40932kb
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