Codeforces Beta Round #24 ABC

发表于 分类于

做过 TC 的比赛感觉上了相对来说，Code Forces 的比赛应该会简单一些，不过很可惜，那晚第三题并没有拍出来，可能是时间不够了，卡在第一题上太久，有点悲剧。。。。

A.Rind Road

这题之前把它看成了图论的题目，没有看清题意，导致到了比赛前半个钟头才写出来，其实很简单，题意大概是说，有 nn 个城市和 nn 条单行道，所有的城市通过单行道连接成了一个环，每个单行道都有一个权值 cc，如果要将单行道改个方向，就要花费 cc 的价钱，现在我们的任务就是花费最小的价钱把 nn 条单行道方向变成同向。

我的方法是将城市看成结点，单行道看成有向边，建立一个图，由于 n≤100n \leq 100，可以利用邻接矩阵来存储，最后从任意一个点出发，正反地跑两次 DFS，如果遇到权值为负的边 (边的方向和遍历的方向相反)，则把费用加 c。最后输出两个费用的较小值。

后来想了想，可以只跑一次 DFS，然后把权值总和减去第一次的值就是我们第二次 DFS 得到的值。

我原版的代码。

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

using namespace std;

int a[101][2], w1[101][2], total, total1, mark[105];

void dfs(int u) {
  int i;
  mark[u] = 1;
  for (i = 0; i <= 1; i++)
    if (!mark[a[u][i]]) {
      if (w1[u][i] < 0) total += (-w1[u][i]);
      dfs(a[u][i]);
    }
}

void dfs1(int u) {
  int i;
  mark[u] = 1;
  for (i = 1; i >= 0; i--)
    if (!mark[a[u][i]]) {
      if (w1[u][i] < 0) total1 += (-w1[u][i]);
      dfs1(a[u][i]);
    }
}

int main() {
  int n, i, x, y, w;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d%d%d", &x, &y, &w);
    if (!a[x][0]) {
      a[x][0] = y;
      w1[x][0] = w;
    } else {
      a[x][1] = y;
      w1[x][1] = w;
    }
    if (!a[y][0]) {
      a[y][0] = x;
      w1[y][0] = -w;
    } else {
      a[y][1] = x;
      w1[y][1] = -w;
    }
  }
  total = 0;
  dfs(1);
  if (w1[1][1] > 0) total += w1[1][1];
  memset(mark, 0, sizeof(mark));
  total1 = 0;
  dfs1(1);
  if (w1[1][0] > 0) total1 += w1[1][0];
  if (total1 < total)
    printf("%d\n", total1);
  else
    printf("%d\n", total);
}

B.F1 Champions

这题是我过的最快的一题，简单的排序，手写比较函数就可以了，题目大意是说，F1 比赛的冠军判断标准有两种，第一种判断积分大小，当积分相等的时候判断获得第一名的次数，还相等的话，判断获得第二的次数，以此类推；第二种判断获得第一名的次数，相等，则判断积分大小，还相等的话和第一种一样，依次比较第二名、第三名。。。

写两个函数比较，分别进行两次排序，输出第一名即可。

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

using namespace std;

const int rate[] = {25, 18, 15, 12, 10, 8, 6, 4, 2, 1};

struct Node {
  string name;
  int point;
  int rank[51];
  Node() {
    name = "";
    point = 0;
    memset(rank, 0, sizeof(rank));
  }
} node[51];
map<string, int> mp;

bool comp1(const Node& a, const Node& b) {
  if (a.point != b.point) return a.point > b.point;
  for (int i = 0; i < 51; i++)
    if (a.rank[i] != b.rank[i]) return a.rank[i] > b.rank[i];
  return a.name < b.name;
}

bool comp2(const Node& a, const Node& b) {
  if (a.rank[0] != b.rank[0])
    return a.rank[0] > b.rank[0];
  else if (a.point != b.point)
    return a.point > b.point;
  for (int i = 1; i < 51; i++)
    if (a.rank[i] != b.rank[i]) return a.rank[i] > b.rank[i];
  return a.name < b.name;
}

int main() {
  int t, n, cnt = 0, pos;
  string name;
  char str[100];
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      scanf("%s", str);
      name = str;
      if (mp[name] == 0) {
        cnt++;
        mp[name] = cnt;
        node[cnt].name = name;
      }
      pos = mp[name];
      node[pos].rank[i]++;
      if (i < 10) node[pos].point += rate[i];
    }
  }
  sort(node + 1, node + cnt + 1, comp1);
  printf("%s\n", node[1].name.c_str());
  sort(node + 1, node + cnt + 1, comp2);
  printf("%s\n", node[1].name.c_str());
  return 0;
}

C.Sequence of Point

这题比较简单，比赛的时候写完代码测试数据没过，也没时间去改，就放弃了，将题意理清之后的到一些公式：

这样将全部式子加起来，就可以得到完整的公式，由于 AiA_i 有周期，我们可以将其取模 2n2n，然后进行计算，为了计算方便，我重载了运算符，封装了一个点的结构体，其实算是向量了。。。

注意题目给的 jj 奇数偶数的时候 M0M_0 前面的符号不同

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

using namespace std;

struct Point {
  int x;
  int y;
  Point(int x = 0, int y = 0) {
    this->x = x;
    this->y = y;
  }
  Point(const Point& point) {
    x = point.x;
    y = point.y;
  }
  ~Point() {}
  Point operator+(const Point& p) { return Point(x + p.x, y + p.y); }
  Point operator-(const Point& p) { return Point(x - p.x, y - p.y); }
  int operator*(const Point& p) { return x * p.x + y * p.y; }
  void Show() { printf("%d %d\n", x, y); }
  void Set(const int& x = 0, const int& y = 0) {
    this->x = x;
    this->y = y;
  }
};
Point m0, a[100100];

int main() {
  int n;
  __int64 k;
  int x, y;
  Point ret(0, 0);
  scanf("%d%I64d", &n, &k);
  scanf("%d%d", &x, &y);
  m0.Set(x, y);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &x, &y);
    a[i].Set(x, y);
  }
  int len = k % (2 * n);
  bool flag = true;
  for (int i = 0; i < len; i++) {
    if (flag)
      ret = ret + a[(k - i - 1) % n];
    else
      ret = ret - a[(k - i - 1) % n];
    flag = !flag;
  }
  ret.x *= 2;
  ret.y *= 2;
  if (k % 2)
    ret = ret - m0;
  else
    ret = ret + m0;
  ret.Show();
  return 0;
}