QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#209533 | #6635. Strange Keyboard | c20230201 | AC ✓ | 1369ms | 372332kb | C++14 | 1.7kb | 2023-10-10 15:36:24 | 2023-10-10 15:36:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e6+5, inf=1e18;
ll tot,k;
ll p[maxn][26], ed[maxn], dis[5005], dep[maxn], val[maxn], dp[5005];
map<ll,ll> E;
vector<ll> vec[maxn];
void insert(string s) {
ll pos=0;
for(ll i=0;i<s.size();i++) {
ll v=s[i]-'a';
if(!p[pos][v]) p[pos][v]=++tot;
pos=p[pos][v];
}
ed[pos]=1;
return ;
}
void dfs(ll x) {
if(ed[x]) vec[x].push_back(x);
val[x]=inf;
for(ll i=0;i<26;i++) {
if(!p[x][i]) continue;
dep[p[x][i]]=dep[x]+1;
dfs(p[x][i]);
for(auto p:vec[p[x][i]]) vec[x].push_back(p);
}
for(auto p:vec[x]) val[x]=min(val[x],(dep[p]-dep[x]+k-1)/k+dis[((dep[x]-dep[p])%k+k)%k]);
return ;
}
void solve() {
ll n; cin>>n>>k;
for(ll i=0;i<=tot;i++){
vec[i].clear();
ed[i]=0;
for(ll j=0;j<26;j++) p[i][j]=0;
}
tot=0;
E.clear();
for(ll i=0;i<k;i++) dis[i]=inf;
dis[0]=0;
for(ll i=1;i<=n;i++) {
string s; cin>>s;
insert(s);
if(E.find(s.size()%k)==E.end()||E[s.size()%k]>s.size()) E[s.size()%k]=s.size();
}
for(auto p:E) {
ll y=p.first, w=p.second;
if(!y) continue;
ll d=__gcd(k,y);
for(ll v=0;v<d;v++) {
ll cnt=0;
for(ll x=(v+y)%k;cnt<2;x=(x+y)%k,cnt+=(x==v)) dis[x]=min(dis[x],dis[(x-y+k)%k]+((x-y+k)%k+w)/k+1);
}
}
dfs(0);
string t; cin>>t;
for(ll i=0;i<=t.size();i++) dp[i]=inf;
dp[0]=0;
for(ll i=0;i<t.size();i++) {
ll x=0;
for(ll j=i+1;j<=t.size();j++) {
if(p[x][t[j-1]-'a']) x=p[x][t[j-1]-'a'];
else break;
dp[j]=min(dp[j],dp[i]+val[x]+1);
}
}
if(dp[t.size()]!=inf) cout<<dp[t.size()]<<'\n';
else cout<<"-1\n";
return ;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
ll q; cin>>q;
while(q--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 31068kb
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: 156ms
memory: 43140kb
input:
1 1413 4867 yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn yumnkkghwtqnhpmmsbfwypcwudihegsvt...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 446ms
memory: 33732kb
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: 1369ms
memory: 32096kb
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: 114ms
memory: 135132kb
input:
1 7 4864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205
result:
ok 1 number(s): "205"
Test #6:
score: 0
Accepted
time: 200ms
memory: 107764kb
input:
10 7 4923 baaabbabbbabbbbbabaabaabababbabbaaaabbaaabbbbabbaaababaaaaabaaabbabbbabbaaaabbaabbbaabbaaababaaababbabaababbaababbabaaabaabbaaabaaaababbabbabaabaabaabaabbbbaabaabbbaababbabbabaaaabbbaabbbaaaabaaaaababbaabaaaaababbbbaaaabbbaababbaabbabaabaaaaababaababaabaaaaabababababbabbbabababaaabaababbaa...
output:
4287 228 3671 549 129 372 475 534 336 288
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 246ms
memory: 40308kb
input:
100 7 4807 abbababaababbaabbabbaabaababbaaababaabaaabbaaaabababbbaabbaaabababbaabaabbaaaaabbbbaabbbaaabbbbabaabbbaaaaabbbaabbaaaabbaaababbaaabbbbabaabbababababbbabaaabaaaabbbbabbabbbbbaabaaabaababbabaaabbaabbabbabaaababbbabbabbbaababaabaaaabaaabbbbabbaabaababbbabbbbaaaabbabbbaabbaabbbbb aaaaababaaab...
output:
45 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 116 1 -1 293 519 5 160 15 126 13 31 619 4...
result:
ok 100 numbers
Test #8:
score: 0
Accepted
time: 112ms
memory: 372332kb
input:
1 1 5000 abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
5023990000
result:
ok 1 number(s): "5023990000"
Test #9:
score: 0
Accepted
time: 96ms
memory: 105596kb
input:
1 100000 4817 acdcaaccca cdbbbbabba bcbccbcdbd cdabaddaad ddbdbabcac dadadbbcba aabcbbcabc cdcadbbbda dabacdbabd dcbadbdabd cdcbacbada cadbbadbac dbadbccdcd babaddcdca aaaddacccc dabdcdadbb abbbadbdaa bcdbbacdaa bcbcbddadb bddaccbaba baddadaaac adbadbdaaa cacbbbcdbc abccdcacdb abaacddbbc acbbbcbcdc ...
output:
618356
result:
ok 1 number(s): "618356"
Test #10:
score: 0
Accepted
time: 109ms
memory: 100384kb
input:
10 3901 4952 srsofqyvrt tazndzviuq jcomfoxkiw huzfqiecss hhdtqpaohy qcrokphbtf xzkxssibix hokmdpzydu jreaeulsjt vmxdsazajq jawyofqbck cwmzupygdm rgsahqyxqt kckgorfgvi kcawvezmyb mpcyhdifgn xiwtmwttmp mzknfqoifl vbpvvdnqpy anpdgjnbew scekjovqpr lzhfocjvld oswjfhjdby pmdbjddkpv yjbnjcdtmc gmpjgtpksa r...
output:
904 208656 4560 30873 28272 5377 1326 93956 93720 282610
result:
ok 10 numbers