核心：
- 组合问题的常见分类：
现在我们假设我们要对一个组合对象 \(U\) 进行考虑并分析一些关于组合的问题。
-
判定： 判断 \(U\) 中是否有满足条件 \(p\) 的集合或元素。这是组合问题中最基础的问题。
-
构造： 找到 \(U\) 中一个满足条件 \(p\) 的集合或元素。此类问题基于判定问题，但是灵活性更高，需要一定的思维（有时候可能会很难）。
-
计数： 统计 \(U\) 中满足条件 \(p\) 的集合或元素数量。
-
最优化： 给 \(U\) 中每一个集合或元素定义一个价值，问 \(U\) 中满足条件 \(p\) 的集合或元素的价值最大 / 最小的价值。
- 组合问题的常见技巧：
-
调整法： 通过证明一个情况可以通过调整到另一个情况使得答案不劣，将问题转化为特殊情况求解。本技巧常用于最优化问题中。
-
局部观察法： 抓住问题判定的本质，从局部入手观察问题的情况，常常和调整法结合。
-
构造双射法： 通过一个双射对应到另一个问题上，简化或明晰问题。
- 计数中的映射问题：
计数中常常会遇到一类操作问题，即一个初始状态 \(U_s\) 可以通过一系列的操作映射 \(f\) 到最终状态 \(U_t\)。问法常有两个：给定 \(U_s, f\)，问有多少种不同的 \(U_0\)；给定 \(U_t, f\)，问有多少种 不同的 \(U_s\)。
解决这类问题时常常会有一个问题：重复。这个时候可能要用到容斥之类的计数技巧。还可能遇到 \(f\) 难以进行判断的问题，此时可以寻找中介以及判断的充要条件。
练习：
CF442C Artem and Array
注意到一次操作只与相邻的三个元素相关，于是对这个 \(\rm Pattern\) 进行观察。可以关注到一种特殊情况：\(a_{i - 1} \ge a_i \le a_{i + 1}\)，即一个下凸的部分，猜想不论如何可以先删 \(a_i\)，否则一定可以调整到该情况使答案不劣。于是最后删完之后会变成一个"倒 \(V\)"的形式。考虑最后部分的答案如何计算，显然最大的两个已经去不到了，于是就是除了两边的数剩下的 \(n - 4\) 个数了。
qwq
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int n, a[N], stk[N], top, ans;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
while(top >= 1 && stk[top] <= stk[top - 1] && a[i] >= stk[top]) ans += min(a[i], stk[top - 1]), top--;
stk[++top] = a[i];
}
sort(stk + 1, stk + top + 1);
for(int i = top - 2; i >= 0; i--) ans += stk[i];
cout << ans;
return 0;
}
CF1239F Swiper, no swiping!
毒瘤分讨题。
- Case 1:
假如有 \(0\) 度点，留着即可。
- Case 2:
假如有两个点 \(1\) 度点相连，即 \(1 - 1\)，留着即可。
- Case 3:
假如有几个 \(2\) 度点组成一个 不可约环，即是一个简单环且没有包含其他的环，这显然是合法的。如何寻找呢？注意到这是一张无向图，于是有一个套路：考虑原图的一个 \(\rm DFS\) 生成树，容易发现该图中只存在树边和返祖边。于是找到一条两端深度差最小的一条返祖边，然后暴力跳即可。
- Case 4:
假如上面的情况都不满足而且 \(1\) 度点个数 \(\ge 2\)，我们考虑一个 \(1 - 2 - ... - 2 - 1\) 这种情况。显然这是符合条件的，这类情况直接从任意 \(1\) 开始 \(\rm BFS\) 并记录路径上的点即可。
- Case 5:
假如上面一个都不满足，显然存在至少一个 \(1\) 度点，而且剩下的 \(2\) 度点会组成一个森林。找到两颗不同的树，直接将叶子和对应的 \(\rm LCA\) 都选上即可。用反证法可以证明这种情况一定存在。那为啥会无解呢？因为可能构造出来的东西是整张图。
qwq
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10, INF = 1e18;
struct edge{
int v, next;
}edges[N << 1];
int head[N], idx = 1;
int n, m, deg[N], ans[N], tot, dep[N], cirsiz = INF, fa[N], vis[N], leafvec[N], lsiz, tag[N], tag2[N];
void add_edge(int u, int v){
edges[++idx] = {v, head[u]};
head[u] = idx;
}
void clrall(){
tot = lsiz = 0; idx = 1; cirsiz = INF;
for(int i = 1; i <= n; i++) deg[i] = head[i] = fa[i] = dep[i] = vis[i] = tag[i] = tag2[i] = 0;
}
void clr(){
for(int i = 1; i <= n; i++) dep[i] = vis[i] = fa[i] = 0;
}
void getout(){
clr();
if(tot == n) cout << "No" << "\n";
else{
cout << "Yes" << "\n" << n - tot << "\n";
for(int i = 1; i <= tot; i++) vis[ans[i]] = 1;
for(int i = 1; i <= n; i++) if(!vis[i]) cout << i << " ";
cout << "\n";
}
}
bool Case1(){
for(int i = 1; i <= n; i++) if(!deg[i]){ans[++tot] = i, getout(); return true;}
return false;
}
bool Case2(){
for(int i = 1; i <= n; i++){
if(deg[i] == 1){
for(int j = head[i]; j; j = edges[j].next){
int v = edges[j].v; if(deg[v] == 1){ans[++tot] = i, ans[++tot] = v, getout(); return true;}
}
}
}
return false;
}
void dfs1(int u, int faid){
vis[u] = 1;
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v; if(i == (faid ^ 1)) continue;
// cout << u << " " << v << " " << i << " " << faid << "\n";
// cout << u << " " << v << "\n";
if(deg[v] == 2){
if(!vis[v]) dep[v] = dep[u] + 1, fa[v] = u, dfs1(v, i);
else if(dep[u] - dep[v] >= 1) cirsiz = min(cirsiz, dep[u] - dep[v]);//, cout << u << " " << v << " " << dep[u] << " " << dep[v] << "\n";
}
}
}
bool _dfs1(int u, int faid){
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v; if(i == (faid ^ 1)) continue;
if(deg[v] == 2){
if(dep[v] == dep[u] + 1 && _dfs1(v, i)) return true;
else if(cirsiz == dep[u] - dep[v]){
ans[++tot] = v; int p = u;
while(p != v){
ans[++tot] = p; p = fa[p];
}
return true;
}
}
}
return false;
}
bool Case3(){
clr();
for(int i = 1; i <= n; i++) if(deg[i] == 2 && (!vis[i])){
dfs1(1, 0); if(cirsiz != INF){assert(_dfs1(1, 0)), getout(); return true;}
}
// cout << 3 << "\n";
return false;
}
bool Case4(){
clr();
int cnt1 = 0, p1 = 0; for(int i = 1; i <= n; i++) if(deg[i] == 1) cnt1++, p1 = i;
if(cnt1 == 1) return false; for(int i = 1; i <= n; i++) dep[i] = INF;
dep[p1] = 0; queue<int> Q; Q.push(p1);
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v;
if(dep[v] > dep[u] + 1){
dep[v] = dep[u] + 1, fa[v] = u;
if(deg[v] == 2) Q.push(v);
}
}
}
for(int i = 1; i <= n; i++){
if(deg[i] == 1 && p1 != i && dep[i] != INF){
int p = i; while(p != p1) ans[++tot] = p, p = fa[p];
ans[++tot] = p1; getout(); return true;
}
}
return false;
}
void dfs2(int u, int father){
bool fl = 1; vis[u] = 1; fa[u] = father;
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v; if(v == father || deg[v] == 1) continue;
dfs2(v, u);
}
}
void dfs3(int u, int father){
bool fl = 1; vis[u] = 1; fa[u] = father;
if(father && tag2[u]){
leafvec[++lsiz] = u;
return;
}
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v; if(v == father || deg[v] == 1) continue;
dfs3(v, u);
}
}
void addpath(int x, int y){
for(int i = 1; i <= n; i++) tag[i] = 0;
int p = x; //cout << "6: " << x << " " << y << "\n";
do{
tag[x] = 1;
x = fa[x];
}while(x);
x = p;
// cout << p << " " << y << "\n";
while(!tag[y]){
// cout << y << " " << fa[y] << "\n";
ans[++tot] = y;
y = fa[y];
}
while(x != y){
ans[++tot] = x; x = fa[x];
}
ans[++tot] = y;
}
bool Case5(){
int p1 = 0, cnt = 0; clr();
for(int i = 1; i <= n; i++) if(deg[i] == 1) p1 = i;
ans[++tot] = p1;
for(int i = head[p1]; i; i = edges[i].next){
int v = edges[i].v; tag2[v] = 1;
}
for(int i = head[p1]; i; i = edges[i].next){
int v = edges[i].v; if(!vis[v]){
dfs2(v, 0); dfs3(v, 0); addpath(leafvec[1], v); cnt++; lsiz = 0;
// cout << v << " " << leafvec[1] << "\n";
if(cnt == 2){getout(); return true;}
}
}
return false;
}
void solve(){
clrall(); cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y; cin >> x >> y;
add_edge(x, y); add_edge(y, x);
deg[x]++; deg[y]++;
}
for(int i = 1; i <= n; i++) deg[i] %= 3;
if(Case1()) return; // deg = 0
if(Case2()) return; // deg = 1 -> 1 -> back
if(Case3()) return; // deg = 2 -> 2 -> 2 -> back
if(Case4()) return; // deg = 1 -> 2 -> 2 -> 1
if(Case5()) return; // deg = 2-leaf -> 1 -> 2-leaf
}
signed main(){
// freopen("lsy.in", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T; cin >> T; while(T--) solve();
return 0;
}
/*
don't UKE love you codeforces and luogu
*/