第十三届蓝桥杯省赛Python 组_python

第十三届蓝桥杯省赛 Python Ｂ组写在前面

本次所有代码均存放于仓库：

Github：GxlHus/Algorithm at 蓝桥杯 (github.com)

Gitee：Algorithm: 算法解题 - Gitee.com

原题目：第十三届蓝桥杯大赛软件赛省赛_PB.pdf · AYO/Algorithm - Gitee.com

本次省赛题目总体来说不难，总体质量比较高，尤其是后边几道题，虽然能轻易做出来，但是想跑通所有测试点，还得下功夫优化，做起来比较有意思，不像之前有些题做出来就满分，做不出来就毫无头绪，参与感不强。

。

把自己的解题思路写在这里，也仅代表我个人理解得出的思路，不代表官方答案，欢迎大家交流，指正错误。

试题A：排列字母

本题总分：5 分

【问题描述】

小蓝要把一个字符串中的字母按其在字母表中的顺序排列。

例如，LANQIAO 排列后为 AAILNOQ。

又如，GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY 。

请问对于以下字符串，排列之后字符串是什么？ WHERETHEREISAWILLTHEREISAWAY

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。

本题的结果为一个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

【思路分析】

这个没啥难的，Python直接转为list再sorted即可，一行搞定

【完整代码】

s = 'WHERETHEREISAWILLTHEREISAWAY'
print(''.join(sorted(list(s))))

【参考答案】

AAAEEEEEEHHHIIILLRRRSSTTWWWY

试题B：寻找整数

本题总分：5 分

【问题描述】

有一个不超过 1 0 17 10^{17} 1017的正整数 n n n，知道这个数除以 2 2 2至 49 49 49后的余数如下表所示，求这个正整数最小是多少。

a	n mod a	a	n mod a	a	n mod a	a	n mod a
2	1	14	11	26	23	38	37
3	2	15	14	27	20	39	23
4	1	16	9	28	25	40	9
5	4	17	0	29	16	41	1
6	5	18	11	30	29	42	11
7	4	19	18	31	27	43	11
8	1	20	9	32	25	44	33
9	2	21	11	33	11	45	29
10	9	22	11	34	17	46	15
11	0	23	15	35	4	47	5
12	5	24	17	36	29	48	41
13	10	25	9	37	22	49	46

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。

本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【思路分析】

这个题思路很直，直接爆。

但爆也有爆的技巧，可以先算一部分，然后得到一组符合条件的，作为步长，再筛选一轮，这样步长比较大的时候，列表中的数量较少，爆起来速度不至于太慢。

至于为什么不直接写大循环，因为我每次生成的范围和结果不一样，如果筛选后剩余的列表元素过多，需要将取余的范围加大，需要实时动态调整。

① 先给一个初值：

ls = [i for i in range(1, 10 ** 4)]

② 再进行一次筛选：

for i in range(2, 10):
    ls = list(filter(lambda x: x % i == mp[i], ls))

③ 然后进行一次输出：

[1649, 4169, 6689, 9209]

④ 然后以ls[0]作为初值，以ls[1]-ls[0]作为步长，再生成一组

ls = [i for i in range(ls[0], 10 ** 9, ls[1] - ls[0])]

⑤ 再筛选，这个筛选的范围不是固定的，10~20，~15都可以，但要根据上边的ls的end值决定，如果太小，则筛选范围相应小一些，反之则大一些：

for i in range(10, 20):
    ls = list(filter(lambda x: x % i == mp[i], ls))

⑥ 输出：

[88209209, 321001769, 553794329, 786586889]

重复④⑤⑥执行

...

直到即得出最终结果

ls = [i for i in range(ls[0], 10 ** 17, ls[1] - ls[0])]
for i in range(30, 50):
    ls = list(filter(lambda x: x % i == mp[i], ls))
print(ls)

【完整代码】

mp = {2: 1, 3: 2, 4: 1, 5: 4, 6: 5, 7: 4, 8: 1, 9: 2, 10: 9, 11: 0, 12: 5, 13: 10, 14: 11, 15: 14, 16: 9, 17: 0, 18: 11,19: 18, 20: 9, 21: 11, 22: 11, 23: 15, 24: 17, 25: 9, 26: 23, 27: 20, 28: 25, 29: 16, 30: 29, 31: 27, 32: 25,33: 11, 34: 17, 35: 4, 36: 29, 37: 22, 38: 37, 39: 23, 40: 9, 41: 1, 42: 11, 43: 11, 44: 33, 45: 29, 46: 15, 47: 5, 48: 41, 49: 46}

ls = [i for i in range(1, 10 ** 4)]
for i in range(2, 10):
    ls = list(filter(lambda x: x % i == mp[i], ls))
print(ls)
ls = [i for i in range(ls[0], 10 ** 9, ls[1] - ls[0])]
for i in range(10, 20):
    ls = list(filter(lambda x: x % i == mp[i], ls))
print(ls)
ls = [i for i in range(ls[0], 10 ** 13, ls[1] - ls[0])]
for i in range(20, 30):
    ls = list(filter(lambda x: x % i == mp[i], ls))
print(ls)
ls = [i for i in range(ls[0], 10 ** 17, ls[1] - ls[0])]
for i in range(30, 50):
    ls = list(filter(lambda x: x % i == mp[i], ls))
print(ls)

【参考答案】

2022040920220409

试题C: 纸张尺寸

时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分

【问题描述】

在 ISO 国际标准中定义了 A0 纸张的大小为 1189 m m × 841 m m 1189mm × 841mm 1189mm×841mm，将 A 0 A0 A0纸沿长边对折后为 A 1 A1 A1纸，大小为 841 m m × 594 m m 841mm × 594mm 841mm×594mm，在对折的过程中长度直接取下整（实际裁剪时可能有损耗）。

将 A 1 A1 A1
纸沿长边对折后为 A 2 A2 A2纸，依此类推。

输入纸张的名称，请输出纸张的大小。

【输入格式】

输入一行包含一个字符串表示纸张的名称，该名称一定是 A 0 A0 A0、 A 1 A1 A1、 A 2 A2 A2、 A 3 A3 A3、 A 4 A4 A4、 A 5 A5 A5、 A 6 A6 A6、 A 7 A7 A7、 A 8 A8 A8、 A 9 A9 A9之一。

【输出格式】

输出两行，每行包含一个整数，依次表示长边和短边的长度。

【样例输入 1】

A0

【样例输出 1】

1189
841

【样例输入 2】

A1

【样例输出 2】

841
594

【思路分析】

这个题没啥难度，找到长边然后除以2就行。

注意一个坑：不是长宽同时除以2，而是长边。

折叠之后长边会变成短边，所以要进行交换

【完整代码】

paper = input()
width = 1189
height = 841
count = int(paper[1])
while count > 0:
    if width < height:
        width, height = height, width
    width //= 2
    count -= 1
if width < height:
    width, height = height, width
print(width)
print(height)

试题D：数位排序

时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分

【问题描述】

小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。

当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。

例如， 2022 2022 2022排在 409 409 409前面，因为 2022 2022 2022的数位之和是 6 6 6，小于 409 409 409的数位之和 13 13 13。

又如， 6 6 6排在 2022 2022 2022前面，因为它们的数位之和相同，而 6 6 6小于 2022 2022 2022。

给定正整数 n n n， m m m，请问对 1 1 1到 n n n采用这种方法排序时，排在第 m m m个的元素是多少？

【输入格式】

输入第一行包含一个正整数 n n n。

第二行包含一个正整数 m m m。

【输出格式】

输出一行包含一个整数，表示答案。

【样例输入】

13
5

【样例输出】

【样例说明】

1 1 1到 13 13 13的排序为： 1 , 10 , 2 , 11 , 3 , 12 , 4 , 13 , 5 , 6 , 7 , 8 , 9 1, 10, 2, 11, 3, 12, 4, 13, 5, 6, 7, 8, 9 1,10,2,11,3,12,4,13,5,6,7,8,9。

第 5 5 5个数为 3 3 3。

【评测用例规模与约定】

对于 30 % 30\% 30%的评测用例， 1 ≤ m ≤ n ≤ 300 1 ≤ m ≤ n ≤ 300 1≤m≤n≤300。

对于 50 % 50\% 50%的评测用例， 1 ≤ m ≤ n ≤ 1000 1 ≤ m ≤ n ≤ 1000 1≤m≤n≤1000。

对于所有评测用例， 1 ≤ m ≤ n ≤ 106 1 ≤ m ≤ n ≤ 106 1≤m≤n≤106。

【思路分析】

这个题也不难，首先是计算数位和，直接拆成列表，然后逐个取int()，再求列表的和即可

def swh(n):
    n = map(int, list(str(n)))
    return sum(n)

然后用字典生成式生成字典然后排序后按要求取值即可。

【完整代码】

def swh(n):
    n = map(int, list(str(n)))
    return sum(n)


def lst(end, start=1):
    ls = [i for i in range(start, end + 1)]
    sw = {i: swh(i) for i in ls}
    s = sorted(sw.items(), key=lambda x: x[1])
    return s


end = int(input())
i = int(input()) - 1
print(lst(end)[i][0])

试题E：蜂巢

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】

蜂巢由大量的六边形拼接而成，定义蜂巢中的方向为： 0 0 0表示正西方向， 1 1 1表示西偏北 60 ° 60° 60°， 2 2 2表示东偏北 60 ° 60° 60°， 3 3 3表示正东， 4 4 4表示东偏南 60 ° 60° 60°， 5 5 5表示西偏南 60 ° 60° 60°。

对于给定的一点 O O O，我们以 O O O为原点定义坐标系，如果一个点 A A A由 O O O点先向 d d d方向走 p p p步再向 ( d + 2 ) m o d 6 (d + 2) mod 6 (d+2)mod6方向（ d d d的顺时针 120 ° 120° 120°方向）走 q q q步到达，则这个点的坐标定义为$(d; p; q)
。

在蜂窝中，一个点的坐标可能有多种。

下图给出了点。

在蜂窝中，一个点的坐标可能有多种。

下图给出了点。

在蜂窝中，一个点的坐标可能有多种。

下图给出了点B(0; 5; 3) 和点和点和点C(2; 3; 2)$的示意。

给定点 ( d 1 , p 1 , q 1 ) (d_1, p_1, q_1) (d1,p1,q1)和点$(d_2, p_2, q_2)，请问他们之间最少走多少步可以到达？

【输入格式】

输入一行包含 6 个整数 d 1 , p 1 , q 1 , d 2 , p 2 , q 2 d_1, p_1, q_1, d_2, p_2, q_2 d1,p1,q1,d2,p2,q2表示两个点的坐标，相邻两个整数之间使用一个空格分隔。

【输出格式】

输出一行包含一个整数表示两点之间最少走多少步可以到达。

【样例输入】

0 5 3 2 3 2

【样例输出】

【评测用例规模与约定】

对于 25 25% 25的评测用例， p 1 , p 2 ≤ 103 p1, p2 ≤ 103 p1,p2≤103；

对于 50 50% 50的评测用例， p 1 , p 2 ≤ 105 p1, p2 ≤ 105 p1,p2≤105；

对于 75 75% 75的评测用例， p 1 , p 2 ≤ 107 p1, p2 ≤ 107 p1,p2≤107；

对于所有评测用例， 0 ≤ d 1 , d 2 ≤ 5 ， 0 ≤ q 1 < p 1 ≤ 109 ， 0 ≤ q 2 < p 2 ≤ 109 0 ≤ d1, d2 ≤ 5，0 ≤ q1 < p1 ≤ 109，0 ≤ q2 < p2 ≤ 109 0≤d1,d2≤5，0≤q1<p1≤109，0≤q2<p2≤109。

【思路分析】

这个题，我不会，但我觉得，将路径看成三角形，已知角度，已知两边和，求出第三边的长，然后得到两点的斜边长，然后再根据夹角算两边的长度。

但是我也不知道对不对，说来惭愧，鄙人三角形学的非常辣鸡，不知道怎么求非直角三角形的第三边长，所以只有这么个想法，并没有实现。

。

如果思路不对，还请大佬赐教，如果思路对的话，麻烦大佬实现😂

试题F：消除游戏

时间限制: 3.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】

在一个字符串 S S S中，如果 S i = S i − 1 S_i = S_{i−1} Si=Si−1且 S i ∗ S i ₊ 1 S_i * S_{i₊1} Si∗Si₊1，则称 S i S_i Si和 S i ₊ 1 S_{i₊1} Si₊1为边缘字符。

如果 S i ∗ S i − 1 S_i * S_{i−1} Si∗Si−1且 S i = S i ₊ 1 S_i = S_{i₊1} Si=Si₊1，则 S i − 1 S_ {i−1} Si−1和 S i S_i Si也称为边缘字符。

其它的字符都不是边缘字符。

对于一个给定的串 S S S，一次 *** 作可以一次性删除该串中的所有边缘字符（ *** 作后可能产生新的边缘字符）。

请问经过 2 64 2^{64} 264次 *** 作后，字符串 S S S变成了怎样的字符串，如果结果为空则输出 EMPTY。

【输入格式】

输入一行包含一个字符串 S 。

【输出格式】

输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY。

【样例输入 1】

edda

【样例输出 1】

EMPTY

【样例输入 2】

sdfhhhhcvhhxcxnnnnshh

【样例输出 2】

【评测用例规模与约定】

对于 25 25% 25的评测用例， ∣ S ∣ ≤ 1 0 3 |S | ≤ 10^3 ∣S∣≤103，其中 ∣ S ∣ |S | ∣S∣表示 S S S的长度；对于 50 50% 50的评测用例， ∣ S ∣ ≤ 1 0 3 |S | ≤ 10^3 ∣S∣≤103；

对于 75 75% 75的评测用例， ∣ S ∣ ≤ 1 0 3 |S | ≤ 10^3 ∣S∣≤103；

对于所有评测用例， ∣ S ∣ ≤ 1 0 6 |S | ≤ 10^6 ∣S∣≤106， S S S中仅含小写字母。

【思路分析】

这个题没有好的思路，只能暴力模拟了😂

需要留意几个地方：

不能直接删除项目中边缘字符，如果直接删除会导致越界
也不能直接将待删除的边缘字符替换成其他字符，因为这样会导致判断出问题，比如xxv中xv待删除，将其替换为0，变为x00，则执行下一步的时候就会将x0作为边缘字符删掉x。
其实循环不了 2 64 2^{64} 264次，如果化到最简，则可以比较处理前和处理后的结果，如果相同，则已经是最简了，直接跳出循环即可

两个解决办法，一个是先判断逆向字符，比如xxv，再判断正向字符：xvv。

另一个是使用一个集合将待删除的下标保存，然后循环结束后统一删除。

【完整代码】

def remove_edge():
    global s
    rm = set()
    for i in range(1, len(s) - 1):
        if s[i] == s[i + 1] and s[i - 1] != s[i]:
            rm.add(i - 1)
            rm.add(i)
        if s[i] == s[i - 1] and s[i] != s[i + 1]:
            rm.add(i)
            rm.add(i + 1)
    for i in rm:
        s[i] = ''
    s = list(''.join(s))


s = list(input())
for i in range(2 ** 64):
    ls = s
    remove_edge()
    if ls == s:
        print(''.join(s))
        break
    if len(s) == 0:
        print('EMPTY')
        break
else:
    print(''.join(s))

试题G：全排列的价值

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

对于一个排列 A = ( a 1 , a 2 , . . . , a n ) A = (a_1, a_2,..., a_n) A=(a1,a2,...,an)，定义价值 c i c_i ci为 a 1 a_1 a1至 a i − 1 a_{i-1} ai−1中小于 a i a_i ai的数的个数，即 b i = ∣ { a j ∣ j < i , a j < a i } ∣ b_i = |\{a_j| j < i, a_j < a_i\}| bi=∣{aj∣j<i,aj<ai}∣。

定义
A A A的价值为 ∑ i = 1 n c i \sum^n_{i=1}c_i ∑i=1nci。

给定 n n n，求 1 1 1至 n n n的全排列中所有排列的价值之和。

【输入格式】

输入一行包含一个整数 n n n。

【输出格式】

输出一行包含一个整数表示答案，由于所有排列的价值之和可能很大，请输出这个数除以 998244353 998244353 998244353的余数。

【样例输入 1】

【样例输出 1】

【样例输入 2】

【样例输出 2】

593300958

【样例说明】

1 至 3 构成的所有排列的价值如下:

(1, 2, 3) : 0 + 1 + 2 = 3 ；
(1, 3, 2) : 0 + 1 + 1 = 2 ；
(2, 1, 3) : 0 + 0 + 2 = 2 ；
(2, 3, 1) : 0 + 1 + 0 = 1 ；
(3, 1, 2) : 0 + 0 + 1 = 1 ；
(3, 2, 1) : 0 + 0 + 0 = 0 ；

故总和为 3 + 2 + 2 + 1 + 1 = 9 3 + 2 + 2 + 1 + 1 = 9 3+2+2+1+1=9。

【评测用例规模与约定】

对于 40 % 40\% 40%的评测用例， n ≤ 20 n ≤ 20 n≤20；

对于 70 % 70\% 70%的评测用例， n ≤ 5000 n ≤ 5000 n≤5000；对于所有评测用例， 2 ≤ n ≤ 1 0 6 2 ≤ n ≤ 10^6 2≤n≤106。

【思路分析】

这道题比较有意思，暴力肯定不行。

首先，试想一下， 2 2 2和 1 1 1的价值，只有在 [ 1 , 2 ] [1, 2] [1,2]的情况下才有价值为1.

在(1, 2, 3)的组合里边，2在1前边有三种情况，分别是：

(1, 2, 3)
(1, 3, 2)
(3, 1, 2)

这三种的情况，也就是2产生的值为3*1，然后再考虑3的位置和价值，3是当前组合里边最大的数，当3置于最后边，可以产生的价值为：2*2，当3的价值置于中间，所产生的价值为1*2。

所以(1, 2, 3)全排列的值为： 3 ∗ 1 + 2 ∗ 2 + 1 ∗ 2 3*1+2*2+1*2 3∗1+2∗2+1∗2。

数据量太小，还看不出什么规律。

我们再做一下(1, 2, 3, 4)的排列。

首先(1, 2, 3)的全排列为9，然后有4个位置可以插入4，所以(1, 2, 3, 4)的全排列中，(1, 2, 3)产生的价值为： 9 ∗ 4 = 36 9*4=36 9∗4=36，当4置于末尾时，(1, 2, 3)
每一种排列方式都能给4带来3的价值，所以即当4置于末尾时即为 3 ∗ A 3 3 3*A_3^3 3∗A33，当4置于第3位，则(1, 2, 3)每一种排列，都能给4带来2的价值，即为 3 ∗ A 2 2 3*A_2^2 3∗A22。

然后是第二位…第一位…

由此可以推得，某一位数的全排列值，等于他本身乘以前一个数的全排列值，然后再加上 ∑ i = 1 n − 1 i A n − 1 n − 1 \sum_{i=1}^{n-1}iA_{n-1}^{n-1} ∑i=1n−1iAn−1n−1， A n n A_n^n Ann即 n ! n! n!，即可得公式

c n = n ∗ ( n − 1 ) + ∑ i = 1 n − 1 i ∗ ( n − 1 ) ! c_n=n*(n-1)+\sum_{i=1}^{n-1}i*(n-1)! cn=n∗(n−1)+i=1∑n−1i∗(n−1)!

∑ i = 1 n − 1 i ∗ ( n − 1 ) ! \sum_{i=1}^{n-1}i*(n-1)! ∑i=1n−1i∗(n−1)!可以进一步化简为 ( n − 1 ) ∗ ( 1 + n − 1 ) 2 ∗ ( n − 1 ) ! \frac{(n-1)*(1+n-1)}{2}*(n-1)! 2(n−1)∗(1+n−1)∗(n−1)!，即 ( n − 1 ) ∗ n 2 ∗ ( n − 1 ) ! \frac{(n-1)*n}{2}*(n-1)! 2(n−1)∗n∗(n−1)!

故可以得出递归函数

@functools.lru_cache(10 ** 6)
def get_value(n):
    m = n - 1
    jcc = jc(m) # jc()，自定义函数，求阶乘
    v = m * n // 2
    return (n * get_value(n - 1) + jcc * v) % 998244353

这个递归很好理解，但是实际跑的时候数据稍大就会栈溢出，所以得给他改成循环。
这里阶乘要用自定义函数加缓存，因为每一个数得价值，都会求一次阶乘，反复求的话自定义的函数加缓存在效率上相比于math.factorial()提升会非常明显，例如样例的2022，缓存求递归仅需要0.01s
，而用math.factorial()则需要0.1s
跑了一下， 5000 5000 5000没啥问题，能过 70 % 70\% 70%的样例，但是跑不了 1 0 6 10^6 106，估计把阶乘的求法再优化优化能跑通

【完整代码】

import functools
import math


@functools.lru_cache(10 ** 6)
def jc(n):
    if n <= 1:
        return 1
    return n * jc(n - 1)


n = int(input())
v = [0, 1]
for i in range(1, n + 1):
    m = i - 1
    jcc = jc(m)
    l = (m * i) // 2
    v[1] = ((v[0] * i + l * jcc) % 998244353)
    v[0] = v[1]
print(v[1])

试题H：技能升级

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

小蓝最近正在玩一款 RPG 游戏。

他的角色一共有 N 个可以加攻击力的技能。

其中第 i 个技能首次升级可以提升 A i A_i Ai点攻击力，以后每次升级增加的点数都会减少 B i B_i Bi。

⌈ A i ⌉ ⌈ Ai ⌉ ⌈Ai⌉(上取整)

次之后，再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。

请你计算小蓝最多可以提高多少点攻击力？

【输入格式】

输入第一行包含两个整数 N N N和 M M M。

以下 N N N行每行包含两个整数 A i A_i Ai和 B i B_i Bi。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

【样例输出】

【评测用例规模与约定】

对于 40 % 40\% 40%的评测用例， 1 ≤ N , M ≤ 1000 1 ≤ N, M ≤ 1000 1≤N,M≤1000；

对于 60 % 60\% 60%的评测用例， 1 ≤ N ≤ 1 0 4 , 1 ≤ M ≤ 1 0 7 1 ≤ N ≤ 10^4, 1 ≤ M ≤ 10^7 1≤N≤104,1≤M≤107；

对于所有评测用例， 1 ≤ N ≤ 1 0 5 ， 1 ≤ M ≤ 2 × 1 0 5 ， 1 ≤ A i , B i ≤ 1 0 5 1 ≤ N ≤ 10^5，1 ≤ M ≤ 2 × 10^5，1 ≤ Ai, Bi ≤ 10^5 1≤N≤105，1≤M≤2×105，1≤Ai,Bi≤105。

【思路分析】

这个第一想法就是直接列表，降序，加攻击，减去攻击加成，再降序…

简单的不像20分的题，，因为前一题推了将近1个小时，怕后边时间不够，所以尽管潜意识觉得有坑，但还是没有深究

【完整代码】

n, m = map(int, input().split())
add = []
ans = 0
for i in range(n):
    a, b = map(int, input().split())
    add.append([a, b])
while m > 0:
    add = sorted(add, key=lambda x: x[0], reverse=True)
    ans += add[0][0]
    add[0][0] -= add[0][1]
    m -= 1
print(ans)

试题I: 最长不下降子序列

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】

给定一个长度为 N 的整数序列： A ₁ , A ₂ , ⋅ ⋅ ⋅ , A N A₁, A₂, · · · , AN A₁,A₂,⋅⋅⋅,AN。

现在你有一次机会，将其中连续的 K K K

个数修改成任意一个相同值。

请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。

最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。

【输入格式】

输入第一行包含两个整数 N N N和 K K K。

第二行包含 N N N个整数 A ₁ , A ₂ , ⋅ ⋅ ⋅ , A N A₁, A₂, · · · , A_N A₁,A₂,⋅⋅⋅,AN。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

5 1
1 4 2 8 5

【样例输出】

【评测用例规模与约定】

对于 20% 的评测用例， 1 ≤ K ≤ N ≤ 100 1 ≤ K ≤ N ≤ 100 1≤K≤N≤100；对于 30% 的评测用例， 1 ≤ K ≤ N ≤ 1000 1 ≤ K ≤ N ≤ 1000 1≤K≤N≤1000；

对于 50% 的评测用例， 1 ≤ K ≤ N ≤ 10000 1 ≤ K ≤ N ≤ 10000 1≤K≤N≤10000；

对于所有评测用例， 1 ≤ K ≤ N ≤ 10 ⁵ ， 1 ≤ A i ≤ 10 ⁶ 1 ≤ K ≤ N ≤ 10⁵，1 ≤ Ai ≤ 10⁶ 1≤K≤N≤10⁵，1≤Ai≤10⁶。

【思路分析】

这个题，没想到好的思路，只有硬干。

。

根据题目描述一行一行写…两层没优化的循环，复杂度 O ( n 2 ) O(n^2) O(n2)，不指望能跑通了

【完整代码】

import copy


# 判断非递减
def isfdj(lst):
    return lst == sorted(lst)


n, k = map(int, input().split())
ls = list(map(int, input().split()))
l = []
for i in range(1, n - k):
    tmp = copy.deepcopy(ls)
    t = ls[i - 1]
    for j in range(i, i + k):
        tmp[j] = t
    ll = 0 # 当前子串长度
    low = 0
    high = 1
    while high < n:
        if isfdj(tmp[low:high]):
            ll += 1
        else:
            l.append(ll)
            ll = 0
            low = high
        high += 1
    l.append(ll)
print(max(l))

试题J: 最优清零方案

时间限制: 5.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】

给定一个长度为 N N N的数列 A ₁ , A ₂ , ⋅ ⋅ ⋅ , A N A₁, A₂, · · · , A_N A₁,A₂,⋅⋅⋅,AN。

现在小蓝想通过若干次 *** 作将这个数列中每个数字清零。

每次 *** 作小蓝可以选择以下两种之一：

选择一个大于 0 0 0的整数，将它减去 1 1 1；
选择连续 K K K个大于 0 0 0的整数，将它们各减去 1 1 1。

小蓝最少经过几次 *** 作可以将整个数列清零？

【输入格式】

输入第一行包含两个整数 N N N和 K K K。

第二行包含 N N N个整数 A ₁ , A ₂ , ⋅ ⋅ ⋅ , A N A₁, A₂, · · · , A_N A₁,A₂,⋅⋅⋅,AN。

【输出格式】

输出一个整数表示答案。

【样例输入】

4 2
1 2 3 4

【样例输出】

【评测用例规模与约定】

对于 20 % 20\% 20%的评测用例， 1 ≤ K ≤ N ≤ 10 1 ≤ K ≤ N ≤ 10 1≤K≤N≤10。

对于 40 % 40\% 40%的评测用例， 1 ≤ K ≤ N ≤ 100 1 ≤ K ≤ N ≤ 100 1≤K≤N≤100。

对于 50 % 50\% 50%的评测用例， 1 ≤ K ≤ N ≤ 1000 1 ≤ K ≤ N ≤ 1000 1≤K≤N≤1000。

对于 60 % 60\% 60%的评测用例， 1 ≤ K ≤ N ≤ 10000 1 ≤ K ≤ N ≤ 10000 1≤K≤N≤10000。

对于 70 % 70\% 70%的评测用例， 1 ≤ K ≤ N ≤ 100000 1 ≤ K ≤ N ≤ 100000 1≤K≤N≤100000。

对于所有评测用例， 1 ≤ K ≤ N ≤ 1000000 , 0 ≤ A i ≤ 1000000 1 ≤ K ≤ N ≤ 1000000, 0 ≤ A_i ≤ 1000000 1≤K≤N≤1000000,0≤Ai≤1000000。

【思路分析】

这个题就没啥好分析的了，甚至暴力模拟都没想好怎么模拟，直接用了贪心，从前往后挨个减一遍。

猜着应该要用动规，但没想出来怎么个规法。

分享下自己的残缺代码，也欢迎大佬赐教。

【完整代码】

n, k = map(int, input().split())
lst = list(map(int, input().split()))
red = lambda x: x - 1
i = 0
c = 0
while True:
    r = i + k
    if r <= n:
        if 0 not in lst[i:r]:
            lst[i: r] = map(red, lst[i:r])
            c += 1
        else:
            i = lst[i: r].index(0) + i + 1
    else:
        break
c += sum(lst)
print(c)

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/578071.html

第十三届蓝桥杯省赛Python 组

发表评论

评论列表（0条）

a	n mod a	a	n mod a	a	n mod a	a	n mod a
2	1	14	11	26	23	38	37
3	2	15	14	27	20	39	23
4	1	16	9	28	25	40	9
5	4	17	0	29	16	41	1
6	5	18	11	30	29	42	11
7	4	19	18	31	27	43	11
8	1	20	9	32	25	44	33
9	2	21	11	33	11	45	29
10	9	22	11	34	17	46	15
11	0	23	15	35	4	47	5
12	5	24	17	36	29	48	41
13	10	25	9	37	22	49	46

a	n mod a	a	n mod a	a	n mod a	a	n mod a
2	1	14	11	26	23	38	37
3	2	15	14	27	20	39	23
4	1	16	9	28	25	40	9
5	4	17	0	29	16	41	1
6	5	18	11	30	29	42	11
7	4	19	18	31	27	43	11
8	1	20	9	32	25	44	33
9	2	21	11	33	11	45	29
10	9	22	11	34	17	46	15
11	0	23	15	35	4	47	5
12	5	24	17	36	29	48	41
13	10	25	9	37	22	49	46

a	n mod a	a	n mod a	a	n mod a	a	n mod a
2	1	14	11	26	23	38	37
3	2	15	14	27	20	39	23
4	1	16	9	28	25	40	9
5	4	17	0	29	16	41	1
6	5	18	11	30	29	42	11
7	4	19	18	31	27	43	11
8	1	20	9	32	25	44	33
9	2	21	11	33	11	45	29
10	9	22	11	34	17	46	15
11	0	23	15	35	4	47	5
12	5	24	17	36	29	48	41
13	10	25	9	37	22	49	46