蓝桥杯刷题DAY3：Horner 法则 前缀和+差分数组 贪心
所谓刷题，最重要的就是细心
📌 题目描述
在 X 进制 中，每一数位的进制不固定。例如：
- 最低位 采用 2 进制，
- 第二位 采用 10 进制，
- 第三位 采用 8 进制，
则 X 进制数 321 的十进制值为：
3×(10×8)+2×8+1=65
现在，给定两个以 X 进制表示的整数 A 和 B，它们的每一数位的进制上限为 N 进制，下限为 2 进制，你需要计算：
A−B
在 十进制下的最小可能值，并输出 模 10^9+7 后的结果。
📌 输入格式
- 第一行：一个正整数
N（表示最高进制）。 - 第二行：一个正整数
Ma（表示 X 进制数 A 的位数）。 - 第三行：
Ma个用空格分隔的整数（表示 A 的各个位，从 高位到低位）。 - 第四行：一个正整数
Mb（表示 X 进制数 B 的位数）。 - 第五行：
Mb个用空格分隔的整数（表示 B 的各个位，从 高位到低位）。
📌 输出格式
- 输出 一个整数，表示 A - B 的最小可能值，转换为十进制后模 10^9+7 的结果。
📌 输入输出示例
输入
11 3 10 4 0 3 1 2 0
输出
94
📌 题目说明
- 你需要 找到最小的进制分配方案，使得
A - B最小：- 每一位的进制必须 ≥ max(1, A[i], B[i]) + 1（确保 A 和 B 的每一位都是合法的）。
- 每一位的进制不能小于 2（最小是二进制）。
- 最优解 是选择 尽可能小的进制，这样计算出的 A 和 B 的十进制值最小，从而
A - B也最小。
- 进制计算方式
- 例如，若
A = [10, 4, 0]，B = [1, 2, 0] - 进制可以选择：
d = [11, 5, 2] - 计算： A10=10×(5×2)+4×2+0=108 B10=1×(5×2)+2×2+0=14
- 最终
A - B = 108 - 14 = 94。
- 例如，若
📌 约束条件
- 对于 30% 的数据：
- N≤10
- 1≤Ma,Mb≤8
- 对于 100% 的数据：
- 2≤N≤1000
- 1≤Ma,Mb≤100000
- 保证 A ≥ B
- 运行限制
- C++ / C / Java / Python3
- 最大运行时间：1s
- 最大运行内存：256MB
import os
import sys
# 请在此输入您的代码
if __name__=="__main__":
mod = 1000000007
N=int(input())
Ma=int(input())
A= list(map(int,input().split()))
Mb=int(input())
B= list(map(int,input().split()))
for i in range(Ma-Mb):
B.insert(0,0)
result=0
for i in range(Ma):
if i==Ma-1:
result= (1)*(result+A[i]-B[i])%mod
else:
result= (max(1,A[i+1],B[i+1])+1)*(result+A[i]-B[i])%mod
print(result%mod)字符迁移【算法赛】
题目描述
小蓝最近获得了一个长度为 N 的字符串 S，他对它爱不释手。
小桥为了考验小蓝对字符串的处理能力，决定给他提出一个挑战：她会进行 Q 次操作，每次操作给定三个整数 l, r, k，将 S 的第 l 个字符到第 r 个字符都循环右移 k 次。
字符右移的含义为：按照字母表顺序进行移动，例如：
'a' 右移 1 次变为 'b'；
'b' 右移 2 次变为 'd'；
特别地，'z' 右移 1 次变回 'a'。
操作完成后，请输出字符串 S 的最终结果。
输入格式
第一行输入两个整数 N, Q
(1 ≤ N, Q ≤ 2×10<sup>5</sup>)，表示字符串 S 的长度以及操作次数。
第二行输入一个字符串 S，保证 S 只包含小写字母。
接下来 Q 行，每行输入三个整数 l, r, k
(1 ≤ l ≤ r ≤ N, 1 ≤ k ≤ 10<sup>9</sup>)，表示一次操作：将 S 中第 l 个字符到第 r 个字符循环右移 k 次。
输出格式
输出一个字符串，表示操作完成后的 S。
输入样例
5 3
abcde
1 5 3
1 2 4
2 5 3
输出样例
hlijk
运行限制
Python3：最大运行时间 3s，最大运行内存 256M
import os
import sys
# 请在此输入您的代码
if __name__=="__main__":
N,Q=map(int,input().split())
S = list(input())
n=len(S)
d=[0]*(n+1)
s=[0]*n
for i in range(Q):
l,r,k=map(int,input().split())
d[l-1]+=k
d[r]-=k
for i in range(n):
if i==0:
s[i]=d[i]
else:
s[i]=s[i-1]+d[i]
for i in range(n):
S[i]= chr(( s[i] +( ord(S[i]) - ord('a') ))%26 + ord('a') )
print("".join(S))
食堂
题目描述
S 学校里一共有
a2 个两人寝、
a3 个三人寝、
a4 个四人寝。食堂里有
b4 个四人桌和
b6 个六人桌。学校想要安排学生们在食堂用餐，并且满足每个寝室里的同学都在同一桌就坐。请问这个食堂最多同时满足多少同学用餐？
输入格式
采用多组数据输入。
输入共 q+1 行：
-
第一行为一个正整数 q，表示数据组数。
-
后面 q 行，每行五个非负整数 a2,a3,a4,b4,b6，表示一组数据。
输出格式
输出共 q 行，每行一个整数，表示对应输入数据的答案。
样例输入
2 3 0 1 0 1 0 2 2 1 1
样例输出
6 10
样例说明
-
第一组数据：
-
仅有一个六人桌，最多安排三个两人寝的同学就餐。
-
答案为 2+2+2=6。
-
-
第二组数据：
-
用一个六人桌安排两个三人寝的同学，用一个四人桌安排一个四人寝的同学。
-
答案为 (3+3)+4=10。
-
评测用例规模与约定
-
20% 的评测用例：
-
保证 a2+a3+a4≤8。
-
-
100% 的评测用例：
-
保证 q≤100，b4+b6≤a2+a3+a4≤100。
-
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Java | 3s | 512M |
| Python3 | 10s | 512M |
import os
import sys
# 请在此输入您的代码
if __name__=="__main__":
q= int(input())
for i in range(q):
a2,a3,a4,b4,b6=map(int,input().split())
total=0
tmp=min(a4,b4)
total+=tmp*4
a4-=tmp
b4-=tmp
tmp=min(a2,a4,b6)
total+=tmp*6
a2-=tmp
a4-=tmp
b6-=tmp
tmp=min(a3//2,b6)
total+=tmp*6
a3-=tmp*2
b6-=tmp
tmp=min(a2//2,b4)
total+=tmp*4
a2-=tmp*2
b4-=tmp
tmp=min(a2//3,b6)
total+=tmp*6
a2-=tmp*3
b6-=tmp
tmp=min(a2,a3,b6)
total+=tmp*5
a2-=tmp
a3-=tmp
b6-=tmp
tmp=min(a4,b6)
total+=tmp*4
a4-=tmp
b6-=tmp
tmp=min(a2//2,b6)
total+=tmp*4
a2-=tmp*2
b6-=tmp
tmp=min(a3,b4)
total+=tmp*3
a3-=tmp
b4-=tmp
tmp=min(a3,b6)
total+=tmp*3
a3-=tmp
b6-=tmp
tmp=min(a2,b4)
total+=tmp*2
a2-=tmp
b4-=tmp
tmp=min(a2,b6)
total+=tmp*2
a2-=tmp
b6-=tmp
print(total)
