QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#135378 | #6635. Strange Keyboard | nameless_story | TL | 833ms | 10136kb | C++20 | 1.3kb | 2023-08-05 14:12:27 | 2023-08-05 14:12:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 1200000
const int INF=0x3f3f3f3f;
int c[N][30],mn[N],tot;
void cmin(int &x,int y) { x=min(x,y); }
void solve()
{
int n,k; cin>>n>>k;
for (int i=1; i<=tot; ++i)
{
memset(c[i],0,sizeof c[i]);
mn[i]=INF;
}
tot=1;
vector<string> s;
vector vis(k,INF);
for (int i=1; i<=n; ++i)
{
string st; cin>>st;
s.push_back(st);
cmin(vis[st.size()%k],st.size()/k+1);
}
string ss; cin>>ss;
int m=ss.size();
vector dp(m+1,INF),f(k+1,INF);
f[0]=0;
for (int i=1; i<k; ++i)
{
// if (vis[i]==INF) continue;
for (int j=0; j<k; ++j)
{
cmin(f[(i+j)%k],f[j]+vis[i]+(i+j>=k));
}
for (int j=0; j<k; ++j)
{
cmin(f[(i+j)%k],f[j]+vis[i]+(i+j>=k));
}
}
for (auto st:s)
{
int x=1,len=st.size(),step=0;
for (auto w:st)
{
if (!c[x][w]) c[x][w]=++tot;
x=c[x][w];
--len;
cmin(mn[x],f[(k-len%k)%k]+len/k);
}
}
dp[0]=0;
for (int i=0; i<ss.size(); ++i)
{
int x=1;
for (int j=i; j<ss.size(); ++j)
{
int w=ss[j];
x=c[x][w];
if (!x) break;
cmin(dp[j+1],dp[i]+mn[x]+1);
// f[i][j+1]=mn[x];
}
}
cout<<(dp[ss.size()]==INF?-1:dp[ss.size()])<<'\n';
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int T; cin>>T;
memset(mn,0x3f,sizeof mn);
while (T--)
{
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 10136kb
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: 84ms
memory: 10076kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 833ms
memory: 9996kb
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...