相逢是问候 分手是祝愿

发布于 2018-03-16  4k 次阅读


Informatik verbindet dich und mich.
信息将你我连结。

Zeit und Raum trennen dich und mich.
时空将你我分开。


今天刷了去年的这两道省选题,当时太菜了,第一题只会30分暴力,第二题还不知道期望是啥= =

 

 

相逢是问候

首先,题目长得和“上帝与集合的正确用法”那题相似,我们可以考虑通过相似的做法来解决。

基础知识:扩展欧拉定理。应用在这道题上,比较麻烦的就是判断与次数的大小关系。实际上,我们只要在一开始判断大小关系,如果出现大于等于就先模后加就好了,中间过程如果算出来了0,就直接加上phi,这样就不会有问题了。

对于一个数,只需要O(logn)次就可以通过取phi操作变成1,从而变成一个常数而停止递归,这一点样例2也给了我们一些提示。

有了这个性质,我们就可以用线段树来解决问题了。维护区间是否完全变为常数以及区间和的标记,如果区间没有完全变成常数就暴力递归,这样每个元素会被暴力修改O(logn)次,如果快速幂是O(logn)的那么总时间复杂度就是O(nlog^3n),在BZOJ上可以卡过去(实测大点需要跑2S+),如果我们给快速幂优化一下,处理[0,65536]的结果,用二进制思想拼起来,每次“快速幂”就是O(1)的,复杂度O(nlog^2n)。

(写的3log的,懒得卡了)

UPD:最后还是改了,复杂度O(nlog(n)log(p)+sqrt(p)log(p))


 

分手是祝愿

记得当时省选讲题的时候,出题人说把题出成这样是因为懒得写SPJ了= =那我们先想想最优策略是怎么搞的。首先每个灯最多只被操作一次,那么考虑最后一个亮灯的位置,如果不按它,那么它就再也不会被熄灭,也就是说只要最后一个在一些操作后仍被点亮,那么一定需要熄灭它。如果枚举因子暴力做,而且还不预处理的话复杂度是O(n^1.5),显然不能接受,所以我们可以换个方法,枚举倍数,这样复杂度就变成了O(nlogn)。

显然第二问应该是个概率DP,那我们来考虑如何设计状态能保证无后效性。无论在哪种状态下,任意进行的操作要么是必须进行的步骤之一,要么需要另一次操作来抵消这次的影响。因此,我们可以定义f[i]:从需要i步到需要i-1步的状态的期望代价。

$$f[i]=\frac{i}{n} + \frac {n-i}{n}*(f[i+1]+f[i]+1)$$

化简一下,就能直接递推了。对于i<=k的情况,f[i]均为1。

感觉这几天应该复习一下期望概率那些常用套路啊,奶一口今年省选还有这些玩意。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974