How Many Answers Are Wrong HDU - 3038 并查集,加权(路径)
InputLine 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.
OutputA 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的数列,m次数据,每次数据给出数列中从第a个到第b个的和为c,问这些数据中有多少数据是
错误的。
思路:将每个数想象成一条线段,线段的左边为这个数,右边为下一个数,因此数组要开n+1大小,用并查集给这些一个祖先,开一个数组存放这些数到祖先的距离。具体见代码
代码:
1 #include <cstdio> 2 #include <fstream> 3 #include <algorithm> 4 #include <cmath> 5 #include <deque> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <cstring> 10 #include <map> 11 #include <stack> 12 #include <set> 13 #include <sstream> 14 #include <iostream> 15 #define mod 998244353 16 #define eps 1e-6 17 #define ll long long 18 #define INF 0x3f3f3f3f 19 using namespace std; 20 21 //fa保存下标对应的祖先 22 //num保存下标到祖先节点的距离 23 int fa[200005],num[200005]; 24 //初始化 25 void init(int n) 26 { 27 //因为有n个线段,那么有n+1个点 28 for(int i=0;i<=n+1;i++) 29 { 30 //初始情况下每个点的祖先为自己 31 fa[i]=i; 32 //初始情况下每个点到祖先的距离为0 33 num[i]=0; 34 } 35 } 36 //找到祖先,并进行压缩路径的优化 37 int find(int s) 38 { 39 //如果祖先为自己则返回自己 40 if(fa[s]==s) 41 { 42 return s; 43 } 44 //递归寻找祖先 45 int temp=find(fa[s]); 46 //将自己到祖先的距离加上祖先到祖先的祖先的距离 47 num[s]+=num[fa[s]]; 48 //压缩路径优化 49 fa[s]=temp; 50 //返回祖先 51 return fa[s]; 52 } 53 int main() 54 { 55 int n,m; 56 while(scanf("%d %d",&n,&m)!=EOF) 57 { 58 //初始化数据 59 init(n); 60 int a,b,c; 61 int ans=0; 62 for(int i=0;i<m;i++) 63 { 64 scanf("%d %d %d",&a,&b,&c); 65 //加一是因为从a到b是从a线段的起点到b线段的终点 66 b++; 67 //找到a和b的最远祖先 68 int x=find(a); 69 int y=find(b); 70 //如果两个祖先不相等,合并两个点到各自祖先的距离 71 if(x!=y) 72 { 73 //将b的祖先上再加一个祖先,即为b的祖先的祖先为a的祖先 74 fa[y]=x; 75 //因为将b的祖先加到了a的祖先的上,所以b到a的祖先的距离为 76 //b的a的距离加上a到a祖先的距离,或b到b祖先的距离加上b祖先到a祖先的距离 77 //因此b祖先到a祖先的距离等于b的a的距离加上a到a祖先的距离减去b到b祖先的距离 78 num[y]=num[a]+c-num[b]; 79 } 80 else 81 { 82 //b到b祖先的距离减去a到a祖先的距离即为a到b的距离 83 //判断c是否为a到b的距离 84 //不是则表示这句话的c是错的 85 if(c!=num[b]-num[a]) 86 { 87 ans++; 88 } 89 } 90 } 91 printf("%d\n",ans); 92 } 93 }优质内容筛选与推荐>>