质量不错。
为什么湖北会有这么 hard 的省选啊 /fn。
D1T1 \(\color{Gold}\bigstar\)
第一题就不会是我没想到的。
考虑一下简单情况，一条链咋做，每次操作相当于把一个空隙的大小减小 \(2\)，因此可以进行一个 dp。
具体咋 dp，先咕。
然后考虑只有一个环咋做，如果是偶环，那么肯定是一直操作，最后所有点都到一条边的两侧，黑白染色即可。
同理，所有的二分图都可以这样，除非是一条链。
考虑奇环咋做，首先答案的上界是黑点乘白点，有一个策略，就是把每一个点黑白染色，然后进行一次操作，把白棋移动到白点，黑棋移动到黑点，这样一直操作下去就可以达到答案上界了。
咋染色呢，就是隔一个的点拿出来，得到两个环，分别黑白染色，其中一个环长是奇数，也就是有一个点左右点颜色相同，这个点钦定为操作的点即可，因此达到答案上界。
非二分图，把所有点拉到奇环上即可，直接达到上界。
D1T2 \(\color{blue}\bigstar\)
看数据范围，感觉就是 \(O(n)\) 算法。
我们把一个方案在前缀选最长的地方统计，那么也就是说 \(S_{l+1}\ne S_r\)，不然左边就可以增加。
一个简单的想法是跑出前后缀的 kmp 树，然后在这个上面进行查询，但是复杂度怎么想都至少是 \(O(n\sum)\)。
首先把前缀或者后缀包含 \(T\) 的情况去掉，那么也就是前缀有一部分，后缀有一部分，容易发现前缀 \([l,r]\) 的这个部分满足 \(S_{r+1}\ne T_{r-l+1}\)，换句话说，\([l,r]\) 一定满足是 \(S_{[l,n]}\) 与 \(T\) 的最长公共前缀。
跑一个 Z 函数，也就是前缀数量变成了 \(O(n)\)。
放到后缀的 kmp 树上，去个重就可以简单查询了。
为啥被 hack 了？？？
D1T3 \(\color{blue}\bigstar\)
妙题。
首先注意到 \(a+b+c\) 三维和相等，所以只需要关注 \(a,b\) 两维即可，但是这两维前面乘的系数之和需要是 \(1\)。
如果选一条向量，那么只能表示一个点 \((a,b)\)，两条向量，就可以表示出 \((a_1,b_1)\to (a_2,b_2)\) 这条线段，三条线段就是一个三角形，同理，相当于是一个凸包，有解需要目标点在这个凸包里面。
否则三角剖分就可以证明，一个方案有用的点只有 \(3\) 个。
但是树上找 \(3\) 个点还是非常困难，我们试试调整。
平面上有 \(4\) 个点，可以得到 \(4\) 个三角形，注意到一个点只要在这个四边形内部，那么肯定有两个三角形包含这个点。
因此对于一种方案，可以在中间选一个点，看看是否可以替换掉原来的点。
这样可以发现，答案一定在一条链上。
点分一下，一条链有两个点，一条链有一个。
两个点的上面，肯定贪心选角度大的，线段树瞎维护一下就行。
复杂度 \(O(n\log^2 n)\)，好像可以双指针做到单 \(\log\)，懒了。
D2T1 \(\color{green}\bigstar\)
真签到题在 Day 2。
查询一个竞赛图最大流，变成一个最小割一下。
分割成两个点集 \(S,T\)，把 \(S\to T\) 的边全部断掉。
容易发现就是 \(S\) 中点出度之和减去 \(S\) 内部边数。
排序，然后枚举即可，复杂度 \(O(nm)\)。
可以数据结构维护吗？？
哦，好像可以，线段树维护一下前缀最小值，把一些点扔到前面就行，然后在线段树上删掉，\(O(m\log n+n^2)\)。
D2T2 \(\color{green}\bigstar\)
考虑一下策略，先考虑链，如果在链的一端，那么必须向前，然后把这条边清空，不然可以退回来就似了。
因此如果是一个奇环就直接先手胜利（环上没有 \(0\)）。
如果在链的中间，那么发现只要两边有一遍的链长是奇数就胜，因此一个长度若干的链的答案也可以算。
然后考虑一个偶环，上面没有 \(0\) 咋做。
相当于如果到了一个左右都是 \(1\) 的局面就必死，因为清空一条边对方就有一个奇数的链了。
左右是 \(0\),左右是 \(1\)，推下去发现左右都是 \(\min\) 必死。
因此可以所有值减去 \(\min\) 算链的答案。
线段树简单维护 \(O(n\log n)\)。
明明可以做区间加减的。
D2T3 \(\color{red}\bigstar\)
屁都不会，通过 \(0\)。
《zky \(26\) pts》。
标签：线段,前缀,color,题解,可以,bigstar,一个,2023,湖北省 From： https://www.cnblogs.com/houzhiyuan/p/17677889.html