首页 > 其他分享 >CF776D(并查集思想)

CF776D(并查集思想)

时间:2024-02-27 10:13:43浏览次数:30  
标签:yi xi 思想 get int 查集 fa CF776D

难度1

em还是一道比较套路的题目。观察发现,如果当\(r_{i}=1\)时他的两把钥匙状态是相同的,当\(r_{i}=0\)时他的两把钥匙状态是不同的,对于这种相同不同的问题可以考虑并差集,状态一样就一样的并在一起,否则就把不一样的并在一起

所以以后看见这些问题(a=b+k,a=!b,a=b)都可以用带权并查集,扩展域并查集等解决。最好所有优化都加上,不然不如dfs

#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,a[100005],fa[200005],b[100005][2];
bool sta[100005];
int get(int x){
	if(fa[x]!=x) return fa[x]=get(fa[x]);
	return fa[x];
}
void merge(int x,int y){
	int xi=get(x),yi=get(y);
	if(xi!=yi){
		fa[xi]=yi;
	}
}
void print(){
	for(int i=1;i<=2*m;i++){
		cout<<get(i)<<" ";
	}cout<<endl;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m*2;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>sta[i];
	}
	for(int i=1;i<=m;i++){
		cin>>k;
		for(int j=1;j<=k;j++){
			cin>>x;
			if(b[x][0]==0) b[x][0]=i;
			else b[x][1]=i;
		}
	}
	for(int i=1;i<=n;i++){
		if(sta[i]==0){
			merge(b[i][0],b[i][1]+m);
			merge(b[i][0]+m,b[i][1]);
		}else{
			merge(b[i][0],b[i][1]);
			merge(b[i][0]+m,b[i][1]+m);
		}
		//print();
	}
	for(int i=1;i<=m;i++){
		//cout<<get(i)<<" "<<get(i+m)<<endl;
		if(get(i)==get(i+m)){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;
	
	return 0;
}

标签:yi,xi,思想,get,int,查集,fa,CF776D
From: https://www.cnblogs.com/wuhupai/p/18036283

相关文章

  • ABC283E (dp思想)
    难度1这题看到一点思路也没有,但是看到最小操作数想到二分,dp和贪心,二分答案的check显然不会,贪心不会。发现对于一行,前面的\(i-2\)是不会影响的,这一行也不会影响后面的\(i+2\)行,所以是dp。考虑如何设计状态因为\(i-1\)和\(i+1\)行都会影响,所以设计出来一个dp[i][0/1][0/1][0/1]的东......
  • P10156(dp思想)
    难度2也是比较有意思的一道题。首先发现每个小团体独立,所以对于每个小团体分开直接暴力dp,dp[i][j]表示当前小团体做到第i人,走了j人,然后O(n)转移,加上部分分喜提50pts。为什么要O(n)转移呢,因为我要枚举匹配的两个人然后算贡献。但是对于这种带绝对值的贡献,我们一般都要把绝对值拆掉......
  • CF1928C (数学思想)
    难度3其实是有点虚高的,可能是我这种数学题做的少了。在考试时式子都写出来了,但不知道怎么处理。然后注意一下细节就可以了。懒懒懒。对于xy=k(k为常数)可以直接枚举k的因子,然后看一下限制条件即可。#include<bits/stdc++.h>usingnamespacestd;longlongT,n,x,tot=0;unorde......
  • P6805 (树上最小路径覆盖思想)
    难度3比较有意思的一道题。首先看到题目是求树上最小路径覆盖,自然想到由叶子入手去分析,所以当子树内有偶数个叶子节点时,那么就有两个叶子向上匹配,否则只有一个叶子向上匹配。这个东西可以用树剖维护,线段树维护的是子树内有多少个偶的,相当于一个区间反转一类的东西。细节不算多,但......
  • P4666 [BalticOI 2011 Day1] Growing Trees题解(平衡树思想)
    自己第一道不看题解写出来的紫题,庆祝一下(没初始化种子导致调了30min)这是一个fhq-treap的题解思路来源:首先看题目,因为是序列上的问题,不难想到是一道数据结构题。首先看到操作C:对于这种操作,我们可以用平衡树解决,具体方法是,将树split成\(<min,min\lex\lemax,>max\)这......
  • 并查集+建图 同样是逆向思维 和星球大战类似
    L2-013红色警报分数25作者 陈越单位 浙江大学战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序,当失去一个城市导致国家被分裂为多个无法连通的区域时,就发出红色警报。注意:若该国本来就不完全连通,是分裂的k个区域,而失去一个城市并不改......
  • 并查集
    作用:1.将两个集合合并2.询问两个元素是否在一个集合当中基本原理:每个集合用一棵树来表示,树根的编号就是整个集合的编号。每个节点存储它的父节点,p[x]表示x的父节点操作:1.判断树根:if(p[x]==x);2.求x的集合编号:while(p[x]!=x)x=p[x];3.如何合并两个集合:p[x]是x的集合编......
  • 贪心算法思想
    贪心算法每一步都找到当前局部最优解,短视,但是有思考贪心算法(GreedyAlogorithm)又叫登山算法,它的根本思想是逐步到达山顶,即逐步获得最优解,是解决最优化问题时的一种简单但是适用范围有限的策略。贪心算法没有固定的框架,算法设计的关键是贪婪策略的选择。每一步都找到最优解,由......
  • Java锁的思想和区别
    乐观锁VS悲观锁乐观锁和悲观锁是两种处理并发访问的不同策略,用于确保多个操作不会同时修改同一资源而导致数据不一致的问题。它们的区别在于处理并发时的思想和实现方式:乐观锁:思想:认为在大多数情况下,读操作远远多于写操作,因此假设在绝大多数情况下并发冲突是不会发生的,直到出......
  • ABC302Ex Ball Collector (可撤销并查集)
    由于博客园存在关站风险,文章以后同步发在这里,可能会有更好的阅读体验。首先我们分析一下,如果我们已经知道了要走哪些点,我们可以怎么做。考虑将\(a_i,b_i\)之间连边,发现题目可以被转化为给定一个图,要求对于每条边将其一个顶点染色,问最多能将多少个点染色。于是我们对于每个连......