人类智慧题
A - Train Splitting
https://www.luogu.com.cn/problem/CF1776F
- 神秘构造题，猜 \(k=2\) 一定能构造
- 考虑直接从图上抠一个点下来，与之相关的边全部染成 1，剩下的染成 2
- 发现如果恰好选中了菊花的根就不行；需要找到一个度数不为 \(n-1\) 的点。那完全图怎么办呢，从根上抠一条当颜色 3 即可。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int n, m;
std::cin >> n >> m;
std::vector<int> deg(n + 1);
std::vector<std::pair<int, int> > e(m + 1);
int pos = -1;
for (int i = 1; i <= m; ++i) {
std::cin >> e[i].first >> e[i].second;
++deg[e[i].first], ++deg[e[i].second];
}
for (int i = 1; i <= n; ++i)
if (deg[i] != n - 1) {
pos = i;
break;
}
if (pos != -1) {
std::cout << 2 << '\n';
for (int i = 1; i <= m; ++i)
if (e[i].first == pos || e[i].second == pos)
std::cout << 1 << ' ';
else
std::cout << 2 << ' ';
std::cout << '\n';
}
else {
std::cout << 3 << '\n';
pos = 1;
bool flag = true;
for (int i = 1; i <= m; ++i)
if (e[i].first == pos || e[i].second == pos) {
if (flag)
std::cout << 3 << ' ', flag = false;
else
std::cout << 1 << ' ';
}
else
std::cout << 2 << ' ';
}
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}B - Graph Partition
https://www.luogu.com.cn/problem/AT_agc039_b
- 考虑二分图染色什么时候不行，即有奇环时
- 考虑有多少种颜色时能染奇环，发现都不行，故二分图染色即可判定。
真的只有绿吗？观察样例，猜测答案为图的直径。考虑构造：
枚举每个点并钦定其为唯一一个 \(1\)，然后依次向下染色。显然最后构造出来的是合法的。最大为直径长度 + 1。
也可以从差分约束的角度理解，但无甚必要。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
std::vector<std::vector<int> > g(n + 1), g1(n + 1, std::vector<int> (n + 1, 0x3f3f3f3f));
for (int i = 1; i <= n; ++i) {
g1[i][i] = 0;
for (int j = 1; j <= n; ++j) {
char t;
std::cin >> t;
if (t == '1')
g[i].push_back(j), g1[i][j] = 1;
}
}
std::vector<int> col(n + 1);
std::function<bool(int, int)> DFS = [&](int x, int now) {
col[x] = now;
for (auto i : g[x])
if (!col[i]) {
if (!DFS(i, 3 - now))
return false;
}
else if (col[i] == now)
return false;
return true;
};
if (!DFS(1, 1))
std::cout << -1 << '\n';
else {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
g1[i][j] = std::min(g1[i][j], g1[i][k] + g1[k][j]);
int mx = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
mx = std::max(mx, g1[i][j] + 1);
std::cout << mx << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C - Strange Housing
https://www.luogu.com.cn/problem/CF1470D
- 第一反应是随便找一个生成树然后二分图染色，但是发现有当且仅当奇环时行为不太正确
- 考虑打个补丁，抛弃二分图染色的想法，不断尝试染成黑色，如果染了下一个点会出现黑黑边，那就不染它，对得比较显然。
- 当且仅当不连通时无解。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int n, m;
std::cin >> n >> m;
std::vector<int> f(n + 1);
std::iota(f.begin() + 1, f.end(), 1);
std::function<int(int)> find = [&](int x) {
return x == f[x] ? x : f[x] = find(f[x]);
};
std::vector<std::vector<int> > g(n + 1), g1(n + 1);
int cnt = 0;
for (int x, y; m--; ) {
std::cin >> x >> y;
g1[x].push_back(y), g1[y].push_back(x);
if (find(x) != find(y)) {
f[find(x)] = find(y);
++cnt, g[x].push_back(y), g[y].push_back(x);
}
}
if (cnt != n - 1) {
std::cout << "NO\n";
continue;
}
std::vector<int> col(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
for (auto i : g[x])
if (i != fa) {
bool flag = true;
for (auto j : g1[i])
if (col[j] == 2) {
flag = false;
break;
}
if (flag)
col[i] = 2;
else
col[i] = 1;
DFS(i, x);
}
return;
};
col[1] = 2, DFS(1, -1);
std::vector<int> res;
for (int i = 1; i <= n; ++i)
if (col[i] == 2)
res.push_back(i);
std::cout << "YES\n" << (int)res.size() << '\n';
for (auto i : res)
std::cout << i << ' ';
std::cout << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}D - Defender of Childhood Dreams
https://www.luogu.com.cn/problem/CF1583F
- 考虑把每连续 \(k\) 个点分为一个一级组，每个一级组内全部连 \(1\) 边。显然组内边最长不超过 \(k-1\)。
- 接着把每连续 \(k\) 个一级组分为一个二级组，二级组内空闲边全部涂成颜色 \(2\)。此时 \(a<b\) 的条件就会派上用场——每个一级组的值域是没有交的，一级组之间的边都是同一个朝向。这样就保证由颜色为 \(2\) 的边构成的连链来自不同的一级组，长度最多为 \(k-1\)。
- 依次类推，\(i\) 级组是大小为 \(k^i\) 的团，故 \(i\) 最大为 \(\left\lceil \log_kn\right\rceil\)。
- 按上述流程构造，即可 \(O(n^2)\) 完成。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, k;
std::cin >> n >> k;
using arr = std::vector<int>;
using brr = std::vector<arr>;
brr pos;
for (int i = 1; i <= n; ++i)
pos.push_back({ i });
brr g(n + 1, arr(n + 1));
std::function<void(brr&, int)> calc = [&](brr &pos, int now) {
if ((int)pos.size() == 1) {
std::cout << now << '\n';
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
std::cout << g[i][j] << ' ';
std::cout << '\n';
return;
}
brr p;
++now;
for (int i = 0; i < (int)pos.size(); i += k) {
p.emplace_back();
for (int j = i; j < i + k && j < (int)pos.size(); ++j) {
for (auto a : p.back())
for (auto b : pos[j])
g[a][b] = now;
for (auto b : pos[j])
p.back().push_back(b);
}
}
calc(p, now);
return;
};
calc(pos, 0);
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}E - Edge Split
https://www.luogu.com.cn/problem/CF1726D
- 题意有些许歧义，『红色连通块』其实是指删掉蓝边之后的连通块。考虑到 \(m\le n+2\) 而不是更多，考虑直接分讨。
- 考虑树的情况，对于任意颜色，删一条边就会带来 \(1\) 个连通块的代价，随便染色即可。
考虑基环树的情况，发现如果环上有某个颜色，那么钦定这个颜色第一次删边删的是环边，就会发现第一次删边不会有代价，故强制环上有两种颜色即可。
考虑 \(m=n+1\) 的情况，环可能有下面三种形态：
对于第一、二种，保证两个环上都有两种颜色即可，第三种乍一看有点复杂，其实还是一样的，保证两个环都有两种颜色即可，这样三个环显然都会有两种颜色。站在不饱和度的角度，第三个环其实是无意义的。
由此类推 \(m=n+2\) 的情况，发现只需要在并查集连边时令树边为蓝，反祖边为红即可。发现这样会且仅会在第一组样例的情况出问题：
如果中间的三角形在最后输入就不能得到最优解 怎么处理这个问题呢，我们使用人类智慧，发现这种情况最后三条红边构成三角形，我们只要发现构造出来的解是这样的三角形，由于造成这一点的顺序很苛刻，故一直
random_shuffle输入，继续构造直到合法即可。（？怎么最优解全是这么做的，我还以为只有我一个人会乱搞。）
当不饱和度为 4 的时候就会出现这种结构：
此时按照刚刚的方法就一定构造不出合法解了。这或许也是 \(m\le n+2\) 的原因。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
std::mt19937 rand(0xabcdef);
int T;
for (std::cin >> T; T--; ) {
int n, m;
std::cin >> n >> m;
std::vector<int> res(m + 1);
std::vector<std::tuple<int, int, int> > e(m + 1);
for (int i = 1, x, y; i <= m; ++i) {
std::cin >> x >> y;
e[i] = { x, y, i };
}
auto work = [&](std::vector<std::tuple<int, int, int> > &e) {
std::vector<int> f(n + 1);
std::iota(f.begin() + 1, f.end(), 1);
std::function<int(int)> find = [&](int x) {
return x == f[x] ? x : f[x] = find(f[x]);
};
std::set<int> t;
for (int i = 1; i <= m; ++i) {
auto [x, y, id] = e[i];
if (find(x) == find(y)) {
t.insert(x), t.insert(y);
res[id] = 1;
}
else {
res[id] = 0;
f[find(x)] = find(y);
}
}
return (int)t.size() != 3;
};
for (; !work(e); std::shuffle(e.begin() + 1, e.end(), rand));
for (int i = 1; i <= m; ++i)
std::cout << res[i];
std::cout << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}