QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#176291#6635. Strange KeyboardmaoyitingWA 65ms76968kbC++141.2kb2023-09-11 14:39:102023-09-11 14:39:11

Judging History

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

  • [2023-09-11 14:39:11]
  • 评测
  • 测评结果:WA
  • 用时:65ms
  • 内存:76968kb
  • [2023-09-11 14:39:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int t,n,m,k,L,len[N],v[N],d[N],tot,ch[N][26],mn[N],f[N];
char a[N];
string s[N];
priority_queue<pair<int,int> >q;
void calc(){
	for(int i=0;i<=len[L];i++) d[i]=1e9,v[i]=0;
	q.push({d[0]=0,0});
	while(q.size()){
		int x=q.top().second;q.pop();
		if(v[x]) continue; v[x]=1;
		int y=x+k;
		if(y<=len[L]&&d[y]>d[x]+1) d[y]=d[x]+1,q.push({-d[y],y});
		for(int i=1;i<=L;i++){
			int y=x-len[i];
			if(y>=1&&d[y]>d[x]+1) d[y]=d[x]+1,q.push({-d[y],y});
		}
	}
}
signed main(){
	scanf("%d",&t),mn[0]=1e9;
	while(t--){
		scanf("%d%d",&m,&k);
		for(int i=1;i<=m;i++)
			scanf("%s",a),s[i]=a,len[i]=s[i].size();
		sort(len+1,len+1+m),L=unique(len+1,len+1+m)-len-1;
		calc();
		for(int i=1;i<=tot;i++) fill(ch[i],ch[i]+26,0);
		tot=1;
		for(int i=1;i<=m;i++){
			int p=1,k,len=s[i].size();
			for(int j=1;j<=len;j++){
				if(!ch[p][k=s[i][j-1]-'a']) mn[ch[p][k]=++tot]=1e9;
				p=ch[p][k],mn[p]=min(mn[p],1+d[len-j]);
			}
		}
		scanf("%s",a+1),n=strlen(a+1);
		fill(f+1,f+1+n,1e9);
		for(int i=1;i<=n;i++){
			int p=1;
			for(int j=i;j<=n;j++)
				p=ch[p][a[j]-'a'],f[j]=min(f[j],f[i-1]+mn[p]);
		}
		printf("%d\n",f[n]<1e9?f[n]:-1);
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 44744kb

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: 35ms
memory: 46152kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 13ms
memory: 46360kb

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: 11ms
memory: 45944kb

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: 65ms
memory: 76968kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205

result:

ok 1 number(s): "205"

Test #6:

score: -100
Wrong Answer
time: 32ms
memory: 73396kb

input:

10
7 4923
baaabbabbbabbbbbabaabaabababbabbaaaabbaaabbbbabbaaababaaaaabaaabbabbbabbaaaabbaabbbaabbaaababaaababbabaababbaababbabaaabaabbaaabaaaababbabbabaabaabaabaabbbbaabaabbbaababbabbabaaaabbbaabbbaaaabaaaaababbaabaaaaababbbbaaaabbbaababbaabbabaabaaaaababaababaabaaaaabababababbabbbabababaaabaababbaa...

output:

4315
229
3715
549
-1
-1
493
-1
-1
-1

result:

wrong answer 1st numbers differ - expected: '4287', found: '4315'