QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#176291 | #6635. Strange Keyboard | maoyiting | WA | 65ms | 76968kb | C++14 | 1.2kb | 2023-09-11 14:39:10 | 2023-09-11 14:39:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int t,n,m,k,L,len[N],v[N],d[N],tot,ch[N][26],mn[N],f[N];
char a[N];
string s[N];
priority_queue<pair<int,int> >q;
void calc(){
for(int i=0;i<=len[L];i++) d[i]=1e9,v[i]=0;
q.push({d[0]=0,0});
while(q.size()){
int x=q.top().second;q.pop();
if(v[x]) continue; v[x]=1;
int y=x+k;
if(y<=len[L]&&d[y]>d[x]+1) d[y]=d[x]+1,q.push({-d[y],y});
for(int i=1;i<=L;i++){
int y=x-len[i];
if(y>=1&&d[y]>d[x]+1) d[y]=d[x]+1,q.push({-d[y],y});
}
}
}
signed main(){
scanf("%d",&t),mn[0]=1e9;
while(t--){
scanf("%d%d",&m,&k);
for(int i=1;i<=m;i++)
scanf("%s",a),s[i]=a,len[i]=s[i].size();
sort(len+1,len+1+m),L=unique(len+1,len+1+m)-len-1;
calc();
for(int i=1;i<=tot;i++) fill(ch[i],ch[i]+26,0);
tot=1;
for(int i=1;i<=m;i++){
int p=1,k,len=s[i].size();
for(int j=1;j<=len;j++){
if(!ch[p][k=s[i][j-1]-'a']) mn[ch[p][k]=++tot]=1e9;
p=ch[p][k],mn[p]=min(mn[p],1+d[len-j]);
}
}
scanf("%s",a+1),n=strlen(a+1);
fill(f+1,f+1+n,1e9);
for(int i=1;i<=n;i++){
int p=1;
for(int j=i;j<=n;j++)
p=ch[p][a[j]-'a'],f[j]=min(f[j],f[i-1]+mn[p]);
}
printf("%d\n",f[n]<1e9?f[n]:-1);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 44744kb
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: 35ms
memory: 46152kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 13ms
memory: 46360kb
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: 11ms
memory: 45944kb
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: 65ms
memory: 76968kb
input:
1 7 4864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205
result:
ok 1 number(s): "205"
Test #6:
score: -100
Wrong Answer
time: 32ms
memory: 73396kb
input:
10 7 4923 baaabbabbbabbbbbabaabaabababbabbaaaabbaaabbbbabbaaababaaaaabaaabbabbbabbaaaabbaabbbaabbaaababaaababbabaababbaababbabaaabaabbaaabaaaababbabbabaabaabaabaabbbbaabaabbbaababbabbabaaaabbbaabbbaaaabaaaaababbaabaaaaababbbbaaaabbbaababbaabbabaabaaaaababaababaabaaaaabababababbabbbabababaaabaababbaa...
output:
4315 229 3715 549 -1 -1 493 -1 -1 -1
result:
wrong answer 1st numbers differ - expected: '4287', found: '4315'