QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209860#6635. Strange KeyboardlefyAC ✓946ms169308kbC++141.8kb2023-10-10 18:34:102023-10-10 18:34:10

Judging History

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

  • [2023-10-10 18:34:10]
  • 评测
  • 测评结果:AC
  • 用时:946ms
  • 内存:169308kb
  • [2023-10-10 18:34:10]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
string s[1000010];
char t[5010];
int len[1000010],tot,nxt[1000010][30];
ll f[1000010],cost[1000010],dp[5010];
void insert(int id){
    int n=s[id].size()-1,now=0;
    for(int i=1;i<=n;i++){
        int ch=s[id][i]-'a'+1;
        if(!nxt[now][ch])nxt[now][ch]=++tot;
        now=nxt[now][ch];
        cost[now]=min(cost[now],f[n-i]);
    }
}
void solve(){
    int n,K,m=0;
    for(int i=1;i<=tot;cost[i]=inf,++i)for(int j=1;j<=26;j++)nxt[i][j]=0;
    memset(nxt,0,sizeof(nxt));
    tot=0;
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++){
        cin>>s[i];s[i]=" "+s[i];
        len[++m]=s[i].size()-1;
    }
    sort(len+1,len+1+m);m=unique(len+1,len+1+m)-len-1;
    queue<int>q;q.push(0);
    for(int i=1;i<=len[m]+K;i++)f[i]=inf;
    f[0]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        // cout<<x<<" "<<f[x]<<"\n";
        //a>=k
        if(x+K<=len[m]+K&&f[x+K]==inf)f[x+K]=f[x]+1,q.push(x+K);
        //a<k
        int p=lower_bound(len+1,len+1+m,x)-len-1;
        for(int i=p;i>=1&&x-len[i]<K;i--)if(f[x-len[i]]==inf){
            f[x-len[i]]=f[x]+1;q.push(x-len[i]);
        }
    }
    for(int i=1;i<=n;i++)insert(i);
    scanf("%s",t+1);
    m=strlen(t+1);
    for(int i=1;i<=m;i++)dp[i]=inf;dp[0]=0;
    for(int i=0;i<m;i++)if(dp[i]!=inf){
        int now=0;
        for(int j=i+1;j<=m;j++){
            int ch=t[j]-'a'+1;
            if(!nxt[now][ch])break;
            now=nxt[now][ch];
            dp[j]=min(dp[j],dp[i]+cost[now]);
        }
    }
    if(dp[m]==inf)printf("-1\n");
    else printf("%lld\n",dp[m]);
}
int main() {
    for(int i=1;i<=1e6;i++)cost[i]=inf;
    int t;scanf("%d",&t);
    while(t--)solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 13ms
memory: 162416kb

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: 31ms
memory: 163628kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 120ms
memory: 162640kb

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: 946ms
memory: 162404kb

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: 57ms
memory: 168716kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205

result:

ok 1 number(s): "205"

Test #6:

score: 0
Accepted
time: 110ms
memory: 166212kb

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: 919ms
memory: 163088kb

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: 28ms
memory: 169308kb

input:

1
1 5000
abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

5023990000

result:

ok 1 number(s): "5023990000"

Test #9:

score: 0
Accepted
time: 27ms
memory: 163420kb

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: 111ms
memory: 163404kb

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