QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209533#6635. Strange Keyboardc20230201AC ✓1369ms372332kbC++141.7kb2023-10-10 15:36:242023-10-10 15:36:25

Judging History

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

  • [2023-10-10 15:36:25]
  • 评测
  • 测评结果:AC
  • 用时:1369ms
  • 内存:372332kb
  • [2023-10-10 15:36:24]
  • 提交

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