2017 ACM-ICPC Asia Regional Xian Online

Contest Info

date 2017.09.16 12:00-17:00

practice link

Solutions

Replay and Summary

Replay

W 惯例倒序看题,发现 J 前两个操作似乎可持久化 treap 搞一搞,第三个操作不会啊。然后 Z 已经发现 C 是道水题,写了一次之后因为很 sb 地没输出换行符,又不知道为什么着急提交,然后 wa 了一次。W 又发现 B 是一道数学题,交给 Z ,Z 写完也过掉了。E 题感觉是要分析这个有向的完全图的性质,但是输入输出都是一个整数,W 就索性打了一个表,然后发现有点规律,Z 发现可以用到前几天补的第十场多校的某题的一个性质,然后写了也过掉了。

W 上了个厕所回来感觉 G 就是一个 big-small 算法,预处理或者暴力每个点到根的答案就可以了,询问的时候直接讨论一下情况。写完让 D 出了一组数据,很感人地没通过,调了调 bug 之后就 a 掉了。D 开场就在想 A 题,写了一个树分治然后复杂度 O((nlogn + q)*64^2) 的做法,各种 TLE。Z 也卡在了很 sb 的 F 题上。

最后两个小时的时候 Z 终于从跑偏的思路上走了回来,把 F 题过掉了。然后 W 帮着 D 一起出数据测 A 题。发现 TLE 是因为离线存储询问的数组开小了,然后交了一发 wa,W 再仔细看了看发现 D 有一个数组没有清空,改掉就 a 了。最后一小时一直在想 I 题,其他队伍通过的做法(五位偏序 bitset,以及暴力 hash)都想过,但是没敢写,还是要胆子大一些。