第一题 彩虹密码
题目描述
彩虹密码是由一个字符串组成，是由原文字符串（由不超过 60 个小写字母组成）中每个字母向后移动 n 位形成的。z 的下一个字母是 a，如此循环。现在知道移动前的原文字符串及 n，请你求出彩虹密码。
输入格式
第一行：n。第二行：未移动前的一串字母。
输出格式
一行，彩虹密码。
输入输出样例
输入
1
qwe
输出
rxf
说明/提示
字符串长度 ≤60，n 在 int 范围内。
n=int(input())
s=input()
xs=""
for i in s:m=ord(i)+nif m>ord("z"):mm=96+m%ord("z")c=chr(mm)else:c=chr(m)xs+=c
print(xs)
第二题 神奇的幻方
题目描述
在一个 N×N 的正方形网格中，每个格子分别填上从 1 到 N×N 的正整数，使得正方形中任一行、任一列及对角线的几个数之和都相等，则这种正方形图案就称为“幻方”（输出样例中展示了一个 3×3 的幻方）。我国古代称为“河图”、“洛书”，又叫“纵横图”。
幻方看似神奇，但当 N 为奇数时有很方便的填法：
- 一开始正方形中没有填任何数字。首先，在第一行的正中央填上 1。
- 从上次填数字的位置向上移动一格，如果已经在第一行，则移到同一列的最后一行；再向右移动一格，如果已经在最右一列，则移动至同一行的第一列。如果移动后的位置没有填数字，则把上次填写的数字的下一个数字填到这个位置。
- 如果第 2 步填写失败，则从上次填数字的位置向下移动一格，如果已经在最下一行，则移到同一列的第一行。这个位置一定是空的（这可太神奇了！）。把上次填写的数字的下一个数字填到这个位置。
- 重复 2、3 步骤，直到所有格子都被填满，幻方就完成了！
快来编写一个程序，按上述规则，制作一个 N×N 的幻方吧。
输入格式
输入为一个正奇数 N，保证 3≤N≤21。
输出格式
输出 N 行，每行 N 个空格分隔的正整数，内容为 N×N 的幻方。 输入输出样例
输入
3
输出
8 1 6
3 5 7
4 9 2
n=int(input())
bns=[]
for i in range(n):ns=[0 for j in range(n)]bns.append(ns)
i=1
j=n//2+1
m=1
bns[i-1][j-1]=1
while m!=n*n:m+=1ii=ijj=ji-=1if i<1:ic=nj+=1if j>n:j=1if bns[i-1][j-1]==0: bns[i-1][j-1]=melse:i=iij=jji+=1if i>n:i=1bns[i-1][j-1]=m
for ns in bns:ns=list(map(str,ns))print(" ".join(ns))
第三题 迷宫
题目描述
给定一个 N×M 方格的迷宫，迷宫里有 T 处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
输入格式
第一行为三个正整数 N,M,T，分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 SX,SY,FX,FY，SX,SY 代表起点坐标，FX,FY 代表终点坐标。
接下来 T 行，每行两个正整数，表示障碍点的坐标。
输出格式
输出从起点坐标到终点坐标的方案总数。
输入输出样例
输入
2 2 1
1 1 2 2
1 2
输出
1
说明/提示
对于 100% 的数据， 1≤N,M≤5， 1≤T≤10， 1≤SX,FX≤n，1≤SY,FY≤m
"""
解题思路：
1、使用DFS来找到所有路径数量的方法
2、因为DFS在回溯过程中更容易跟踪路径的生成和销毁。一般适合迷宫较小的。
3、如果迷宫可能包含循环，则需要在DFS实现中添加额外的逻辑来检测和处理循环，以避免无限递归。
"""
def DFS(maze,start,end,visited):#起点等于终点，找到一条路径if start==end:return 1#设置当前节点（位置）已访问visited[start[0]-1][start[1]-1] = True#局部变量计数器，累加来自子递归调用的结果path_count = 0#定义四个方向改变的数据：上 下 左 右directions=[(-1,0),(1,0),(0,-1),(0,1)]#循环访问4个方向for dx,dy in directions:nx,ny=start[0]+dx,start[1]+dy#检查新位置是否在迷宫内且不是障碍且未访问if 1<=nx<=n and 1<=ny<=m and maze[nx-1][ny-1]==1 and visited[nx-1][ny-1]==False:# 递归地搜索新位置path_count+=DFS(maze,(nx,ny),end,visited)# 回溯：撤销对当前节点的访/问标记 visited[start[0]-1][start[1]-1] = False#返回找到的路径数量return path_countn,m,t=list(map(int,input().split()))
# 初始化迷宫（1表示可通行）
maze=[[1]*m for _ in range(n)]
#设置起点、终点
sx,sy,fx,fy=list(map(int,input().split()))
start=(sx,sy)
end=(fx,fy)
# 设置迷宫障碍（0表示障碍）
for i in range(t):x,y=list(map(int,input().split()))maze[x-1][y-1]=0
# 初始化visited数组，所有元素初始化为False
visited=[[False]*m for _ in range(n)]
# 调用DFS函数计算路径数量
path_count=DFS(maze,start,end,visited)
print(path_count)
第四题 距离的智慧
题目描述
学校新建造了一个有 N（2≤N≤10^5) 个小隔间的自习室，这些隔间分布在一条直线上，坐标是x1,x2,x3,…xn（0≤xi≤10^9）。为了保持尽可能的安静，减少周边环境的影响，睿智的大树老师想把自习学生安置在指定的隔间，所有自习学生中相邻两人的最近距离越大越好。有 C（2≤C≤N）名学生，那么，这个最大的最近距离是多少呢？
输入格式
第 1 行：两个用空格隔开的数字 N 和 C。
第 2∼ N+1 行：每行一个整数，表示每个隔间的坐标。
输出格式
输出只有一行，即相邻读者最大的最近距离。
输入输出样例
输入
5 3
1
2
8
4
9
输出
3
"""
找最大的最小问题，用二分查找和贪心算法的结合
解题思路：
1、排序
2、二分：确定最大的最小距离
3、贪心：检测可能性
"""
def check(n,c,mid,ps):count=1begin_p=ps[0]for i in range(1,n):if ps[i]-begin_p>=mid:count+=1begin_p=ps[i]if count==c:return Truereturn Falsedef f(n,c,ps):#距离的最小情况和最大情况left=0right=ps[-1]-ps[0]#所有情况 0,1,2,3,4,5,6,7,8best=0#最优距离#当距离最小情况小于等于最大情况，一直找最优解while left<=right:mid=(left+right)//2 #二分拿中间值if check(n,c,mid,ps): #检查中间值位置间隔是否放得下要放的人数best=midleft=mid+1 #能放下，在右半区位置范围找else:right=mid-1 #不能放下，作左半区位置范围找return bestn,c=map(int,input().split())
ps=[int(input()) for _ in range(n)]
ps.sort()
rs=f(n,c,ps)
print(rs)
第五题 排队形
题目描述
为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小A需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 n 个人，第 i 个人的身高为 ℎi米（1000≤hi≤2000），并已知任何两个人的身高都不同。假定最终排出的队形是 A 个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终棑排出的队形中：
- 第一个人直接插入空的当前队形中。
- 对从第二个人开始的每个人，如果他比前面那个人高（h 较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（h 较小），那么将他插入当前队形的最左边。
当 n 个人全部插入当前队形后便获得最终排出的队形。
例如，有6个人站成一个初始队形，身高依次为 1850,1900,1700,1650,1800,1750，那么小 A 会按以下步骤获得最终排出的队形：
- 1850。
- 1850,1900，因为 1900>1850。
- 1700,1850,1900，因为 1700<1900。
- 1650,1700,1850,1900 因为 1650<1700。
- 1650,1700,1850,1900,1800，因为 1800>1650。
- 1750,1650,1700,1850,1900,1800，因为 1750<1800。
因此，最终排出的队形是 1750,1650,1700,1850,1900,1800。
小 A 心中有一个理想队形，他想知道多少种初始队形可以获得理想的队形。
请求出答案对 19650827 取模的值。
输入描述
第一行一个整数 n
第二行 n 个整数，表示小 A 心中的理想队形。
输出描述
输出一行一个整数，表示答案 mod19650827 的值。 输入输出样例：
输入：
4
1701 1702 1703 1704
输出：
8
说明/提示
对于 30% 的数据，n≤100。
对于 100% 的数据，n≤1000，1000≤hi≤2000。
"""
考察区间动态规划，给定的区间，要么加在左边，要么加在右边，不断增加。
解题步骤：
1、定义问题状态 f[i][j][0]表示从左边进 f[i][j][1]表示从右边进
2、找到问题的转移方程，确定初始状态和终止状态
3、通过程序还原模拟过程
"""
MOD=19650827
n=int(input())
nums=list(map(int,input().split()))
f=[[[0,0] for _ in range(n)] for _ in range(n)]#初始化基本状态
for i in range(0,n):f[i][i][0]=1#动规和转移方程
for length in range(1,n):for i in range(0,n-length): #i起点j=i+length #j终点#从左边进入if nums[i]<nums[i+1]:f[i][j][0]+=f[i+1][j][0]if nums[i]<nums[j]:f[i][j][0]+=f[i+1][j][1]#从右边进入if nums[j]>nums[i]:f[i][j][1]+=f[i][j-1][0]if nums[j]>nums[j-1]:f[i][j][1]+=f[i][j-1][1]f[i][j][0]%=MODf[i][j][1]%=MODrs=(f[0][n-1][0]+f[0][n-1][1])%MOD
print(rs)
