How Many Answers Are Wrong
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 20324 Accepted Submission(s): 7002
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.
BoringBoringa 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
以下純屬個人了解，如果錯誤請及時指出：
題目大意，就說給你n個區間，要你推斷哪些區間一定是錯誤的。
思路：合并區間，檢查區間的值和所給的值。
第一次遇見帶權并查集，所謂并查集就是在原有的關系上求等價關系，而帶權并查集不僅僅要求等價關系，還要統計區間權值。
這個題還需要将路徑壓縮，因為條件隻給的x->y的權值，和x、y的權值，以及x的根節點和y的根節點的權值，如果不将路徑壓縮那麼問題會變得很複雜。首先講一下路徑壓縮，畫個圖示意：
在一棵深度為2的樹上，我們将深度為2上面的根節點直接與根節點相連，這就是所謂的路徑壓縮，因為這隻是深度為2是以感覺沒什麼，但是設想一下深度100+的樹将他壓縮的效果，簡直不要太好，（特殊問題特殊求解）。
路徑壓縮代碼：
int FIND_X(int x)//路徑壓縮+求解沿路權值之和
{
if(x!=parent[x]){
parent[x]=FIND_X(parent[x]);//路徑壓縮
}
return parent[x];
}
然後了解然路徑壓縮後，我們将每個節點賦予權值，在路徑壓縮的基礎上直接求出該節點到根節點的權值，畫個圖示意：
給出代碼
int FIND_X(int x)//路徑壓縮+求解沿路權值之和
{
if(x!=parent[x]){
int i=parent[x];
parent[x]=FIND_X(parent[x]);//路徑壓縮
sum[x]+=sum[i];//沿路權值之和
}
return parent[x];
}
其實就說先記錄上一個節點的編号然後遞歸求和。
先上ac代碼：
#include<iostream>
#define MAXSIZE 200000
using namespace std;
int parent[MAXSIZE];
int sum[MAXSIZE];//sum[i]代表sum[i]到sum[i]的上一個節點的權值
int FIND_X(int x)//路徑壓縮+求解沿路權值之和
{
if(x!=parent[x]){
int i=parent[x];
parent[x]=FIND_X(parent[x]);//路徑壓縮
sum[x]+=sum[i];//沿路權值之和
}
return parent[x];
}
int main()
{
int ans;
int n,m;
while(cin>>n>>m){
for(int i=0;i<=n;i++){//初始化
parent[i]=i;
sum[i]=0;
}
ans=0;
while(m--)
{
int begin,end,value;
cin>>begin>>end>>value;
begin--;//閉區間展開成左開右閉區間
int x=FIND_X(begin);
int y=FIND_X(end);
if(x==y){
if(sum[begin]-sum[end]!=value){
ans++;
}
}else{
parent[x]=y;//更新根節點
sum[x]=value+sum[end]-sum[begin];//求出x的根節點到end的權值
}
}
cout<<ans<<endl;
}
}
重點是這個判斷也是全文畫龍點睛之處，下面進行講解：
if(x==y){
if(sum[begin]-sum[end]!=value)
ans++;
}else{
parent[x]=y;//更新根節點
sum[x]=value+sum[end]-sum[begin];//求出x的根節點到end的權值
}
根據前面2組樣例得到如下圖：
當第2組樣例1 3 32輸入後，得到如下圖
那麼可以得到sum[10]的計算公式sum[x]=value+sum[end]-sum[begin]，如果這個圖還不好了解那麼把這個圖變化一下：
我們求的也就是px到py的值，根據傳遞性可以知道px=value+sum[end]-sum[begin]
我再把值帶進去畫個圖：
這裡的py實際上是3自己，因為3還沒有和任何元素合并，不過為了一眼就能看出表達式才這麼畫的。
當兩個元素的根節點相同時，隻需要判斷sum[begin]-sum[end]是不是等于value就能知道題目中錯誤的個數了。
畫個圖：（根據前面4組樣例）
以上就是全部了，可能寫的不是很好有什麼意見可以評論交流，這個題目我認為出的非常好，教會了我許多東西，比如将并查集離散化，（因為我之前都是按照父親存儲的，原來根據題目的要求可以去掉一些沒必要的東西，可以，很不錯），還學會的路徑壓縮+帶權并查集的處理（合并那裡也需要出來）。