Codeforces Round #514 (Div. 2) 题解集/随笔

 

    这场是UTC+8的22:35~0:35场。

 

随笔部分

    首先提一下打了这场的收获和教训吧。A题是在开场2分钟看到题面,开场7分钟切掉的,放在以前应该是B题的位置,不过这次只有五道,想必是删掉了最简单的。

 

    然后是B题。感觉代码简洁易懂,18分钟的时候写完了,手造了几组数据都过了。交上去WA5,于是继续生成(手动)数据,然后发现是枚举\(i\ 1\ \text{to}\ n,j\ 1\ \text{to}\ m\)的时候,两个都打成\(n\)了。在30分钟的时候发现了问题交上去也就PP了。

 

    谁知道第二天一起来,本来以为要涨个三五分的结果掉了60?然后是这样的:

    然后挂在了第18个test……可能是前面函数写多了i<3,j<3吧,习惯性地就写了一样的……丢了800分,非常吃亏……

 

    然后去看CD,发现D题有点长,先看C。给定一个\(1\sim n\)的排列,要求每次删掉一个数,使得剩下的数\(\gcd\)最大并输出,同时保证输出的答案字典序最大。

 

    也就是说,每次尽可能把\(gcd\)变大。如果一个方向有多种,还要做更多的决策。不过好像发现了奇数偶数之间的谁先谁后的关系,稍微撕烤了一下就过了还好没有fst

 

    D,E看上去都不难,但是E没有思路,去想D,想到了很多思路,但是感觉要么复杂度不对,要么贪心不对。最后Dew给出了一个二分答案(事后说明是正解%%%)的做法,我稍微算了一下发现可行,于是开始打。打完了发现总是WA4(有3个样例),猜到是极限数据精度卡掉了,但是不清楚枚举上界,那么枚举的精度就不好设置。中途找过其他问题,但是只找出一个细节。

 

    比赛结束后看到果然是一组极端数据,我的相对误差是\(1.6\times 10^{-6}\),感觉相差不大,但是除了long double实在是没有别的办法了,最后压到刚好\(1\times 10^{-6}\)。但是要求小于\(10^{-6}\)我也没办法……第二天改的时候发现还有个大问题,就是在判断全是负数的时候二分下界没有调整,导致WA9。把这个改了之后继续WA13……这时候才知道要反过来取最小值,改了之后就A掉了。

 

    不过ouuanA得比较快,他用的是int存坐标,不知道会不会对这里的精度有影响。但是开根的精度是不可避免的。

 

    EternalAlexander放掉了CD去磕E还好最后做出来了,还是要%%%的。

 

题解:

    先咕咕咕,大致弄出来E了一起写写。