QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#210964#6635. Strange KeyboardzyxawaAC ✓302ms144640kbC++141.7kb2023-10-11 21:58:322023-10-11 21:58:33

Judging History

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

  • [2023-10-11 21:58:33]
  • 评测
  • 测评结果:AC
  • 用时:302ms
  • 内存:144640kb
  • [2023-10-11 21:58:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int p,n,m,k,tot=1000000,t[1000001][26],vis[5001];
long long dis[5001],dp[5001],val[1000001];
vector <int> str[1000001];
char s[1000001];
map <int,int> len;
priority_queue <pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > q;
void insert(int d){
	int p=0,cnt=str[d].size(),now=0;
	for(auto i:str[d]){
		if(!t[p][i]) t[p][i]=++tot;
		p=t[p][i],now++,val[p]=min(val[p],(cnt-now)/k+dis[(k-(cnt-now)%k)%k]+((k-(cnt-now)%k)%k!=0));
//		cout<<now<<" "<<(cnt-now)/k<<" "<<(cnt-now)%k<<" "<<(cnt-now)/k+dis[(k-(cnt-now)%k)%k]+1<<endl;
	}
//	val[p]=0;
}
int main(){
	scanf("%d",&p);
	while(p--){
		scanf("%d%d",&n,&k),len.clear();
		for(int i=1;i<=n;i++) str[i].clear();
		for(int i=0;i<=tot;i++) val[i]=1e16,memset(t[i],0,sizeof(t[i]));
		for(int i=0;i<=5000;i++) dp[i]=dis[i]=1e16,tot=vis[i]=0;
		for(int i=1;i<=n;i++){
			scanf("%s",s+1),m=strlen(s+1);
			if(!len.count(m%k)) len[m%k]=m/k+1;
			else len[m%k]=min(len[m%k],m/k+1);
			for(int j=1;j<=m;j++) str[i].push_back(s[j]-97);
		}
		scanf("%s",s+1),m=strlen(s+1),dp[0]=dis[0]=0;
		q.push({0,0});
		while(!q.empty()){
			int x=q.top().second;
			q.pop();
			if(vis[x]) continue;
			vis[x]=1;
			for(auto i:len){
				int y=(x+i.first)%k,w=(x+i.first>=k);
				if(dis[y]>dis[x]+i.second+w) dis[y]=dis[x]+i.second+w,q.push({dis[y],y});
			}
		}
		for(int i=1;i<=n;i++) insert(i);
		for(int i=0;i<m;i++){
			for(int j=i+1,p=0;j<=m;j++){
				if(!t[p][s[j]-97]) break;
				p=t[p][s[j]-97];
				//cout<<val[p]<<endl;
				dp[j]=min(dp[j],dp[i]+val[p]+1);
			}
		}
		if(dp[m]>=1e16) printf("-1\n");
		else printf("%lld\n",dp[m]);
	}
	return 0;
}
/*
abc abc defgh

2
2 3
defgh
abc
abcde
1 1
a
b
*/

详细

Test #1:

score: 100
Accepted
time: 11ms
memory: 136708kb

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: 80ms
memory: 142840kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 141ms
memory: 138452kb

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: 302ms
memory: 136888kb

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: 61ms
memory: 141512kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205

result:

ok 1 number(s): "205"

Test #6:

score: 0
Accepted
time: 52ms
memory: 139704kb

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: 81ms
memory: 138968kb

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: 33ms
memory: 141600kb

input:

1
1 5000
abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

5023990000

result:

ok 1 number(s): "5023990000"

Test #9:

score: 0
Accepted
time: 36ms
memory: 144640kb

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: 32ms
memory: 139948kb

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