C 等式

xiaoxiao2021-02-28  92

题目描述 我有n 个式子 对于每个个式子,要么是xi = xj 的形式,要么是xi ̸= xj 的形式。 现在我给出这n 个式子,你要告诉我,这n 个式子是否可能同时成立。 输入格式 每个个测试点有多组测试数据。 第一行有一个整数T,表示测试数据的组数。 对于每一组测试数据,第一行包含一个正整数n,表示式子的数目。 接下来n 行,每行三个整数i,j,e,描述一个式子。如果e=1,则这个式子 为xi=xj。如果e=0,则这个式子是xi≠xj。 输出格式 对于每⼀个测试数据输出一行。如果存在一种方案,使得所有的式子都被满足, 输出“YES”(不包含引号)。否则输出“NO”(不包含引号)。 样例输入1 2 2 1 2 1 1 2 0 2 1 2 1 2 1 1 样例输出1 NO YES 样例输入2 2 3 1 2 1 2 3 1 3 1 1 4 1 2 1 2 3 1 3 4 1 1 4 0 样例输出2 YES NO 数据范围 对于20% 的数据,n ≤ 10。 对于40% 的数据,n ≤ 100。 对于70% 的数据,n ≤ 10^5,1 ≤ i, j ≤ 10^4。 对于100% 的数据,n ≤ 10^5,1 ≤ i, j ≤ 10^9,1 ≤ t ≤ 10。 补充: 题目中提到,对于每一个测试点,都有“多组测试数据”。每组测试数据之间是

互相独立,互不影响的。

分析:

有n个等式/不等式,问是否可以同时满足 20% 继续爆搜 40% 不晓得这个要如何搞。。 70% floodfill算法。将所有的等式关系建成一个图。然后我们循环每一个点,如果当前点还没有被访问过,则从这个点开始,dfs遍历所有和它有边相连的点,并标记。注意,标记是不一样的。从1开始遍历就标记为1,从2开始遍历就标记为2 然后我们检查所有的不等式。如果要求不等的两个点i和j标记相同,说明它们被要求“等于”,就输出NO。如果所有要求不等的两个点都不在一个联通块内,则输出YES。 100% 标号过大? 通过离散化重新进行标号 我们可以用并查集维护所有数之间的相等关系。先处理所有的等式,将等式两边的两个数所在的集合合并在一起 然后我们检查所有的不等式。如果某个不等式两边的数字在一个集合中(被要求相等),则输出NO。不存在这样的情况则输出YES 如果不用离散化的话(f[i],i不能从1~N,也不能从1~2*n,这个数可能很大,最低得200000)最后一个点过不了。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int t,n; int f[200010],tmp[200010]; int x[100005],y[100005],z[100005]; int fd(int x) { if(f[x]!=x) f[x]=fd(f[x]); return f[x]; } void solve() { int i; scanf("%d",&n); for(i=1;i<=n*2;i++) f[i]=i; for(i=1;i<=n;++i) { scanf("%d%d%d",&x[i],&y[i],&z[i]); tmp[i*2-1]=x[i];tmp[i*2]=y[i]; } sort(tmp+1,tmp+1+n*2); for(i=1;i<=n;i++)//就是把每个数字重新编个在1~2*n内的编号。 {//这里可以不用去重(想一想为什么?)。 x[i]=lower_bound(tmp+1,tmp+1+n*2,x[i])-tmp;//这里附上lower_bound的用法: y[i]=lower_bound(tmp+1,tmp+1+n*2,y[i])-tmp; if(z[i]) { int r1=fd(x[i]); int r2=fd(y[i]); if(r1!=r2) f[r1]=r2; } } for(i=1;i<=n;i++) { if(z[i]) continue; if(fd(x[i])==fd(y[i])) {printf("NO\n");return;} } printf("YES\n"); return; } int main() { freopen("equ.in","r",stdin); freopen("equ.out","w",stdout); scanf("%d",&t); while(t--) solve(); fclose(stdin); fclose(stdout); return 0; } 这就是一种简单的离散化(当然用哈希也不会错),其思想还是值得借鉴的。 lower_bound用法 int a[]={0,1,2,2,3}; printf("%d\n",lower_bound(a,a+5,2)-a); printf("%d\n",upper_bound(a,a+5,2)-a); 结果:2 4 lower的意义是对于给定的已经排好序的a,key最早能插入到那个位置, 0 1 | 2 2 3 所以2最早插入到2号位置。 upper的意义是对于给定的已经排好序的a,key最晚能插入到那个位置, 0 1 2 2 | 3 所以2最晚插入到4号位置。

转载请注明原文地址: https://www.6miu.com/read-52515.html

最新回复(0)