OI 比赛记录

link

昨日 APIO 心态炸没了，不想多说。
然后不知道为啥就睡不着，翻来覆去的直到凌晨。
但还是爬起来打 CF 了。
就，从比较远古的场次里随机抽了一场。

好，打完了。共 7 题，过了 ACDEF。B 神奇的 WA 了。G 写了个类似匈牙利的东西然后 WA 了。
看了眼题解，发现 B 果然简单，G 果然是网络流相关。
记录下简要题解吧。
A：模拟。
B：1 可以随意动而 02 相对顺序不变，将 1 全部移动至第一个 2 前即可。
C：按 $d$ 正负性贪心。
D：先从 $1$ 号点连到所有点，再尽量多构造边。小于等于 $1000$ 的互质的数约有 $3\times 10^5$ 对。
E：$dp_i$ 表示到了 $i$ 的答案，转移就考虑所有 $a_j(j \le i)$ 对 $i$ 位置的贡献。
F：树上启发式合并，维护最大值位置。
G：看起来就像是网络流。二分图，左侧位置右侧字符。贪心，从前向后看填某字符是否可行，Hall 定理判断。之后优化右侧子集枚举即可，复杂度 $O(nA2^A)$，其中 $A$ 为字符集大小。

感觉这场 CF 挺简单。

link

昨日 ARC 交了两遍 A，没过，遂弃赛，感觉不太能思考了（
然后又是睡不着……不过还是起来了。

昨天那 Edu 有点简单，所以今天做点难的（
然后就只会 AB 了。
算了下 Rating，大概略高于 2200。
C 结论猜出来了不会证也没想咋写。感觉亏了。
D 也知道咋做然后没调出来。虽然交的那次是错误做法。
E 看了题然后不会博弈论。
F 比赛时没看，赛后看了，觉得是好题（。

感觉 CF 题解写的挺好。不讲了。
D 再多提一句，手动枚举余数如何来的比较难写。虽然我就是这么写的，不到 2k（。而且要每一种方式都取个 min。
E 就不写了吧（
费了些时间把 F 写了……写了 3k，感觉好长啊。不过很有趣。用线段树维护区间中关键点的直径就行，因为算两点距离有个 $\log $，也是 $\log^2$ 的。

link

好。第一次 Div1 过了 C（
虽然 A 挂了 4 次，C 也挂了一次（

就，A 想了 4 个假结论，心态就有点炸（
然后 B 还好，直接猜对了结论（
10circle 的 C 的做法非常麻烦……写了 0.5h 调了 0.5h（
看了 D，感觉好像在哪里见过，但是没啥思路。

表现分大概 2300（？）不很确定。

似乎 10circle A 的做法和题解不太一样……
A：考虑何时不可行，发现不可行一定是中间的被两侧限制住而无法消去。由左向右第一次变大和由右向左第一次变大之间的可能会被限制住。考虑把被限制住的那一部分提出来，发现消去这些所用的操作和 NOIP2013 积木大赛一样，于是计算一下需要的和可进行的操作数（即最小值的二倍）。
C：当图翻转次数较大，需要的代价大于 $n$ 时，一定要尽量减少这个次数。用最短路算法分别计算出每个点在图已翻转和图未翻转时到 $n$ 号点所需的最小翻转次数和沿边走的次数。然后枚举翻转次数较小时所用的次数（不超过 $\log n$），之后也是类似最短路算出从 $1$ 号点到每个点的距离，然后算最小值就行。

发现 D 的暴力目前在 CF 上最快是 1.731s……可以试试卡过去（
CF 评测机和 10circle 的电脑构造好像完全不一样（，10circle 电脑上最快的方式在 CF 上最慢。
算了，就这 0.1s 真就卡不过去了。不想写指令集。
好吧这能卡过去……10circle 写法太奇怪了而已。
卡过去了就当做完了吧（

E 看了题解，不很想写。F 就根本看不下去题面了。
有时间就补（

link

10circle 菜。B 都挂一次。
DE 都知道怎么做，然后 D 写完了调不对，E 没写完。
直接掉 17 分。

赛后 D 调过了，E 也调过了。做法都是对的。
看了一下 F，发现 F 比 DE 都好写，很快的过了。
感觉 CF 题解非常好，就不写做法了。
算了，考虑到 10circle 的 DE 做法和题解不太一样还是写写。
D：对每个数维护上一个和下一个大于它的数在哪，之后枚举最大值是什么，算左侧和右侧的最大子段和。时空复杂度 $O(n)$。
E：把线段放到平衡树里，然后算出某一个和这个线段有交的线段，递归的搜索并删除。

link

用别人号打的，因为自己号很久没打连 1900 都无所以打不了 Div1（
似乎还能上分（

过了 ABC，B 因为 p[i] 写成 i 挂了一次，C 因为变量重名挂了两次。10circle 菜。
C 刚开始性质还推错了，想了半天错误做法。后来因为不会做而且性质很奇怪，就发现性质错了。浪费了好多时间啊。
最后 20min 感觉做不出来 D 了，遂锁题并尝试 Hack。发现都写的很对，Hack 不掉。
CF 题解很好，所以就不写解法了（

link

好离谱啊，打到一半 Codeforces 炸了。
A 开始时不会，于是看 B。然后过了。
开 CD，全不会。C 感觉了一下，只会 $O(nq)$，D 打个表发现偶数 First，奇数 Second。但奇数不会构造方案……。
之后给 A 猜了个结论，写完代码也没交上去。有点不爽。赛后 A 交上去然后过了。
期望分很低……（明明是因为 CF 炸了（尝试找借口（

赛后补了 C。CF 题解写的都不错。
DE 很快就会补的（

link

赛时看 A。猜了几个写法全挂了，就心态有点炸。然后开 B，一下过了。再细细写 A 才过……
开了 CDEF 全不会……掉大分了。

有时间补 CDEF。

link

许久没做 AtCoder 和 CodeForces 了。（才不是看到有奖金才来打的

感觉很高妙，不过 EF 的难度差距有点大。

评价：
A：简单模拟
B & C：简单贪心
D：性质题
E：简单暴力
F：高妙博弈论（到这就不会了（
G：高妙构造
H：高妙多项式计数

上分了 + 拿了 8 Toncoin（
好像期望 rating 2500 左右……？挺好。

不过赛时挂了两次还是很不舒服的。就是，明明会但就是写错了，然后就差 100pts，大概 20 名。

link

很早就说要打，然后拖到了现在。
Day1 感觉差不多 CF Div1 的 BCD 难度。
过了 T1 和 T2，T3 不会。
T1：考虑把大小关系变成连边，如果不可行就是区间内出现了环。然后就可以 $O(n^2\log n)$ 或 $O(n^2)$ 预处理出所有区间。
T2：从左到右贪心，棚子不够了再向左侧买伞，然后算一下还能把右侧的棚子中的人向左移多少个。