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，问题到此就解决了
代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std; int f[]={};
int rank[]={};
int n;
void initial()
{
for(int i=;i<=n;i++)
{
f[i]=i; rank[i]=;
}
}
int find(int x){
if(x==f[x]) return x;
int fa=f[x];
f[x] = find(f[x]);
rank[x] += rank[fa];
return f[x];
}
bool istrue(int x, int y, int d){
int ra=find(x), rb=find(y);
if(ra==rb){
if(rank[y]-rank[x]!=d) return false;
return true;
} f[rb] = ra; rank[rb] = rank[x]-rank[y]+d; return true; } int main() { int iw; scanf("%d",&iw); while (iw--) { int k,i,x,y,d; int ans=; scanf("%d%d",&n,&k); initial(); bool flag=true; for(i=;i<=k;i++) { scanf("%d%d%d",&x,&y,&d); if( !istrue(x,y,d) ) { if (flag) printf("Bessie is blind.\n"); flag=false; } } if (flag) printf("Bessie's eyes are good\n"); } }
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}。
思路：
逐一枚举质因数，然后并查集合并
代码：
#include<cstring>
#include<iostream>
using namespace std;
#define N 100005 bool vis[N];
int p[N], cnt, phi[N],father[N],prime[N],choose[N];
int a,b,k;
int Eratosthenes (int n){
int i, j, k;
phi[] = ;
for (i = ; i < n; ++i){
if (!vis[i]) p[cnt++] = i,prime[i] = ;
for (j = i; j < n; j += i) {
if (!phi[j]) phi[j] = j;
phi[j] = phi[j] / i * (i - );
vis[j] = true;
}
}
return cnt;
}
int findf(int x){
int j = x,t;
while(father[x] != x) x = father[x];
while(j != x){
t = father[j];
father[j] = t;
j = t;
}
return x;
}
int main(){
//freopen("set.in","r",stdin);
//freopen("set.out","w",stdout);
cin>>a>>b>>k;
for(int i = ;i <= b;i++) father[i] = i;
Eratosthenes(b);
for(int i = k;i <= b;i++){
if(prime[i]){
for(int j = ;j * i <= b;j++){
if(j*i < a) continue;
father[findf(j*i)] = findf(i);
}
}
}
int ans = ; for(int i = ;i <= b;i++) father[i] = findf(i);
for(int i = a;i <= b;i++){
if(!choose[father[i]]){
choose[father[i]] = ;
ans++;
}
}
cout<<ans;
return ;
}