Codeforces Beta Round #27 ABC 题

发表于 分类于

因为今天要打区域赛的缘故，昨晚 CF 没有做，现在放出 ABC 的思路，后两题表示不怎么会，一题图论，一题数论，平时都是队友搞定的。。。

A Next Test

这题很简单，写的暴力点也无妨，n≤50n \leq 50 的，开个 32003200 大小的数组，然后记录 use[i]use[i] 表示 i 这个序号是否被用过，然后从头到尾循环一遍即可，时间复杂度是 O(n)O(n) 的。

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

bool use[3200] = {0};

int main() {
  int n, id;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &id);
    use[id] = true;
  }
  for (int i = 1; i < 3200; i++)
    if (!use[i]) {
      printf("%d\n", i);
      break;
    }
  return 0;
}

B Tournament

这题要求找到剩下的那场比赛的结果，这题可以转化一下模型，告诉你一个有向无环图，缺了一条边，并且要保证全部点连通 (弱连通)，可以先用一个数组标记有向边，nn 很小，直接建个邻接矩阵，然后剩下两个没有连边的随便加一条，跑 bfs 看是否有回路，如果没有，那么说明这条边是正确的，否则就将这条边反向一下。最后输出这条边的两个端点就可以了。

我的代码：

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

using namespace std;

bool mp[100][100] = {0};
int n;

bool bfs(int st) {
  bool vis[100] = {0};
  queue<int> q;
  int now;
  q.push(st);
  while (!q.empty()) {
    now = q.front();
    q.pop();
    for (int i = 1; i <= n; i++) {
      if (mp[now][i] && !vis[i]) {
        if (i == st) return false;
        vis[i] = true;
        q.push(i);
      }
    }
  }
  return true;
}

int main() {
  int t;
  int x, y;
  scanf("%d", &n);
  t = n * (n - 1) / 2 - 1;
  for (int i = 0; i < t; i++) {
    scanf("%d%d", &x, &y);
    mp[x][y] = true;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      if (mp[i][j] == false && mp[j][i] == false) {
        mp[i][j] = true;
        if (!bfs(i)) {
          printf("%d %d\n", j, i);
        } else {
          printf("%d %d\n", i, j);
        }
        return 0;
      }
    }
  }
  return 0;
}

C Unordered Subsequence

这题直接模拟，如果原来的序列是有序的，那么就输出 00，否则答案一定是 33，剩下的三个数。可以取第一个，转折点，还有就是转折点之后的第一个点。

之前要先把相等的数字去掉，然后找到第一个不同的数字当做第一个和第二个答案。

时间复杂度是 O(n)O(n) 的。

我的代码：

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

using namespace std;

const int MAX = 100010;

int main() {
  bool up;
  int n, st;
  int a[MAX];
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  st = 0;
  while (st < n - 1 && a[st] == a[st + 1]) st++;
  if (n - st <= 2) {
    puts("0");
    return 0;
  }
  if (a[st + 1] > a[st])
    up = true;
  else
    up = false;
  if (up) {
    for (int i = st + 2; i < n; i++) {
      if (a[i] < a[i - 1]) {
        puts("3");
        printf("%d %d %d\n", st + 1, i, i + 1);
        return 0;
      }
    }
    puts("0");
  } else {
    for (int i = 2; i < n; i++) {
      if (a[i] > a[i - 1]) {
        puts("3");
        printf("%d %d %d\n", st + 1, i, i + 1);
        return 0;
      }
    }
    puts("0");
  }
  return 0;
}