首页 > 其他分享 >组合问题记录

组合问题记录

时间:2024-08-02 10:29:54浏览次数:13  
标签:组合 记录 int top stk 问题 dep deg

this and this

核心:

  • 组合问题的常见分类:

现在我们假设我们要对一个组合对象 \(U\) 进行考虑并分析一些关于组合的问题。

  1. 判定: 判断 \(U\) 中是否有满足条件 \(p\) 的集合或元素。这是组合问题中最基础的问题。

  2. 构造: 找到 \(U\) 中一个满足条件 \(p\) 的集合或元素。此类问题基于判定问题,但是灵活性更高,需要一定的思维(有时候可能会很难)。

  3. 计数: 统计 \(U\) 中满足条件 \(p\) 的集合或元素数量。

  4. 最优化: 给 \(U\) 中每一个集合或元素定义一个价值,问 \(U\) 中满足条件 \(p\) 的集合或元素的价值最大 / 最小的价值。


  • 组合问题的常见技巧:
  1. 调整法: 通过证明一个情况可以通过调整到另一个情况使得答案不劣,将问题转化为特殊情况求解。本技巧常用于最优化问题中。

  2. 局部观察法: 抓住问题判定的本质,从局部入手观察问题的情况,常常和调整法结合。

  3. 构造双射法: 通过一个双射对应到另一个问题上,简化或明晰问题。


  • 计数中的映射问题:

计数中常常会遇到一类操作问题,即一个初始状态 \(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
*/

标签:组合,记录,int,top,stk,问题,dep,deg
From: https://www.cnblogs.com/little-corn/p/18337235

相关文章

  • 解决Leaflet地图初始化后更改容器宽度,新增部分瓦片没有请求问题
    当使用Leaflet初始化地图并在后续操作中动态更改地图容器的宽度时,可能会出现地图新增加的部分没有请求瓦片的情况。这是因为Leaflet在初始化时计算并缓存了地图的尺寸,当容器的尺寸发生变化时,地图没有自动刷新来适应新的尺寸。为了解决这个问题,需要在动态更改容器宽度后调用L......
  • druid数据库连接池在使用中遇到的一些问题和说明
    getconnectiontimeoutretry:12024-02-0611:18:26.364ERROR23752---[eate-1838225797]com.alibaba.druid.pool.DruidDataSource:createconnectionSQLException,url:jdbc:oracle:thin:@192.168.66.88:1521:orcl,errorCode17002,state08006有正在执行的SQL......
  • Luogu7740 [NOI2021]机器人游戏 做题记录
    link一道炸裂的题目。首先样例解释已经告诉我们可以容斥。考虑枚举可行的位置集合\(S\),我们需要统计\(\forallp\inS\),纸条初始状态和目标状态都相同的方案数。显然每个机器人独立,可以分开考虑。对于一个机器人,他的行动对纸条的每个格子要么赋值为\(0/1\),要么不变,要么取......
  • 2024.8 - 做题记录与方法总结
    2024.8-RecordofQuestionsandSummaryofMethodology先分享一个歌单:永无止境的八月!2024/08/01先来点重量级的P4768[NOI2018]归程题面:[NOI2018]归程题目描述本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。魔力之都可以抽象成一个\(n\)个节......
  • 2024年1月刷题记录
    2024年1月1日【leetcode】1599.经营摩天轮的最大利润题意:你正在经营一座摩天轮,该摩天轮共有4个座舱,每个座舱最多可以容纳4位游客。你可以逆时针轮转座舱,但每次轮转都需要支付一定的运行成本runningCost。摩天轮每次轮转都恰好转动1/4周。给你一个长度为n的......
  • 2024年4月刷题记录
    2024年4月1日【leetcode】2810.故障键盘题意:你的笔记本键盘存在故障,每当你在上面输入字符'i'时,它会反转你所写的字符串。而输入其他字符则可以正常工作。给你一个下标从0开始的字符串s,请你用故障键盘依次输入每个字符。返回最终笔记本屏幕上输出的字符串。2024......
  • 2024年3月刷题记录
    2024年3月1日【leetcode】2369.检查数组是否存在有效划分题意:给你一个下标从0开始的整数数组nums,你必须将数组划分为一个或多个连续子数组。如果获得的这些子数组中每个都能满足下述条件之一,则可以称其为数组的一种有效划分:子数组恰由2个相等元素组成,例如,子......
  • 2024年2月刷题记录
    2024年2月2日【leetcode】1686.石子游戏VI题意:Alice和Bob轮流玩一个游戏,Alice先手。一堆石子里总共有n个石子,轮到某个玩家时,他可以移出一个石子并得到这个石子的价值。Alice和Bob对石子价值有不一样的的评判标准。双方都知道对方的评判标准。给你两个长度为......
  • 2024年7月刷题记录
    2024年7月1日【leetcode】494.目标和题意:给你一个非负整数数组nums和一个整数target。向数组中的每个整数前添加'+'或'-',然后串联起所有整数,可以构造一个表达式:例如,nums=[2,1],可以在2之前添加'+',在1之前添加'-',然后串联起来得到表达式"+2-1"。......
  • 2024年6月刷题记录
    2024年6月1日【leetcode】2928.给小朋友们分糖果I题意:给你两个正整数n和limit。请你将n颗糖果分给3位小朋友,确保没有任何小朋友得到超过limit颗糖果,请你返回满足此条件下的总方案数。2024年6月2日【leetcode】575.分糖果题意:Alice有n枚糖,其中第i......