CF1473E
思考了一会发现既有 min 又有 max 很难约束。
发现如果要在路径中选一条边加上,选最小边最有,选一条边减去选最大边最有。
于是把问题转化为在路径中选一条边加选一条边减,求最短路,直接分层图即可。
总结:没见过这种类似寻找更宽松限制的题。
CF2022E2
发现限制等同于每一行的异或值都为常数。
于是对于合法矩阵,必有数组 \(X,Y\) 使得 \(a_{i,j}=X_i \text{xor} Y_j\)
对于给出的 \(a_{i,j}\) 可以看作一条 \(i\) 到 \(j+n\) 边权为 \(a_{i,j}\) 的边。
用带权并查集维护即可。
CF2131H
考虑给互质的之间建边,不合法当且仅当:
-
\(n\) 个独立点。
-
一个菊花加一堆独立点。
-
一个三元环加一堆独立点。
发现我们不关心图的形态,只需要图的度数就可以判断,直接莫反即可。
CF1217F
这个强制在线纯诈骗。
发现操作的 \(x,y\) 只可能有两种,\(x,y\) 或 \(x\mod n+1,y\mod n+1\)。
直接对询问线段树分治即可,由于线段树分治是按顺序处理的,所以可以很容易维护 lstans