QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #135332 | #6635. Strange Keyboard | PlentyOfPenalty# | TL | 205ms | 40400kb | C++20 | 1.7kb | 2023-08-05 13:51:07 | 2023-08-05 13:51:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6,MK=5000;
const long long INF=1e18;
int Q,n,K,m,len[N+10],c[N+10][26],vis[N+10][26],ap[MK+10],cnt,TIM,tmp;
long long mn[MK+10],g[MK+10],cst[N+10],dp[MK+10];
string s[N+10],T;
void Ins(int x,int id,int nw){
//cout<<"INS "<<x<<" "<<id<<","<<nw<<"\n";
cst[x]=min(cst[x],g[K-(len[id]-nw)%K]+1+1+(len[id]-nw)/K);
//cout<<"CST="<<cst[x]<<"\n";
if(nw==len[id])return;
int t=s[id][nw]-'a';
if(vis[x][t]!=TIM)vis[x][t]=TIM,c[x][t]=++cnt,cst[cnt]=INF;
Ins(c[x][t],id,nw+1);
}
int main(){
#ifdef memset0
freopen("E.in","r",stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
cin>>Q;
while(Q--){
cin>>n>>K;
++TIM;
for(int i=1;i<K;++i)mn[i]=g[i]=INF;
//cin>>s[0];
for(int i=1;i<=n;++i){
cin>>s[i];
//s[i]=s[0];
len[i]=s[i].size();
mn[len[i]%K]=min(mn[len[i]%K],1ll+len[i]/K);
ap[len[i]%K]=TIM;
}
for(int i=1;i<K;++i)
if(ap[i]){
long long t=mn[i]*2;
for(int j=2,l=(i<<1)%K;j<K;++j,t+=mn[i]){
mn[l]=min(mn[l],t);
if(t>INF)break;
if((l+=i)>=K)l-=K;
}
}
g[K]=-1;
for(int i=1;i<K;++i)for(int j=0,t=i;j<K;++j,((++t)==K?t=0:0)){
g[t]=min(g[t],g[j]+mn[i]);
}
//for(int i=0;i<K;++i)cout<<"G "<<i<<"="<<g[i]<<"\n";
cnt=1;
for(int i=1;i<=n;++i)Ins(1,i,0);
cin>>T,m=T.size();
for(int i=1;i<=m;++i)dp[i]=INF;
for(int i=0;i<m;++i)if(dp[i]!=INF){
tmp=1;
//cout<<"DP "<<i<<"="<<dp[i]<<"\n";
for(int j=i+1;j<=m;++j){
if(vis[tmp][T[j-1]-'a']!=TIM)break;
tmp=c[tmp][T[j-1]-'a'];
dp[j]=min(dp[j],dp[i]+cst[tmp]);
}
}
cout<<(dp[m]==INF?-1ll:dp[m])<<endl;
}
return 0;
}
/*
2
2 3
defgh
abc
abcde
1 1
a
b
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 40108kb
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: 34ms
memory: 40400kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 205ms
memory: 39764kb
input:
10 446 4905 afigcjhcgagabbiccehjcjajigghgbjjadccicghggijjdfeciaccgheedjdhgfjdfdbgidbbdjaiehhceeehchhabhaideggjbjajgfgicfdggahhbjgdebccbgbiedhehaebdccdfdffaacjcfbgjeegbahhbgcdjigijajheidchbddicehhhjbeiaajgedhdcjiefdgdbjjfaegheeidieheecaicciaajbabiidcecefgiicccdidegeica afigcjhcgagabbiccehjcjajigghgbj...
output:
3 2 2 11 6 5 1 1 1 1
result:
ok 10 numbers
Test #4:
score: -100
Time Limit Exceeded
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