AtCoder Regular Contest 219

ARC219 A

题目大意：

数据范围：

思路：

 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


struct Node {
    int son[2];
    Node() { son[0] = son[1] = -1; }
};
void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> ma(n);
    map<string, int> ma2;
    vector<Node> tree(1);
    rep(i, 0, n - 1) {
        cin >> ma[i];
        ma2[ma[i]]++;
        int cur = 0;
        for (char c : ma[i]) {
            int b = c - '0';
            if (tree[cur].son[b] == -1) {
                tree[cur].son[b] = sz(tree);
                tree.emplace_back();
            }
            cur = tree[cur].son[b];
        }
    }
    if (m <= 30 && sz(ma2) == (1 << m)) {
        cout << "No" << endl;
        return;
    }
    cout << "Yes" << endl;
    string res;
    bool flag = false;
    auto dfs = [&](this auto&& dfs, int x, int cnt) -> void {
        if (flag) return;
        if (cnt == m) return;
        rep(i, 0, 1) {
            if (flag) return;
            if (tree[x].son[i] == -1) {
                res.push_back(char('0' + i));
                while (sz(res) < m) {
                    res.push_back('0');
                }
                flag = true;
                return;
            }
            res.push_back(char('0' + i));
            dfs(tree[x].son[i], cnt + 1);
            if (flag) return;
            res.pop_back();
        }
    };
    dfs(0, 0);
    rep(i, 0, m - 1) { res[i] = (res[i] == '0') ? '1' : '0'; }
    cout << res << endl;
    return;
}

ARC219 B

出处：ARC219 B

题目大意：

数据范围：

思路：

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


const ll MOD = 998244353;
void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll tem = 0;
    rep(i, 0, n - 1) {
        if (a[i] != i + 1) break;
        tem = (tem + (n - 1 - i) + MOD) % MOD;
    }
    bool flag = true;
    rep(i, 0, n - 1) {
        if (a[i] != i + 1) {
            flag = false;
            break;
        }
    }
    cout << (tem + flag) % MOD << endl;
    return;
}

ARC219 C

出处：ARC219 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


const ll MOD = 998244353;
void solve() {
    ll h, w;
    cin >> h >> w;
    int n;
    cin >> n;
    vector<pll> ma(n);
    map<ll, vl> ma2;
    rep(i, 0, n - 1) {
        cin >> ma[i].first >> ma[i].second;
        ma2[ma[i].first].push_back(ma[i].second);
    }
    ll tem = 0;
    for (auto& [x, y] : ma2) {
        ranges::sort(y);
        y.erase(unique(all(y)), y.end());
        tem += 2 * (y[sz(y) - 1] - 1);
    }
    vl dp(3, LLONG_MAX / 3);
    dp[0] = 0;
    for (auto& [x, y] : ma2) {
        int m = sz(y);
        vl pre(m + 1);
        ll tem2 = LLONG_MAX / 3;
        tem2 = min(tem2, 2 * (y[m - 1] - 1));
        tem2 = min(tem2, 2 * (w - y[0]));
        rep(i, 0, m - 2) { tem2 = min(tem2, 2 * (y[i] - 1) + 2 * (w - y[i + 1])); }
        vl ndp(3, LLONG_MAX / 3);
        rep(i, 0, 2) {
            if (dp[i] == LLONG_MAX / 3) continue;
            ndp[i] = min(ndp[i], dp[i] + tem2);
        }
        if (dp[0] < LLONG_MAX / 3) {
            ndp[1] = min(ndp[1], dp[0] + w - 1);
        }
        if (dp[1] < LLONG_MAX / 3) {
            ndp[2] = min(ndp[2], dp[1] + w - 1);
        }
        if (dp[2] < LLONG_MAX / 3) {
            ndp[1] = min(ndp[1], dp[2] + w - 1);
        }
        dp = ndp;
    }
    cout << min({dp[0] + 2 * (w - 1), dp[1] + w - 1, dp[2], tem}) << endl;
    return;
}

ARC219 D

出处：ARC219 D

题目大意：

数据范围：

思路：

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


void solve() {
    ll n, k;
    cin >> n >> k;
    vvl ma(n, vl(n));
    rep(i, 0, n - 1) { rep(j, 0, n - 1) cin >> ma[i][j]; }
    int tem = 0;
    rep(i, 0, n - 1) {
        rep(j, 0, n - 1) {
            if ((i + j) % 2 == 0) continue;
            tem ^= ma[i][j] % (k + 1);
        }
    }
    if (tem != 0)
        cout << "Alice" << endl;
    else
        cout << "Bob" << endl;
    return;
}

ARC219 E

出处：ARC219 E

题目大意：

数据范围：

思路：

 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


void solve() {
    ll h, w;
    cin >> h >> w;
    vector<string> ma(2 * h);
    rep(i, 0, 2 * h - 1) cin >> ma[i];
    vvi res(2 * h, vi(2 * w));
    vector<pii> tem;
    rep(i, 0, 2 * h - 1) tem.emplace_back(i, 0);
    rep(i, 1, 2 * w - 1) tem.emplace_back(2 * h - 1, i);
    frep(i, 2 * h - 2, 0) tem.emplace_back(i, 2 * w - 1);
    frep(i, 2 * w - 2, 1) {
        if ((2 * w - 1 - i) % 2) {
            rep(j, 0, 2 * h - 2) tem.emplace_back(j, i);
        } else {
            frep(j, 2 * h - 2, 0) tem.emplace_back(j, i);
        }
    }
    int tem2 = 0;
    int l, r;
    rep(i, 0, 4 * h * w - 1) {
        tem2 += (ma[tem[i].first][tem[i].second] == 'o');
        if (i < 2 * h * w - 1) continue;
        if (tem2 == h * w) {
            r = i, l = i - 2 * h * w + 1;
            break;
        }
        tem2 -= (ma[tem[i - 2 * h * w + 1].first][tem[i - 2 * h * w + 1].second] == 'o');
    }
    rep(i, l, r) res[tem[i].first][tem[i].second] = 1;
    rep(i, 0, 2 * h - 1) {
        rep(j, 0, 2 * w - 1) cout << (res[i][j] ? 'A' : 'B');
        cout << endl;
    }
    return;
}