并查集-HDU-3038-How Many Answers Are Wrong

2023-10-17 07:18
文章标签 查集 many hdu wrong 3038 answers

本文主要是介绍并查集-HDU-3038-How Many Answers Are Wrong,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

How Many Answers Are Wrong

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

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

Source
2009 Multi-University Training Contest 13 - Host by HIT


题意:
给出一个序列,并给出一系列a b c这样的问答,其意思是序列中第a个到第b个元素的和为c,问题是这一系列问答中,答案有明显逻辑问题的有多少个。


题解:
其实一开始并不知道该怎么做,但是想到这道题是在并查集专题里(真的是难度大减,毕竟水平不够随机刷题),于是想着怎么和并查集联系在一起。最后的方案是,保存其前驱以及和。
举个栗子就是,如果有个问答是a b c,我们这里都先将a–,原因是这里表示的是sum[a,b]=c,而不是sum(a,b]=c,例如6 6 6指的是第6个是6,相信大家都能明白这一点。那么father[a]保存的是能够找到的a的前驱,father[b]同理。在这个问答里,a相当于是b的前驱。于是我们要来看这个问答是否合法,那么当father[a]==father[b]时,sum[a]保存的是father[a]到a的和,sum[b]同理,所以我们只需要比较c和sum[b]-sum[a]就行了。你怎么当father[a]!=father[b]时,我们只需要推一下公式就知道,其实让fa=father[a],fb=father[b],那么令father[fb]=fa,sum[fb]=c+sum[a]-sum[b]。推理过程很简单,c表示(a,b](因为a已经减一,所以左边是不包含),sum[a]表示[fa,a],sum[b]表示[fb,b],那么[fa,a]+(a,b]=[fa,b],然后[fa,b]-[fb,b]=[fa,fb],即是sum[fb]了。
这样一来,就能判断不合法的问答了,需要注意的是,在并查集操作路径压缩的时候,不要忘了sum值的刷新。


//
//  main.cpp
//  并查集-D-How Many Answers Are Wrong
//
//  Created by 袁子涵 on 16/2/18.
//  Copyright © 2016年 袁子涵. All rights reserved.
//
//  78ms    4348KB#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define MAXN 200005
using namespace::std;
long long int n,m,a,b,sum,total=0;
long long int father[MAXN],num[MAXN];long long int find(long long int p)
{long long int tmp;if (p!=father[p]){tmp=father[p];father[p]=find(father[p]);num[p]+=num[tmp];}return father[p];
}int main(int argc, const char * argv[]) {while (cin >> n >> m) {total=0;memset(num, 0, sizeof(num));for (long long int i=0; i<=n; i++)father[i]=i;for (long long int i=1; i<=m; i++) {scanf("%lld %lld %lld",&a,&b,&sum);a--;long long int fa=find(a),fb=find(b);if (fa==fb) {if (num[b]-num[a]!=sum)total++;}else{father[fb]=fa;num[fb]=sum+num[a]-num[b];}}cout << total << endl;}return 0;
}

这篇关于并查集-HDU-3038-How Many Answers Are Wrong的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/223811

相关文章

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

uva 10061 How many zero's and how many digits ?(不同进制阶乘末尾几个0)+poj 1401

题意是求在base进制下的 n!的结果有几位数,末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零,以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是: 1. n阶位数:直接 lg(n!)就是得数的位数。 2. n阶末尾0的个数:由于2 * 5 将会在得数中以0的形式存在,所以计算2或者计算5,由于因子中出现5必然出现2,所以直接一

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

hdu 1102 uva 10397(最小生成树prim)

hdu 1102: 题意: 给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。 解析: 把已经修的路的权值改为0,套个prim()。 注意prim 最外层循坏为n-1。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri