Codeforces Beta Round #29 ACD 解题报告

发表于 分类于

好吧。。我的第二题现在还是挂着，算了，就把第二题无视掉吧，贴一下 ACD 的解题思路。

A

水题，不说太多，直接模拟就可以了，用 aa 数组表示指定位置的 dd，为了防止出现负数，把 xx 都加了 2000020000，读取了一个 xx 和一个 dd，判断 a[x+d]a[x+d] 是否是 −d-d 即可，如果是，就说明找到了一对。

我的代码：

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

using namespace std;

const int step = 20000;

int a[100000];

int main() {
  int n;
  int x, d;
  scanf("%d", &n);
  while (n--) {
    scanf("%d%d", &x, &d);
    x += step;
    if (a[x + d] == -d) {
      puts("YES");
      return 0;
    } else
      a[x] = d;
  }
  puts("NO");
  return 0;
}

C

欧拉通路变形，因为要保证每个点都访问到一次，于是就找从奇度数结点出发进行 dfs，运用类似套圈法的方法来把结点加入路径中。

还要注意因为范围很大，所以需要离散化，或者用 map 来存放结点信息。

我的代码：

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
#include <cstdio>
#include <cstring>
#include <list>
#include <map>
#include <string>
#include <vector>

using namespace std;

int n;
map<int, list<int> > lst;  // 邻接表
vector<int> ret;           // 最后结果
map<int, int> d;           // 度数
map<int, bool> use;        // 访问标记

void dfs(int u) {
  int v;
  list<int>& l = lst[u];
  while (!l.empty()) {
    v = *(l.begin());
    l.pop_front();
    if (!use[v]) dfs(v);
  }
  ret.push_back(u);
}

int main() {
  int n, s;
  int x, y;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &x, &y);
    lst[x].push_back(y);
    lst[y].push_back(x);
    d[x]++;
    d[y]++;
  }
  // 找到度数是奇数的点作为起点
  for (map<int, int>::iterator it = d.begin(); it != d.end(); it++) {
    if ((it->second) % 2) {
      s = it->first;
      break;
    }
  }
  dfs(s);
  for (int i = 0; i < n; i++) printf("%d ", ret[i]);
  printf("%d\n", ret[n]);
  return 0;
}

D

经典 LCA 问题，为了得到有顺序的结点，我们求出相邻的结点的 LCA 即可，建议大家先看相关的资料再理解这个算法。

我的代码：

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
const int MAX = 305;
int lst[MAX][MAX];  // 邻接表
int father[MAX];    // 父亲结点
bool vis[MAX];      // 访问数组
bool leaf[MAX];     // 是否是叶子
int order[MAX];     // 叶子的顺序
int lca[MAX];       // order[i]和order[i+1]的LCA

// dfs判断叶子数量
void dfs(int x) {
  bool flag = false;
  vis[x] = true;
  for (int i = 1; i <= lst[x][0]; i++) {
    if (!vis[lst[x][i]]) {
      flag = true;
      father[lst[x][i]] = x;
      dfs(lst[x][i]);
    }
  }
  if (!flag) leaf[x] = true;
}

int st[MAX], cnt[MAX][MAX];
int ret[600000];

int main() {
  int x, y, n;
  int nleaf, temp, P, top;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) lst[i][0] = 0;
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    lst[x][0]++;
    lst[x][lst[x][0]] = y;
    lst[y][0]++;
    lst[y][lst[y][0]] = x;
  }
  for (int i = 1; i <= n; i++) {
    vis[i] = false;
    leaf[i] = false;
  }
  father[1] = -1;
  dfs(1);
  nleaf = 0;
  for (int i = 1; i <= n; i++)
    if (leaf[i]) nleaf++;
  for (int i = 1; i <= nleaf; i++) scanf("%d", &order[i]);
  for (int i = 1; i < nleaf; i++) {
    for (int j = 1; j <= n; j++) vis[j] = false;
    temp = order[i];  // 向上寻找祖先
    while (temp != 1) {
      vis[temp] = 1;
      temp = father[temp];
    }
    temp = order[i + 1];
    vis[1] = true;
    while (temp != 1) {
      if (vis[temp]) break;
      temp = father[temp];
    }
    lca[i] = temp;
  }
  order[0] = 1;
  lca[0] = 1;
  lca[nleaf] = 1;
  order[nleaf + 1] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) cnt[i][j] = 0;
  P = 1;
  ret[0] = 1;
  for (int i = 1; i <= nleaf; i++) {
    temp = order[i];
    top = 0;
    while (temp != lca[i - 1]) {
      st[top++] = temp;
      cnt[temp][father[temp]]++;
      cnt[father[temp]][temp]++;
      if (cnt[father[temp]][temp] > 2) {
        puts("-1");
        return 0;
      }
      temp = father[temp];
    }
    for (int j = top - 1; j >= 0; j--) ret[P++] = st[j];
    temp = order[i];
    top = 0;
    while (temp != lca[i]) {
      st[top++] = temp;
      cnt[temp][father[temp]]++;
      cnt[father[temp]][temp]++;
      if (cnt[father[temp]][temp] > 2) {
        puts("-1");
        return 0;
      }
      temp = father[temp];
    }
    st[top] = lca[i];
    for (int j = 1; j <= top; j++) ret[P++] = st[j];
  }
  for (int i = 0; i < P - 1; i++) printf("%d ", ret[i]);
  printf("%d\n", ret[P - 1]);
}