Codeforces Round 989 (Div. 1 + Div. 2)

构造 Round

Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)

Problems	AC
A. King Keykhosrow’s Mystery	○
B. Rakhsh’s Revival	○
C. Trapped in the Witch’s Labyrinth	○
D. Darius’ Wisdom	⊕
E. Permutations Harmony	⊕
F1. Khayyam’s Royal Decree (Easy Version)
F2. Khayyam’s Royal Decree (Hard Version)
G1. Simurgh’s Watch (Easy Version)
G2. Simurgh’s Watch (Hard Version)
H. Rayan vs. Rayaneh

A

听说有人暴力枚举被叉了，乐

Code >folded

void solve() {
    int a = read();
    int b = read();
    cout << a * b / std::__gcd(a, b) << '\n';
}

B

Code >folded

void solve() {
    int n = read();
    int m = read();
    int k = read();

    string s;
    cin >> s;

    int ans = 0;

    for (int i = 0; i < n; ) {
        if (s[i] == '1') { i++; continue; }
        int j = i;
        int cnt = 0;
        while (s[j] == '0' and j < n) {
            cnt++;
            if (cnt == m) {
                cnt = 0;
                j += k;
                ans++;
                break;
            }
            j++;
        }
        i = (j == i) ? i + 1 : j;

        // cout << i << '\n';
    }

    cout << ans << '\n';
}

C

Code >folded

void solve() {
    int n = read();
    int m = read();

    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    vector bad(n, vector<int>(m));

    std::queue<pii> q;

    for (int i = 0; i < n; i++) {
        if (s[i][0] == 'L') {
            bad[i][0] = 1;
            q.ep(i, 0);
        }
        if (s[i][m - 1] == 'R') {
            bad[i][m - 1] = 1;
            q.ep(i, m - 1);
        }
    }
    for (int i = 0; i < m; i++) {
        if (s[0][i] == 'U') {
            bad[0][i] = 1;
            q.ep(0, i);
        }
        if (s[n - 1][i] == 'D') {
            bad[n - 1][i] = 1;
            q.ep(n - 1, i);
        }
    }

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        if (x > 0 and !bad[x - 1][y] and s[x - 1][y] == 'D') {
            bad[x - 1][y] = 1;
            q.ep(x - 1, y);
        }
        if (x < n - 1 and !bad[x + 1][y] and s[x + 1][y] == 'U') {
            bad[x + 1][y] = 1;
            q.ep(x + 1, y);
        }
        if (y > 0 and !bad[x][y - 1] and s[x][y - 1] == 'R') {
            bad[x][y - 1] = 1;
            q.ep(x, y - 1);
        }
        if (y < m - 1 and !bad[x][y + 1] and s[x][y + 1] == 'L') {
            bad[x][y + 1] = 1;
            q.ep(x, y + 1);
        }
    }

    int ans = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!bad[i][j] and s[i][j] != '?') ans++;
            else if (!bad[i][j]) {
                bool f = 1;
                if (i > 0) f &= bad[i - 1][j];
                if (i < n - 1) f &= bad[i + 1][j];
                if (j > 0) f &= bad[i][j - 1];
                if (j < m - 1) f &= bad[i][j + 1];
                if (!f) ans++;
            }
        }
    }

    cout << ans << '\n';
}

D

重写了一遍就过了，，，，做法是从右往左确定位置，次数容易证明是正确的。

Code >folded

void solve() {
    int n = read();
    
    vector<int> a(n + 1);
    vector<int> cnt(3);

    std::set<int> s[3];

    for (int i = 1; i <= n; i++) {
        a[i] = read();
        s[a[i]].ep(i);
    }

    int p1 = s[0].size(), p2 = s[0].size() + s[1].size();

    vector<pii> ans;

    for (int i = n; i > p2; i--) {
        if (a[i] == 2) continue;
        if (a[i] == 0) {
            int j = *s[1].begin();

            ans.eb(i, j);
            swap(a[i], a[j]);

            s[0].erase(i);
            s[1].erase(j);
            s[0].ep(j);
            s[1].ep(i);
        }

        if (a[i] == 1) {
            int j = *s[2].begin();

            ans.eb(i, j);
            swap(a[i], a[j]);

            s[1].erase(i);
            s[2].erase(j);
            s[1].ep(j);
            s[2].ep(i);
        }
    }

    for (int i = p2; i > p1; i--) {
        if (a[i] == 1) continue;
        if (a[i] == 0) {
            int j = *s[1].begin();

            ans.eb(i, j);
            swap(a[i], a[j]);

            s[0].erase(i);
            s[1].erase(j);
            s[0].ep(j);
            s[1].ep(i);
        }
    }

    bool flag = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[i + 1]) {
            flag = 0;
            break;
        }
    }

    assert(flag);
    assert(ans.size() <= n);

    cout << ans.size() << '\n';
    for (auto [i, j] : ans) {
        cout << i << " " << j << '\n';
    }
}

E

总和是 $(1 + n) * n / 2 * k$

一列是 $(1 + n) * k / 2$

因此 $(n + 1)$ 和 $k$ 同时是奇数时是无解的。

平均到每个 $k$ 就是 $(1 + n) / 2$。

因此有个想法是让两个排列配对，使得这两个排列每一列加起来是 $n + 1$。

发现这样能构造出最多的方案。前提是 $n$ 是偶数。

假如 $n$ 是奇数呢？考虑构造一个 3 行的，然后转化成偶数，用 2 行去凑。

发现其中一种构造是

1 2 3 4 5
3 4 5 1 2
5 3 1 4 2

1 2 3 4 5 6 7
4 5 6 7 1 2 3
(n + 1) * 3 / 2 - a[i] - b[i]

思路和代码实现是学习的 这个视频。

Code >folded

void solve() {
    int n = read();
    int k = read();

    // n 0 k 1
    vector<vector<int>> ans;

    auto fill = [&](std::set<vector<int>> forbid) {
        vector<int> p(n), q(n);
        std::iota(p.begin(), p.end(), 1);

        while (ans.size() < k) {
            for (int i = 0; i < n; i++) {
                q[i] = n + 1 - p[i];
            }

            if (p >= q) {
                break;
            }

            if (forbid.contains(p) or forbid.contains(q)) {
                // continue;
            } else {
                ans.eb(p);
                ans.eb(q);
            }

            std::next_permutation(p.begin(), p.end());
        }
    };

    auto go = [&]() -> bool {
        if ((n + 1) % 2 and k % 2) {
            return 0;
        }
        if (n == 1) {
            if (k == 1) {
                ans.eb(vector<int>(1, 1));
                return 1;
            }
            return 0;
        }

        if (k % 2 == 0) {
            fill({});
            return ans.size() == k;
        }
        // k is odd
        if (k == 1) {
            return 0;
        }

        vector<int> a(n);
        vector<int> b(n);
        vector<int> c(n);
        for (int i = 0; i < n; i++) {
            a[i] = i + 1;
            b[i] = (i + n / 2) % n + 1;
            c[i] = (n + 1) * 3 / 2 - a[i] - b[i];
        }

        std::set<vector<int>> forbid;
        forbid.ep(a);
        forbid.ep(b);
        forbid.ep(c);       
        ans.eb(a);
        ans.eb(b);
        ans.eb(c);
        fill(forbid);
        return ans.size() == k;
    };

    if (go()) {
        cout << "YES\n";
        for (auto x : ans) {
            for (auto y : x) {
                cout << y << " ";
            }
            cout << "\n";
        }
    } else {
        cout << "NO\n";
    }
}