QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#190279 | #6635. Strange Keyboard | ucup-team870 | TL | 582ms | 205612kb | C++17 | 1.7kb | 2023-09-28 16:32:58 | 2023-09-28 16:32:59 |
Judging History
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;
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();
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]);
}
cin>>s+1; int m=strlen(s+1); //下次用n吧..
rep(l,1,m){
ll v=0;
rep(r,l,m){
auto &lr=dp[l][r]; lr=INF;
v=(v*bs+s[r])%mod; //忘%mod了
if(!mp.count(v))continue;
for(auto len:mp[v]){
int x=((-len)%k+k)%k;
if(dis[x]<INF)Min(lr,(dis[x]+len)/k+1);
}
}
}
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: 3556kb
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: 333ms
memory: 205612kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 582ms
memory: 67628kb
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...