当前位置: 代码迷 >> 综合 >> hdu 3038 How Many Answers Are Wrong (带权并查集好题+思维)
  详细解决方案

hdu 3038 How Many Answers Are Wrong (带权并查集好题+思维)

热度:46   发布时间:2024-01-04 12:02:02.0


题意: 给出区间[1,n],下面有m组数据,l r v区间[l,r]之和为v,每输入一组数据,判断此组条件是否与前面冲突 ,最后输出与前面冲突的数据的个数. 比如 [1 5]区间和为100 然后后面给出区间[1,2]的和为 200 那肯定就是有问题的了。

思路:一开始并没有什么思路,只是想想假如有区间【1,10】的数和,区间【1,5】的数和(那么就可以判断【5,10】的数和了),这就有点像前缀数组,但是继续就想不下去了。后来知道可以用并查集,感觉十分妙啊,但是看题解说很容易想到用并查集的话,说明我做的题目还不够多,思考太少了,要将一切奇淫怪技能熟练自如得运用起来得时候自己就很棒了。
这题让我学到了很多,特别是关于向量偏移,可以直接找到根节点与子节点的关系

所谓带权并查集,指的是在合并时不仅要将区间合并,而且要记录某些信息,记录的方法类似于数学的坐标系,以一个点为参考点(根节点),然后求出其他点到这个店的相对信息值,难点在于合并两个不同的集合时相对信息值的更新,分别在find和union里面进行更新,不理解的同学可以在纸上划一下,一边不懂多划几遍,表示我划了了两张纸才搞懂到底是如何更新如何维护的。。


具体代码实现与分析:
https://www.cnblogs.com/liyinggang/p/5327055.html
https://blog.csdn.net/niushuai666/article/details/6981689
这题我们利用一个sum[i]表示i与根节点之间节点的和 ,根节点定义为区间最左端的数字,因为类似用了一个前缀和的操作,所以a-b的区间和是sum[b]-sum[a-1]的,然后代码实现也是用a-1作为根的
于是我们要对find和mix函数做一下修改,具体看注释:


代码:
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn =200006;
int fa[maxn];
int sum[maxn];
int ans=0;

void init(int n){//初始化,并查集辅助数组,sum维护的区间和数组
 for(int i=0;i<=n;i++){
  fa[i]=i;
  sum[i]=0;
 }
}

int find(int x){
 if(fa[x]==x)return x;v     //如果自己就是根节点,返回,不需要修改
 int f=fa[x];
 fa[x]=find(f);
 sum[x]+=sum[f];     //修改sum[],比如有区间[1,2][3,4]可以合成[1,4],
 return fa[x];
}
void mix(int a,int b,int c){
 int ffa=find(a);
 int ffb=find(b);
 if(ffa<ffb){      //如果ffa<ffb,说明a在b的前面,想要将啊a,b所在的区间建立联系,那么就是通过根节点与c的关系进行传递,具体多画画图,注意c的权重是指a->b的是具有符号的向量
  fa[ffa]=ffb;
  sum[ffa]=sum[b]+c-sum[a];
 }else if(ffa>ffb){//同理推一下就行了
  fa[ffb]=ffa;
  sum[ffb]=sum[a]-sum[b]-c;
 }else{      //根节点相同,则a,b的关系已经知道,可以进行判断
  if(sum[a]-sum[b]!=c)
   ans++;
 }
}
int main(){
 int n,m;
 while(~scanf("%d%d",&n,&m)){
  init(n);
  ans=0;
  while(m--){
   int a,b,c;
   scanf("%d%d%d",&a,&b,&c);
   b++;
   mix(a,b,c);
  }
  printf("%d\n",ans);
 }
}


https://www.cnblogs.com/QAQorz/p/9041743.html

  相关解决方案