机房比赛记录
Codeforces Round #742
题解
AB略
C: 二进制枚举哪些位置进位然后搞一下即可
D: 注意到尽量不进位是最优的, 也能手推出, 如果要进位, 把次数低的拆开更优, 优先队列维护即可
E: 线段树sb题,每个节点维护:答案,左连续增长度,右连续增长度
实况
赛场上很快写到了C。
D的结论也推出来了,但是我写挂了,挂在了一个简单的case(复杂的那个case反而没有挂),然后一直没想到是那边的问题,就没调出来。
在调D的过程中也看了一下E,也想出来了,但是在合并节点的地方写挂了,也一直没调出来。
本来应该A掉五个题,只过了3题。
这次的教训是,我还得提升基础码力。
Atcoder Regular Contest 122
赛时:AB
赛后:ABC
题解
A:no ... in a row,意思是没有相邻的某某某,不是“在一行”,然后就是傻逼dp
B:把式子变形,
注意到 (min(a,b)=dfrac{a+b-|a-b|}{2})
那么 (min(x,0)=dfrac{x-|x|}{2})
继续变,
本题中期望就相当于和除以 (n)。(a_i) 的和是定值,相当于要让 (sumlimits_{i=1}^{n} |2x-a_i|) 最小。
令 (2x=a_i) 的中位数即可。即 (x) 为中位数/2。带进去算即可。
C:并不知道正解是啥,我写的随机化
首先写一个差不多对的东西:(f(a,b)) 表示使得 (x=a,y=b) 的 “够小”的步数。注意到 (x,y) 对称,因此 (f(a,b)=f(b,a))。
比赛实况&总结
很快啊,我就秒了AB
但是C卡了好久,根本不会,中途还睡着了
醒来之后就想C和D。我的思维水平很明显还有待提高,这俩题一个都没思路
在最后的20min,我想出来了C题的随机化打法。但赛场上,我 (1e18) 要 (200) 步。赛后我继续加了更多乱搞,才卡进了 (130),最后AC。
Atcoder Regular Contest 121
赛时:AB
赛后:还没补题
题解
A:每个点找 (x,y) 坐标离它最远的两个点,一共 (4n) 种距离,判个重完了取第 (2) 大的即可。
B:傻逼分类讨论
比赛实况&总结
像上次一样,秒了AB,但是CD锤子思路也没有。
还是太菜了qaq
ARC126
题解
A,B 略
C:如果 (k) 大到把每个数都变成 (max),那之后就平均分配就是对的。否则,我们枚举一个 (g),算一下把每个数都变成 (g) 的倍数需要多少代价,如果 (le k),就更新答案。这个计算可以用前缀和+调和级数,(O(nlog n)) 的完成。
D:假设我们知道搞哪些数,那肯定先靠拢,然后就是一个 (k) 的排列,每次交换俩位置,变成 (1,2,3...k) 这样一个问题。
这是个经典问题,我们知道它的答案就是逆序对数。
“靠拢”这里也有个经典结论,就是我们会把它们都靠到中位数的位置(即,前一半往右移,后一半往左移),是最优的。
那我们先枚举一个划分位置,然后左边动 (k/2) 个,右边动 (k-k/2) 个,计算出靠过来的代价,再加上逆序对数,更新答案就行了。
靠过来的代价本质是坐标的和。总的答案可以写成如下形式:
(常数-左边的下标和)+(右边的下标和-常数)+逆序对数
逆序对数=左边逆序对数+右边逆序对数+左到右逆序对数。
左到右逆序对数,我们只需要两边数的种类就能算了。然后左右内部的逆序对数,和下标和合并起来,作为一个权值。
我们关注的是:1. 选了哪些种类的数 2. 权值多少
很容易写出dp:(f(i,S)) 表示: ([1,i]),选了 (S) 集合里的数(任意排列),权值(-下标和+逆序对,因为左边下标带负号)的最小值。(g(i,S)) 表示:([i,n]),选了 (S) 集合里的数(任意排列),权值(下标和+逆序对)的最小值。
(f,g) 都容易转移,枚举分界点合并一下就行了。
复杂度 (O(n 2^k imes k))。( imes k) 也许可以消掉,这不重要。
实况
13:30开始的vp。讲道理我不是很有精神,在机房里转转转了好久。
A题是一个神秘贪心题,虽然不是很难,但是让我调整了好几次策略。好傻逼啊。
B题我傻逼了,一眼看去还以为是二维偏序上升子序列,啪啪啪的打了好久的cdq分治,一看发现我傻逼了,就是个一维的LIS。看来是数据结构做傻了。
C题还挺有意思的,我是先想出枚举 (gcd),再发现 (k) 大的时候均匀分的。发现 (k) 很大均匀分之后,我发现我枚举 (gcd) 复杂度假了,然后推了一小会就发现可以调和。这题做起来还挺舒服的,可能是数论题的缘故吧。
D题我也一开始就想到了策略,但是我傻逼的把逆序对数记到状态里去了,然后复杂度就多了个 (O(k^4)),过不去了。
(O(k^4)=O(inom{k}{2}^2)),就是要枚举两边的逆序对各是多少。
此时已经赛后了。我赛后经过wjy的提醒,稍微改一下就过了。wjy好强啊!!!!1
总结:傻逼次数太多,在简单题上耽误了太多时间。真是 too young, too simple, sometimes naive。