QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#190288#6635. Strange Keyboarducup-team870TL 584ms206232kbC++171.8kb2023-09-28 16:38:292023-09-28 16:38:29

Judging History

你现在查看的是最新测评结果

  • [2023-09-28 16:38:29]
  • 评测
  • 测评结果:TL
  • 用时:584ms
  • 内存:206232kb
  • [2023-09-28 16:38:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define ll long long
#define vi vector<int>
#define db double
const ll mod=1231453023109121,INF=1e18;
const int N=5005,bs=131,M=1e6+6;
void Min(ll &x,ll y){x=min(x,y);}
unordered_map<ll,vi>mp;
unordered_map<ll,ll>res;
char s[M];
ll l[N],dis[N],dp[N][N],ans[N];
// ll mul(ll x,ll y){
//     return x*y%mod;
// }
void slv(){
    int n,k;cin>>n>>k;
    mp.clear(); res.clear();
    rep(i,0,k)l[i]=INF;
    rep(i,1,n){
        cin>>s+1;
        int len=strlen(s+1); ll v=0;
        rep(j,1,len){
            v=(bs*v+s[j])%mod; mp[v].push_back(len-j);
        }
        Min(l[len%k],k+len);
    }
    dis[0]=0; rep(i,1,k-1)dis[i]=INF;
    vi vis(k+1);
    while(1){
        ll mi=INF; int x;
        rep(i,0,k-1){
            if(!vis[i] && dis[i]<mi){
                mi=dis[i]; x=i;
            }
        }
        if(mi==INF)break; vis[x]=1;
        rep(i,0,k-1)Min(dis[i],dis[x]+l[(i-x+k)%k]);
    }
    for(auto &[key,vec]:mp){
        ll val=INF;
        for(auto len:vec){
            int x=((-len)%k+k)%k;
            if(dis[x]<INF)Min(val,(dis[x]+len)/k+1);
        }
        res[key]=val;
    }
    cin>>s+1; int m=strlen(s+1); //下次用n吧..
    rep(l,1,m){
        ll v=0;
        rep(r,l,m){
            dp[l][r]=INF;
            v=(v*bs+s[r])%mod; //忘%mod了
            if(mp.count(v))dp[l][r]=res[v];
        }
    }
    rep(i,1,m){
        ans[i]=dp[1][i];
        rep(j,1,i-1)Min(ans[i], ans[j]+dp[j+1][i]);
    }
    cout<<(ans[m]>=INF?-1:ans[m])<<'\n';
}
signed main(){
    IOS
    int T;cin>>T;
    while(T--)slv();
}
/*
1
2 3
defgh
abc
abcde
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3464kb

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: 294ms
memory: 206232kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 584ms
memory: 68188kb

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:


result: