试题 历届真题 重复字符串【第十一届】【决赛】【Python】

一、题目来源：第十一届蓝桥杯决赛——重复字符串

资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

【问题描述】
如果一个字符串 S 恰好可以由某个字符串重复 K 次得到，我们就称 S 是
K 次重复字符串。例如 “abcabcabc” 可以看作是 “abc” 重复3次得到，所以
“abcabcabc"是3次重复字符串。
同理 “aaaaaa” 既是2次重复字符串、又是3次重复字符串和6次重复字
符串。
现在给定 一个字符串S，请你计算最少要修改其中几个字符，可以使 S 变
为一个 K 次字符串?

【输入格式】
输入第一行包含一个整数 K。
第二行包含一个只含小写字母的字符串 S 。

【输出格式】
输出一个整数代表答案。如果 S 无法修改成K次重复字符串，输出-1。

【样例输入】

2
aabbaa

【样例输出】

2

【评测用例规模与约定】
对于所有测评用例，1≤K≤100000，1≤|S|≤100000。其中 |S| 表示 S 长度。

二、解题

1、思路

1、首先 S 可以重复 K 次，那么len(S)%K == 0，但这有坑！
2、将 S 分成 K 组，每组 d=len(S)//K个字符，因此可以建立一个二维数组res[K][d]。每行表示一组重复的子字符串。
3、统计每列的出现字符次数最多的字符的次数，把出现次数少于出现次数最多的字符变成该字符，那么这一列改变字符次数最少。
4、累计K组应该改变字符的次数，即得到最终的改变次数。
5、如果程序中使用了下列代码，则只能得到90分。感谢这篇博客的提醒。

if len(S)%K == 0: print(-1)
1

2、举例

K = 5
S = asdadsfsdavklsdnkvls

第k组	0	1	2	3
0	a	s	d	a
1	d	s	f	s
2	d	a	v	k
3	l	s	d	n
4	k	v	l	s
最多次数字符 : 次数	d:2	s:3	d:2	s:2
需要改动次数 :	3	2	3	3

则最后需要更改字符的次数为：3+2+3+3=11

3、代码

K = int(input()) # 字符串重复的次数
S = input() # 字符串
d = len(S)//K # 重复节的长度

index = 0 # 指示字符串S的下标
res = [{} for _ in range(d)] # 用于记录每列各个字符出现的次数
ans = 0 # 记录更改的次数

for i in range(d):
    for j in range(K):
        temp = index+j*d # S 中处于同一列的字符下标
        # 统计各个字符出现的次数
        if S[temp] not in res[i]: 
            res[i][S[temp]] = 1
        else:
            res[i][S[temp]] +=1
    index+=1
    ans += K - max(res[i].values()) # 每列需要更改得次数

# 如果加上此段代码，只能得90分
# if len(S)%K!=0: 
#     print(-1)
# else:
print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25