考试好难......先把会的题写一下，不会的有缘再写
A：斐波那契与7
【问题描述】
斐波那契数列的递推公式为：Fn= Fn-1＋ Fn-2，其中F1= F2= 1。
请问，斐波那契数列的第 1 至 202202011200项(含)中，有多少项的个位是 7。
【解析及代码】
找到循环一切都好办，答案：26960268160
num = 202202011200
f1 = f2 = 1
# 个位列表
cycle = [1, 1]
for i in range(3, num):
# 斐波那契数列递进
f1, f2 = f2, f1 + f2
# 求出个位
f2 %= 10
cycle.append(f2)
# 查找循环
if cycle[-2:] == cycle[:2]: break
# 除去末两位
cycle = cycle[:-2]
print(cycle)
# 循环的长度
cycle_len = len(cycle)
count_7 = cycle.count(7)
# num 刚好可被 60 整除
print(num % cycle_len)
result = num // cycle_len * count_7
# 26960268160
print(result)
B：小蓝做实验
【问题描述】
小蓝很喜欢科研，他最近做了一个实验得到了一批实验数据，一共是两百万个正整数。如果按照预期，所有的实验数据 x 都应该满足 。但是做实验都会有一些误差，会导致出现一些预期外的数据，这种误差数据 y 的范围是 。由于小蓝做实验很可靠，所以他所有的实验数据中 99.99% 以上都是符合预期的。小蓝的所有实验数据都在 primes.txt 中，现在他想统计这两百万个正整数中有多少个是质数，你能告诉他吗?
【解析及代码】
罗里吧嗦一堆其实就是找出一个文件里面有多少个数是质数，因为数字不大，用试除法就可以解决
答案：342693
from math import isqrt
def try_divide(n):
''' 试除法'''
if n <= 3: return n in [2, 3]
bound = isqrt(n)
for i in range(2, bound + 1):
if n % i == 0: return False
return True
cnt = 0
with open('primes.txt') as f:
lines = list(f.readlines())
for cur, i in enumerate(lines):
# 除去换行符
i = int(i.strip())
if try_divide(i): cnt += 1
# 输出进度
print(f'r{(cur + 1) / len(lines) * 100:.2f} %', end='')
print()
# 342693
print(cnt)
C：取模
【问题描述】
给定 n,m，问是否存在两个不同的数 x,y 使得 1 ≤ x < y ≤ m 且 n mod x = n mod y
【输入格式】
输入包含多组独立的询问。
第一行包含一个整数 T 表示询问的组数。
接下来 T 行每行包含两个整数 n,m，用一个空格分隔，表示一组询问。
【输出格式】
输出 T 行，每行依次对应一组询问的结果。如果存在，输出单词 Yes；如果不存在，输出单词 No
【样例】
| 输入 | 输出 |
| 3 1 2 | No No Yes |
【评测用例规模与约定】
| 20% | |
| 50% | |
| 100% |
【解析及代码】
D：内存空间【问题描述】
小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。为了简化问题，变量的类型只有以下三种:
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 正则表达式进行字符串匹配，算得内存空间总数
import re
space = {'int': 4, 'long': 8}
byte = 0
for _ in range(int(input())):
sentence = input().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()
# 除去双引号、等号
# 长度即为 bytes
byte += len(find[2: -1])
else:
# sentence 多长就有多少个变量
byte += len(sentence) * space[type_]
然后单位换算之后输出
BASE = 2 ** 10
result = {unit: 0 for unit in ('GB', 'MB', 'KB', 'B')}
# 计算 GB
result['GB'] = byte // BASE ** 3
byte -= BASE ** 3 * result['GB']
# 计算 MB
result['MB'] = byte // BASE ** 2
byte -= BASE ** 2 * result['MB']
# 计算 KB
result['KB'] = byte // BASE
byte -= BASE * result['KB']
# 记录 B
result['B'] = byte
final = ''
for unit in result:
value = result[unit]
if value:
final += f'{value}{unit}'
print(final)
E：近似GCD
【问题描述】
小蓝有一个长度为 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% |
【解析及代码】
如果某个区间中的每个数都是 g 的倍数，那么随意修改其中一个为 g，则近似公约数为 g
如果某个区间中出现了不可被 g 整除的数，则直接替换成 g
from math import gcd
length, g = map(int, input().split())
array = list(map(int, input().split()))
cnt = 0
# 枚举左边界
for left in range(length):
# 当前的最大公约数
last_gcd = array[left]
if last_gcd % g == 0:
is_change = False
else:
last_gcd = g
is_change = True
# 枚举右边界
for right in range(left + 1, length):
cur_gcd = gcd(last_gcd, array[right])
# 如果当前 gcd 可被 g 整除, 随便修改一个数为 g 便可以
if cur_gcd % g == 0:
cnt += 1
elif not is_change:
# 只修改当前位置上的数为 g
cur_gcd = gcd(last_gcd, g)
is_change = True
if cur_gcd == g:
cnt += 1
else:
break
last_gcd = cur_gcd
print(cnt)
F: 交通信号
【问题描述】
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% |
【解析及代码】
G：点亮【问题描述】
小蓝最近迷上了一款名为《点亮》的谜题游戏，游戏在一个 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% 的格子是黑色格子 |
【解析及代码】
H：打折【问题描述】
小蓝打算采购 n 种物品，每种物品各需要 1 个。
小蓝所住的位置附近一共有 m 个店铺，每个店铺都出售着各种各样的物品。
第 i 家店铺会在第 si 天至第 ti 天打折，折扣率为 pi，对于原件为 b 的物品，折后价格为 。其它时间需按原价购买。
小蓝很忙，他只能选择一天的时间去采购这些物品。请问，他最少需要花多少钱才能买到需要的所有物品。
题目保证小蓝一定能买到需要的所有物品。
【输入格式】
输入的第一行包含两个整数 n, m，用一个空格分隔，分别表示物品的个数和店铺的个数。
接下来依次包含每个店铺的描述。每个店铺由若干行组成，其中第一行包含四个整数 si, ti, pi, ci，相邻两个整数之间用一个空格分隔，分别表示商店优惠的起始和结束时间、折扣率以及商店内的商品总数。之后接 ci 行，每行包含两个整数 aj, bj ，用一个空格分隔，分别表示该商店的第 j 个商品的类型和价格。商品的类型由 1 至 n 编号。
【输出格式】
输出一行包含一个整数表示小蓝需要花费的最少的钱数
【样例】
| 输入 | 输出 |
| 2 2 1 97 | 101 |
【评测用例规模与约定】
| 40% | |
| 70% | |
| 100% |
【解析及代码】
I：owo【问题描述】
小蓝很喜欢 owo ，他现在有一些字符串，他想将这些字符串拼接起来，使得最终得到的字符串中出现尽可能多的 owo 。
在计算数量时，允许字符重叠，即 owowo 计算为 2 个，owowowo 计算为 3 个。
请算出最优情况下得到的字符串中有多少个 owo。
【输入格式】
输入的第一行包含一个整数 n ，表示小蓝拥有的字符串的数量。
接下来 n 行，每行包含一个由小写英文字母组成的字符串 si 。
【输出格式】
输出 n 行，每行包含一个整数，表示前 i 个字符串在最优拼接方案中可以得到的 owo 的数量
【样例】
| 输入 | 输出 |
| 3 owo w ow | 1 1 2 |
【评测用例规模与约定】
| 10% | n ≤ 10 |
| 40% | n ≤ 300 |
| 60% | n ≤ 5000 |
| 100% |
【解析及代码】
J：替换字符【问题描述】
给定一个仅含小写英文字母的字符串 s，每次操作选择一个区间 [li,ri] 将 s 的该区间中的所有字母 xi 全部替换成字母 yi，问所有操作做完后，得到的字符串是什么。
【输入格式】
输入的第一行包含一个字符串 s 。
第二行包含一个整数 m 。
接下来 m 行，每行包含 4 个参数 li,ri, xi, yi，相邻两个参数之间用一个空格分隔，其中 li,ri 为整数，xi, yi 为小写字母。
【输出格式】
输出一行包含一个字符串表示答案
【样例】
| 输入 | 输出 |
| abcaaea 4 1 7 c e 3 3 e b 3 6 b e 1 4 a c | cbecaea |
【评测用例规模与约定】
| 40% | |
| 100% |
【解析及代码】
这个题这么简单放在压轴区我就很不理解 —— 还 25 分，我都没有给这个题预留时间，看到的时候已经来不及做了
string = 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 = string[:l], string[l: r + 1], string[r + 1:]
string = ''.join([l_part, mid_part.replace(old, new), r_part])
print(string)
