AtCoder Beginner Contest 209

发表于2021-07-17更新于2023-09-15字数统计1.6k阅读时长15分

比赛链接

C Not Equal

Description

题目链接

Solution

将数组 C 从小到大排序。则序列 A 的个数为 C1⋅max⁡(C2−1,0)⋅max⁡(C3−2,0)⋅...⋅max⁡(Cn−n+1,0)C_1 \cdot \max (C_2 - 1, 0) \cdot \max (C_3 - 2, 0) \cdot ... \cdot \max (C_n - n + 1, 0)。

Code

Not Equal
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;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 2e5 + 5, MOD = 1e9 + 7;

int n;
array<int, MAXN> c;

int main() {
    boost;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    sort(c.begin() + 1, c.begin() + n + 1);
    long long ans = c[1];
    for (int i = 2; i <= n; i++) {
        ans = ans * max(0, c[i] - i + 1) % MOD;
    }
    cout << ans << endl;
    return 0;
}

D Collision

Description

题目链接

Solution

由题意知 The Kingdom of Takahashi 构成一颗树。

任选一个节点作为根，进行 dfs 处理出每个节点的深度。容易发现，当两个节点的深度奇偶性不同时，Takahashi 和 Aoki 在道路上相遇；否则在某个小镇相遇。

Code

Collision
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
#include <bits/stdc++.h>

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7;

int n, q;
vector<int> g[MAXN];
array<int, MAXN> dep;

void dfs(int cur, int f) {
    dep[cur] = dep[f] + 1;
    for (auto& to : g[cur]) {
        if (to == f) continue;
        dfs(to, cur);
    }
}

signed main() {
    boost;
    cin >> n >> q;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1, c, d; i <= q; i++) {
        cin >> c >> d;
        if ((dep[c] ^ dep[d]) & 1) cout << "Road\n";
        else cout << "Town\n";
    }
    return 0;
}

E Shiritori

Description

题目链接

Solution

将 nn 个单词看作一个有向图的 nn 条边，图的顶点为单词的前 3 和后 3 个字母，且前 3 个字母向后 3 个字母连一条有向边。则得到的图有至多 52352^3 个顶点和 nn 条边。

于是问题等价于给定一个有向图，其中一个顶点上放有一颗棋子。然后两人轮流选择一条边，边的起点为棋子初始位置，然后将棋子移动到边的终点。最终不能移动棋子的玩家输。

该问题可通过倒推法 (backward induction) 解决。首先将顶点分为 3 类，分别为 winning、 losing、 drawing：

  • 没有出边的顶点类型为 losing
  • 如果一个顶点连出去的所有边的终点类型为 winning，该顶点类型为 losing
  • 如果一个顶点连出去的其中一条边的终点类型为 losing，该顶点类型为 winning
  • 如果一个顶点类型既不是 winning 也不是 losing，则顶点类型为 drawing

于是可通过类似拓扑排序的方法在反图上进行倒推，当一个节点类型确定后，将其入队，继续倒推。最终得到所有节点类型的时间复杂度为 O(n)O(n)。

需要注意最后判断时，一个单词只对应一条边，需要通过边的终点类型推断起点类型。

Code

Shiritori
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
#include <bits/stdc++.h>

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int charToInt(int a) {
    if (isupper(a)) return a - 'A' + 26;
    else return a - 'a';
}

int stringToInt(char a, char b, char c) {
    return charToInt(a) * 52 * 52 + charToInt(b) * 52 + charToInt(c);
}

constexpr int MAXN = 2e5 + 5, MOD = 1e9 + 7, M = 52 * 52 * 52;

int n;
string s;
vector<int> revG[M];
array<int, M> in, ans; // ans = 0 -> lose, 1 -> win, -1 -> draw
array<int, MAXN> u, v;

signed main() {
    boost;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        u[i] = stringToInt(s[0], s[1], s[2]);
        v[i] = stringToInt(s[s.size() - 3], s[s.size() - 2], s[s.size() - 1]);
        in[u[i]]++;
        revG[v[i]].push_back(u[i]);
    }
    queue<int> q;
    for (int i = 0; i < M; i++) ans[i] = -1;
    for (int i = 0; i < M; i++) if (!in[i]) ans[i] = 0, q.push(i);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (const auto& to : revG[cur]) {
            if (ans[to] == -1) {
                in[to]--;
                if (ans[cur] == 0) ans[to] = 1, q.push(to);
                else if (in[to] == 0) {
                    ans[to] = 0;
                    q.push(to);
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (ans[v[i]] == -1) cout << "Draw\n";
        else if (ans[v[i]] == 0) cout << "Takahashi\n";
        else cout << "Aoki\n";
    }
    return 0;
}

F Deforestation

Description

题目链接

Solution

可以证明，要让总的 cost 最小，当且仅当砍树的顺序满足如下条件：

  • 如果 Hi<Hi+1H_i < H_{i+1}，则第 i+1i+1 棵树需要在第 ii 棵树之前被砍掉
  • 如果 Hi>Hi+1H_i > H_{i+1}，则第 ii 棵树需要在第 i+1i+1 棵树之前被砍掉

考虑 DP，设 dpi,jdp_{i,j} 表示枚举到第 ii 棵树，且第 ii 棵树是第 jj 个被砍去的 1...i1 ... i 的全排列的个数。

则有状态转移如下：

  • 如果 Hi=Hi+1H_i = H_{i+1}，则 dpi+1,j=∑k=1idpi,kdp_{i+1,j} = \sum \limits_{k = 1}^{i} dp_{i,k}
  • 如果 Hi<Hi+1H_i < H_{i+1}，则 dpi+1,j=∑k=jidpi,kdp_{i+1,j} = \sum \limits_{k = j}^{i} dp_{i,k}
  • 如果 Hi>Hi+1H_i > H_{i+1}，则 dpi+1,j=∑k=1j−1dpi,kdp_{i+1,j} = \sum \limits_{k = 1}^{j-1} dp_{i,k}

朴素 DP 的时间复杂度为 O(N3)O(N^3)，使用前缀和优化 DP 可做到 O(N2)O(N^2)。

Code

Deforestation 
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
#include <bits/stdc++.h>

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 4e3 + 3, MOD = 1e9 + 7;

int n;
array<int, MAXN> h;
long long dp[MAXN][MAXN], sum[MAXN][MAXN];

template<typename T>
void add(T& a, T b) {
    a += b;
    if (a > MOD) a -= MOD;
}

signed main() {
    boost;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    h[0] = h[1];
    dp[0][0] = 1;
    for (int i = 0; i <= n; i++) sum[0][i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (h[i - 1] == h[i]) {
                add(dp[i][j], sum[i - 1][i]);
            } else if (h[i - 1] < h[i]) {
                add(dp[i][j], (sum[i - 1][i] - sum[i - 1][j - 1] + MOD) % MOD);
            } else { // i + 1 be removed after i
                add(dp[i][j], (sum[i - 1][j - 1] - sum[i - 1][0] + MOD) % MOD);
            }
        }
        for (int j = 1; j <= n; j++)
            add(sum[i][j], (sum[i][j - 1] + dp[i][j]) % MOD);
    }
    long long ans = 0;
    for (int j = 1; j <= n; j++) add(ans, dp[n][j]);
    cout << ans << "\n";
    return 0;
}