去年有个 CSP-S 2021 Unofficial 的题解但是那玩意咕掉了（主要是不想写最后一题，但是准备省选的时候会补上毕竟 ZJ 卷怪一堆懂得都懂），不过今年保证在 NOIP2022 前会写完这份题解的（所以这个保证会不会实现呢？）。
Author: Plozia, written on 2022/10/30。
目前 T4 还没有更新。
T1 假期计划(holiday)
首先可以预处理每个点在走了 \(k+1\) 步之后能够到哪些点，\(n\) 遍 bfs 即可，这样我们就知道了每个点后面或者前面能跟哪些点（前面也可以是因为无向图）。
做法就是暴力 bfs，队列里面存一下这一路过来哪些点走过了，然后可以过 \(O(n^4)\) 能过的点以及 \(k\le0\) 的点，然后看起来就没有什么算法可以优化了。
但实际上有个叫 meet in middle 的相对冷门的玩意，这玩意就是处理前半段处理后半段然后拼接，考虑到这题上，因为题中要求 4 个不同景点 \(A,B,C,D\)，考虑枚举 \(B,C\)，此时问题就变成了 \(1\to A\to B,C\to D\to 1\) 然后拼接，对所有点 \(x\) 预处理 \(p\) 个 \(y\)，满足 \(x\to y,y\to 1\) 成立并且 \(a_x+a_y\) 为前 \(p\) 大，这样可以枚举 \(B,C\) 然后暴力合并前 \(p\) 大即可，可以证明 \(p\) 最小值为 3，然后就过了。
注意点就是 \(B\to C\) 需要成立，然后 \(A,B,C,D\) 不重合。
好像有人在预处理的时候先跑了 \(n\) 遍 bfs 求两两之间最短路，但是这个做法要判连通性不然会寄，直接存下能到哪些点不是更舒服吗，连通性也不用判（
T2 策略游戏(game)
这玩意赛时我按照两个人区间内只有正数，只有负数，正负都有大力分类讨论九种情况，然后接上含有 0 的情况大概分讨了 18 种，虽然烦但是保证对，毕竟合并情况之后谁还知道对不对呢（
大众写法是只考虑第一个人的正负情况，第一个人选正的后面这人必选最小值，第一个人选负的后面这人必选最大值，第一个人选 0 后面这人咋选也没用，实际情况中可以将 0 归到正数的情况。
因此考虑求出第一个人正数的区间最大最小值，负数的区间最大最小值，第二个人的区间最值，然后就只有 4 种情况了（第一个人选正最大正最小负最大负最小），取个最大值即可。
T3 星战(galaxy)
题意也太长了，简化一下：给出 \(n\) 点 \(m\) 边有向图，初始所有边存在，有四种操作，1,3 操作是删除一条存在的边或者是恢复一条被删除的边，2,4 操作是将一个点的所有入边全部删除或者是将所有入边恢复，问每次操作后所有点的出度是否为 1（实际上题中还有一个条件是所有点自选路径往前走最后一定能走到一个环，但是出度均为 1 是这玩意的充要条件）。
为什么 CSP-S2021 T3，NOIP2021 T3，CSP-S2022 T3 全是人类智慧啊（
这道题人类智慧的离谱，首先 1,3 操作是能够 \(O(1)\) 的关键是 2,4 怎么办如果暴力模拟实现的好可以做到 60pts，但是如何做到可接受复杂度。
这里有两个选择，一个是 hash 乱搞另一个是随机化权值然后异或乱搞，两者本质差不多，这里讲讲第二种做法。
考虑对每一个点随机一个权值 \(a_i\)（最好是用 mt19937_64 开到 unsigned long long 范围内），这样每个点出度为 1 就变成了如下两个要求：一是总边数为 \(n\)，二是所有边的起点权值异或和为 \(\oplus_{i=1}^na_i\)。
这样 2,4 操作就好维护了，因为题中保证删边加边操作合法，所以我们只需要知道一个点的所有入边的起点异或和即可，然后因为异或有结合律所以可以做到 \(O(1)\)，至于维护边数显然可以 \(O(1)\)。
T4 数据传输(transmit)
咕咕咕~
标签：题解,T3,然后,Unofficial,异或,玩意,CSP From： https://www.cnblogs.com/Plozia/p/16841974.html