QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#234130 | #6635. Strange Keyboard | ugly2333 | WA | 91ms | 42428kb | C++20 | 1.4kb | 2023-11-01 14:18:55 | 2023-11-01 14:18:56 |
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 int inf = 1e9;
int n,k,l,w,rt,c[N][M],f[N],g[N],b[K],d[K],e[K],h[K];
char s[N],t[K];
vector<int> v;
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;
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],x);
}
d[0]=0;
for(i=1;i<=n;i++){
o=-1;
x=inf+1;
for(j=0;j<k;j++)
if(e[j]&&x>d[j])
x=d[j],o=j;
if(x>=inf)
break;
e[o]=1;
for(j=0;j<k;j++){
if(b[j]>=inf)
continue;
x=(o+j)%k;
d[x]=min(d[x],d[o]+(o+b[j])/k);
}
}
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("%d\n",h[l]>=inf?-1:h[l]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3580kb
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: 24ms
memory: 3904kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 40ms
memory: 3728kb
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: 91ms
memory: 3688kb
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: -100
Wrong Answer
time: 36ms
memory: 42428kb
input:
1 7 4864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
132
result:
wrong answer 1st numbers differ - expected: '205', found: '132'