hdu 3038D - How Many Answers Are Wrong [kuangbin带你飞]专题五 并查集

简介:

点击打开链接

 

How Many Answers Are Wrong

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4106    Accepted Submission(s): 1571


Problem Description
TT and FF are ... friends. Uh... very very good friends -________-b

FF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game. To begin with, TT should write down a sequence of integers-_-!!(bored).

Then, FF can choose a continuous subsequence from it(for example the subsequence from the third to the fifth integer inclusively). After that, FF will ask TT what the sum of the subsequence he chose is. The next, TT will answer FF's question. Then, FF can redo this process. In the end, FF must work out the entire sequence of integers.

Boring~~Boring~~a very very boring game!!! TT doesn't want to play with FF at all. To punish FF, she often tells FF the wrong answers on purpose.

The bad boy is not a fool man. FF detects some answers are incompatible. Of course, these contradictions make it difficult to calculate the sequence.

However, TT is a nice and lovely girl. She doesn't have the heart to be hard on FF. To save time, she guarantees that the answers are all right if there is no logical mistakes indeed.

What's more, if FF finds an answer to be wrong, he will ignore it when judging next answers.

But there will be so many questions that poor FF can't make sure whether the current answer is right or wrong in a moment. So he decides to write a program to help him with this matter. The program will receive a series of questions from FF together with the answers FF has received from TT. The aim of this program is to find how many answers are wrong. Only by ignoring the wrong answers can FF work out the entire sequence of integers. Poor FF has no time to do this job. And now he is asking for your help~(Why asking trouble for himself~~Bad boy)
 

Input
Line 1: Two integers, N and M (1 <= N <= 200000, 1 <= M <= 40000). Means TT wrote N integers and FF asked her M questions.

Line 2..M+1: Line i+1 contains three integer: Ai, Bi and Si. Means TT answered FF that the sum from Ai to Bi is Si. It's guaranteed that 0 < Ai <= Bi <= N.

You can assume that any sum of subsequence is fit in 32-bit integer.
 

Output
A single line with a integer denotes how many answers are wrong.
 

Sample Input
      
      
10 5 1 10 100 7 10 28 1 3 32 4 6 41 6 6 1
 

Sample Output
      
      
1

题目大意:

找有几个数据是错误的,具体我给你们样例解释,首先输入一个m 和 n,

m表示有区间的最大值,然后有n行数 u, v, w

分别表示[u, v] == w,看有几个矛盾的

解题思路:

种类并查集,就是找u-1就行了,看是否能够找到他们的父亲是一样的,

具体详见代码


样例解释:

1 - 10 -> 100

7 - 10 ->28

1 - 3 -> 32

4 - 6-> 41

6 - 6 -> 1 

可以将1-3和4-6结合 == 1-6,然后在与7-10结合 == 1-10

32+41==73  + 28==101!=100

所以有一个是错误的

上代码:


/**
2015 - 09 - 19 中午

Author: ITAK

Motto:

今日的我要超越昨日的我,明日的我要胜过今日的我,
以创作出更好的代码为目标,不断地超越自己。
**/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
const int maxn = 200005;
const double eps = 1e-7;

struct node
{
    int x, y;
} arr[maxn];

int rank[maxn], fa[maxn], sum[maxn];
int w, ans;
///基本上是模板
void Init(int x)
{
    for(int i=0; i<=x; i++)
    {
        fa[i] = i;
        ///rank[i] = 0;
        sum[i] = 0;
    }
}

int Find(int x)
{
    int t;
    if(fa[x] != x)
    {
        t = fa[x];
        fa[x] = Find(fa[x]);
        sum[x] += sum[t];
    }
    return fa[x];
}

void Union(int x, int y)
{
    int fx = Find(x), fy = Find(y);
    if(fx == fy)
    {
        if(sum[y] != sum[x]+w)
            ans++;
        return;
    }
    if(fx > fy)
    {
        fa[fx] = fy;
        sum[fx] = sum[y]-sum[x]-w;
    }
    else
    {
        fa[fy] = fx;
        sum[fy] = sum[x]+w-sum[y];
    }
}

int main()
{
    int m, n;
    int u, v;
    while(cin>>m>>n)
    {
        ans = 0;
        Init(m);

        while(n--)
        {
            cin>>u>>v>>w;
            Union(u-1, v);
        }
        cout<<ans<<endl;
    }
    return 0;
}


目录
相关文章
|
Java C# 索引
List集合常用方法java与c#
List 是工作中最常用的集合类型之一,在工作中经常把两种集合的方法搞混,这里列举一下java与c#一些常用的方法。
395 0
|
4天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
5261 9
|
4天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
2029 5
|
7天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
7天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
20天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
9650 58
|
2天前
|
传感器 安全 区块链
Windows 电脑运行安卓应用教程:开源工具 ApkStart 双击 APK 即装、独立窗口运行
ApkStart 是一款开源Windows工具,让安卓APP像原生软件一样运行:双击APK即安装、生成真实图标、独立窗口启动、开始菜单可搜索。无需传统模拟器,内置QEMU运行时,支持数据互通、ARM兼容与命令行操作。(239字)
|
14天前
|
Linux 开发工具 iOS开发
2026最新codex下载安装保姆级使用教程(下载+安装+登录+使用,含所有历史版本)
本文详解OpenAI Codex国内快速上手指南:提供Win/macOS/Linux全平台免安装包、npm/Homebrew等多方式安装、账号/API Key双登录、简体中文切换,覆盖下载、安装、汉化、使用及高频避坑(如微软商店失败、npm超时等),10分钟即可跑通。
3287 9
|
20天前
|
JavaScript API iOS开发
DeepSeek Harness下载、安装、配置一篇搞定(2026整理,送常用插件)
DeepSeek Harness(DSH)是DeepSeek于2026年开源的MIT协议AI Agent框架,支持插件化组装模型、工具、沙箱与UI,兼容主流大模型。本文提供免Node.js的桌面端安装包(Win/macOS),含详细图文教程及热门插件推荐。
5991 69