【2018百度之星初赛 B】1001并查集 1004二分 1006不等式

1001 degree

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6380

并查集向图中加点，分别记录与初始度数最多的点直接相连的点数、独立的点数；则间接相连的点数 = n-1-直接相连的点数；

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 #include<map>
 5 using namespace std;
 6 
 7 int T,n,m,k;
 8 int f[200005], a[200005];
 9 
10 int find(int x) {
11     if(f[x]!=x)
12         f[x]=find(f[x]);
13     return f[x];
14 }
15 
16 void Union(int x, int y) {
17     int w = find(x);
18     int s = find(y);
19     f[w] = s;
20 }
21 
22 int main()
23 {
24     cin>>T;
25     while(T--)
26     {
27         cin>>n>>m>>k;
28         for(int i=0; i<n; i++) {
29             a[i]=0; f[i]=i;
30         }
31         int maxn=0, maxx=0;
32         for(int x,y,i=0; i<m; i++) {
33             cin>>x>>y;
34             Union(x, y);
35             if(x==y) continue;
36             a[x]++, a[y]++;
37             if(a[x]>maxn) maxx=x, maxn=a[x];
38             if(a[y]>maxn) maxx=y, maxn=a[y];
39         }
40         
41         int root = find(maxx);
42         for(int i=0; i<n; i++) {
43             int t = find(i);
44             if(t==i && t!=root) maxn++;
45         }
46 
47         int dir = n-maxn-1;
48         if(k>=dir) maxn=n-1;
49         else maxn+=k;
50         
51         if(!n) maxn = 0;
52         cout<<maxn<<endl;
53     }
54     return 0;
55 }

1004 p1m2

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6383

找出数列中最大值和最小值，二分枚举答案，对于每一个答案都循环计算一次；思想同二分查找，每次答案所在区间缩小一半；

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 #define min(a,b) a>b?b:a
 6 #define LL long long 
 7 const int N = 300005;
 8 LL T, n, a[N];
 9 
10 int main()
11 {
12     ios::sync_with_stdio(false);
13     cin>>T;
14     while(T--)
15     {
16         cin>>n;
17         LL minn=1e9, maxn=-1;
18         for(int i=0; i<n; i++) {
19             cin>>a[i];
20             minn = min(a[i], minn);
21             maxn = max(a[i], maxn);
22         }
23         
24         while(minn <= maxn) {
25             LL mid = (minn+maxn)/2, tmp = 0;
26             for(int i=0; i<n; i++) {
27                 if(a[i]>mid) tmp += (a[i]-mid)/2;
28                 else tmp += a[i]-mid;
29             }
30             if(tmp<0)
31                 maxn = mid-1;
32             else
33                 minn = mid+1;
34         }
35         cout<<maxn<<endl;
36     }
37     
38     return 0;
39 }

1006 rect

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6385

假设有交叉线的情况存在，对这种假设列满足条件的不等式，发现矛盾，所以不存在交叉线情况；

 1 #include<iostream>
 2 using namespace std;
 3 
 4 #define min(a,b) a>b?b:a
 5 #define LL long long
 6 int T;
 7 LL mx, my, n;
 8 
 9 int main()
10 {
11     cin>>T;
12     while(T--) {
13         cin>>mx>>my>>n;
14         
15         LL ans=0;
16         int x,y;
17         for(int i=0; i<n; i++) {
18             cin>>x>>y;
19             if(x<=mx/2 && y<=my/2) ans += min(x,y);
20             else if(x>=mx/2 && y<=my/2) ans += min(mx-x, y);
21             else if(x>=mx/2 && y>=my/2) ans += min(mx-x, my-y);
22             else if(x<=mx/2 && y>=my/2) ans += min(x, my-y);
23         }
24         cout<<ans<<endl;
25     }
26     
27     return 0;
28 }