分析 不难发现，对于一个城堡，早驻守不如晚驻守。因为驻守早了完全没有额外收益，驻守晚了也没有额外代价。所以对于每个城堡 \(x\)，记录 \(d(x)\) 为 \(x\) 的最晚可控制时间。也就是它必须在哪一个城堡被攻下之前，必须派兵驻守。特别的，如果某个城堡是独立的，令这个时间为它自身的编号。 设 \(f(i,j)\) 为已经攻下了前 \(i\) 个城堡，攻打第 \(i\) 个城堡之后还

写一下近期写的简单二分图题目的题解。 luogu3967 匹配 分析 \(TJOI\) 板子题 \(\times 1\)。 找出所有完美匹配的交集，意思是无论任何完美匹配都包含这些边，反过来，如果没有这些边中任意一边，都不存在完美匹配。 由于数据范围小，直接用 DFS 版的 \(KM\) 算法求出带权最大匹配。然后枚举每一条匹配边， 把它的边权置为 \(0\)，表示删去它。如果此时求出

分析 \[ \gcd_{i,j \in [1,n] \text{ and } i< j} \{ \operatorname{lcm}(a_i,a_j) \} \] \[ \gcd_{i,j \in [1,n] \text{ and } i < j} \{ \frac{a_i \cdot a_j}{\gcd(a_i,a_j)} \} \] 两两元素的最大公约数就是

CF1699. A. The Third Three Number Problem 分析 首先判断无解。 异或运算可以看作二进制「不进位加法」，而在二进制加法中，第一位也不会存在进位，所以 \((a \oplus b) + (b \oplus c) + (a \oplus c)\) 与 $(a+b) + (b + c) + (a + c) = 2(a+b+c) $ 奇偶性相同。所以

分析 小清新构造题。 不难发现，对于一个有序序列，假设是 \[ [1,2,3,4,5,6] \] 那么 \[ \sum_{i=1}^3 | a_{2i} - a_{2i-1} | = | \sum_{i=1}^3 a_{2i} - a_{2i-1} | = 3 \] 把 \(2\) 提前， \[ [2,1,3,4,5,6] \] 发现得到的结果是 \(2\)。 把 \(3\)

分析 不是那么显然的 DP。 对于每一次连抽，只会累计开始连抽的那张卡的欧气值，损失之后 \(c-1\) 张卡的欧气值。而单抽则不会损失欧气值。题目要求最大化欧气值，那么就是要尽量减小连抽损失的欧气值。 形式化地，对于一次在 \(i\) 位置开始的连抽，得到 \(a_i\)，损失 \(\sum_{j=i+1}^{i+c-1} a_i\) 的欧气。对于 \(j\) 位置的单抽，只会得到

定义 一个网络 \(G= (V,E)\) 是一张有向图，对于每条有向边 \((x \rightarrow y)\) 都有一个权值 \(c(x,y)\)，称之为这条边的容量。另外，存在特殊节点 \(S\)，称为源点；\(T\)，称为汇点。 设函数 \(f(x,y)\)，其定义域为 \(x,y \in V\)，满足 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 \(f(x

分析 没错还是构造…… 明确某个数异或另一个数偶数次，结果仍然是它本身。 再明确所有的数字都是正整数，不能用 \(0\)。 任意两个叶子之间的路径权值的异或和为 \(0\)，如果它们之间的距离是偶数的话，那么都填同一个数就好了。最小数量为 \(1\)。 如果存在某两个叶子之间的距离不为偶数，如下图 \(1\) 和 \(5\)。 钦定 \((1 \rightarrow 3)\) 的

分析 构造题使人神清气爽。 先判断无解的情况，如果 \(n \nmid \sum_{i=1}^n a_i\)，那么显然无解。 做构造题不能只局限于样例给出的方法，因为它们一般都是特殊情况，而我们的目标是使用一般方法进行构造。 注意到无论怎么操作，元素的总和是不变的，我们可以尝试把所有值移动到一个元素上，然后因为 \(n \nmid \sum_{i=1}^n a_i\)，所以一定能够用

分析 等价于判断 \(n\) 能否写成如下形式 \[ n = a^x + by \] 多乘个 \(a\) 或者多加个 \(b\) 仍然形如这样。 这就相当于 \[ n \equiv a^x \quad (\bmod b) \] 因为 \(y\) 是个未知数，可以利用这个转化同余方程。或者说，\(x \equiv y \quad (\bmod b) \iff b \mid (x-y