即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

C 等式

编程语言 huihao123456 26℃ 0评论

题目描述

我有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
#include
#include
#include
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号位置。









转载请注明:CodingBlog » C 等式

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情