How Many Answers Are Wrong

题意:输入一连串的区间和,问和前面的矛盾个数;

思路:我在做专题,知道是并查集,可是还是不知道怎么做,学了一下权值并查集和大佬的优秀思路,感觉回了一点;

    具体就是 在并查集的基础上,加上val【】数组用来记录区间和,而原来的fa【】数组表示的是这个数能到达的最左边的下标;

   下面是ac代码

#include <cstdio>
#include <algorithm>
using namespace std; const int maxn = ;
int val[maxn],fa[maxn],n,m,ans=;//fa记录下标所能到达最左端(),val表示前缀和 void init(){
for(int i=;i<=n;i++)
{
fa[i] = i;
val[i]=;
}
} int find (int x)
{
if(fa[x]==x)return x;
else
{
int fn = find(fa[x]);
val[x] +=val[fa[x]];
return fa[x] = fn;
}
}
void uni(int a,int b,int s)
{
int px = find(a);
int py = find(b);
if(px==py) //只有左区间相同是才能比较
{
if(val[b]-val[a]!=s)ans++;
}
else
{
fa[py] = px;
val[py] = val[a] + s - val[b];
}
}
int main(){
while(~scanf("%d%d",&n,&m))
{
init();
ans = ;
for(int i=;i<=m;i++)
{
int a,b,s;
scanf("%d%d%d",&a,&b,&s);
a--;
uni(a,b,s);
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. 一道返回num值的小题目
  2. BZOJ1090: [SCOI2003]字符串折叠
  3. OCJP(1Z0-851) 模拟题分析(一)11
  4. RMAN duplciate 准备时,需要检查的target数据库参数内容
  5. MUI - 图片预览(perviewimage)的优化
  6. HTML的列表标签
  7. Python调用Webservice、访问网页
  8. MVVM架构的一次实践,重写iOS头条客户端
  9. [PWA] 6. Hijacking response
  10. 深入浅出理解QTimeLine类
  11. MySQL库目录下db.opt文件的作用
  12. js获取url中的参数方法
  13. ConstraintLayoutDemo【约束性布局知识梳理】【基于1.1.3】
  14. 搭建IIS并配置网站之旅
  15. 一个方法教你认识ref(简单易懂)
  16. Burnside引理的感性证明
  17. 【python练习题】程序15
  18. [爬虫]采用Go语言爬取天猫商品页面
  19. Pandas 基础(8) - 用 concat 组合 dataframe
  20. unittest框架assert断言

热门文章

  1. Vue项目的创建和UI资源
  2. Mybatis整合Spring 使用
  3. spring boot 学习笔记之前言----环境搭建(如何用Eclipse配置Maven和Spring Boot)
  4. H3C模拟器单臂路由配置实例
  5. 【Java例题】7.5 文件题2-学生成绩统计
  6. [转载]windows下mongodb安装与使用整理
  7. JAVA MQ API方式通信采用Binding MQ Server方式
  8. Kafka集群配置---Windows版
  9. Mock Server的搭建
  10. 003——Netty之Buffer、Channel以及多路复用器Selector