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

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

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

A题

按题意模拟即可；

B题

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

C题

初中数学题，按照切割三角形的直线在$x_{c}x\_c$左侧和右侧两种情况分类讨论，具体分类讨论的式子请看视频题解的推导；

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

D题

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

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

E题

考虑倒着的期望dp；

$dp[i]dp[i]$表示前$i-1i-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]$，同理；

因此写出转移式子，按$ii$从$nn$到$11$顺序转移：

$dp[i]=0.5\ast min(a[i],dp[i+1])+0.5\ast min(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)$的编号为$\mathrm{\mid }x-y\mathrm{\mid }|x-y|$；

结论：

1、若当前点是必败点，则一定还有$2\ast \mathrm{\mid }x-y\mathrm{\mid }2*|x-y|$个回合结束；

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

（结论证明见题解视频）

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

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