训练

2019 China Collegiate Programming Contest Qinhuangdao Onsite

A B C D E F G H I J K L
O x x O Ø O x x O O O x
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • x 没有尝试

A. Angle Beats

给定$n$个点$P_i$和$q$个点$A_i$，问对于每个\(A_i\) ，有多少二元组$(u, v), 1 ≤ u < v ≤ n$，满足$A_i, P_u, P_v$构成了一个直角三角形。

如果三个点构成了一个直角三角形，那么存在两个方向向量点积为$0$。所有只需要用 map 存下各个向量的数目即可。注意需要约分和判断特殊情况。

PS：在查询时最好使用迭代器而不是方括号，避免扩大 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
50
51
52
53
54
55
56
57
58
59

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 2e3 + 3;
pii a[MAXN], b[MAXN];
int ans[MAXN];
map<pii, int> cnt;

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(10);

  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;
  for (int i = 0; i < q; ++i) cin >> b[i].first >> b[i].second;

  auto gao = [](int a, int b) {
    if (a == 0) return make_pair(0, 1);
    if (b == 0) return make_pair(1, 0);
    int g = __gcd(a, b);
    a /= g, b /= g;
    if (a < 0) return make_pair(-a, -b);
    return make_pair(a, b);
  };

  for (int i = 0; i < q; ++i) {
    cnt.clear();
    for (int j = 0; j < n; ++j) {
      int dx = a[j].first - b[i].first, dy = a[j].second - b[i].second;
      ++cnt[gao(dx, dy)];
      auto it = cnt.find(gao(-dy, dx));
      if (it != cnt.end()) ans[i] += it->second;
    }
  }

  for (int i = 0; i < n; ++i) {
    cnt.clear();
    for (int j = 0; j < n; ++j) {
      if (i == j) continue;
      int dx = a[j].first - a[i].first, dy = a[j].second - a[i].second;
      ++cnt[gao(dx, dy)];
    }
    for (int j = 0; j < q; ++j) {
      int dx = b[j].first - a[i].first, dy = b[j].second - a[i].second;
      auto it = cnt.find(gao(-dy, dx));
      if (it != cnt.end()) ans[j] += it->second;
    }
  }

  for (int i = 0; i < q; ++i) cout << ans[i] << "\n";

  return 0;
}

D. Decimal

询问$\frac{1}{n}$是不是一个无限循环小数。

判断$n$是否为$2^a × 5^b$即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

# include <bits/stdc++.h>
# define LL long long

using namespace std;

int T,x;

int main(){
  scanf("%d",&T);
  while (T--)
  {
    scanf("%d",&x);
    while (x % 2 == 0) x /= 2;
    while (x % 5 == 0) x /= 5;
    if (x == 1) printf("No\n");
    else printf("Yes\n");
  }
}

E. Escape

给定一个$n × m$的网格（有格子毁坏），上方有$a$个机器人，下方有$b$个出口。机器人只会直线走（初始向下），可以在好的格子中放若干个转向器，让机器人转向。问能否让所有机器人离开。

很标准的网络流，根据方向将图分为两层即可。

  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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 103;
const int MAX_NODES = 2e4 + 3;
const int MAX_EDGES = 2e5 + 3;

struct Edge {
  int to, rest;
} edges[MAX_EDGES];

vector<int> adj[MAX_NODES];
int n, m, a, b, nm, source, sink, edge_count;
int dep[MAX_NODES], depc[MAX_NODES], last[MAX_NODES];

void init() {
  edge_count = 0, nm = n * m;
  source = 0, sink = nm * 2 + 1;
  for (int i = 0; i <= sink; ++i) adj[i].clear();
}

void add_edge(int u, int v, int cap) {
  // cerr << u << " -> " << v << " : " << cap << "\n";
  edges[edge_count] = {v, cap};
  adj[u].push_back(edge_count++);
  edges[edge_count] = {u, 0};
  adj[v].push_back(edge_count++);
}

int dfs(int u, int flow) {
  if (u == sink || !flow) return flow;
  int v, e, temp, res = 0;
  for (int &i = last[u]; i < (int)adj[u].size(); ++i) {
    e = adj[u][i], v = edges[e].to;
    if (!edges[e].rest || dep[v] != dep[u] - 1) continue;
    temp = dfs(v, min(flow, edges[e].rest));
    res += temp, flow -= temp;
    edges[e].rest -= temp, edges[e ^ 1].rest += temp;
    if (!flow || !dep[source]) return res;
  }
  last[u] = 0;
  if (!--depc[dep[u]]) dep[source] = sink + 1;
  ++depc[++dep[u]];
  return res;
}

int max_flow() {
  size_t sz = sizeof(int) * (sink + 1);
  memset(dep, 0, sz);
  memset(depc, 0, sz);
  memset(last, 0, sz);

  static queue<int> q;
  dep[sink] = 1, q.push(sink);

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    ++depc[dep[u]];
    for (int e : adj[u]) {
      int v = edges[e].to;
      if (dep[v]) continue;
      dep[v] = dep[u] + 1;
      q.push(v);
    }
  }

  int res = 0;
  while (dep[source] <= sink) res += dfs(source, INT_MAX);
  return res;
}

char maze[MAXN][MAXN];
inline int idx(int i, int j, int dense) {
  return (i - 1) * m + j + (dense ? nm : 0);
}
inline bool valid(int i, int j) {
  return i >= 1 && i <= n && j >= 1 && j <= m && maze[i][j] == '0';
}

void solve() {
  cin >> n >> m >> a >> b;
  init();

  for (int i = 1; i <= n; ++i) cin >> (maze[i] + 1);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (maze[i][j] == '1') continue;

      add_edge(idx(i, j, 0), idx(i, j, 1), 1);
      add_edge(idx(i, j, 1), idx(i, j, 0), 1);

      static const int dx[] = {0, 1, 0, -1};
      static const int dy[] = {1, 0, -1, 0};
      for (int d = 0; d < 4; ++d) {
        int i_ = i + dx[d], j_ = j + dy[d];
        if (!valid(i_, j_)) continue;
        add_edge(idx(i, j, d & 1), idx(i_, j_, d & 1), 1);
      }
    }
  }

  for (int i = 0, x; i < a; ++i) {
    cin >> x;
    if (maze[1][x] == '0') add_edge(source, idx(1, x, 1), 1);
  }
  for (int i = 0, x; i < b; ++i) {
    cin >> x;
    if (maze[n][x] == '0') add_edge(idx(n, x, 1), sink, 1);
  }
  cout << (max_flow() == a ? "Yes\n" : "No\n");
}

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  int o_o;
  for (cin >> o_o; o_o; --o_o) solve();

  return 0;
}

I. Invoker

给定一系列技能，每个技能需要三个特定元素在技能槽（容量为三）中。询问实现给定技能串需要的最小的操作序列。

使状压 DP 即可

 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

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 1e5 + 3;
const int INF = 0x3f3f3f3f;

char s[MAXN];
int d[MAXN][27];
char skill[4][4][4];
// Q:0 W:1 E:2

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(10);

  skill[3][0][0] = 'Y';
  skill[2][1][0] = 'V';
  skill[2][0][1] = 'G';
  skill[0][3][0] = 'C';
  skill[1][2][0] = 'X';
  skill[0][2][1] = 'Z';
  skill[0][0][3] = 'T';
  skill[1][0][2] = 'F';
  skill[0][1][2] = 'D';
  skill[1][1][1] = 'B';

  auto gao = [&](int s) {
    int c[3] = {0};
    ++c[s % 3], s /= 3;
    ++c[s % 3], s /= 3;
    ++c[s % 3];
    return skill[c[0]][c[1]][c[2]];
  };

  cin >> s;
  int n = strlen(s);
  memset(d, 0x3f, sizeof(d));
  queue<pii> q;
  for (int s = 0; s < 27; ++s) {
    d[0][s] = 3;
    q.emplace(0, s);
  }

  while (!q.empty()) {
    pii p = q.front();
    int step = p.first, s = p.second, dp = d[step][s];
    q.pop();

    // cerr << step << " " << s << " " << dp << endl;
    if (step == n) continue;
    char sk = gao(s);
    if (sk == ::s[step] && dp + 1 < d[step + 1][s]) {
      d[step + 1][s] = dp + 1;
      q.emplace(step + 1, s);
    }
    for (int i = 0; i < 3; ++i) {
      int _s = (s * 3 + i) % 27;
      if (dp + 1 < d[step][_s]) {
        d[step][_s] = dp + 1;
        q.emplace(step, _s);
      }
    }
  }

  int ans = INT_MAX;
  for (int i = 0; i < 27; ++i) ans = min(ans, d[n][i]);
  cout << ans << "\n";

  return 0;
}

J. MUV LUV EXTRA

给定一个小数的前面部分，判断循环节，输出得分最高的节的得分。

倒着做一次 KMP 就好了。

 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

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 1e7 + 3;

int nxt[MAXN];
char s[MAXN], str[MAXN];

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  int a, b, n, m = 0;
  cin >> a >> b >> s;
  n = strlen(s);
  for (int i = n - 1; ~i; --i) {
    if (s[i] == '.') break;
    str[m++] = s[i];
  }

  nxt[0] = -1;
  for (int i = 1, j = -1; i < m; ++i) {
    while ((~j) && str[j + 1] != str[i]) j = nxt[j];
    nxt[i] = (str[j + 1] == str[i]) ? (++j) : j;
  }

  ll ans = LLONG_MIN;
  for (int i = 0; i < m; ++i) {
    ans = max(ans, 1ll * a * (i + 1) - 1ll * b * (i - nxt[i]));
  }
  cout << ans << "\n";

  return 0;
}

K. MUV LUV UNLIMITED

给定一棵树，每次可以删除若干个叶子节点，无法删除的一方输。

对于每一个树枝，若其长度为奇数，则先手胜。证明方法则是按照奇偶分类，操作对二取模即可。

 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

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 6;

int p[MAXN], son[MAXN];

void solve() {
  int n;
  cin >> n;
  memset(son + 1, 0, sizeof(int) * n);
  for (int i = 2; i <= n; ++i) {
    cin >> p[i];
    ++son[p[i]];
  }

  for (int i = 1; i <= n; ++i) {
    if (son[i]) continue;
    int cnt = 0, u = i;
    while (u && son[u] < 2) {
      ++cnt;
      u = p[u];
    }
    if (cnt & 1) {
      cout << "Takeru\n";
      return;
    }
  }
  cout << "Meiya\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int o_o;
  for (cin >> o_o; o_o; --o_o) solve();
  return 0;
}
comments powered by Disqus