2023NOIP A层联测30 总结
题目
T1 草莓列车
\(n\leq 10^5,m\leq 10^7\)
赛时思路
一开始看错 \(m\) 数据范围，以为 \(O(m\log m)\) 可以过，后来发现问题以后，集中在考虑线段树之类的 \(\log\) 级别的算法维护序列，或者线段区间，一直没有想过 ST 表相关数据结构，于是最后只有 60。
赛后思路
有两种写法：
1.分块维护区间，\(O(1)\) 修改 \(O(\sqrt n)\) 查询，时间复杂度 \(O(n\sqrt n)\)。
2.考虑逆序 ST 表，每一位的答案时 \(ST[i][0]\)，每次修改修改 \(ST[l][k]\) 和 \(ST[r-2^k+1][k]\)。最后用类似于 \(ST\) 表维护的方式向下更新，时间复杂度 \(O(n\log n)\)。
T2 草莓路径
有一张 \(n\) 个点 \(m\) 条边的无向联通图（可能存在重边、自环）。边上有权值 \(w\)。定义一条路径的草莓值为这条路径的所有边上的边权的异或和。
求最大的草莓值。
\(n,m\leq 10^5\)，\(w\leq 10^{18}\)
赛时思路
没有考虑到树，只发现路中的路径经过一次最优，然后写暴力。
赛后思路
考虑建出一棵树，那么两个点间的路径可以由树上的路径异或若干个环上的路径得出。
把环上的路径丢进线性基，设线性基集合为 \(B\)，树上点到根路径异或和集合为 \(A\)，则答案为在 \(A\) 中选两个数，在 \(B\) 中选若干数，使答案最大即可。
有式子 \(\max(s_x\oplus s_y \oplus D)\)。
等价于 \(\max(\max(s_x\oplus D_x)\oplus\min(s_y\oplus D_y))\)。
其中 \(D_x\oplus D_y=D\)。
这样子使 \(\max(s_x\oplus D_x)\) 中前置 \(1\) 数量最多，使 \(\min(s_y\oplus D_y)\) 中前置 \(0\) 更多，于是有最大值。
T3 草莓城市
\(H,W \leq 10^9,k\leq 200\)。
赛时思路
先二分斜边长度。
考虑一个点对应 4 个直角三角形，这是一个 4-SAT 问题，拆分，将 4 个大直角三角形拆成 4 个小的直角三角形，这样有在左上右下选一个三角形，在右上左下选一个三角形，转换成了 2-SAT 问题，最后暴力枚举判断三角形是否相交即可（然而没想出来）。
赛后思路
所有点坐标乘以 2，可变为整数点，将坐标乘以 2，只考虑整数部分，然后暴力枚举三角形 3 边求交点即可。
时间复杂度 \(O(k^2\log V+k \log V)\)，其中由于枚举线段，所以 \(k^2\log V\) 带有较大常数，约在 \(16\) 左右。
还在调……
T4 草莓之歌
\(n \leq 10^6\)
赛时思路
一开始看错题，后来及时红色部分一定要都在金色部分左边时，就不会了，后面暴力思路只有 \(O(n^n)\)，最低档部分分也没有。
赛后思路
还没开始看……
赛时
一开始看错 T1，分配时间：T1:30,T2:50,T3:50,T4:30。
后来发现 T1 之严重错误后，先看了 T3，T3 很快想到正解，但一直苦于两条线段的相交的判断写不出来，后来接着看 T1。
已开始 1h30min。
T1 还是一直在想 \(\log\) 级别的常用算法维护，于是后面去看 T4 然后 T4 发现问题后暴力也写不出来。
跑完操准备先写 T2，T2 部分分写完以后写了 T1 的 60pts，后面剩 80min 准备写 T3，结果 T3 一直写不出来，中间的判断极其复杂，然后没调出来。
赛后
就 T1 60……
反思
1.T1 的思路没有打开，一直在平常经常用的维护算法上下功夫，反而忘记了许多更改或查询是 \(O(1)\) 的算法。
2.没有检查 T2，T2 的思路可能出现问题，但没有意识到。
3.T1 没写出了就有点慌张，导致后面的时间分配全部给了 T1 一道题，连最有把握的 T3 也没写出来。
1.要及时调整时间分配特别是有题目 FAKE 的情况，不要蛮干。
2.想题目的思路要发散，不要集中在一两个普通的算法。
3.数据结构都要多练，多熟悉一下，不然容易在赛场上想不出来。
计划
1.每周加入 Ynoi 的数据结构题。