2018百度之星-初赛（B）ADF题解

发表于 | 更新于 | 分类于 ， ， | 评论数： | 阅读次数：

链接：http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=826

只会签到。。。

A： 因为无限添加，考虑先把另外一些树加到这个点上，再把其他子树的叶子加到某一个点上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200200;
int n, m, k;
int in[maxn];
int pre[maxn];

int find(int x) { return x == pre[x] ? x : pre[x] = find(pre[x]); }
int unite(int x, int y) { pre[find(x)] = find(y); }

signed main() {
  // freopen("in", "r", stdin);
  int T, u, v;
  scanf("%d", &T);
  while(T--) {
    scanf("%d%d%d",&n,&m,&k);
    memset(in, 0, sizeof(in));
    for(int i = 0; i < n; i++) pre[i] = i;
    for(int i = 0; i < m; i++) {
      scanf("%d%d",&u,&v);
      in[u]++, in[v]++;
    }
    int ret = 0;
    for(int i = 0; i < n; i++) {
      ret = max(ret, in[i]+n-in[i]-1-max(0, m-in[i]-k));
    }
    printf("%d\n", ret);
  }
  return 0;
}

D：这题直接二分答案，即最小的那个数字。然后按照这个数字来划分是加还是减，保证加的次数的2倍比减的次数多就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const LL maxn = 300200;
LL n;
LL x[maxn];

LL gao(LL mid) {
  LL a = 0, b = 0;
  for(int i = 1; i <= n; i++) {
    if(x[i] > mid+1) {
      b += (x[i] - mid) / 2;
    }
    else a += max(0LL, mid-x[i]);
  }
  return  b >= a;
}

signed main() {
  // freopen("in", "r", stdin);
  LL T;
  scanf("%I64d", &T);
  while(T--) {
    scanf("%I64d", &n);
    for(LL i = 1; i <= n; i++) {
      scanf("%I64d", &x[i]);
    }
    sort(x+1, x+n+1);
    LL lo = 0, hi = 1E9;
    LL ret = 0;
    while(lo <= hi) {
      LL mid = (lo + hi) >> 1;
      if(gao(mid)) {
        lo = mid + 1;
        ret = mid;
      }
      else {
        hi = mid - 1;
      }
    }
    printf("%I64d\n", ret);
  }
  return 0;
}

F：因为$x_i$和$y_i$不会存在重复的，那么直接垂直接到最近的边上就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
LL mx, my, q, x, y;

signed main() {
  // freopen("in", "r", stdin);
  int T;
  cin >> T;
  while(T--) {
      cin >> mx >> my >> q;
      LL ret = 0;
      while(q--) {
          cin >> x >> y;
          LL tmp = x < mx - x ? x : mx - x;
          if(x < mx - x) tmp = x;
          else tmp = mx - x;
          if(tmp >= y) tmp = y;
          if(tmp >= my - y) tmp = my - y;
          ret += tmp;
      }
      cout << ret << endl;
  }
  return 0;
}