备战2024年蓝桥杯 -- 每日一题
Python大学A组
试题一：斐波那契
试题二：垒筛子
试题三：斐波那契数列前n项和
试题四：牛站
试题一：斐波那契
【题目描述】
在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)给定整数 n，求Fibnmod10000。
【输入格式】
输入包含不超过 100 组测试用例。
每个测试用例占一行，包含一个整数 n。
当输入用例 n=−1时，表示输入终止，且该用例无需处理。
【输出格式】
每个测试用例输出一个整数表示结果。
每个结果占一行。
【数据范围】
0≤n≤2×109
【输入样例】
0
9
999999999
1000000000
-1【输出样例】
0
34
626
6875【解题思路】
【f2，f3】 = 【[0，1]，[1，1]】*【f1，f2】，也就是【fn，fn-1】 = A^n【f0，f1】
【Python程序代码】
def matrix_mul(A,B,MOD):
res = [[0]*2 for _ in range(2)]
for i in range(2):
for j in range(2):
for k in range(2):
res[i][j] = (res[i][j] +A[i][k]*B[k][j])%MOD
return res
def fib(k):
ans = [[0,1],[0,0]]
mat = [[0, 1], [1, 1]]
while k>0:
if k&1==1:
ans = matrix_mul(ans,mat,10000)
k = k>>1
mat = matrix_mul(mat,mat,10000)
return ans[0][0]
while True:
n = int(input())
if n==-1:break
if n==0:print(0)
elif n==1:print(1)
else:
print(fib(n))试题二：垒筛子
【题目描述】
赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。atm想计算一下有多少种不同的可能的垒骰子方式。两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。由于方案数可能过多，请输出模 109+7的结果。
【输入格式】
第一行包含两个整数 n,m，分别表示骰子的数目和排斥的组数。
接下来 m 行，每行两个整数 a,b，表示 a 和 b 数字不能紧贴在一起。
【输出格式】
共一个数，表示答案模 109+7 的结果。
【数据范围】
1≤n≤109
1≤m≤361
1≤a,b≤6
【输入样例】
2 1
1 2【输出样例】
544【解题思路】
状态转移 f[i][j] = f[i - 1][k] * 4 ，肯定是会爆的，考虑如何变成矩阵乘法的形式。构建状态转移矩阵，A，当x,y不能放一块时置为0，能放一块时置为4.
【Python程序代码】
n,m = map(int,input().split())
a = [[4]*6 for i in range(6)]
p = 10**9+7
def get_op(x):
if x<3:return x+3
else:return x-3
for i in range(m):
x,y = map(int,input().split())
x,y =x-1,y-1
a[x][get_op(y)]=0
a[y][get_op(x)]=0
f = [[0]*6 for i in range(6)]
f[0]=[4,4,4,4,4,4]
k = n-1
def matrix_mul(a,b):
c = [[0]*6 for i in range(6)]
for i in range(6):
for j in range(6):
for k in range(6):
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % p
return c
while k:
if k&1:f = matrix_mul(f,a)
a = matrix_mul(a,a)
k>>=1
res = 0
for i in range(6):
res = (res+f[0][i])%p
print(res)
试题三：斐波那契前 n 项和
【题目描述】
【解题思路】
构建状态转移矩阵 a = [[0,1,0],[1,1,1],[0,0,1]]，F（f2,f3,s2） = a*F（f1,f2,s1）
【Python程序代码】
n,m = map(int,input().split())
f = [[0]*3 for i in range(3)]
f[0] = [1,1,1]
a = [[0,1,0],[1,1,1],[0,0,1]]
def matrix_mul(a,b):
c = [[0]*3 for i in range(3)]
for i in range(3):
for j in range(3):
for k in range(3):
c[i][j] = (c[i][j]+a[i][k]*b[k][j])%m
return c
k = n-1
while k:
if k&1:f=matrix_mul(f,a)
a = matrix_mul(a,a)
k>>=1
print(f[0][2])试题四：牛站
【题目描述】
给定一张由 T 条边构成的无向图，点的编号为 1∼1000 之间的整数。求从起点 S 到终点 E 恰好经过 N 条边（可以重复经过）的最短路。注意: 数据保证一定有解。
【输入格式】
第 1 行：包含四个整数 N，T，S，E。
第 2..T 行：每行包含三个整数，描述一条边的边长以及构成边的两个点的编号。
【输出格式】
输出一个整数，表示最短路的长度。
【数据范围】
2≤T≤100
2≤N≤106
【输入数据】
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9【输出数据】
10【解题思路】
类Floyd算法+qmi，参考AcWing 345. 牛站矩阵做法详解(类Floyd算法) - AcWing
【Python代码】
n,t,s,e = map(int,input().split())
cnt = 0
d = dict()
d[s] = cnt; cnt+=1
s = d[s]
d[e] = cnt; cnt+=1
e = d[e]
g = [[0x3f3f3f3f]*(210) for _ in range(210)]
for i in range(t):
c,a,b = map(int,input().split())
if a not in d:
d[a]=cnt; cnt+=1
if b not in d:
d[b]=cnt; cnt+=1
a,b = d[a],d[b]
g[a][b]=g[b][a] = min(g[a][b],c)
def work(a,b):
temp = [[0x3f3f3f3f]*(cnt+5) for _ in range(cnt+5)]
for i in range(cnt):
for j in range(cnt):
for k in range(cnt):
temp[i][j] = min(temp[i][j],a[i][k]+b[k][j])
return temp
res = [[0x3f3f3f3f]*(cnt+5) for _ in range(cnt+5)]
for i in range(cnt):res[i][i]=0
while n:
if n&1:
res = work(res,g)
g = work(g,g)
n>>=1
print(res[s][e])