THUWC 2025 游记

sangshang · 2025-01-18 22:22:45 · 生活·游记

Day -x

THU 和 PKU 都过审了。我是比较想去 THU，但看了下 THU 的工程题感到有点反感。再三思索还是决定去 THU。~其实是觉得 PKU 的题太难了。~

Day 0

报道有点慢，试机打了个 A+B 走人。

Day 1

开了 T1，感觉很可做，但一时想不到头绪，就先把后面题都开了。但没有什么发现。

回头想 T1，感觉很可 DP，想了一个线段树优化 DP。写完 AC，过了 40min。

开 T2，发现可以离散化后整体二分加暴力容斥。写到一半发现好像复杂度伪了，思索一会后又发现没伪。

交上去发现 45pts TLE。虽说是 5\times 10^5 的 n\log n，但常数极大，还只给一秒，TLE 正常。搓了随机数据，本机跑了 1.2 秒，并且离散化就花了 0.8 秒。修改离散化方式后用时变为 0.3s 预处理和 0.4s 整体二分，共 0.7s。再交一发，发现 53pts TLE。对特殊性质特化处理后 71pts TLE。写了个 fread 快读后 79pts TLE。然后就卡不动常了，最后一个 Subtask 死活过不了。

开 T3。注意到单调性显然，写了个 nq\log n 的做法（用线段树上二分是单 \log，但考虑代码长度和常数，写了树状数组加二分）。拿了 25pts。

开 T4，先写了暴搜，然后发现 20pts 暴力很好拿，写完。

总结 100+79+25+20。

Day 2

工程题爆了，因为 T4 没有看到矩阵转置一直虚空调试，差大众分 200pts，一等是不可能哩。

Day +x

听说 Day1T2 是只有离散化的 n\log n，虽然复杂度没变，但常数要小。