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 的数据结构题。