真身败名裂了。 A #include<bits/stdc++.h> using namespace std; #define ll long long #define uint unsigned long long #define PII pair<int,int> #define MP make_pair #define …

$\text{Solution}$ 一生之敌。 中间的操作既涉及变量间的赋值，又有常量赋值。错误的做法是把这两种操作分开处理，把常量赋值特殊化，然后通过赋值关系推导别的变量再得出矛盾。 错误的原因是这个做法难以实现。 最大的瓶颈在于常量赋值。笔者在场上不由自主地怀疑这种操作会改变初始值，进而误入歧途。 理清逻辑，我们应该是先求出每个变量的最终值，然…

二分图判定 没啥技巧，最难的是把图论模型建起来。 luogu1330 封锁阳光大学 相邻两个点只能封锁一个，但是要覆盖所有边。对应到二分图上就是左部右部点的数量取较小值。 图可能不连通，取的是每一张二分图的左右边的较小值。 #include<bits/stdc++.h> using namespace std; #define int …

欧拉路径 定义 从一个点出发，不重不漏地经过图中每一条边的一条路径，允许重复经过节点。 无向图 首先必须是连通图，其次是两种情况。 所有点的度数是偶数。 恰好存在两个点的度数是奇数。 有向图 要求连通。 所有点的入度等于出度。 恰好存在一个节点入度比出度多 $1$，一个节点入度比出度少 $1$。 欧拉回路 定义 起点和终点是一个点的欧拉路径。 无向…

Hankson的趣味题 从质因子的角度考虑。 把 $a,b,c,d$ 都分解了，对于一个质因子 $p_i$，题目给出的条件等价于$$\min \Big( e_{p_i} (x) ,e_{p_i} (a)\Big) =e_{p_i}(c)$$ $$\max \Big( e_{p_i}(x),e_{p_i}(b) \Big) = e_{p_i}(d)$…

图论这一块内容比较多，而且题目涉及的 Trick 也很多，因此分若干篇。 本文略去所有算法本身性质的证明过程。 最短路 Dijkstra和SPFA $\text{Dijkstra}$ 算法基于一个重要的性质：全局最小值不可能再被任何边更新。这样，在边权为非负数的最短路问题中显然满足，在存在负边时不满足。同时，保证了最多从每个节点处扩展 $1$ 次，…

突破口永远在环上。 找环是常用操作，但是并没有一个合适的模板。 笔者在写这篇文章之前就做过一些基环树的简单题，但是每一次写的找环都不尽相同。仅仅用dfs的回溯模拟一个栈，显然是不够公式化的，且容易出 bug，因此我们需要确定一种可靠的写法。 关于dfn的那套理论再合适不过了。 当然这玩意只能找一个环。 int cnt, num, fa[N]…