竞赛讨论区 > 周赛25-提高组题解
头像
nit
发布于 2021-05-05 08:45
+ 关注

周赛25-提高组题解

**1.找滚木--solution**

可以手推一下,
每次开宝箱得到滚木概率都是\frac1nn1,第i次开宝箱得到和之前得到的一样的卡牌概率为\frac{i-1}nni1

所以递推,设第i次开宝箱就可以得到滚木的概率是f_ifi得到转移式f_i=(1-\sum_{j=1}^{i-1}f_j)*\frac infi=(1j=1i1fj)ni

ans=\sum_{i=1}^nf_i*ians=i=1nfii,O(n)即可

**2.跑步--solution**
  • f_xfx表示从起点到点x的最短距离,如果x不能被到达,令f_x=\inftyfx=
  • 我们称点x可以从点y转移过来当且仅当f_x=f_y+1fx=fy+1且点x和点y相邻
  • 称一条路径是合法的当且仅当这条路径是一个至少包着一颗树的环,且经过起点。

进入正题:

描述一个状态:

这个圆表示一条合法路径,其中有4个点,满足点pp是路径中f_xfx最大的一个点。p_左pp_右p表示两个紧挨着的p的路径上的点。点v表示这条路径上和点p相邻但不能转移到p的点。

  • 证明描述的这个状态存在

    因为这是一个路径,所以点pp一定可以从点p_左p和点p_右p转移过来。此时p_左pp_右p一定不相邻否则这就不是最优路径,所以一定存在点v且v不能转移到p。

  • 证明描述的这个状态一定表示一条合法路径

    当存在点v时,一定是因为这条路径包含了至少一颗树,否者点v可以转移到点p。

    所以这个状态表示的路径一定合法。

  • 证明一条最优合法路径一定可以找到这样4个满足条件的点

    一条最优合法路径中一定存在距离起点最远的点,所以存在点p,p_左pp_右p

    因为这条路径包含至少一棵树,所以存在v点使得v不能转移到p

  • 结论

    存在上述的4个满足条件的点时,一定存在这样一条合法路径。

  • 实现

    所以我们枚举点pp,再验证是否存在满足条件的点即可。

    细节:在验证的时候因为路径上最大的点可以有两个,所以要讨论6种情况。

**3.简单题--easy**

从大到小枚举 gcd,设为g,钦定 i,j 都是 g 的倍数,然后假定 gcd(i,j) 就是 g 做一次卷积。但这样会算到真正的 gcd 是 g 的倍数的情况,做一个简单的容斥减掉即可。

复杂度:O(n log^2 n),常数不大。
如果想要数据或标程可以去https://share.weiyun.com/5WxfkoNe

全部评论

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

等你来战

查看全部

热门推荐