我寻思着因为我们是提前跟衡中打了招呼才拿到的账号,所以题还是不能公开的吧.......
所以我就只聊聊自己怎么搞的
听说衡中那边一考完就有个金牌爷给他们讲题(好羡慕啊),我们就很郁闷了......一群人围着黑板讲各种错解......
T1 : 序列
考场上:
我第一次看的时候看错了,导致浪费了1h.......
看懂题之后开始推几个小结论
solution1 : 合法序列的长度不超过60
很简单但又有很多人推不出来的结论,因为题目要求为每个数都小于1e18,有60项时,设公比为2(最小合法正整数),2^60就已经爆了.
如果是连续相同的数?想判就判一个,数据也有可能卡一下这里.
solution2 : 枚举质数是可行的.
题目要求公比小等于1000,那么当序列不满足这个条件时可以直接判否,这是应用之一.
应用之二在于,小于1000的质数只有168个,枚举质数只会造成一个200的常数(好像已经很大了)
然后我想写二分,就在我写下while(l<r)的时候,老师过来康了康我的代码,然后笑了笑走了,我就很慌,想着是不是错了,想有没有比二分更好的枚举序列方式.
想到由于序列是连续的,要求合法,而且可以乱序,所以我就想到了two_pointers.
具体处理为r++,while(不合法)l++;这样的话我的枚举复杂度就是相对优美的O(n)
关键就在于合法判断.
因为solution1所以sort是没问题的,考场上想的方法是把每个数质因数分解,然后乱七八糟比一番(懒得说了)
在我们机房被认为最有可能正确(?),但常数过大容易T:
总复杂度O(168*60log60*n + n*sqrt(n)).sqrt刷不满上限因为q<=1000;60log60也是不严格的因为很难达到60,168的质数判断也可以在一个不合法时就停下来.
看上去没啥错.
考场下:
大家的看上去都差不多,有些写了明显错误的判断居然有 80 分,早知道我就不写那个又臭又长的去写个假判骗分了(20分还不如去看看后面的题)(我的还没写完日哦).
T2 熟练剖分:
考场上 : 连看都没看一眼(搞T1)
考完了 : 没人讨论这题
自己看了下大概是个树形DP+期望,但是期望的DP一直难写(我不会).
最后应该用费马小定理求个逆元就行.
T3 建造游乐园:
考场上:看都没看一眼
考完了:没人讨论这题
(衡中能造个游乐园给我们玩吗谢谢茄子)
TAG : SIN_XIII ⑨