CF1325F Ehab’s Last Theorem
题意
给定一个 n n n 个点， m m m 条边的无向图。让你找出一个至少有 ⌈ n ⌉ \lceil\sqrt n\rceil ⌈n ⌉ 个点的环 或 正好有 ⌈ n ⌉ \lceil\sqrt n\rceil ⌈n ⌉ 个点的独立集。
解析
-
构造环
考虑将原图放到 DFS 树上考虑，在 DFS 树上记录每个点的深度 dep \text{dep} dep 值，如果一条非树边连接的两个点 u ， v u，v u，v，使得 d e p u − d e p v + 1 ≥ ⌈ n ⌉ dep_u-dep_v+1\ge \lceil\sqrt n\rceil depu−depv+1≥⌈n ⌉，则我们在原图找到了一个至少有 ⌈ n ⌉ \lceil\sqrt n\rceil ⌈n ⌉ 个点的环。
结论显而易见嘛，在树边上 u，v 这条链上至少有 d e p u − d e p v + 1 dep_u-dep_v+1 depu−depv+1 个节点，又因为有返祖边就形成了环。
-
构造独立集
如果用上述方法找不到满足条件的环，我们就只能考虑构造独立集，根据第一问的结论，运用反证法，我们就可以得到结论：
如果图上不存在一个至少有 ⌈ n ⌉ \lceil\sqrt n\rceil ⌈n ⌉ 个点的环，那么最多存在一个至少有 ⌈ n ⌉ − 2 \lceil\sqrt n\rceil-2 ⌈n ⌉−2 个点的环，即图上每个节点至多只存在 ⌈ n ⌉ − 3 \lceil\sqrt n\rceil-3 ⌈n ⌉−3 条返祖边。
证明很简单，假设有节点存在 ⌈ n ⌉ − 1 \lceil\sqrt n\rceil-1 ⌈n ⌉−1 条返祖边，那么必然有一条返祖边所连接的点与自己就会形成一个至少有 ⌈ n ⌉ \lceil\sqrt n\rceil ⌈n ⌉ 个点的环，矛盾。
接下来我们就可以构造独立集了，每次我们可以选择一个节点放入独立集，并将与该点相连接的点删除，重复此操作 ⌈ n ⌉ \lceil\sqrt n\rceil ⌈n ⌉ 次，我们就可以得到一个 ⌈ n ⌉ \lceil\sqrt n\rceil ⌈n ⌉ 个点的独立集了。
这时候可能会有人有疑惑：为什么你能保证一定可以重复 ⌈ n ⌉ \lceil\sqrt n\rceil ⌈n ⌉ 此操作呢？
根据上面的结论，一个节点最多只有 ⌈ n ⌉ − 3 \lceil\sqrt n\rceil-3 ⌈n ⌉−3 条返祖边，再算上该节点的父亲和自己本身，每次操作最多只会删除 ⌈ n ⌉ − 1 \lceil\sqrt n\rceil-1 ⌈n ⌉−1 个节点，所以前 ⌈ n ⌉ − 1 \lceil\sqrt n\rceil-1 ⌈n ⌉−1 次操作最多只会删除 ( ⌈ n ⌉ − 1 ) × ( ⌈ n ⌉ − 1 ) ≤ n (\lceil\sqrt n\rceil-1)\times(\lceil\sqrt n\rceil-1)\le n (⌈n ⌉−1)×(⌈n ⌉−1)≤n 各节点，所以一定删不完,所以最后还能再取一次，所以能取 ⌈ n ⌉ \lceil\sqrt n\rceil ⌈n ⌉ 次。
做到这里整道题目就做完了，总结一下，能构造出第二问的充分条件就是构造不出第一问。
最后附上代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n, m, k;
int dep[maxn];
bool vis[maxn];
vector<int> e[maxn], ans, st;
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
st.push_back(u);
for (auto v: e[u]) {
if (!dep[v]) dfs(v, u);
if (dep[u] - dep[v] + 1 >= k) {
cout << 2 << '\n' << dep[u] - dep[v] + 1 << '\n';
for (int i = dep[v]; i <= dep[u]; ++i) cout << st[i - 1] << ' ';
exit(0);
}
}
if (!vis[u]) {
ans.push_back(u);
for (auto v: e[u]) vis[v] = 1;
}
st.pop_back();
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
k = sqrt(n - 1) + 1;
for (int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
cout << 1 << '\n';
for (int i = 1; i <= k; ++i) cout << ans[i - 1] << ' ';
}
CF1476C Longest Simple Cycle
思路
一眼题，考虑 dp 做法
很容易看出，如果是成环的话有两种情况
-
与上一条链连接的起点，终点所连节点重合（ a i = b i a_i=b_i ai=bi），那么前一个的最大值要舍去，环长度为 f i = a i + 1 f_i=a_i + 1 fi=ai+1。
-
起点，终点不重合（ a i ≠ b i a_i\ne b_i ai=bi），那么可以对前一条链组成的环进行选择。容易得到 f i = max ( f i − 1 + a i + 1 − ∣ b i − c i ∣ , a i + 1 + ∣ b i − c i ∣ ) f_i=\max(f_{i - 1} + a_i + 1 - \left|b_i - c_i\right|,a_i + 1 + \left|b_i - c_i\right|) fi=max(fi−1+ai+1−∣bi−ci∣,ai+1+∣bi−ci∣)。
代码
#include <bits/stdc++.h>
#define int long long
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const int maxn = 1e5 + 10;
int n;
int a[maxn], b[maxn], c[maxn];
int f[maxn];
inline void solve() {
cin >> n;
int ans = 0;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i];
for (int i = 1; i <= n; ++i) cin >> c[i];
f[1] = 1;
for (int i = 2; i <= n; ++i) {
if (b[i] == c[i]) f[i] = (a[i] - 1) + 2;
else f[i] = max(f[i - 1] + a[i] - 1 + 2 - abs(b[i] - c[i]), a[i] - 1 + 2 + abs(b[i] - c[i]));
ans = max(ans, f[i]);
}
cout << ans << '\n';
}
signed main() {
ios;
int t;
cin >> t;
while (t--) solve();
}