QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#210964 | #6635. Strange Keyboard | zyxawa | AC ✓ | 302ms | 144640kb | C++14 | 1.7kb | 2023-10-11 21:58:32 | 2023-10-11 21:58:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int p,n,m,k,tot=1000000,t[1000001][26],vis[5001];
long long dis[5001],dp[5001],val[1000001];
vector <int> str[1000001];
char s[1000001];
map <int,int> len;
priority_queue <pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > q;
void insert(int d){
int p=0,cnt=str[d].size(),now=0;
for(auto i:str[d]){
if(!t[p][i]) t[p][i]=++tot;
p=t[p][i],now++,val[p]=min(val[p],(cnt-now)/k+dis[(k-(cnt-now)%k)%k]+((k-(cnt-now)%k)%k!=0));
// cout<<now<<" "<<(cnt-now)/k<<" "<<(cnt-now)%k<<" "<<(cnt-now)/k+dis[(k-(cnt-now)%k)%k]+1<<endl;
}
// val[p]=0;
}
int main(){
scanf("%d",&p);
while(p--){
scanf("%d%d",&n,&k),len.clear();
for(int i=1;i<=n;i++) str[i].clear();
for(int i=0;i<=tot;i++) val[i]=1e16,memset(t[i],0,sizeof(t[i]));
for(int i=0;i<=5000;i++) dp[i]=dis[i]=1e16,tot=vis[i]=0;
for(int i=1;i<=n;i++){
scanf("%s",s+1),m=strlen(s+1);
if(!len.count(m%k)) len[m%k]=m/k+1;
else len[m%k]=min(len[m%k],m/k+1);
for(int j=1;j<=m;j++) str[i].push_back(s[j]-97);
}
scanf("%s",s+1),m=strlen(s+1),dp[0]=dis[0]=0;
q.push({0,0});
while(!q.empty()){
int x=q.top().second;
q.pop();
if(vis[x]) continue;
vis[x]=1;
for(auto i:len){
int y=(x+i.first)%k,w=(x+i.first>=k);
if(dis[y]>dis[x]+i.second+w) dis[y]=dis[x]+i.second+w,q.push({dis[y],y});
}
}
for(int i=1;i<=n;i++) insert(i);
for(int i=0;i<m;i++){
for(int j=i+1,p=0;j<=m;j++){
if(!t[p][s[j]-97]) break;
p=t[p][s[j]-97];
//cout<<val[p]<<endl;
dp[j]=min(dp[j],dp[i]+val[p]+1);
}
}
if(dp[m]>=1e16) printf("-1\n");
else printf("%lld\n",dp[m]);
}
return 0;
}
/*
abc abc defgh
2
2 3
defgh
abc
abcde
1 1
a
b
*/
详细
Test #1:
score: 100
Accepted
time: 11ms
memory: 136708kb
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: 80ms
memory: 142840kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 141ms
memory: 138452kb
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: 302ms
memory: 136888kb
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: 61ms
memory: 141512kb
input:
1 7 4864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205
result:
ok 1 number(s): "205"
Test #6:
score: 0
Accepted
time: 52ms
memory: 139704kb
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: 81ms
memory: 138968kb
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: 33ms
memory: 141600kb
input:
1 1 5000 abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
5023990000
result:
ok 1 number(s): "5023990000"
Test #9:
score: 0
Accepted
time: 36ms
memory: 144640kb
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: 32ms
memory: 139948kb
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