How Many Answers Are Wrong
题目描述 :
TT和FF是…朋友。呃…非常非常好的朋友
FF是个坏孩子，他总是向TT示好，让他和他一起玩下面这个游戏。这是一个非常乏味的游戏。首先，TT应该写下一个整数序列-_-！！（无聊）。
然后，FF可以从中选择一个连续的子序列（例如，从第三个到第五个整数的子序列，包括在内）。之后，FF会问TT他选择的子序列的总和是多少。接下来，TT会回答FF的问题。然后，FF可以重做这个过程。最后，FF必须算出整个整数序列。
无聊无聊一个非常非常无聊的游戏！! TT根本就不想和FF玩。为了惩罚FF，她经常故意告诉FF错误的答案。
这个坏小子不是个傻子。FF检测到一些答案是不相容的。当然，这些矛盾让我们很难计算出序列。
然而，TT是一个善良可爱的女孩。她没有心思去为难FF。为了节省时间，她保证，如果确实没有逻辑错误，答案都是正确的。
更重要的是，如果FF发现一个答案是错的，他在判断下一个答案时就会忽略它。
但是问题太多，可怜的FF无法在短时间内确定当前的答案是对还是错。所以他决定写一个程序来帮助他解决这个问题。这个程序将接收来自FF的一系列问题，以及FF从TT那里得到的答案。这个程序的目的是找出有多少答案是错误的。只有通过忽略错误的答案，FF才能算出整个整数序列。可怜的FF没有时间来做这项工作。现在他在请求你的帮助（为什么要给自己找麻烦~坏孩子)
输入
第1行。两个整数，N和M（1<=N<=200000，1<=M<=40000）。意味着TT写了N个整数，FF问了她M个问题。
第2行…M+1。第i+1行包含三个整数。Ai，Bi和Si。意味着TT回答FF，从Ai到Bi的总和是Si。可以保证0 < Ai <= Bi <= N。
你可以假设任何子序列的和都适合于32位整数。
输出
一行整数表示有多少个答案是错误的。
输入样本
10 5
1 10 100
7 10 28
1 3 32
4 6 41
6 6 1
样本输出
1
思路解析
题目大意 :
给出一个长度为n的序列,然后给出m对查询,需要你找出自相矛盾的个数
并查集维护权值的正确性
带权并查集模板
int pre[maxn];
int value[maxn]; // value是该节点到其根的和，比如说value[3],3的根是1，那么value[3]表示的就是1到3的和……
void init(){
for(int i = 0; i <= n; i++) {
pre[i] = i;
value[i] = 0;
}
}
int find(int x) {
if (x == pre[x]) return x;
else {
int root = find(pre[x]); // 找到根节点
value[x] += value[pre[x]]; // 权值合并，更新
return pre[x] = root; // 压缩路径
}
}
//带权路径的合并
void merge(){
int px = find(x);
int py = find(y);
if (px != py)
{
pre[px] = py;
value[px] = -value[x] + value[y] +s;
}//s是他们之间的关系
}
AC代码
#include <cstdio>
const int maxn = 200000 + 10;
int n, m;
int pre[maxn];
int value[maxn]; // value是该节点到其根的和，比如说value[3],3的根是1，那么value[3]表示的就是1到3的和……
void init(){
for(int i = 0; i <= n; i++) {
pre[i] = i;
value[i] = 0;
}
}
int find(int x) {
if (x == pre[x]) return x;
else {
int root = find(pre[x]); // 找到根节点
value[x] += value[pre[x]]; // 权值合并，更新
return pre[x] = root; // 压缩路径
}
}
int main() {
while(~scanf("%d%d", &n, &m)) {
init();
int x, y, s;
int ans = 0;
while(m--) {
scanf("%d%d%d", &x, &y, &s);
x--; // 想一下为什么要减一，可以让类似【1,5】【6,10】这样的区间可以合并……
int fx = find(x);
int fy = find(y);
if (fx != fy) {
pre[fy] = fx;
value[fy] = value[x] - value[y] + s;
}
else if (value[y] - value[x] != s) ans++;//此时value[y]的值就等于到根节点的距离,应该等于value[x]+s;
}
printf("%d\n", ans);
}
return 0;
}
|