AGM 2023 资格赛没被打爆记

Lynkcat

·

2023-04-23 10:02:06

·

个人记录

今年没输。

https://judge.agm-contest.com/public

还是单人队，比 rk2 多一题。

开场就看到了一个最小割裸题 field，不过感觉还有更简单的签到，所以先不写。

榜上有人过了 game，于是去看，是个简单博弈，于是写完交上去就过了。

写完 game 发现有人过了 montyhall（这么快的？？？

然后看了一下，大概还是想了一会儿发现 n\times C_{n-1} 就是答案。

有点慢了，所以先去写 field 了，拿了一血。

这个时候有好多队过 flips 了，于是去看 flips 了，结果没看见可以翻相同的 wa 了一发，然后因为忘记把调试用的 endl 换回 '\n' 又 t 了一发（蠢猪

又有很多队过了 pirates，于是去看发现是简单数据结构。

然后回来看 drah，简单分析一下就发现有支配对了，然后就做完了。

然后去看 palindrome，发现是 pam 傻逼题。

然后，网站就炸了！！！！

幸亏下了一个小模拟 Construction 还有另一个博弈题 Pawn 的题面。

然后 pawn 是个简单阶梯博弈，但是代码感觉写起来是个答辩，闭幕式的时候跟出题人交流了一下出题人也认为这个题是个 boring 题。

然后等待网站修复。修好了之后延时 1.5h。交了下小模拟一发过了，不知道为啥榜上其他队都交这么多发的，然后交了一下 pawn 发现 wa 了。然后小拍了一下查出来一个错误就过了。

剩下的 3 个题除了 ips 其它都看过了，先开过的人多的 nadloc。看了下题，这不是 sam 板子？？？然后因为看错题 wa 了 5 发，吐了。

然后封榜了，ips 题目又臭又长不想看，貌似是个 ds，感觉最后一小时也写不太完。毕竟另一个题 ysae 也是个 ds。

ysae n,q 只有 5e4 并且 6.5s，暴力做是 n^2 log n 的。但是操作 1 的排序因为题目保证了区间不交或包含，所以可以 n log^2 n set 合并有序段然后再把这个 set 的元素打回原序列上。

写完交上去发现 tle，思考了一下造出了能卡满的数据。然后发现这种数据下需要合并的有序段很少，遍历 set 太慢，不如换成常数次归并排序。

然后改完之后发现飞快，交上去竟然也过了。

然后看了下 ips，我的评价是纯纯的答辩和 boring，不写也罢。

最后凭借 ysae 这个题险胜了下面一火车越南队。虽然今年打的也是答辩，不过比去年牛一点。

去年资格赛冠军 zalau01 怎么今年拉了啊