QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358751#6635. Strange Keyboarducup-team134AC ✓340ms114504kbC++171.8kb2024-03-19 23:36:042024-03-19 23:36:05

Judging History

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

  • [2024-03-19 23:36:05]
  • 评测
  • 测评结果:AC
  • 用时:340ms
  • 内存:114504kb
  • [2024-03-19 23:36:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

const int N=1000050;
const ll inf=1e18;
const int M=5005;
char s[N];

int go[N][26],tsz,root,ptr[N],len[N];
ll mn[M],best[N];
void Add(char*s,int n,int k){
	if(!root)root=++tsz;
	int now=root;
	for(int i=0;i<n;i++){
		if(!go[now][s[i]-'a']){
			go[now][s[i]-'a']=++tsz;
			best[tsz]=inf;
		}
		now=go[now][s[i]-'a'];
		if((n-1-i)%k!=0){
			best[now]=min(best[now],(n-1-i)/k+2+mn[k-(n-1-i)%k]);
		}else{
			best[now]=min(best[now],(ll)(n-1-i)/k+1);
		}
	}
}

ll dp[M];
char t[M];
ll mnl[M];
int main(){
	int q;
	scanf("%i",&q);
	while(q--){
		int n,k;
		scanf("%i %i",&n,&k);
		for(int i=0;i<k;i++)mnl[i]=inf;
		for(int i=1;i<=n;i++){
			scanf("%s",s+ptr[i]);
			len[i]=strlen(s+ptr[i]);
			ptr[i+1]=ptr[i]+len[i];
			mnl[len[i]%k]=min(mnl[len[i]%k],(ll)len[i]);
		}

		priority_queue<pair<ll,int>> pq;
		for(int i=1;i<k;i++)mn[i]=inf;
		pq.push({(ll)0,0});
		vector<int> ids;
		for(int i=1;i<k;i++)if(mnl[i]!=inf)ids.pb(i);
		while(pq.size()){
			int x=pq.top().second;
			int d=-pq.top().first;
			pq.pop();
			if(d!=mn[x])continue;
			for(int i:ids){
				int w=1+mnl[i]/k+(x+i>=k);
				if(mn[(x+i)%k]>mn[x]+w){
					mn[(x+i)%k]=mn[x]+w;
					pq.push({-mn[(x+i)%k],(x+i)%k});
				}
			}
		}

		for(int i=1;i<=n;i++){
			Add(s+ptr[i],len[i],k);
		}

		scanf("%s",t+1);
		int m=strlen(t+1);
		for(int i=1;i<=m;i++)dp[i]=inf;
		for(int i=0;i<m;i++){
			int now=root;
			for(int j=i+1;j<=m;j++){
				now=go[now][t[j]-'a'];
				if(!now)break;
				dp[j]=min(dp[j],dp[i]+best[now]);
			}
		}
		if(dp[m]==inf)printf("-1\n");
		else printf("%lld\n",dp[m]);
		root=0;
		for(int i=1;i<=tsz;i++){
			for(int j=0;j<26;j++){
				go[i][j]=0;
			}
		}
		tsz=0;
	}
	return 0;
}

详细

Test #1:

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

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: 40ms
memory: 5160kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 109ms
memory: 4368kb

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: 340ms
memory: 3900kb

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: 48ms
memory: 35468kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205

result:

ok 1 number(s): "205"

Test #6:

score: 0
Accepted
time: 41ms
memory: 31524kb

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: 76ms
memory: 7680kb

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: 114504kb

input:

1
1 5000
abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

5023990000

result:

ok 1 number(s): "5023990000"

Test #9:

score: 0
Accepted
time: 37ms
memory: 33156kb

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

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