蓝桥杯刷题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

---

📌 题目说明

1. 你需要 找到最小的进制分配方案，使得 A - B 最小：
   • 每一位的进制必须 ≥ max(1, A[i], B[i]) + 1（确保 A 和 B 的每一位都是合法的）。
   • 每一位的进制不能小于 2（最小是二进制）。
   • 最优解 是选择 尽可能小的进制，这样计算出的 A 和 B 的十进制值最小，从而 A - B 也最小。
2. 进制计算方式
   • 例如，若 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 = 1000000007N=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=0for i in range(Ma):if i==Ma-1:result= (1)*(result+A[i]-B[i])%modelse:result= (max(1,A[i+1],B[i+1])+1)*(result+A[i]-B[i])%modprint(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⁵)，表示字符串 S 的长度以及操作次数。

第二行输入一个字符串 S，保证 S 只包含小写字母。

接下来 Q 行，每行输入三个整数 l, r, k
(1 ≤ l ≤ r ≤ N, 1 ≤ k ≤ 10⁹)，表示一次操作：将 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]*nfor i in range(Q):l,r,k=map(int,input().split())d[l-1]+=kd[r]-=kfor 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  

样例说明

1. 第一组数据：

   • 仅有一个六人桌，最多安排三个两人寝的同学就餐。

   • 答案为 2+2+2=6。

2. 第二组数据：

   • 用一个六人桌安排两个三人寝的同学，用一个四人桌安排一个四人寝的同学。

   • 答案为 (3+3)+4=10。

---

评测用例规模与约定

1. 20% 的评测用例：

   • 保证 a2+a3+a4≤8。

2. 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=0tmp=min(a4,b4)total+=tmp*4a4-=tmpb4-=tmptmp=min(a2,a4,b6)total+=tmp*6a2-=tmpa4-=tmpb6-=tmptmp=min(a3//2,b6)total+=tmp*6a3-=tmp*2b6-=tmptmp=min(a2//2,b4)total+=tmp*4a2-=tmp*2b4-=tmptmp=min(a2//3,b6)total+=tmp*6a2-=tmp*3b6-=tmptmp=min(a2,a3,b6)total+=tmp*5a2-=tmpa3-=tmpb6-=tmptmp=min(a4,b6)total+=tmp*4a4-=tmpb6-=tmptmp=min(a2//2,b6)total+=tmp*4a2-=tmp*2b6-=tmptmp=min(a3,b4)total+=tmp*3a3-=tmpb4-=tmptmp=min(a3,b6)total+=tmp*3a3-=tmpb6-=tmptmp=min(a2,b4)total+=tmp*2a2-=tmpb4-=tmptmp=min(a2,b6)total+=tmp*2a2-=tmpb6-=tmpprint(total)