VP 记录 - 2020 ICPC Asia EC-final

发表于 更新于 分类于 ， ， 合著者：Foi 本文字数： 1.2k 阅读时长 ≈ 4 分钟

比赛链接

题目概览

题号 标题 做法
A Namomo Subsequence DP
B Rectangle Flip 2
C Random Shuffle Gauss 消元
D City Brain 最短路 + 三分
E Tube Master III
F Rooks (签到)
G Prof. Pang's sequence
H Prof. Pang Earning Aus
I Plants vs Zombies 二分
J Circle 计算几何
K Allin 模拟
L Square 数学 (签到)
M Fillomino 构造

官方题解

A - Namomo Subsequence

题意简述

统计给定字符串 \(s\) 中形如 ABCDCD 的子串个数

解题思路

复杂度

代码参考

Show code

A.cppview raw
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 <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define inc(i) (++(i))
#define dec(i) (--(i))
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; inc(i))
#define rep(i, a, b) for (int i = (a), i##Limit = (b); i >= i##Limit; dec(i))
using namespace std;
const int N = 1000000 + 7, M = 60 + 7, Mod = 998244353;
string S;
int n, A[N];
int Dp1[N][M], Dp2[N][M], Sum[N], tot[N][M];
int f1[M][M], f2[M][M], Cnt[N];
void Inc(int &A, int B) { (A = A + B) %= Mod; }
void Dec(int &A, int B) { (A = A - B + Mod) %= Mod; }
int Mul(int A, int B) { return 1ll * A * B % Mod; }
int main() {
  cin >> S, n = S.size();
  Rep(i, 1, n) {
    char C = S[i - 1];
    if (isdigit(C)) A[i] = C - '0';
    else if (C <= 'Z') A[i] = C - 'A' + 10;
    else A[i] = C - 'a' + 36;
  }
  Rep(i, 1, n) {
    Rep(j, 0, 61) {
      Dp1[i][j] = Dp1[i - 1][j];
      Dp2[i][j] = Dp2[i - 1][j];
      tot[i][j] = tot[i - 1][j];
    }
    inc(tot[i][A[i]]);
    Rep(j, 0, 61) if (j != A[i]) {
      Inc(Dp1[i][j], tot[i - 1][j]);
      Inc(Dp2[i][A[i]], tot[i - 1][j]);
    }
    Rep(j, 0, 61) Inc(Sum[i], Dp2[i][j]);
  }
  int Ans = 0, tem;
  rep(i, n, 1) {
    Rep(j, 0, 61) if (j != A[i]) {
      Inc(f1[A[i]][j], f2[j][A[i]]);
      Inc(f2[A[i]][j], Cnt[j]);
    }
    inc(Cnt[A[i]]);
    Rep(j, 0, 61) if (j != A[i]) {
      tem = Sum[i - 1];
      Dec(tem, Dp1[i - 1][A[i]]);
      Dec(tem, Dp1[i - 1][j]);
      Dec(tem, Dp2[i - 1][j]);
      Dec(tem, Dp2[i - 1][A[i]]);
      Inc(tem, Mul(tot[i - 1][j], tot[i - 1][A[i]]));
      Inc(Ans, Mul(f1[j][A[i]], tem));
    }
  }
  cout << Ans;
  return 0;
}

B - Rectangle Flip 2

题意简述

给定 \(n\times m\) 的网格，有若干次操作，每次操作均为删去一个格子并询问剩下个格子构成多少个矩形

解题思路

复杂度

代码参考

Show code

B.cppview raw
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 <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define int long long
#define inc(i) (++(i))
#define dec(i) (--(i))
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; inc(i))
#define rep(i, a, b) for (int i = (a), i##Limit = (b); i >= i##Limit; dec(i))
using namespace std;
const int N = 500 + 7;
int n, m, Up[N][N], Down[N][N];
bool Book[N][N];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cin >> n >> m;
  int Ans = n * (n + 1) * m * (m + 1) / 4, x, y;
  Rep(i, 1, n) Rep(j, 1, m) Up[i][j] = 0, Down[i][j] = n + 1;
  while (cin >> x >> y) {
    int u = 0, d = n + 1;
    for (int j = y; j >= 1 && !Book[x][j]; dec(j)) {
      u = max(u, Up[x][j]), d = min(d, Down[x][j]);
      int uu = u, dd = d;
      for (int k = y; k <= m && !Book[x][k]; inc(k)) {
        uu = max(uu, Up[x][k]), dd = min(dd, Down[x][k]);
        Ans -= (x - uu) * (dd - x);
      }
    }
    Rep(i, x + 1, n) if (!Book[i][y]) Up[i][y] = x;
    else break; rep(i, x - 1, 1) if (!Book[i][y]) Down[i][y] = x;
    else break; cout << Ans << '\n';
    Book[x][y] = 1;
  }
  return 0;
}

C - Random Shuffle

题意简述

根据 shuffle 后的数组来计算出随机数种子

解题思路

复杂度

代码参考

Show code

D - City Brain

题意简述

给定一个边权为 1 的简单无向图，可以选择若干条边，将第 \(i\) 的选择的边的权值变为 \(\frac{1}{a_i}\), 其中 \(a_i\) 为正整数，可任意选取，只需保证 \(\sum a_i=k\), 问对两对给定的起讫点的最短路和的最小值

解题思路

复杂度

代码参考

Show code

D.cppview raw
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
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <queue>
#include <vector>
#define inc(i) (++(i))
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; inc(i))
using namespace std;
const int N = 5000 + 7, M = 10000 + 7;
int n, m, k, Dis[N][N], Min[N];
vector<int> E[N];
queue<int> Q;
void BFS(int S) {
  Q.push(S), Dis[S][S] = 0;
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (auto v : E[u])
      if (-1 == Dis[S][v]) {
        Dis[S][v] = Dis[S][u] + 1;
        Q.push(v);
      }
  }
}
double f(int k, int b) {
  return b ? 1.0 * (k % b) / (k / b + 2.0) + 1.0 * (b - k % b) / (k / b + 1.0) :
             0.0;
}
double sanfen(int a, int b) {
  int l = 0, r = k;
  while (r > l) {
    int Mid1 = l + (r - l) / 3, Mid2 = r - (r - l) / 3;
    double f1 = f(Mid1, a) * 2 + f(k - Mid1, b);
    double f2 = f(Mid2, a) * 2 + f(k - Mid2, b);
    if (f1 <= f2) r = Mid2 - 1;
    else l = Mid1 + 1;
  }
  return f(l, a) * 2.0 + f(k - l, b);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> m >> k;
  int u, v;
  Rep(i, 1, m) cin >> u >> v, E[u].push_back(v), E[v].push_back(u);
  Rep(i, 1, n) Rep(j, 1, n) Dis[i][j] = -1;
  Rep(i, 1, n) BFS(i);
  Rep(i, 0, n) Min[i] = 2147483647;
  int s1, s2, t1, t2;
  cin >> s1 >> t1 >> s2 >> t2;
  double Ans = sanfen(0, Dis[s1][t1] + Dis[s2][t2]);
  Rep(i, 1, n) Rep(j, 1, n) {
    if (~Dis[i][j] && ~Dis[s1][i] && ~Dis[s2][i] && ~Dis[j][t1] && ~Dis[j][t2])
      Min[Dis[i][j]] =
        min(Min[Dis[i][j]], Dis[s1][i] + Dis[s2][i] + Dis[j][t1] + Dis[j][t2]);
    if (~Dis[i][j] && ~Dis[s1][i] && ~Dis[s2][j] && ~Dis[j][t1] && ~Dis[i][t2])
      Min[Dis[i][j]] =
        min(Min[Dis[i][j]], Dis[s1][i] + Dis[s2][j] + Dis[j][t1] + Dis[i][t2]);
  }
  Rep(i, 0, n) if (Min[i] != 2147483647) Ans = min(Ans, sanfen(i, Min[i]));
  cout << fixed << setprecision(10) << Ans;
  return 0;
}

E - Tube Master III

题意简述

Slitherlink, 连边时有代价，问最小代价

解题思路

复杂度

代码参考

Show code

F - Rooks

题意简述

在 \(n\times m\) 的网格上放若干 Rooks, 一对 Rooks 会相互攻击当且仅当

  • 分属不同阵营
  • 在一条直线上
  • 中间没有其他 Rooks

问哪些 Rooks 会被攻击

解题思路

复杂度

代码参考

Show code

F.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
#define N 400010
int n, m, b[N];
struct node {
  int x, y, id, belong;
} a[N];
bool cmp1(node x, node y) { return x.x < y.x || (x.x == y.x && x.y < y.y); }
bool cmp2(node x, node y) { return x.y < y.y || (x.y == y.y && x.x < y.x); }
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &a[i].x, &a[i].y);
    a[i].id = i;
    a[i].belong = 0;
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &a[n + i].x, &a[n + i].y);
    a[n + i].id = i + n;
    a[n + i].belong = 1;
  }
  sort(a + 1, a + n + m + 1, cmp1);
  for (int i = 2; i <= n + m; ++i) {
    if (a[i].x == a[i - 1].x && a[i].belong != a[i - 1].belong) {
      b[a[i].id] = 1;
      b[a[i - 1].id] = 1;
    }
  }
  sort(a + 1, a + n + m + 1, cmp2);
  for (int i = 2; i <= n + m; ++i) {
    if (a[i].y == a[i - 1].y && a[i].belong != a[i - 1].belong) {
      b[a[i].id] = 1;
      b[a[i - 1].id] = 1;
    }
  }
  for (int i = 1; i <= n; ++i) printf("%d", b[i]);
  puts("");
  for (int i = 1; i <= m; ++i) printf("%d", b[n + i]);
  return 0;
}

G - Prof. Pang's sequence

题意简述

给定数列 \(\{a_n\}\), 若干次询问，每次询问一段区间中 数的种类为奇数 的子区间个数

解题思路

复杂度

代码参考

Show code

G.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
#define N 500010
#define ll long long
int n, m, a[N], lst[N], h[N];
int tag1[N << 2], tag2[N << 2], cov[N << 2], cnt[N << 2];
ll sum[N << 2], ans[N];
struct Query {
  int x, y, id;
} q[N];
bool operator<(Query x, Query y) {
  return x.y < y.y || (x.y == y.y && x.x < y.x);
}
void pushdown(int v, int l, int r) {
  int mid = l + r >> 1;
  if (cov[v]) {
    cov[v] = 0;
    cov[v << 1] ^= 1;
    swap(tag1[v << 1], tag2[v << 1]);
    cnt[v << 1] = mid - l + 1 - cnt[v << 1];
    cov[v << 1 | 1] ^= 1;
    swap(tag1[v << 1 | 1], tag2[v << 1 | 1]);
    cnt[v << 1 | 1] = r - mid - cnt[v << 1 | 1];
  }
  if (tag1[v]) {
    tag1[v << 1] += tag1[v];
    sum[v << 1] += 1ll * tag1[v] * cnt[v << 1];
    tag1[v << 1 | 1] += tag1[v];
    sum[v << 1 | 1] += 1ll * tag1[v] * cnt[v << 1 | 1];
    tag1[v] = 0;
  }
  if (tag2[v]) {
    tag2[v << 1] += tag2[v];
    sum[v << 1] += 1ll * tag2[v] * (mid - l + 1 - cnt[v << 1]);
    tag2[v << 1 | 1] += tag2[v];
    sum[v << 1 | 1] += 1ll * tag2[v] * (r - mid - cnt[v << 1 | 1]);
    tag2[v] = 0;
  }
}
void change(int v, int l, int r, int x, int y) {
  if (x <= l && r <= y) {
    cov[v] ^= 1;
    swap(tag1[v], tag2[v]);
    cnt[v] = r - l + 1 - cnt[v];
    return;
  }
  int mid = l + r >> 1;
  pushdown(v, l, r);
  if (x <= mid) change(v << 1, l, mid, x, y);
  if (mid < y) change(v << 1 | 1, mid + 1, r, x, y);
  sum[v] = sum[v << 1] + sum[v << 1 | 1];
  cnt[v] = cnt[v << 1] + cnt[v << 1 | 1];
}
void add(int v, int l, int r, int x, int y) {
  if (x <= l && r <= y) {
    tag1[v]++;
    sum[v] += 1ll * cnt[v];
    return;
  }
  int mid = l + r >> 1;
  pushdown(v, l, r);
  if (x <= mid) add(v << 1, l, mid, x, y);
  if (mid < y) add(v << 1 | 1, mid + 1, r, x, y);
  sum[v] = sum[v << 1] + sum[v << 1 | 1];
  cnt[v] = cnt[v << 1] + cnt[v << 1 | 1];
}
ll query(int v, int l, int r, int x, int y) {
  if (x <= l && r <= y) { return sum[v]; }
  int mid = l + r >> 1;
  pushdown(v, l, r);
  ll res = 0;
  if (x <= mid) res += query(v << 1, l, mid, x, y);
  if (mid < y) res += query(v << 1 | 1, mid + 1, r, x, y);
  return res;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    lst[i] = h[a[i]];
    h[a[i]] = i;
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &q[i].x, &q[i].y);
    q[i].id = i;
  }
  sort(q + 1, q + m + 1);
  for (int i = 1, j = 1; i <= n && j <= m; ++i) {
    change(1, 1, n, lst[i] + 1, i);
    add(1, 1, n, 1, i);
    while (q[j].y == i) {
      ans[q[j].id] = query(1, 1, n, q[j].x, q[j].y);
      ++j;
    }
  }
  for (int i = 1; i <= m; ++i) { printf("%lld\n", ans[i]); }
  return 0;
}

H - Prof. Pang Earning Aus

题意简述

有三种物品 \(A\), \(B\), \(C\), \(B\) 和 \(C\) 最多分别有 \(n_b\), \(n_c\) 个，每次交易可以用一个物品 \(i\) 换取 \(k_{ij}\) 个物品 \(j\), (\(i,j=A,B,C\), \(i\ne j\)), 初始只有 1 个 \(A\), 问经过若干次交易后最多可获得多少个 \(A\)

解题思路

复杂度

代码参考

Show code

I - Plants vs Zombies

题意简述

有 \(n\) 个僵尸，第 \(i\) 个僵尸会在 \(t_i\) s 时出现在第 0 格，每秒所有存活的僵尸均向前移动 \(V\) 格，受到经过的这 \(V\) 格 (不含起始点) 中所有水草的攻击，之后受到前方的豌豆攻击 (已死亡的僵尸不会受到攻击), 问每个僵尸会在什么时候死亡 (血量不超过 0)

解题思路

二分

代码参考

Show code

J - Circle

题意简述

计算以 \(r\) 为半径，能覆盖住给定凸包的圆的圆心构成的面积

解题思路

显然是以凸包顶点为圆心，\(r\) 为半径的圆的面积交

复杂度

代码参考

Show code

K - Allin

题意简述

德州扑克，问是否必胜

代码参考

Show code

K.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
int T, a[10], b[10];
char str[10];
int main() {
  scanf("%d", &T);
  while (T--) {
    char op;
    int f = 1;
    for (int i = 1; i <= 5; ++i) {
      scanf("%s", str);
      if (i == 1) {
        op = str[1];
      } else {
        if (op != str[1]) f = 0;
      }
      switch (str[0]) {
        case 'A': a[i] = 1; break;
        case 'T': a[i] = 10; break;
        case 'J': a[i] = 11; break;
        case 'Q': a[i] = 12; break;
        case 'K': a[i] = 13; break;
        default: a[i] = str[0] - '0';
      }
      b[i] = a[i];
    }
    if (!f) {
      puts("check");
      continue;
    }
    sort(a + 1, a + 6);
    sort(b + 3, b + 6);
    if (b[2] < b[1]) swap(b[1], b[2]);
    if (a[1] == 1 && a[5] == 13 && a[4] == 12 && a[3] == 11 && a[2] == 10) {
      puts("allin");
    } else if (a[5] - a[1] == 4) {
      if (a[1] == 9) {
        puts("allin");
      } else if (a[1] == 8) {
        if (b[1] == 8 && b[2] == 9) {
          puts("check");
        } else puts("allin");
      } else if (a[1] == 7) {
        if (b[4] == 10 && b[5] == 11) {
          puts("check");
        } else puts("allin");
      } else if (a[1] == 1) {
        if (b[1] == 1 && b[2] == 5) {
          puts("allin");
        } else puts("check");
      } else {
        if (b[2] == a[1] + 4) {
          puts("allin");
        } else puts("check");
      }
    } else puts("check");
  }
  return 0;
}

L - Square

题意简述

对给定的数列 \(\{a_n\}\) 求 \(\prod_{i=1}^nt_i\) 的最小值，其中 \(t_ia_it_{i+1}a_{i+1}\), \(\forall i=1,2,...,n-1\)

解题思路

考虑单个素因子 \(p\), 设 \(p^{\alpha_i}\mid a_i\), \(p^{\alpha_i+1}\mid a_i\), 则答案显然为

\[ p^{\min\left\{n-\sum_{i=1}^n(\alpha_i\bmod 2),\sum_{i=1}^n(\alpha_i\bmod 2)\right\}} \]

然后对每个素因子的答案乘起来就行了

复杂度

\(O(n\log^2{m})\), 其中 \(m\) 为 \(\{a_n\}\) 的最大值

代码参考

Show code

L.cppview raw
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;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
const int N = 1e5 + 5, M = 1e3 + 5;
const int MOD = 1000000007;
bool vis[M];
int prime[M];
int cnt_p;
void init_prime(int n = M - 1) {
  _for(i, 2, n) {
    if (!vis[i]) vis[prime[++cnt_p] = i] = 1;
    for (int j = 1; j <= cnt_p && i * prime[j] <= n; ++j) {
      vis[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
i64 qpow(i64 a, i64 b) {
  a %= MOD;
  i64 res = 1;
  for (; b; b >>= 1, a = a * a % MOD)
    if (b & 1) res = res * a % MOD;
  return res;
}
int cnts[M * M];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  init_prime();
  int n;
  cin >> n;
  map<int, int> cnts;
  int maxa = 0;
  _for(i, 1, n, a) {
    cin >> a;
    maxa = max(maxa, a);
    _for(i, 1, cnt_p, sqrt_a = sqrt(a), cnt) {
      if (prime[i] > sqrt_a) break;
      if (a % prime[i] == 0) {
        cnt = 0;
        while (a % prime[i] == 0) {
          ++cnt;
          a /= prime[i];
        }
        cnts[prime[i]] += cnt % 2;
      }
    }
    if (a > 1) ++cnts[a];
  }
  i64 ans = 1;
  _for(i, 2, maxa)
    if (cnts[i]) ans = ans * qpow(i, min(cnts[i], n - cnts[i])) % MOD;
  cout << ans;
  return 0;
}

M - Fillomino

题意简述

给定 \(n\times m\) 的循环网格，要求将网格划分成三个给定大小连通块，且连通块必须包含指定的一个格子

解题思路

复杂度

代码参考

Show code