AtCoder Beginner Contest 167

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

比赛链接

D Teleporter

Description

有 nn 个小镇，小镇 ii 有一个传送能传送到小镇 jj。从小镇 1 开始传送，求出经过 kk 次传送最终到哪个小镇。

Solution

可通过拓扑排序找到环(拓扑排序后入度 inin 不为 0 的节点为环上的节点)。然后处理出环长，起点到环的距离，即可判断传送 kk 次后所在的节点编号。

Code

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

using namespace std;
using LL = long long;

constexpr int MAXN = 2e5 + 5;

int n, to[MAXN], in[MAXN], step1[MAXN], step2[MAXN], vis[MAXN];
LL k, len1, len2;

void toposort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!in[i]) q.push(i);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if(!(--in[to[cur]])) q.push(to[cur]);
    }
}

void getLen(int cur) {
    if (vis[cur]) return;
    vis[cur] = 1;
    if (in[cur]) step2[++len2] = to[cur], getLen(to[cur]);
    else step1[++len1] = to[cur], getLen(to[cur]);
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> to[i], in[to[i]]++;
    toposort(), getLen(1);
    if (k <= len1) cout << step1[k] << endl;
    else {
        k = (k - len1) % len2 ? (k - len1) % len2 : len2;
        cout << step2[k] << endl;
    }
    return 0;
}

E Colorful Blocks

Description

有排列于一行的 NN 个格子，每个格子染上颜色 1 到 MM，求至多有 KK 对颜色相同的相邻格子的染色方案数。

Solution

  • KK 对相邻颜色相同，则相邻颜色相同的一对格子缩成一个格子，则有 N−KN−K 个格子颜色互不相同，其中一个格子颜色有 MM 种取法，其它格子只有 M−1M−1 种。
  • 所以答案为 ΣCn−1im(m−1)n−i−1\Sigma C_{n-1}^im(m−1)^{n−i−1}

Code

Colorful Blocks
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;
using LL = long long;

constexpr int MAXN = 2e5 + 5;
constexpr LL Mod = 998244353;

LL n, m, k, ans, fac[MAXN];

inline void Init() {
    fac[0] = 1;
    for (LL i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % Mod;
}

inline LL qpow(LL a, LL b) {  // a^b
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

inline LL C(LL N, LL M) {
    if (M > N || M < 0) return 0;
    return fac[N] * qpow(fac[M], Mod - 2) % Mod * qpow(fac[N - M], Mod - 2) % Mod;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    Init();
    for (LL i = 0 ; i <= k; i++)
        ans = (ans + C(n - 1, i) * m % Mod * qpow(m - 1, n - i - 1) % Mod) % Mod;
    cout << ans << endl;
    return 0;
}

F Bracket Sequencing

Description

给出n个括号序列，总长不超过 10610^6，能否用它们按照一定顺序拼接成一个合法的括号序列。

Solution

  • 设 “(“ 的权为 1，“)” 的权为 -1。
  • 对于一个合法括号序列，任意前缀和一定大于等于 0，且总权值和为 0(任意位置只允许有 “(“ 待配对，且整个序列 “(“ 和 “)” 数量相同)
  • 首先用 sumsum 记录 nn 个序列中权值的和，sumsum 不为 0 一定不能拼接出合法序列
  • 考虑一种最优的拼接方案，如果该方案不成功，则其他方案一定不会成功
    • 显然，先选权值和大于等于零的，且任意前缀最小值大的先选
    • 接下来取权值和小于零的。如果用前面的选取方法，可以举出反例
  • 接下来推权值和小于零时一种方案更优的等价条件
    • 设 ii 和 jj 是之后紧接着拼接的序列，它们之前已构造和为 sumsum 的序列，那么这两个序列放入后满足任意前缀大于等于 0
    • 先 ii 后 jj，则 sum+cnti+min⁡prej>=0sum+cnt_i+\min pre_j>=0
    • 先 jj 后 ii，则 sum+cntj+min⁡prei>=0sum+cnt_j+\min pre_i>=0
    • 设先放 ii 更优，有 cnti−min⁡prei>cntj−min⁡prejcnt_i−\min pre_i >cnt_j−\min pre_j
    • 于是先选 cnt−min⁡precnt−\min pre 大的更优

Code

Bracket Sequencing
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
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
vector<pii> ls, rs;
bool check() {
    int tot = 0;  //记前缀和
    for (int i = 0; i < ls.size(); i++) {
        if (tot + ls[i].first < 0) return false;
        tot += ls[i].second;
    }
    for (int i = 0; i < rs.size(); i++) {
        if (tot + rs[i].second - rs[i].first < 0) return false;
        tot += rs[i].second;
    }
    return true;
}
bool cmp(const pii &a, const pii &b) {
    if (a.first == b.first) return a.second > b.second;
    return a.first > b.first;
}
int main() {
    int n;
    cin >> n;
    int sum = 0;  //所有序列值总和
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        int cnt = 0, min_pre = 1e9;
        //对每个序列，cnt记任权值和，min_pre记任意前缀最小值
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(')
                ++cnt;
            else
                --cnt;
            min_pre = min(min_pre, cnt);
        }
        sum += cnt;
        if (cnt >= 0)
            ls.push_back(make_pair(min_pre, cnt));
        else
            rs.push_back(make_pair(cnt - min_pre, cnt));
    }
    sort(ls.begin(), ls.end(), cmp);
    sort(rs.begin(), rs.end(), cmp);
    if (sum == 0 && check())
        puts("Yes");
    else
        puts("No");
    return 0;
}