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

点击量：215

    这场是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了一起写写。