竞赛讨论区 > 【出题人题解】牛客小白月赛67
头像
FriedChicken
发布于 2023-02-24 22:12 北京
+ 关注

【出题人题解】牛客小白月赛67

本贴提供简略的文字版题解,如果不理解的话可以观看B站的视频讲解,链接: https://www.bilibili.com/video/BV1So4y1Y7UB/

标程可以查看榜上大佬提交或搜索我的提交来查看,不过还是鼓励理解写法后不看代码自己写一个。

A题

按题意模拟即可;

B题

仍然按题意模拟即可,有许多不同的枚举方式都可以在时限内通过;

C题

初中数学题,按照切割三角形的直线在xcx_c左侧和右侧两种情况分类讨论,具体分类讨论的式子请看视频题解的推导;

如果你使用了浮点数且没有处理好精度,可能会因为精度问题wa,建议学习题解的仅使用intint的做法。

D题

c[x]c[x]表示xx这张牌因多少个当前已有的牌变为比较安全牌;

则询问答案相当于是有多少个xx满足c[x]0c[x]\neq 0成立,这个问题的答案可以在添加一张牌和删除一张牌的时候顺便维护。

E题

考虑倒着的期望dp;

dp[i]dp[i]表示前i1i-1天都没有买,只考虑从第ii天开始直到第nn天这段,期望的最低购买价格;

在第ii天,有0.50.5概率价格为a[i]a[i],此时要比较a[i]a[i]dp[i+1]dp[i+1],谁小选谁;还有0.50.5概率价格为b[i]b[i],同理;

因此写出转移式子,按iinn11顺序转移:

dp[i]=0.5min(a[i],dp[i+1])+0.5min(b[i],dp[i+1])dp[i]=0.5*min(a[i],dp[i+1])+0.5*min(b[i],dp[i+1])

F题

(题目名倒过来读是威佐夫博弈)

假设做这题之前,你对博弈的基本思想和必胜必败分析有所了解;

注意到本题必败点即为威佐夫博弈的必败点,我们记威佐夫的必败点(x,y)(x,y)的编号为xy|x-y|

结论:

1、若当前点是必败点,则一定还有2xy2*|x-y|个回合结束;

2、若当前点是必胜点,则必胜点一步能到的必败点不超过33个;

(结论证明见题解视频)

对于11答案直接就有了,对于22枚举能到的33个必败点的编号,取最小的那个走就可以。

必败点需要预处理,预处理方式有114514114514种,选一种自己喜欢的即可。

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐