备战2024年蓝桥杯 -- 每日一题
Python大学A组

        试题一：收集卡牌
        试题二：爬树的甲壳虫
        试题三：绿豆蛙的归宿
        试题四：扑克牌

---

试题一：收集卡牌

【题目描述】

        小林在玩一个抽卡游戏，其中有 n 种不同的卡牌，编号为 1到 n。每一次抽卡，她获得第 i 种卡牌的概率为 pi。如果这张卡牌之前已经获得过了，就会转化为一枚硬币。可以用 k 枚硬币交换一张没有获得过的卡。小林会一直抽卡，直至集齐了所有种类的卡牌为止，求她的期望抽卡次数。如果你给出的答案与标准答案的绝对误差不超过 10−4，则视为正确。提示：聪明的小林会把硬币攒在手里，等到通过兑换就可以获得剩余所有卡牌时，一次性兑换并停止抽卡。

【输入格式】

        输入共两行。

        第一行包含两个用空格分隔的正整数 n,k，第二行给出 p1,p2,…,pn，用空格分隔。

【输出格式】

        输出共一行，一个实数，即期望抽卡次数。

【数据范围】

        对于 20%20% 的数据，保证 1≤n,k≤5
        对于另外 20%20% 的数据，保证所有 pi是相等的。
        对于 100%100% 的数据，保证 1≤n≤16,1≤k≤5，所有的 pi 

【输入样例】

2 2
0.4 0.6

【输出样例】

2.52

【解题思路】

        参考AcWing 4009. 收集卡牌 - AcWing

【Python程序代码】

python">n,k = map(int,input().split())
a = list(map(float,input().split()))
f = [[0]*(1<<16) for _ in range(90)]
def dp(depth,coin,state,cnt):if f[coin][state]:return f[coin][state]if cnt*k<=coin:return depths = 0for i in range(n):if (state>>i)&1:s += a[i]*dp(depth+1,coin+1,state,cnt)else:s += a[i]*dp(depth+1,coin,state|(1<<i),cnt-1)f[coin][state]=sreturn s
print(dp(0,0,0,n))

---

试题二：爬树的甲壳虫

【题目描述】

        有一只甲壳虫想要爬上一棵高度为 n 的树，它一开始位于树根，高度为 00，当它尝试从高度 i−1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。

【输入格式】

        输入第一行包含一个整数 n 表示树的高度。

        接下来 n 行每行包含两个整数 xi,yi，用一个空格分隔，表示 Pi=xi/yi

【输出格式】

        输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数 998244353 取模的结果。

【数据范围】

        对于 20%20% 的评测用例，n≤2，1≤xi<yi≤20
        对于 50%50% 的评测用例，n≤500，1≤xi<yi≤200
        对于所有评测用例，1≤n≤100000，1≤xi<yi≤109

【输入样例】

python">1
1 2

【输出样例】

python">2

【解题思路】

        参考AcWing 4646. 爬树的甲壳虫(概率递推+快速幂逆元) - AcWing

【Python程序代码】

python">n = int(input())
res = 0
p = 998244353
for i in range(n):x,y = map(int,input().split())res = (res+1)*y%p*pow(y-x,p-2,p)%p
print(res)

---

试题三：绿豆蛙的归宿

【题目描述】

        给出一个有向无环的连通图，起点为 1，终点为 N，每条边都有一个长度。数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有 K 条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K。现在绿豆蛙想知道，从起点走到终点所经过的路径总长度的期望是多少？

【输入格式】

        第一行: 两个整数 N，M代表图中有 N 个点、M 条边。

        第二行到第 1+M1行: 每行 33 个整数 a,b,c，代表从 a 到 b 有一条长度为 c 的有向边。

【输出格式】

        输出从起点到终点路径总长度的期望值，结果四舍五入保留两位小数。

【数据范围】

        1≤N≤105
        1≤M≤2N

【输入样例】

python">4 4
1 2 1
1 3 2
2 3 3
3 4 4

【输出样例】

python">7.00

【解题思路】

        参考AcWing 217. 绿豆蛙的归宿(概率dp) - AcWing

【Python程序代码】

python">import sys
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline
n,m = map(int,input().split())
h,e,ne,d,idx,w = [-1]*(2*n+5),[0]*(2*n+10),[0]*(2*n+10),[0]*(2*n+10),0,[0]*(2*n+10)
def add(a,b,c):global idxe[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx; idx+=1
for i in range(m):a,b,c = map(int,input().split())add(a,b,c)d[a]+=1
f = [-1]*(n+10)
def dp(u):if f[u]>=0:return f[u]f[u],i = 0,h[u]while i!=-1:j = e[i]f[u] += (w[i]+dp(j))/d[u]i = ne[i]return f[u]
print("%.2f"%(dp(1)))

---

试题四：扑克牌

【题目描述】

        Admin 生日那天，Rainbow 来找 Admin 玩扑克牌。玩着玩着 Rainbow 觉得太没意思了，于是决定给 Admin 一个考验。Rainbow 把一副扑克牌(5454 张)随机洗开，倒扣着放成一摞。然后 Admin 从上往下依次翻开每张牌，每翻开一张黑桃、红桃、梅花或者方块，就把它放到对应花色的堆里去。Rainbow 想问问 Admin，得到 A 张黑桃、B 张红桃、C 张梅花、D 张方块需要翻开的牌的张数的期望值 E 是多少？特殊地，如果翻开的牌是大王或者小王，Admin 将会把它作为某种花色的牌放入对应堆中，使得放入之后 E 的值尽可能小。由于 Admin 和 Rainbow 还在玩扑克，所以这个程序就交给你来写了。

【输入格式】

        输入仅由一行，包含四个用空格隔开的整数，A,B,C,D

【输出格式】

        输出需要翻开的牌数的期望值 E，四舍五入保留 3位小数。

        如果不可能达到输入的状态，输出 -1.000。

【数据范围】

        0≤A,B,C,D≤15

【输入样例】

python">1 2 3 4

【输出样例】

python">16.393

【解题思路】

        参考：AcWing 218. 扑克牌(期望dp) - AcWing

【Python程序代码】

python">import sys
sys.setrecursionlimit(1000000)
f = [[[[[[0]*5 for _ in range(5)] for i in range(16)] for j in range(16)] for k in range(16)] for p in range(16)]
v = [[[[[[0]*5 for _ in range(5)] for i in range(16)] for j in range(16)] for k in range(16)] for p in range(16)]A,B,C,D = map(int,input().split())
def dp(a,b,c,d,x,y):if v[a][b][c][d][x][y]:return f[a][b][c][d][x][y]v[a][b][c][d][x][y]=1if (a+(x==0)+(y==0))>=A and (b+(x==1)+(y==1))>=B and (c+(x==2)+(y==2))>=C and (d+(x==3)+(y==3))>=D:# print("YES")return 0su = 1cnt = a+b+c+d+(x!=4)+(y!=4)if a<13:su+=dp(a+1,b,c,d,x,y)*(13-a)/(54-cnt)if b<13:su+=dp(a,b+1,c,d,x,y)*(13-b)/(54-cnt)if c<13:su+=dp(a,b,c+1,d,x,y)*(13-c)/(54-cnt)if d<13:su+=dp(a,b,c,d+1,x,y)*(13-d)/(54-cnt)if x==4:minn=1e9for i in range(4):minn=min(minn,dp(a,b,c,d,i,y)/(54-cnt))su+=minnif y==4:minn=1e9for i in range(4):minn=min(minn,dp(a,b,c,d,x,i)/(54-cnt))su+=minnf[a][b][c][d][x][y]=su# print(su)return f[a][b][c][d][x][y]
if max(A-13,0)+max(B-13,0)+max(C-13,0)+max(D-13,0)>2:print("-1.000")
else:ans = dp(0,0,0,0,4,4)print("%.3f"%ans)