Codeforces Round #254

只能说杜教两场由紫变红太强。。
两场。。。
我拼死拼活只能从紫名打到黄名。。
而且是在两场都比较送rating的情况下。。

啥时候打到红名就再也不打cf了。。。
我只要gym能看数据就好了。。

situation

这场推迟了5min开始。。
家里的网比较渣。。
开始的时候怎么都打不开cf。。前5min基本就是啥题都没看。。在思考自己是弃疗比较好还是弃疗比较好。
搞了半天终于能看题了。。
开场看的B。。
看了半小时没有想法。。
(中途想了10分钟研究(x*37+10007)%(1e9+7)除了能当随机数生成器使外。。还有什么特点。。你怕不怕)
感觉要神作。。
然后想想这样下去要神作。。
看了一下发现A已经有200+人过掉了。。
B还没人过。。
然后赶快看A。。发现一副浓浓的二分+最小割既视感。
再看一眼发现分子分母看反了。。然后就没有然后了。
接下来已经有30人碾压了B了。。
我就看B。。想了半天觉得随机生成数据。。就是字面上的随机意思。。
然后想了一想暴力的期望复杂度。。发现好像是可以接受的。。就搞过去了。。
接下来看C。。
发现C的样例看起来像是道裸数据结构。。
读完题意觉得就是道线段树暴力。。感觉这题看起来比B要简单得多啊。。
八分钟写好。。又花了四分钟写了个暴力+对拍器。。
拍了一下没有问题。。就交了。。

ydc跟我说他这题用分块的。。我不理解为啥会有人产生这题分块比线段树好写的错觉。。

C过掉pretest之后还有30+min供我浪。。
我就锁了ABC去cha人了。。
发现毫无cha点。。

发现房间一韩国友人过掉了E。。发现shizhouxing和我一个room。。
发现shizhouxing也过了E。。

这时候发现卧槽E被各国人民怒艹了。。
我一直觉得chinese round不需要E来着啊。。

然后还有十几分钟。。读了一下E。。不会做。。
又看了一下D。。看起来是hash。。但是hash之后球最接近值。。依旧不会。。

想了一会感觉可以分块。
只有10分钟也写不出。。就作罢了。

这时候ydc拉我跟他的C对拍。。结果他C用我造的数据在我本地(linux)跑不出来。。他那里直接输出了浮点数。。
sad story。。

然后比赛就结束了。。这场system test结束得很快。。rating也出得很快。。

一群人fst了E。。

拿了个不痛不痒的rank。。。

发现chinese round画风变了。。

就用这两句话概括这场吧。


题解

A

一定存在最优解只有一条边。。
很显然。。

两个数的情况显然能扩展到多个数的情况。。
稍微调整一下就会发现当导出子图的边数大于1的时候。。一定不是最优的。

B

因为数据随机可以暴力。。
定义

显然Sel只有d个元素。
显然对于位置i。。
只有这些位置的c才有可能等于a[i]
那么我们很容易想到这样一个做法。。
枚举k=n,n-1,n-2,..,到n-x+1。。
然后找到pos使得a[pos]=k。。枚举所有c[pos+j]=max(c[pos+j],k)..
这样做x次后。
然后有些c[i]可能没有被更新。。说明c[i]<=n-x。。那么对于i暴力O(d)算卷积就行。

关键是做了x次后。。期望有多少个c没有被更新。
一个位置可以被d个位置更新,那d个位置的a[]都小于等于n-x的概率大约是((n-x)/n)^d。。
所以一个位置不被更新的概率大约是((n-x)/n)^d。。
那么期望有n((n-x)/n)^d个位置需要暴力。
很显然当d比较大的时候。。取很小的x就行了。。因为是关于d指数级下降的。

总之随便写写就能过。。
(上面的概率分析都比较不严谨。。想看严谨的还是自己推吧。。而且真的要分析还得分析方差。。)

C

直接线段树暴力。
大致思路。。如果线段树当前节点代表的区间的数字已经全部相同。。
那么对于这个节点代表区间的染色。。可以直接打标记。。算sum的delta。。
否则如果我们要将这个区间全部染成同一色的话。。暴力左右递归下去染色。。直接维护一下。。
根据势能分析。。复杂度是靠谱的。。

D

询问字符串长度这么短,明显是hash。
hash完了之后就转化成了已知26^4序列,第i个是ai1,ai2,ai3,..,ain,询问最小的|ai-bj|。。
分块就好。。
对于长度大于sqrt(n)的序列。。这样的序列不会超过sqrt(n)个。。
对于每一个大序列我们暴力算出它与其它所有序列的答案。。
对于小序列。。询问的时候暴力就好。。

E

这我tm哪里会。。
本来以为是网络流。。
结果发现直接并查集就能过。。
一题多解。。xyz太强了。。

Comments

comments powered by Disqus