Codeforces Beta Round #34 解题报告

发表于 分类于

嗯，今晚状态不错，除了卡最后一题以外没有什么太大的问题。

最后一题到最后还是 wa 了，估计卡精度卡的不够好。

A Reconnaissance 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
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int ar[1100];

int main() {
  int n;
  int ret = 0;
  int a, b;
  int now;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &ar[i]);
  }
  ret = abs(ar[n] - ar[1]);
  a = 1;
  b = n;
  for (int i = 1; i < n; i++) {
    now = abs(ar[i] - ar[i + 1]);
    if (now < ret) {
      ret = now;
      a = i;
      b = i + 1;
    }
  }
  printf("%d %d\n", a, b);
  return 0;
}

B Sale

这题还是水，贪心，直接找到最小的 mm 个加起来，注意要小于 00 的，大于等于 00 的就 break，先排序。

注意 nn 和 mm 双重限制，i<ni<n 和 j<mj<m

我的代码：

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
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int ar[1100];

int main() {
  int n, m;
  int ret = 0;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", &ar[i]);
  }
  sort(ar, ar + n);
  for (int i = 0, j = 0; i < n && j < m; i++) {
    if (ar[i] < 0) {
      j++;
      ret -= ar[i];
    } else {
      break;
    }
  }
  printf("%d\n", ret);
  return 0;
}

C Page Numbers

这题直接排序，找相邻的两个数字是不是连在一起的，是就归在一起，否则新开一个区间，把原来的区间打印出来。

我的代码：

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
46
47
48
49
50
51
52
53
54
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

char s[11000] = {0};
int ar[120], n = 0;

void hash() {
  int now;
  for (int i = 0; s[i]; i++) {
    now = 0;
    while (s[i] && s[i] != ',') {
      now = now * 10 + s[i++] - '0';
    }
    ar[n++] = now;
  }
}

int main() {
  gets(s);
  hash();
  int fi, se;
  bool flag = false;
  sort(ar, ar + n);
  fi = se = ar[0];
  for (int i = 1; i < n; i++) {
    if (ar[i] == ar[i - 1] || ar[i] == ar[i - 1] + 1) {
      se = ar[i];
    } else {
      if (flag)
        putchar(',');
      else
        flag = true;
      if (fi == se)
        printf("%d", fi);
      else
        printf("%d-%d", fi, se);
      fi = se = ar[i];
    }
  }
  if (flag)
    putchar(',');
  else
    flag = true;
  if (fi == se)
    printf("%d", fi);
  else
    printf("%d-%d", fi, se);
  puts("");
  return 0;
}

D Road Map

基础图论，建立一颗树，注意根是 r1r_1，第一步就是连边，然后直接从 r2r_2 开始 DFS，记录父亲就可以了，由于 nn 很大，开成邻接表。

我的代码：

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
46
47
48
49
50
51
52
53
54
55
56
57
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAX = 51000;

struct Edge {
  int num, ne;
} e[2 * MAX];
int p[MAX], K;
int val[MAX], vis[MAX] = {0};

void add(const int& u, const int& v) {
  e[K].num = v;
  e[K].ne = p[u];
  p[u] = K++;
}

void dfs(int k, int fa) {
  val[k] = fa;
  for (int i = p[k]; i != -1; i = e[i].ne) {
    if (!vis[e[i].num]) {
      vis[e[i].num] = true;
      dfs(e[i].num, k);
    }
  }
}

int main() {
  int n, r1, r2;
  int x;
  scanf("%d%d%d", &n, &r1, &r2);
  for (int i = 1; i <= n; i++) p[i] = -1;
  K = 0;
  for (int i = 1; i <= n; i++) {
    if (i == r1) continue;
    scanf("%d", &x);
    add(i, x);
    add(x, i);
  }
  vis[r2] = true;
  dfs(r2, 0);
  bool done = false;
  for (int i = 1; i <= n; i++) {
    if (i == r2) continue;
    if (done)
      putchar(' ');
    else
      done = true;
    printf("%d", val[i]);
  }
  puts("");
  return 0;
}

总结：恶心模拟还是没写够 - -，计算几何太薄弱 - -