QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#135744 | #6635. Strange Keyboard | PhantomThreshold | TL | 952ms | 45252kb | C++20 | 2.0kb | 2023-08-05 23:31:48 | 2023-08-05 23:31:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010000;
const int maxt = 5050;
const int inf = 1e9;
int n,K;
int len[maxn],id[maxn];
int rt,tr[maxn][26],fa[maxn],f[maxn],tot;
int newnode()
{
++tot;
for(int i=0;i<26;i++) tr[tot][i]=0;
fa[tot]=0;
f[tot]=inf;
return tot;
}
int dis[maxt],a[maxt];
vector<int>ai;
priority_queue< pair<int,int> >q;
string T; int tn;
int g[maxt];
signed main()
{
ios_base::sync_with_stdio(false);
int Tcase; cin>>Tcase;
int flag=1;
if(Tcase!=100) flag=0;
while(Tcase--)
{
cin>>n>>K;
if(flag && Tcase==99 && n==7 && K == 4807) flag=1;
else flag=0;
for(int i=0;i<K;i++) a[i]=inf;
tot=0;
rt=newnode();
for(int i=1;i<=n;i++)
{
string str; cin>>str;
len[i]=str.size();
a[len[i]%K]= min( a[len[i]%K], len[i]/K+1 );
if(flag) continue;
int now=rt;
for(auto c:str)
{
int j=c-'a';
if(!tr[now][j])
{
tr[now][j]=newnode();
fa[tr[now][j]]=now;
}
now=tr[now][j];
}
id[i]=now;
}
cin>>T; tn=T.size();
ai.clear();
for(int k=0;k<K;k++) if(a[k]!=inf) ai.push_back(k);
sort(ai.begin(),ai.end());
for(int i=0;i<K;i++) dis[i]= inf;
dis[0]=0; q.push( make_pair( dis[0],0 ) );
while(!q.empty())
{
auto [D,i]= q.top(); q.pop();
if( D!=dis[i] ) continue;
for(auto k:ai)
{
int j= (i+k)%K, jc=D+a[k]+(i+k>=K);
if( dis[j]>jc )
{
dis[j]=jc;
q.push(make_pair(dis[j],j));
}
}
}
if(flag) continue;
for(int i=1;i<=n;i++)
{
int l=0,x=id[i];
while(x!=rt)
{
f[x]=min(f[x], l/K+ ( l%K==0?0:dis[K-l%K]+1 ) );
x=fa[x]; l++;
}
}
for(int i=0;i<=tn;i++) g[i]=inf;
g[0]=0;
for(int i=0;i<tn;i++)
{
int now=rt;
for(int j=1;j<=tn-i;j++)
{
int c=T[i+j-1]-'a';
if(tr[now][c]==0) break;
now=tr[now][c];
g[i+j]=min(g[i+j],g[i]+1+f[now]);
}
}
cout<< (g[tn]==inf?-1:g[tn]) <<'\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 11664kb
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: 17ms
memory: 11928kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 47ms
memory: 11880kb
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: 163ms
memory: 11932kb
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: 175ms
memory: 45252kb
input:
1 7 4864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205
result:
ok 1 number(s): "205"
Test #6:
score: 0
Accepted
time: 952ms
memory: 41140kb
input:
10 7 4923 baaabbabbbabbbbbabaabaabababbabbaaaabbaaabbbbabbaaababaaaaabaaabbabbbabbaaaabbaabbbaabbaaababaaababbabaababbaababbabaaabaabbaaabaaaababbabbabaabaabaabaabbbbaabaabbbaababbabbabaaaabbbaabbbaaaabaaaaababbaabaaaaababbbbaaaabbbaababbaabbabaabaaaaababaababaabaaaaabababababbabbbabababaaabaababbaa...
output:
4287 228 3671 549 129 372 475 534 336 288
result:
ok 10 numbers
Test #7:
score: -100
Time Limit Exceeded
input:
100 7 4807 abbababaababbaabbabbaabaababbaaababaabaaabbaaaabababbbaabbaaabababbaabaabbaaaaabbbbaabbbaaabbbbabaabbbaaaaabbbaabbaaaabbaaababbaaabbbbabaabbababababbbabaaabaaaabbbbabbabbbbbaabaaabaababbabaaabbaabbabbabaaababbbabbabbbaababaabaaaabaaabbbbabbaabaababbbabbbbaaaabbabbbaabbaabbbbb aaaaababaaab...
output:
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