蓝桥杯【第13届国赛】Python B组 127.80分

每道题的分数都是在下面的链接测的，再按照蓝桥的分数 (可参考我的里的说明) 计算出这个分数。当初比赛的时候只有 32 分，拿了个国三，真的是菜死我了

测试链接：https://www.dotcpp.com/oj/train/1024/

A：斐波那契与 7  100🏆

【问题描述】

        斐波那契数列的递推公式为：，其中 。

        请问，斐波那契数列的第 1 至 202202011200 项 (含) 中，有多少项的个位是 7。

【解析及代码】

这道题的运算次数大约是 1e11，而 Python 每秒可以进行的运算次数大约是 8e7，暴力的话可能需要十几分钟

求解斐波那契数列，比较传统的方法是递归，但是递归很容易爆栈，所以建议 for 循环解决

找到循环一切都好办，答案：26960268160

x = 202202011200cycle = [1, 1]
for i in range(3, x):cycle.append(sum(cycle[-2:]) % 10)# 查找循环if cycle[-2:] == cycle[:2]: break# 除去末两位
cycle = cycle[:-2]
print(cycle)# x 刚好可被 60 整除
print(x % len(cycle))
# 26960268160
print(x // len(cycle) * cycle.count(7))

B：小蓝做实验  100🏆

【问题描述】

        小蓝很喜欢科研，他最近做了一个实验得到了一批实验数据，一共是两百万个正整数。如果按照预期，所有的实验数据 x 都应该满足 。但是做实验都会有一些误差，会导致出现一些预期外的数据，这种误差数据 y 的范围是 。由于小蓝做实验很可靠，所以他所有的实验数据中 99.99% 以上都是符合预期的。小蓝的所有实验数据都在 primes.txt 中，现在他想统计这两百万个正整数中有多少个是质数，你能告诉他吗?

【解析及代码】

罗里吧嗦一堆其实就是找出一个文件里面有多少个数是质数，因为数字不大，用试除法就可以解决

当给定数字 n 的时候，如果 n 是合数，那么 n 必然可被 内的某一整数整除，从而可以写出判质函数

使用 open 函数读取 txt 文件，对每一行的数字进行判断，并输出进度信息

答案：342693

import math
import timedef try_divide(n):''' 试除法'''if n <= 3: return n in (2, 3)for i in range(2, math.isqrt(n) + 1):if n % i == 0: return Falsereturn Truecnt, start = 0, time.time()
with open('primes.txt') as f:lines = list(f.readlines())for cur, i in enumerate(lines):# 除去换行符i = int(i.strip())cnt += try_divide(i)# 输出耗时、进度cost = time.time() - startprogress = (cur + 1) / len(lines) * 100print(f'\r{progress:.2f} %\t---\t{cost:.2f} s', end='')
# 342693
print('\n', cnt)

C：取模  100🏆

【问题描述】

        给定 n,m，问是否存在两个不同的数 x,y 使得 1 ≤ x < y ≤ m 且 n mod x = n mod y

【输入格式】

        输入包含多组独立的询问。

        第一行包含一个整数 T 表示询问的组数。

        接下来 T 行每行包含两个整数 n,m，用一个空格分隔，表示一组询问。

【输出格式】

        输出 T 行，每行依次对应一组询问的结果。如果存在，输出单词 Yes；如果不存在，输出单词 No

【样例】

输入	输出
3 1 2 5 2 999 99	No No Yes

【评测用例规模与约定】

20%
50%
100%

【解析及代码】

特殊情况：当  时，有  使得 

一般情况：其它情况下暴力枚举就行了

def judge(n, m):# 特殊情况: x = n + 1, y = n + 2 满足if n + 2 <= m: return 'Yes'# 一般情况: 暴力搜索 (以 x 作最外层循环会导致超时)for y in range(1, m + 1):res_y = n % yfor x in range(1, y):if res_y == n % x: return 'Yes'return 'No'for _ in range(int(input())):n, m = map(int, input().split())print(judge(n, m))

D：内存空间  100🏆

【问题描述】

        小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。为了简化问题，变量的类型只有以下三种:

        int：整型变量，一个 int 型变量占用 4 Byte 的内存空间。

        long：长整型变量，一个long型变量占用8 Byte 的内存空间。

        string：字符串变量，占用空间和字符串长度有关，设字符串长度为 L，则字符串占用 L Byte 的内存空间，如果字符串长度为 0 则占用 0 Byte 的内存空间。

        定义变量的语句只有两种形式，第一种形式为:

        type var1=value1,var2=value2…;

        定义了若干个 type 类型变量 var1、var2、…，并且用 value1、value2… 初始化，多个变量之间用 ',’ 分隔，语句以 ';’ 结尾，type可能是int、long 或string。例如 int a=1,b=5,c=6; 占用空间为12 Byte；long a=1,b=5;占用空间为16 Byte；String s1="",s2="hello",s3="world";占用空间为10 Byte

        第二种形式为：

        type[] arr1=new type[size1],arr2=new type[size2]…；

        定义了若干 type 类型的一维数组变量 arr1、arr2…，且数组的大小为 size1、size2…，多个变量之间用 ',' 进行分隔，语句以 ';' 结尾，type 只可能是 int 或 long。例如int[] a1=new int[10];占用的内存空间为 40 Byte；long[] a1=new long[10],a2=new long[10];占用的内存空间为 160 Byte。

        已知小蓝有 T 条定义变量的语句，请你帮他统计下一共占用了多少内存空间。结果的表示方式为：aGBbMBcKBdB，其中 a、b、c、d 为统计的结果，GB、MB、KB、B为单位。优先用大的单位来表示，1GB=1024MB，1MB=1024KB，1KB=1024B，其中 B 表示 Byte。如果 a、b、c、d 中的某几个数字为 0，那么不必输出这几个数字及其单位。题目保证一行中只有一句定义变量的语句，且每条语句都满足题干中描述的定义格式，所有的变量名都是合法的且均不重复。题目中的数据很规整，和上述给出的例子类似，除了类型后面有一个空格，以及定义数组时 new 后面的一个空格之外，不会出现多余的空格。

【输入格式】

        输入的第一行包含一个整数 T，表示有 T 句变量定义的语句。接下来 T 行，每行包含一句变量定义语句

【输出格式】

        输出一行包含一个字符串，表示所有语句所占用空间的总大小

【样例】

输入	输出
1 long[] nums=new long[131072];	1MB
4 int a=0,b=0; long x=0,y=0; String s1="hello",s2="world"; long[] arr1=new long[100000],arr2=new long[100000];	1MB538KB546B

【评测用例规模与约定】

        对于所有评测用例，1 ≤ T ≤ 10，每条变量定义语句的长度不会超过 1000。所有的变量名称长度不会超过 10，且都由小写字母和数字组成。对于整型变量，初始化的值均是在其表示范围内的十进制整数，初始化的值不会是变量。对于 String 类型的变量，初始化的内容长度不会超过 50，且内容仅包含小写字母和数字，初始化的值不会是变量。对于数组类型变量，数组的长度为一个整数，范围为：[0, 2^30]，数组的长度不会是变量。T 条语句定义的变量所占的内存空间总大小不会超过 1 GB，且大于 0 B。

【解析及代码】

思路就是暴力，使用 re 正则表达式进行字符串匹配，算得内存空间总数：

• 对语句按照空格划分成若干段，第一段即为该语句声明的变量类型 type，如果 type 的结尾是 []，则该语句声明的是数组
• 非数组变量：除去变量类型 type 那一段之外就只剩一段，对该段按照逗号分成若干段，段数即为变量个数；如果是 String 类型的话，就使用正则表达式捕获字符串，统计长度以计算内存
• 数组变量：除去变量类型 type 那一段之外还有若干段，使用正则表达式匹配出现的“[size]”，从而可以计算内存

最后使用字典记录每个单位对应的数值，将总内存空间换算后写入，使用 for 循环输出

import rebyte, space = 0, {'int': 4, 'long': 8}
for _ in range(int(input())):# 如果不考虑首尾的空格可能过不了 C 语言网的测试 !sentence = input().strip().rstrip(';').split()type_ = sentence.pop(0)# 如果是数组if type_[-2:] == '[]':type_ = type_[:-2]# 取出语句块进行统计for token in sentence:find = re.search(r'\[[0-9]+]', token)if find:find = int(find.group()[1:-1])byte += space[type_] * find# 如果是普通变量else:sentence = sentence[0].split(',')# 字符类型需要看字符串的长度if type_ == 'String':for token in sentence:find = re.search(r'=.*', token)if find:find = find.group()# 除去双引号、等号# 长度即为 bytesbyte += len(find[2: -1])else:# sentence 多长就有多少个变量byte += len(sentence) * space[type_]ret = {u: 0 for u in ('GB', 'MB', 'KB', 'B')}
# 计算 GB, MB, KB
for i, u in enumerate(['GB', 'MB', 'KB']):div = (2 ** 10) ** (3 - i)ret[u] = byte // divbyte -= div * ret[u]
# 记录 B
ret['B'] = byteresult = ''
for u, v in ret.items():if v: result += f'{v}{u}'
print(result)

E：近似GCD  100🏆

【问题描述】

        小蓝有一个长度为 n 的数组 A = (a1, a2, · · · , an)，数组的子数组被定义为从原数组中选出连续的一个或多个元素组成的数组。数组的最大公约数指的是数组中所有元素的最大公约数。如果最多更改数组中的一个元素之后，数组的最大公约数为 g，那么称 g 为这个数组的近似 GCD。一个数组的近似 GCD 可能有多种取值。具体的，判断 g 是否为一个子数组的近似 GCD 如下：

        1. 如果这个子数组的最大公约数就是 g，那么说明 g 是其近似 GCD。

        2. 在修改这个子数组中的一个元素之后（可以改成想要的任何值），子数组的最大公约数为 g，那么说明 g 是这个子数组的近似 GCD。

        小蓝想知道，数组 A 有多少个长度大于等于 2 的子数组满足近似 GCD 的值为 g

【输入格式】

        输入的第一行包含两个整数 n, g，用一个空格分隔，分别表示数组 A 的长度和 g 的值。

        第二行包含 n 个整数 a1, a2, · · · , an，相邻两个整数之间用一个空格分隔。

【输出格式】

        输出一行包含一个整数表示数组 A 有多少个长度大于等于 2 的子数组的近似 GCD 的值为 g

【样例】

输入	输出	说明
5 3 1 3 6 4 10	5	满足条件的子数组有 5 个： [1, 3]：将 1 修改为 3 后，满足条件。 [1, 3, 6]：将 1 修改为 3 后，满足条件。 [3, 6]：满足条件。 [3, 6, 4]：将 4 修改为 3 后，满足条件。 [6, 4]：将 4 修改为 3 后，满足条件。

【评测用例规模与约定】

20%
40%
100%

【解析及代码】

满足 gcd 的子数组有以下两种：

• 全为 g 的倍数：将其中任意一个数修改为 g，则 gcd = g
• 只有 1 个数不是 g 的倍数：将该数修改为 g 即可

也就是说，满足 gcd 的子数组中至多只含有 1 个不能被 g 整除的数

将数组中不能被 g 整除的数的 索引 记为 idx，以 n = 7, idx = [0, 3, 4] 为例：

• 修改数组索引 0 处的数为 g，以 0 为左边界的子数组有 (0, 1), (0, 2)
• 修改数组索引 3 处的数为 g，以 1 为左边界的子数组有 (1, 2), (1, 3)，以 2 为左边界的子数组有 (2, 3)，以 3 为左边界则没有子数组
• 修改数组索引 4 处的数为 g，以 4 为左边界的子数组有 (4, 5), (4, 6)
• 修改数组索引 7 (也就是超出索引) 处的数为 g，以 5 为左边界的子数组有 (5, 6)

为这个过程编写相关的变量，完善求解步骤即可

n, g = map(int, input().split())
array = list(map(int, input().split()))# 查找不能被 g 整除的值
idx = [i for i, v in enumerate(array) if v % g] + [n] * 2
l, cnt = 0, 0
for i in range(len(idx) - 1):x, r = idx[i: i + 2]lb = min(r - 2, x)# 等差数列求和: 左闭边界为 [l, lb], 右开边界为 r 且长度为 >= 2 的区间个数cnt += (2 * (r - 1) - (l + lb)) * (lb - l + 1) // 2# 更新左闭边界 的左边界l = x + 1
print(cnt)

F: 交通信号  55🏆

【问题描述】

        LQ 市的交通系统可以看成由 n 个结点和 m 条有向边组成的有向图。在每条边上有一个信号灯，会不断按绿黄红黄绿黄红黄... 的顺序循环 (初始时刚好变到绿灯)。当信号灯为绿灯时允许正向通行，红灯时允许反向通行，黄灯时不允许通行。每条边上的信号灯的三种颜色的持续时长都互相独立，其中黄灯的持续时长等同于走完路径的耗时。当走到一条边上时，需要观察边上的信号灯，
如果允许通行则可以通过此边，在通行过程中不再受信号灯的影响；否则需要等待，直到允许通行。

        请问从结点 s 到结点 t 所需的最短时间是多少，如果 s 无法到达 t 则输出 −1

【输入格式】

        输入的第一行包含四个整数 n, m, s, t，相邻两个整数之间用一个空格分隔。

        接下来 m 行，每行包含五个整数 ui, vi, gi,ri, di ，相邻两个整数之间用一个空格分隔，分别表示一条边的起点，终点，绿灯、红灯的持续时长和距离（黄灯的持续时长）。

【输出格式】

        输出一行包含一个整数表示从结点 s 到达 t 所需的最短时间

【样例】

输入	输出
4 4 1 4 1 2 1 2 6 4 2 1 1 5 1 3 1 1 1 3 4 1 99 1	11

【评测用例规模与约定】

40%
70%
100%

【解析及代码】

参考了这位大佬的题解：https://blog.csdn.net/m0_64675532/article/details/129867716

为每一条双向边编写一个类 Edge，用于计算正向通行、反向通行的所需时间 (等待时间 + 距离)

然后使用 Dijkstra 算法求解最短时间

import heapq
import mathclass Edge:def __init__(self, green_t, red_t, dist):self.g, self.r, self.d = green_t, red_t, dist# 一个循环的时间: 绿 -> 黄 -> 红 -> 黄self.to_red = green_t + distself.cycle_t = self.to_red + red_t + distdef forward(self, t):# 出发点为绿灯所在点t %= self.cycle_treturn self.d + (0 if t < self.g else self.cycle_t - t)def backward(self, t):# 出发点为红灯所在点t = (t - self.to_red) % self.cycle_treturn self.d + (0 if t < self.r else self.cycle_t - t)n, m, source, target = map(int, input().split())
# 邻接表
adj = [[] for _ in range(n + 1)]
for _ in range(m):i, j, *_info = tuple(map(int, input().split()))# 初始化无向边, 并提供耗时的计算方法e = Edge(*_info)adj[i].append((j, e.forward))adj[j].append((i, e.backward))def dijkstra(source, adj):''' 单源最短路径 (不带负权)source: 源点adj: 图的邻接表'''n = len(adj)# 记录单源最短路, 未访问标记info = [[float('inf'), True] for _ in range(n)]info[source][0] = 0# 记录未完成搜索的点 (优先队列)undone = [(0, source)]while undone:# 找到离源点最近的点作为中间点 mm = heapq.heappop(undone)[1]if m == target: breakif info[m][1]:info[m][1] = False# 更新单源最短路for i, f in adj[m]:if info[i][1]:tmp = info[m][0] + f(info[m][0])if info[i][0] > tmp:info[i][0] = tmpheapq.heappush(undone, (info[i][0], i))return inforet = dijkstra(source, adj)[target][0]
print(ret if math.isfinite(ret) else -1)

G：点亮  100🏆

【问题描述】

        小蓝最近迷上了一款名为《点亮》的谜题游戏，游戏在一个 n × n 的格子棋盘上进行，棋盘由黑色和白色两种格子组成，玩家在白色格子上放置灯泡，确保任意两个灯泡不会相互照射，直到整个棋盘上的白色格子都被点亮（每个谜题均为唯一解）。灯泡只会往水平和垂直方向发射光线，照亮整行和整列，除非它的光线被黑色格子挡住。黑色格子上可能有从 0 到 4 的整数数字，表示与其上下左右四个相邻的白色格子共有几个灯泡；也可能没有数字，这表示可以在上下左右四个相邻的白色格子处任意选择几个位置放置灯泡。游戏的目标是选择合适的位置放置灯泡，使得整个棋盘上的白色格子都被照亮。

        例如，有一个黑色格子处数字为 4，这表示它周围必须有 4 个灯泡，需要在他的上、下、左、右处分别放置一个灯泡；如果一个黑色格子处数字为 2，它的上下左右相邻格子只有 3 个格子是白色格子，那么需要从这三个白色格子中选择两个来放置灯泡；如果一个黑色格子没有标记数字，且其上下左右相邻格子全是白色格子，那么可以从这 4 个白色格子中任选出 0 至 4 个来放置灯泡。

        题目保证给出的数据是合法的，黑色格子周围一定有位置可以放下对应数量的灯泡。且保证所有谜题的解都是唯一的。

        现在，给出一个初始的棋盘局面，请在上面放置好灯泡，使得整个棋盘上的白色格子被点亮。

【输入格式】

        输入的第一行包含一个整数 n，表示棋盘的大小。

        接下来 n 行，每行包含 n 个字符，表示给定的棋盘。字符 . 表示对应的格子为白色，数字字符 0、1、2、3、4 表示一个有数字标识的黑色格子，大写字母 X 表示没有数字标识的黑色格子。

【输出格式】

        输出 n 行，每行包含 n 个字符，表示答案。大写字母 O 表示对应的格子包含灯泡，其它字符的意义与输入相同

【样例】

输入	输出	说明
5 ..... .2.4. ..4.. .2.X. .....	...O. .2O4O .O4O. .2OX. O....

【评测用例规模与约定】

100%	2 ≤ n ≤ 5 ，且棋盘上至少有 15% 的格子是黑色格子

【解析及代码】

从这道题的数据规模可以看出，完全是暴力 DFS 可以解决的 —— 但是 DFS 不做好剪枝还是很容易超时

在自定义类 Board 的初始化方法中，定义一种便于我们程序处理的格式，以表示棋盘：

• 白格 bool：False (.), True (O)
• 黑格 int：-1 (X), 0, 1, 2, 3, 4

为了判断搜索是否结束，以及棋盘上可以放置的位置，需要使用 light 变量记录被点亮的位置 (黑格可以看作被点亮)

黑格规定了周围应有的灯泡数，其影响到了状态合法性的判断、最优解的判断，所以定义一个 neighbor 方法以查找某个点附近的四个点

is_black 用于判断某个位置是否为黑格

is_complete 用于判断是否为最优解，即所有黑格附近的灯泡数达到指定值、所有位置都被点亮 (light 全为 True)

place 则是在某个点放置灯泡，同时根据黑格检查该位置是否能放置灯泡 —— 如果可以的话则进行水平方向、竖直方向的点亮 (修改 light 矩阵)

solve 为主函数 (递归)，其为每个棋盘选择未被点亮的白格以放置灯泡 (调用 place 函数)，如果放置的位置是合法的，则进行递归求解

import copyn = int(input())
map_ = [list(input()) for _ in range(n)]class Board(list):def __init__(self, map_):# 白格 bool: False (.), True (O)# 黑格 int : -1 (X), 0, 1, 2, 3, 4super().__init__([eval(','.join(s).replace('X', '-1').replace('.', 'False').join('[]')) for s in map_])self.light = [[self[i][j] is not False for j in range(n)] for i in range(n)]def neighbor(self, i, j):return [x for x, f in zip(((i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)),(i >= 1, j >= 1, i + 1 < n, j + 1 < n)) if f]def is_black(self, i, j):return not isinstance(self[i][j], bool)def is_complete(self):for i in range(n):for j in range(n):m = self[i][j]# 如果是黑格, 而且有限制if self.is_black(i, j) and m >= 0:nl = sum(self[x][y] is True for x, y in self.neighbor(i, j))if nl < m: return Falsereturn all(sum(self.light, []))def place(self, i, j):self[i][j] = self.light[i][j] = True# 校对该位置是否合法for a, b in self.neighbor(i, j):m = self[a][b]# 如果是黑格, 而且有限制if self.is_black(a, b) and m >= 0:nl = sum(self[x][y] is True for x, y in self.neighbor(a, b))if nl > m: return False# 竖直方向点亮for iterable in (range(i - 1, -1, -1), range(i + 1, n)):for a in iterable:if self.is_black(a, j): breakself.light[a][j] = True# 水平方向点亮for iterable in (range(j - 1, -1, -1), range(j + 1, n)):for a in iterable:if self.is_black(i, a): breakself.light[i][a] = Truereturn Truedef solve(self, index=0):for x in range(index, n ** 2):i, j = x // n, x % n# 白格, 且未被点亮if self[i][j] is False and not self.light[i][j]:other = copy.deepcopy(self)# 如果新的放置位置是合法的, 递归求解if other.place(i, j):ret = other if other.is_complete() else other.solve(x + 1)if ret: return retret = Board(map_).solve()
# 获取灯泡位置, 修改后输出
for i in range(n):for j in range(n):if ret[i][j] is True: map_[i][j] = 'O'for s in map_: print(''.join(s))

H：打折  69🏆

【问题描述】

        小蓝打算采购 n 种物品，每种物品各需要 1 个。

        小蓝所住的位置附近一共有 m 个店铺，每个店铺都出售着各种各样的物品。

        第 i 家店铺会在第 天至第 天打折，折扣率为 ，对于原件为 b 的物品，折后价格为 。其它时间需按原价购买。

        小蓝很忙，他只能选择一天的时间去采购这些物品。请问，他最少需要花多少钱才能买到需要的所有物品。

        题目保证小蓝一定能买到需要的所有物品。

【输入格式】

        输入的第一行包含两个整数 n, m，用一个空格分隔，分别表示物品的个数和店铺的个数。

        接下来依次包含每个店铺的描述。每个店铺由若干行组成，其中第一行包含四个整数 ，相邻两个整数之间用一个空格分隔，分别表示商店优惠的起始和结束时间、折扣率以及商店内的商品总数。之后接 行，每行包含两个整数 ，用一个空格分隔，分别表示该商店的第 j 个商品的类型和价格。商品的类型由 1 至 n 编号。

【输出格式】

        输出一行包含一个整数表示小蓝需要花费的最少的钱数

【样例】

输入	输出
2 2 1 2 89 1 1 97 3 4 77 1 2 15	101

【评测用例规模与约定】

40%
70%
100%

【解析及代码】

把总花费划分为 原价 + 省下的钱 来算

为每个商品定义一个类 Obj，price 表示其最低的原价，disc 记录折扣的起始时间和价格 (这些信息在读取输入的时候记录)

在商品的所有价钱信息录入完毕后，调用类的 process 函数将 disc 的信息进行转换：

• 如果给定 disc = [(2, 7, 100), (5, 9, 90)]，那么可以用 disc = [100, 90, 90] 分别表示 [2, 5), [5, 7), [7, 9) 的时间段内的折扣价
• 额外定义 range = [2, 5, 7, 9] 以辅助折扣价的查询 (定义于 __getitem__ 方法中)
• 合并区间 (比如上面的 [5, 7) 和 [7, 9) 的合并) 的话没有必要，因为使用了 bisect 库提供的二分法查找所以速度极快，而合并操作反而可能增加过多的比较时间

此时 Obj 类里的所有价格信息都是最优的，然后就开始枚举时间 (所有 Obj 类的 range 便可以覆盖价格发生改变的时间点)，计算每一天可以省下的钱

import bisectclass Obj:def __init__(self):# 原价, 折扣信息self.price, self.disc = float('inf'), []def add(self, s, e, d, p):self.price = min(self.price, p)# 打折后的价格self.disc.append((s, e + 1, d * p // 100))def process(self):# 根据 disc 的信息划分区间self.range = sorted(set(sum((i[:2] for i in self.disc), tuple())))# 每段时间所能省下的钱tmp = [0] * (len(self.range) - 1)for s, e, p in self.disc:s = bisect.bisect_left(self.range, s)e = bisect.bisect_left(self.range, e)# 折扣价 -> 省下的钱p = self.price - pfor i in (range(s, e) if p > 0 else []):tmp[i] = max(tmp[i], p)self.disc = tmpdef __getitem__(self, item):i = bisect.bisect(self.range, item)return self.disc[i - 1] if 1 <= i < len(self.range) else 0n, m = map(int, input().split())
# 初始化购物车
objects = [Obj() for _ in range(n)]
for _ in range(m):s, e, d, has = map(int, input().split())# 添加商品信息for _ in range(has):i, p = map(int, input().split())objects[i - 1].add(s, e, d, p)
# 数据预处理
for obj in objects: obj.process()# 不考虑折扣所需的钱
total = sum(obj.price for obj in objects)
# 能省下的最多钱数
save = 0
for i in set(sum((obj.range for obj in objects), [])):save = max(save, sum(obj[i] for obj in objects))
print(total - save)

I：owo  67🏆

【问题描述】

        小蓝很喜欢 owo ，他现在有一些字符串，他想将这些字符串拼接起来，使得最终得到的字符串中出现尽可能多的 owo 。

        在计算数量时，允许字符重叠，即 owowo 计算为 2 个，owowowo 计算为 3 个。

        请算出最优情况下得到的字符串中有多少个 owo。

【输入格式】

        输入的第一行包含一个整数 n ，表示小蓝拥有的字符串的数量。

        接下来 n 行，每行包含一个由小写英文字母组成的字符串 。

【输出格式】

        输出 n 行，每行包含一个整数，表示前 i 个字符串在最优拼接方案中可以得到的 owo 的数量

【样例】

输入	输出
3 owo w ow	1 1 2

【评测用例规模与约定】

10%	n ≤ 10
40%	n ≤ 300
60%	n ≤ 5000
100%

【解析及代码】

没拿满分是因为部分答案错误，感觉还有边界条件没推到，点到为止了

在进行字符串的拼接时，只有以下几种特殊形式的字符串有可能增加新的 owo：wo 开头、o 开头、o 结尾、ow 结尾、单个 w

先不考虑单个 w，我们使用二元组 (i, j) 表示字符串的特殊形式：

• i = 1 表 wo 开头，i = 2 表 o 开头
• j = 1 表 o 结尾，j = 2 表 ow 结尾

(0, 0) 则表示这个字符串不可能增加新的 owo，统计完该字符串中的 owo 之后可以直接丢掉

相反的话，对于 "owoto"(2, 1) 我们可以找到 "wowot"(1, 0) 与之拼接，那么拼接完成后的字符串的标志为 (2, 0)，即 (2, 1) + (1, 0) = (2, 0)

因为每次拼接只会产生一个 owo，所以在每次拿到新的字符串时，我们无需存储这个字符串，而只需要直接统计其中的 owo 的个数，并存储其标记 (i, j)

所以得到最优解只需要存储：(i, j) 的出现次数，单个 w 的个数，总的 owo 的个数

最优解由三部分组成：

• 每个字符串的 owo 的个数总和
• 标志 (i, j) 之间的拼接所产生的 owo
• 单个 w 与 (2, j)、(i, 1) 拼接所产生的 owo

我为此编写了一个 Container 的类

在 append 方法中，首先使用 re 库将 1 个 o 扩充成 2 个 o，然后使用字符串的 count 方法得到第一部分

然后根据这个字符串的标志 (i, j) 进行拼接，得到第二部分

在 query 方法中，则首先将单个 w 与 (2, 1) 交替连接，然后将剩余的 w 与 (2, j)、(i, 1) 拼接得到第三部分

import itertools as it
import reclass Container:def __init__(self):# owo 的基础计数self.cnt = 0# 单个 w 的子字符串数, 以及其它字符串缓存self.w_only = 0self.cache = {c: 0 for c in set(it.permutations([0, 1, 2] * 2, 2))}def append(self, s: str):# 获取该字符串的特殊标志code = (s.startswith('wo') + s.startswith('o') * 2,s.endswith('o') + s.endswith('ow') * 2)s = re.sub(r'o+', 'oo', s)# 计算该字符串中的 owoself.cnt += s.count('owo')if s == 'w':self.w_only += 1else:# 如果 开头 是特殊形式if code[0]:for i in range(3):# 找到相应的 结尾 code[0]tar = (i, code[0])if self.cache[tar]:self.cache[tar] -= 1# tar + code = (i, code[1])code = (i, code[1])self.cnt += 1break# 如果 结尾 是特殊形式if code[1]:for i in range(3):# 找到相应的 开头 code[1]tar = (code[1], i)if self.cache[tar]:self.cache[tar] -= 1# code + tar = (code[0], i)code = (code[0], i)self.cnt += 1break# 原字符串 / 新拼接的字符串 添加进缓存if any(code): self.cache[code] += 1def query(self):w, cnt = self.w_only, 0# 利用单个 w, 得到本次查询结果ostart = sum(self.cache[(2, i)] for i in (0, 2))oend = sum(self.cache[(i, 1)] for i in (0, 1))omax, omin = max(ostart, oend), min(ostart, oend)# 开头结尾都有 0oboth = self.cache[(2, 1)]if oboth > 1:# 与单个 w 交替连接cnt = min(w, oboth - 1)w, oboth = w - cnt, oboth - cntomax, omin = omax + 1, omin + 1# oboth = 1 / w = 0if omin != omax: omin += obothcnt += min(w, omin)return self.cnt + cntctr = Container()
for _ in range(int(input())):ctr.append(input())print(ctr.query())

J：替换字符  96🏆

【问题描述】

        给定一个仅含小写英文字母的字符串 s，每次操作选择一个区间 将 s 的该区间中的所有字母 全部替换成字母 ，问所有操作做完后，得到的字符串是什么。

【输入格式】

        输入的第一行包含一个字符串 s 。

        第二行包含一个整数 m 。

        接下来 m 行，每行包含 4 个参数 ，相邻两个参数之间用一个空格分隔，其中 为整数， 为小写字母。

【输出格式】

        输出一行包含一个字符串表示答案

【样例】

输入	输出
abcaaea 4 1 7 c e 3 3 e b 3 6 b e 1 4 a c	cbecaea

【评测用例规模与约定】

40%
100%

【解析及代码】

这个题这么简单放在压轴区我就很不理解 —— 还 25 分，我都没有给这个题预留时间，看到的时候已经来不及做了

因为字符串是没办法原地修改的，所以使用切片表达式切成三段，对中间段进行字符替换，再进行拼接操作

s = input()
for _ in range(int(input())):l, r, old, new = input().split()l, r = map(lambda i: int(i) - 1, (l, r))l_part, mid_part, r_part = s[:l], s[l: r + 1], s[r + 1:]s = l_part + mid_part.replace(old, new) + r_part
print(s)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！