[[2023年11月10日总结]] 这一天的题目。
[USACO22OPEN] Alchemy B
link。
二分答案。倒着建图，是一个 dag。验证的方法感觉类似 [NOIP2020] 排水系统。但是要注意中间判断一下往下传的多余量有没有超过总金属数。不然容易指数级增长爆掉。这道题写的时候降智了，还搞了一遍拓扑排序，其实倒着来就行。 #二分答案
[USACO22OPEN] Visits S
link。
会发现是一个内向基环树（应该是叫这个名字），发现只要删去环上面那个最小的边就行。可以边反过来拓扑排序找环。我这里直接使用的是最小（大）生成树的方式。
[USACO22OPEN] COW Operations S
link。
把 \('C','O','W'\) 分别映射到 \(1, 2, 3\)，发现两种操作异或和不变，并且可以发现可以操作交换相邻两个字符。可以证明最后一定能只剩下一个字符或者空。所以求得区间异或和是否为 \(1\) 即可。
[USACO22OPEN] Hoof and Brain P
link。
很有趣的一道题。首先把走不到环中的点去掉，拓扑排序即可。然后易证两个在剩余图上能够遇到一定是在两个的共同必经点，而且两个棋子如果有共同的必经点一定能碰到。朴素的方法就是对于一个起始点，枚举点删掉，如果这个起点不能到一个环里了，那么这个点就一定是必经点。用 bitset 存一下，询问的时候与一下就行。考虑正解。会发现所有的必经关系可以抽象成几条链，参考 luogu 上的第一篇题解。因此在同一个必经关系中一定有共同必经的点。然后参考洛谷上第三篇题解，发现对于一个缩点的图，出度为 \(1\) 的点一定能和其指向的点连到一个关系图中，使用启发式合并。如果合并后指向这一坨的点有出度变成1了，那就代表这个点一定必经这个缩的点，而进入这个缩的点后一定又必经一些点，所以也要加入。这样最后剩下的图中每个点的出度一定大于 1 （包括自环）。可以证明这样的图中一定没有新的必经点了，因此所有的都被合并了。查询的时候并查集查询即可。复杂度：\(O(m\log^2{n}+q)\)。参考代码：
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int n, m;
int Q;
int u, v;
int fa[N]; //并查集
void ini() {
for (int i = 1; i <= n; ++i) fa[i] = i;
}
int getfa(int v) {
return v == fa[v] ? v : fa[v] = getfa(fa[v]);
}
set<int> g[N], r[N]; //用set维护图，方便去除重边，可以使用更高效的方法。
//g: 正向图，r: 反向边的图
int main() {
scanf("%d%d", &n, &m);
ini();
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &u, &v);
g[u].emplace(v);
r[v].emplace(u);
}
queue<int> q; //队列，拓扑排序和后面合并可以用一个队列，节省一点
for (int i = 1; i <= n; ++i) {
if (g[i].size() == 0) q.emplace(i);
}
while (!q.empty()) { //去除走不到环里的点
int u = q.front();
q.pop();
fa[u] = 0;
for (auto i : r[u]) {
g[i].erase(u);
if (!g[i].size()) q.emplace(i);
}
}
for (int i = 1; i <= n; ++i) { //将出度为1的点加入队列
if (g[i].size() == 1) q.emplace(i);
}
while (!q.empty()) { //合并所有在一个必经关系中的点
int u = q.front();
q.pop();
int v = *g[u].begin();
u = getfa(u), v = getfa(v);
if (u == v) continue;
if (r[u].size() > r[v].size()) swap(u, v);//启发式合并
for (auto i : r[u]) { //这里只用合并入的边，因为出的边更改后也会找到根继续合并入的边
g[i].erase(u);
g[i].emplace(v);
r[v].emplace(i);
if (g[i].size() == 1) q.emplace(i); //出度为1加入队列
}
fa[u] = v;
}
scanf("%d", &Q);
while (Q--) {
scanf("%d%d", &u, &v);
u = getfa(u), v = getfa(v);
if (!u || !v || u == v) { //询问，如果有点走不到环或在一个关系中
标签：必经,记录,int,拓扑,合并,USACO,作题,排序,出度
From： https://www.cnblogs.com/huasushis/p/17825327.html