07月28, 2018

7.28 牛客网多校4题解及补题

比赛过程

签到题分别是:D,G,F。 开场Bocity和Wrzz签到了D,Xander签到了F,接下来Bocity卡了G。Xander和Wrzz讨论了J的做法,想到了拓扑排序,但是没有想出优化建图的方法,Xander觉得可以打个暴力试一下说不定就A了,于是让卡F的Bocity下来上J。 中间Bocity突然想清楚了卡的地方,于是改了改就A了G。

接下来就没有过题了。

Xander把J的暴力写完了,发现MLE,缩了空间就T了。接下来都没有成功优化建图。

Bocity和Wrzz推出了A的dp方程(在oeis的帮助下),但是方程中含有2的和上一个状态结果有关的幂函数,但是上一个状态结果已经取过模了,用广义欧拉定理需要维护太多量。

这需要用到欧拉函数的一个特点:一个很大的数不断地取欧拉函数,很快就会降到0,次数是log级的。原因暂时不清楚。

比赛最后才想到这个特点,但是已经没有时间了,因此这场也就停留在签到完成梯队。

知识点总结

  • A 找规律dp,欧拉定理降幂的高级用法
  • F 贪心

题解

本文链接:https://www.haolovej.com/post/multi4.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。