2019 China Collegiate Programming Contest Final (CCPC-Final 2019)

A	B	C	D	E	F	G	H	I	J	K	L
+1	+1	+		+3				+1		+	+
00:50				03:29				02:55		01:01	00:24

A. Kick Start

签到题，C++ 的字符串太难了吧。。。

 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 <bits/stdc++.h>
using namespace std;

string mm[13], dd[32];
unordered_map<string, int> month, day;

void init() {
  mm[1] = "Jan", mm[2] = "Feb", mm[3] = "Mar", mm[4] = "Apr", mm[5] = "May",
  mm[6] = "Jun", mm[7] = "Jul", mm[8] = "Aug", mm[9] = "Sept", mm[10] = "Oct",
  mm[11] = "Nov", mm[12] = "Dec";
  for (int i = 1; i <= 12; ++i) month[mm[i]] = i;

  for (int i = 1; i < 32; ++i) dd[i] = to_string(i) + "th";
  dd[1] = "1st", dd[2] = "2nd", dd[3] = "3rd", dd[21] = "21st", dd[22] = "22nd",
  dd[23] = "23rd", dd[31] = "31st";
  for (int i = 1; i < 32; ++i) day[dd[i]] = i;
}

void solve() {
  static string s1, s2;
  static set<pair<int, int>> s;

  int n;
  s.clear();
  for (cin >> n; n; --n) {
    cin >> s1 >> s2;
    s.emplace(month[s1], day[s2]);
  }

  cin >> s1 >> s2;
  auto p = make_pair(month[s1], day[s2]);
  auto it = s.upper_bound(p);
  if (it != s.end()) {
    cout << mm[it->first] << " " << dd[it->second] << "\n";
  } else {
    cout << "See you next year\n";
  }
}

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

  init();
  int o_o, step = 0;
  for (cin >> o_o; step < o_o; solve()) cout << "Case #" << ++step << ": ";

  return 0;
}

B. Infimum of Paths

给定一个有权图（权重为 0 到 9），询问从 0 到 1 的最短路。一条路的权值为上面数字构成的小数，即 $0.e_1e_2e_3$ 。

这位大佬的博客写的解法更多且详细。大体思路是寻找最优循环节，而在$[2n, 3n]$步内一定存在这个循环节。

  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


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

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

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

const int MOD = 1e9 + 7;
const int MAXN = 2e3 + 3;

int fpow(int a, int b) {
  int r = 1;
  for (; b; b >>= 1, a = 1ll * a * a % MOD) (b & 1) && (r = 1ll * r * a % MOD);
  return r;
}

bitset<MAXN> mark;
vector<pii> adj[MAXN];
vector<int> radj[MAXN];
int n, n3, m, q[MAXN], inv[MAXN * 3], fail[MAXN * 2], ans[MAXN * 3];

void solve() {
  cin >> n >> m;
  for (int i = 0, u, v, w; i < m; ++i) {
    cin >> u >> v >> w;
    adj[u].emplace_back(v, w);
    radj[v].push_back(u);
  }
  adj[1].emplace_back(1, 0);

  int *l = q, *r = q;
  *r++ = 1;
  mark[1] = 1;
  while (l < r) {
    int u = *l++;
    for (int v : radj[u]) {
      if (mark[v]) continue;
      mark[v] = 1;
      *r++ = v;
    }
  }

  n3 = n * 3;
  vector<int> nodes = {0};
  for (int step = 0; step < n3; ++step) {
    pair<int, vector<int>> cur(INT_MAX, {});
    for (int u : nodes)
      for (pii e : adj[u])
        if (mark[e.first]) {
          if (e.second < cur.first) {
            cur = {e.second, {e.first}};
          } else if (e.second == cur.first) {
            cur.second.push_back(e.first);
          }
        }
    ans[step] = cur.first;
    nodes = cur.second;
    sort(nodes.begin(), nodes.end());
    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
  }

  // for (int i = 0; i < n3; ++i) debug(ans[i]);

  int res = 0;
  for (int i = 0; i < n; ++i) res = (10ll * res + ans[i]) % MOD;
  res = 1ll * res * inv[n] % MOD;

  int n2 = n * 2, p = -1;
  fail[0] = -1;
  for (int i = 1; i < n2; ++i) {
    while (~p && ans[n + p + 1] != ans[n + i]) p = fail[p];
    fail[i] = ans[n + p + 1] == ans[n + i] ? ++p : p;
  }

  int cycle_len = n2 - fail[n2 - 1] - 1;
  int cycle = 0;
  for (int i = 0; i < cycle_len; ++i) cycle = (10ll * cycle + ans[i + n]) % MOD;
  cycle = 1ll * cycle * inv[cycle_len] % MOD *
          fpow(MOD + 1 - inv[cycle_len], MOD - 2) % MOD * inv[n] % MOD;
  cout << (res + cycle) % MOD << "\n";

  debug(res, cycle, cycle_len);

  for (int i = 0; i < n; ++i) {
    mark[i] = 0;
    adj[i].clear();
    radj[i].clear();
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(10);

  int inv_10 = fpow(10, MOD - 2);
  inv[0] = 1, inv[1] = inv_10;
  for (int i = 2; i < MAXN * 3; ++i) inv[i] = 1ll * inv[i - 1] * inv_10 % MOD;

  int o_o, omo = 1;
  for (cin >> o_o; omo <= o_o; ++omo, solve()) cout << "Case #" << omo << ": ";
  return 0;
}

C. Mr. Panda and Typewriter

给定一个字符串以及三种操作：

花费 X，在已经打出的字符串后面打任一字符；
花费 Y，复制现有串的任一子串到剪切板；
花费 Z，在当前字符串的末尾粘贴当前剪切板的字符串；

询问从空串打印到给定字串的最小花费。

显然这是一道动态规划，但是 DP 状态定义就难以下手。 容易发现， 在完成粘贴操作后，剪切板的串一定是打印出的串的一个后缀。所以我们可以定义$dp_{i, j}$ 表示我们已经打印出了$i$ 个字符，剪切板中内容为子串$s_{i - j + 1: i}$ 。特别地，我们定义$dp_{i, 0}$ 表示我们不关系剪切板中内容的最小代价，即我们后续不会再使用当前剪切板中的部分，这样就表示了我们剪切板内容不是当前后缀的状态。

设 $pre_{i, j}$ 表示在$s_{i - j + 1: i}$ 前方（不重叠）的最靠后相同子串的结束位置，即 $s_{i - j + 1 : i} = s_{pre_{i, j} - j + 1, pre_{i, j}}, i < pre_{i, j} - j + 1$ 。如此我们便有转移方程 \[ dp_{i, 0} = \min\{dp[i][j]\} \] \[ dp_{i, j} = \min\{dp[i - j][0] + y + z, dp[pre[i][j]][j] + x * (i - j - pre[i][j]) + z\} \]

对于 $pre$ 数组，我们可以使用最长公共后缀 $lcs$ 在 $O(n^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
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


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

typedef long long ll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

const int MOD = 1e9 + 7;
const int MAXN = 5e3 + 3;
const ll INF = 0x3f3f3f3f3f3f3f3fll;

void solve() {
  static ll dp[MAXN][MAXN];
  static int s[MAXN], lcs[MAXN][MAXN], pre[MAXN][MAXN];

  int n;
  ll x, y, z;
  cin >> n >> x >> y >> z;
  for (int i = 1; i <= n; ++i) cin >> s[i];
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= i; ++j)
      lcs[i][j] = s[i] == s[j] ? lcs[i - 1][j - 1] + 1 : 0;
  for (int i = 1; i <= n; ++i) {
    memset(pre[i] + 1, -1, sizeof(int) * n);
    for (int j = 1; j < i; ++j) pre[i][min(i - j, lcs[i][j])] = j;
    for (int j = i - 1; j; --j) pre[i][j] = max(pre[i][j], pre[i][j + 1]);
  }

  for (int i = 0; i <= n; ++i) memset(dp[i], 0x3f, sizeof(ll) * (n + 1));
  dp[1][0] = x;
  for (int i = 2; i <= n; ++i) {
    dp[i][0] = dp[i - 1][0] + x;
    for (int j = 1; j <= i; ++j) {
      if (pre[i][j] == -1) continue;
      dp[i][j] = min({dp[i][j], dp[i - j][0] + y + z,
                      dp[pre[i][j]][j] + x * (i - j - pre[i][j]) + z});
      dp[i][0] = min(dp[i][0], dp[i][j]);
    }
  }
  cout << dp[n][0] << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(10);

  int o_o, omo = 0;
  for (cin >> o_o; omo < o_o; solve()) cout << "Case #" << ++omo << ": ";
  return 0;
}

E. Non-Maximum Suppression

模拟非极大值抑制 NMS，按 IoU threshold 去除重复的检测框。

想了一个使用 KD-tree 来进行类似矩形区域搜索的算法，但是一万年没写 KD-tree 了，而且 OI 时写 KD-tree 就 AC 过。。。最后写了一个分块的假算法过了。

 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


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

const int MAXN = 1e5 + 3;
const double EPS = 1e-9;
const int BIAS = 20;
const int LOWER_BITS = (1 << BIAS) - 1;

struct Box {
  int x, y;
  double score;
} boxes[MAXN];

double threshold, a, b;
int ord[MAXN], ans[MAXN], n, S, vis[MAXN], vis_clk;
map<long long, vector<int>> idx;

int sign(double x) {
  if (fabs(x) < EPS) return 0;
  return x < 0 ? -1 : 1;
}

long long encode(int x, int y) { return (1ll * x) << BIAS | y; }
long long split(int x, int y) { return (1ll * x / S) << BIAS | (y / S); }

bool checkIoU(int x1, int y1, int x2, int y2) {
  int ix = max(0, S - abs(x1 - x2));
  int iy = max(0, S - abs(y1 - y2));
  return sign(a * ix * iy - b) <= 0;
}

void gao(const Box &box) {
  int bx = box.x / S, by = box.y / S;
  for (int dx = -1; dx <= 1; ++dx)
    for (int dy = -1; dy <= 1; ++dy) {
      int x = bx + dx, y = by + dy;
      long long code = encode(x, y);
      auto it = idx.find(code);
      if (it == idx.end()) continue;
      for (int i : it->second) {
        if (vis[i] != vis_clk &&
            !checkIoU(box.x, box.y, boxes[i].x, boxes[i].y)) {
          vis[i] = vis_clk;
        }
      }
    }
}

void solve() {
  cin >> n >> S >> threshold;
  a = 1 + threshold, b = 2ll * S * S * threshold;
  for (int i = 0; i < n; ++i) {
    ord[i] = i;
    cin >> boxes[i].x >> boxes[i].y >> boxes[i].score;
  }
  sort(ord, ord + n,
       [&](int a, int b) { return boxes[a].score > boxes[b].score; });

  idx.clear();
  for (int i = 0; i < n; ++i) {
    long long code = split(boxes[i].x, boxes[i].y);
    if (idx.find(code) == idx.end()) idx[code] = vector<int>();
    idx[code].push_back(i);
  }

  ++vis_clk;
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    int x = ord[i];
    if (vis[x] == vis_clk) continue;
    vis[x] = vis_clk;
    ans[cnt++] = x + 1;
    gao(boxes[x]);
  }
  sort(ans, ans + cnt);
  cout << cnt << "\n";
  for (int i = 0; i < cnt; ++i) cout << ans[i] << " \n"[i == cnt - 1];
}

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

  int o_o;
  cin >> o_o;
  for (int step = 1; step <= o_o; ++step) {
    cout << "Case #" << step << ": ";
    solve();
  }

  return 0;
}

I. Mr. Panda and Blocks

有 n 种颜色，颜色两两组合最终形成 $\frac{n(n+1)}{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


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

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j) {
      cout << i << " " << j << " " << i << " " << j << " 0 " << i << " " << j
           << " 1\n";
    }
}

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

  int o_o;
  cin >> o_o;
  for (int step = 1; step <= o_o; ++step) {
    cout << "Case #" << step << ":\nYES\n";
    solve();
  }

  return 0;
}

K. Russian Dolls on the Christmas Tree

统计每一棵子树的连续数字段的段数。

可以使用树上启发式合并来做。

 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


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

const int MAXN = 2e5 + 3;

vector<int> adj[MAXN];
int n, pa[MAXN], ans[MAXN];
set<int> contains[MAXN], *idx[MAXN];

int find(int x) { return x == pa[x] ? x : pa[x] = find(pa[x]); }

void merge(int u, int v) {
  ans[u] += ans[v];
  if (idx[u]->size() < idx[v]->size()) swap(idx[u], idx[v]);

  auto &su = *idx[u], &sv = *idx[v];
  for (int x : sv) {
    if (su.find(x + 1) != su.end()) { --ans[u], pa[x + 1] = find(x); }
    if (x != find(x)) continue;
    if (su.find(x - 1) != su.end()) { --ans[u], pa[x] = find(x - 1); }
  }
  for (int x : sv) su.insert(x);
  sv.clear();
}

void dfs(int u, int from) {
  ans[u] = 1;
  idx[u]->insert(u);

  for (int v : adj[u]) {
    if (v == from) continue;
    dfs(v, u);
    merge(u, v);
  }
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    pa[i] = i;
    adj[i].clear();
    contains[i].clear();
    idx[i] = contains + i;
  }

  for (int i = 1, a, b; i < n; ++i) {
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  dfs(1, 1);
  for (int i = 1; i <= n; ++i) cout << " " << ans[i];
  cout << "\n";
}

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

  int o_o;
  cin >> o_o;
  for (int step = 1; step <= o_o; ++step) {
    cout << "Case #" << step << ":";
    solve();
  }

  return 0;
}

L. Spiral Matrix

给定一个矩阵，问从一个点出发只能直行或者右拐走完矩阵的方案数。

打表容易发现方案数为$2(n + m) - 4$ ，这位大佬给了一个比较详情的证明。注意$n, m$ 为 1 的情况。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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

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

  int o_o;
  cin >> o_o;
  for (int n, m, step = 1; step <= o_o; ++step) {
    cout << "Case #" << step << ": ";
    cin >> n >> m;
    if (n == 1 && m == 1) {
      cout << "1\n";
    } else if (n == 1 || m == 1) {
      cout << "2\n";
    } else {
      cout << 2 * n + 2 * m - 4 << "\n";
    }
  }

  return 0;
}