Wikioi 4246 NOIP模拟赛Day2T1 奶牛的身高
奶牛们在FJ的养育下茁壮成长。这天,FJ给了奶牛Bessie一个任务,去看看每个奶牛场中若干只奶牛的身高,由于Bessie是只奶牛,无法直接看出第i只奶牛的身高,而只能看出第i只奶牛与第j只奶牛的身高差,其中第i 只奶牛与第j只奶牛的身高差为A(i<=n)。当A大于0时表示这只奶牛比前一只奶牛高A cm,小于0时则是低。现在,FJ让Bessie总共去看了m次身高,当然也就传回给FJ m对奶牛的身高差,但是Bessie毕竟是奶牛,有时候眼睛可能会不好使……(大雾)你的任务是帮助FJ来判断是不是需要给Bessie看看眼睛了……
注:Hj-Hi=A 注意T1的样例 注意注意注意 重要的事情说三遍。
第一行为一个正整数w,表示有w组数据,即w个奶牛场,需要你判断。每组数据的第一行为两个正整数n和m,分别表示对应的奶牛场中的奶牛只数以及看了多少个对奶牛身高差。接下来的m行表示Bessie看m次后传回给FJ的m条信息,每条信息占一行,有三个整数s,t和v,表示第s只奶牛与第t只奶牛的身高差为v。
包含w行,每行是”Bessie’s eyes are good”或”Bessie is blind.”(不含双引号),其中第i行为”Bessie’s eyes are good”当且仅当第i组数据,即无法从第i个奶牛场传回的身高差判断Bessie视力好不好;第i行为”Bessie is blind.”当且仅当第i组数据,即从第i个奶牛场传回的身高差是有问题的。
2
3 3
1 3 10
2 3 5
1 2 5
4 3
1 4 100
3 4 50
1 3 100
Bessie’s eyes are good
Bessie is blind.
对于30%的数据,保证n<=100,m<=1000;
对于100%的数据,保证w<=100,n<=1000,m<=30000,|A|<=30000.
思路：
可以使用一个并查集，维护父亲节点减去儿子节点的值（儿子节点减去父亲节点也可，但需要把之后的维护反过来）用rank表示，由于a-b+b-c=a-c的性质，路径压缩的时候只要累加到根的权值和就是该点对于根的权值。合并的时候则要计算一下，如果要合并的两个节点是a,b，他们的父亲节点是x,y，如果x=y，那么说明x-a=rank[a],y-b=rank[b],a-b=v（v是输入的值），由此可得a-b=rank[y]-rank[x]，判断是否矛盾即可，如果a,b不同根，那么一定没有矛盾，只需要合并即可，但是合并的时候要重新处理a,b的rank值，还是像刚才那样设元，那么就可以得出rank[y]=rank[a]-rank[b]+d，问题到此就解决了
代码：
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<stdlib.h> 5 #include<algorithm> 6 #include<string> 7 #include<math.h> 8 using namespace std; 9 10 int f[50005]={0}; 11 int rank[50005]={0}; 12 int n; 13 void initial() 14 { 15 for(int i=1;i<=n;i++) 16 { 17 f[i]=i; rank[i]=0; 18 } 19 } 20 int find(int x){ 21 if(x==f[x]) return x; 22 int fa=f[x]; 23 f[x] = find(f[x]); 24 rank[x] += rank[fa]; 25 return f[x]; 26 } 27 bool istrue(int x, int y, int d){ 28 int ra=find(x), rb=find(y); 29 if(ra==rb){ 30 if(rank[y]-rank[x]!=d) return false; 31 return true; 32 } 33 34 f[rb] = ra; 35 36 rank[rb] = rank[x]-rank[y]+d; 37 38 return true; 39 40 } 41 42 43 44 int main() 45 46 { 47 48 int iw; 49 50 scanf("%d",&iw); 51 52 while (iw--) 53 54 { 55 56 int k,i,x,y,d; int ans=0; 57 58 scanf("%d%d",&n,&k); 59 60 initial(); 61 62 bool flag=true; 63 64 for(i=1;i<=k;i++) 65 66 { 67 68 scanf("%d%d%d",&x,&y,&d); 69 70 if( !istrue(x,y,d) ) 71 72 { 73 74 if (flag) printf("Bessie is blind. "); 75 76 flag=false; 77 78 } 79 80 } 81 82 if (flag) 83 84 printf("Bessie's eyes are good "); 85 86 } 87 88 }
NOIP模拟赛 集合
【题目描述】
现在给你一些连续的整数，它们是从 A 到 B 的整数。一开始每个整数都属于各自的集 合，然后你需要进行一下的操作： 每次选择两个属于不同集合的整数，如果这两个整数拥有大于等于 P 的公共质因数， 那么把它们所在的集合合并。 反复如上操作，直到没有可以合并的集合为止。 现在 Caima 想知道，最后有多少个集合。
【输入格式】
一行，三个整数 A,B,P。
【输出格式】
一个数，表示最终集合的个数。
【数据规模】
A≤B≤100000； 2≤P≤B。
【输入样例】
10 20 3
【输出样例】
7
【注意事项】
有 80%的数据 B≤1000。 样例解释{10,20,12,15,18}，{13}，{14}，{16}，{17}，{19}。
思路：
逐一枚举质因数，然后并查集合并
代码：
1 #include<cstring> 2 #include<iostream> 3 using namespace std; 4 #define N 100005 5 6 bool vis[N]; 7 int p[N], cnt, phi[N],father[N],prime[N],choose[N]; 8 int a,b,k; 9 int Eratosthenes (int n){ 10 int i, j, k; 11 phi[1] = 1; 12 for (i = 2; i < n; ++i){ 13 if (!vis[i]) p[cnt++] = i,prime[i] = 1; 14 for (j = i; j < n; j += i) { 15 if (!phi[j]) phi[j] = j; 16 phi[j] = phi[j] / i * (i - 1); 17 vis[j] = true; 18 } 19 } 20 return cnt; 21 } 22 int findf(int x){ 23 int j = x,t; 24 while(father[x] != x) x = father[x]; 25 while(j != x){ 26 t = father[j]; 27 father[j] = t; 28 j = t; 29 } 30 return x; 31 } 32 int main(){ 33 //freopen("set.in","r",stdin); 34 //freopen("set.out","w",stdout); 35 cin>>a>>b>>k; 36 for(int i = 1;i <= b;i++) father[i] = i; 37 Eratosthenes(b); 38 for(int i = k;i <= b;i++){ 39 if(prime[i]){ 40 for(int j = 1;j * i <= b;j++){ 41 if(j*i < a) continue; 42 father[findf(j*i)] = findf(i); 43 } 44 } 45 } 46 int ans = 0; 47 48 for(int i = 1;i <= b;i++) father[i] = findf(i); 49 for(int i = a;i <= b;i++){ 50 if(!choose[father[i]]){ 51 choose[father[i]] = 1; 52 ans++; 53 } 54 } 55 cout<<ans; 56 return 0; 57 }