Codeforces Round #632 (Div. 2) 裂开记

AutumnKite

题解Codeforces

发布于：2020年4月10日

次浏览

打得非常裂开，被 D 续了半年。

A - Little Artem

题目传送门

题解

首先我们考虑将所有格子填上黑色，此时 \(B=W=0\)。

我们尝试将一个格子变成白色，可以发现将一个格子变成白色会使得 \(W\) 变成 \(1\)，\(B\) 变成这个格子上下左右的黑色格子数量。

我们的目标是使得 \(B=2,W=1\)，那么我们只要选择角落上的格子变成白色即可。

代码

void solve() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i == n && j == m) {
                putchar('W');
            } else {
                putchar('B');
            }
        }
        putchar('\n');
    }
}

B - Kind Anton

题目传送门

题解

考虑从后往前依次将 \(a_i\) 变成 \(b_i\)。

考虑对于当前位置 \(i\)，若 \(b_i < a_i\)（即需要变小），那么显然只需要存在一个 \(j\) 满足 \(j < i\) 且 \(a_j=-1\) 就可以不断将 \(a_i\) 减 \(1\) 直到等于 \(b_i\)；同理，若 \(b_i > a_i\)（即需要变大），那么只需要存在一个 \(j\) 满足 \(j < i\) 且 \(a_j=1\) 就可以不断将 \(a_i\) 加 \(1\) 直到等于 \(b_i\)。

那么我们只需要从左往右找到第一个 \(1\) 和 \(-1\) 然后进行判断即可。

代码

const int N = 200005;

int n, a[N], b[N];

void solve() {
    read(n);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        read(b[i]);
    }
    int p1 = 1, p2 = 1;
    while (p1 <= n && a[p1] < 1) {
        if (a[p1] < b[p1]) {
            printStr("NO");
            return;
        }
        ++p1;
    }
    if (p1 <= n && a[p1] < b[p1]) {
        printStr("NO");
        return;
    }
    while (p2 <= n && a[p2] > -1) {
        if (a[p2] > b[p2]) {
            printStr("NO");
            return;
        }
        ++p2;
    }
    if (p2 <= n && a[p2] > b[p2]) {
        printStr("NO");
        return;
    }
    printStr("YES");
}

C - Eugene and an array

题目传送门

题解

不知道为什么 CF 的评论里有很多人说这题很难，感觉好像就是个套路题？

首先考虑求出 \(a_i\) 的前缀和 \(b_i=\sum\limits_{j=1}^{i} a_j\)，那么一个区间 \((l,r]\) 合法当且仅当不存在 \(l\le j < i\le r\) 使得 \(b_i=b_j\)。

考虑对于一个 \(b_i\)，求出上一个与 \(b_i\) 相同的位置 \(lst_i\)，即 \[lst_i=\max\{j\ |\ j<i,b_j=b_i\}\]

不存在则 \(lst_i=-1\)。

那么区间 \((l,r]\) 合法的条件变为对于所有 \(0\le i\le n\)，满足 \(l > lst_i\) 或 \(r < i\)。

那么我们只要从左往右枚举 \(r\)，那么 \(l\) 需要大于 \(\max\{lst_j\ |\ j \le r\}\)，直接在枚举的同时维护 \(lst\) 数组的前缀 \(\max\) 即可。

代码

const int N = 200005;

int n, lst[N];
long long a[N];
std::map<long long, int> M;

void solve() {
    read(n);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        a[i] += a[i - 1];
    }
    for (int i = 0; i <= n; ++i) { // 用 std::map 计算 lst 数组
        if (!M.count(a[i])) {
            lst[i] = -1;
        } else {
            lst[i] = M[a[i]];
        }
        M[a[i]] = i;
    }
    int mx = -1;
    long long ans = 0;
    for (int i = 0; i <= n; ++i) {
        mx = std::max(mx, lst[i]);
        ans += i - mx - 1;
    }
    print(ans);
}

D - Challenges in school №41

题目传送门

题解

考场上的我不知道在干什么...

首先我们把 \(\mathtt{R}\) 看成 \(1\)，\(\mathtt{L}\) 看成 \(0\)，那么交换轮数的上界为逆序对数。如果 \(k\) 大于逆序对数，那一定无解。

然后我们考虑求出交换轮数的下界并求出一组解。

由于总交换次数固定，为逆序对数，那么我们只要每一轮贪心地将可以交换的相邻的数对交换即可。

考场上并没有过多的时间证明交换轮数下界的级别，所以代码中我直接使用了 \(\mathtt{set}\) 来快速找到所有需要交换的数对。

在求出达到下界的这一组解后，若 \(k\) 大于这个下界，我们只需要将同一轮中的若干次交换拆成若干轮，直到轮数搞好为 \(k\) 即可。

由于我使用了 \(\mathtt{set}\)，所以复杂度是 \(O(n^2\log n)\) 的，可以通过此题。

另外，可以证明下界一定是 \(O(n)\) 级别的（根据官方题解的下界求法），所以直接每次暴力找可以交换的数对，时间复杂度 \(O(n^2)\)。

代码

const int N = 3005;

int n, k, a[N];
char s[N];
std::set<int> S;
std::vector<std::pair<int, int>> move;

void solve() {
    read(n), read(k), readStr(s + 1);
    for (int i = 1; i <= n; ++i) {
        a[i] = (s[i] == 'R');
        if (i == 1 || a[i] != a[i - 1]) S.insert(i);
    }
    S.insert(n + 1);
    int cnt = 0;
    while (1) {
        std::vector<int> p;
        int x = 1;
        while (x <= n) {
            if (a[x] || x == 1) {
                x = *S.upper_bound(x);
                continue;
            }
            p.push_back(x - 1);
            std::swap(a[x], a[x - 1]);
            int tmp = *S.upper_bound(x);
            if (x > 2 && !a[x - 2]) {
                S.erase(x - 1);
            } else {
                S.insert(x - 1);
            }
            if (!a[x + 1]) {
                S.insert(x + 1);
            }
            x = tmp;
        }
        if (p.empty()) {
            break;
        }
        ++cnt;
        for (int v : p) {
            move.push_back({v, cnt});
        }
    }
    if (k < cnt || k > (int)move.size()) {
        print(-1);
        return;
    }
    for (int i = (int)move.size() - 1; i >= 1; --i) {
        move[i].second -= move[i - 1].second;
    }
    for (int i = 0; i < (int)move.size(); ++i) {
        if (move[i].second) {
            continue;
        }
        if (cnt == k) {
            break;
        }
        move[i].second = 1;
        ++cnt;
    }
    std::vector<std::vector<int>> ans(k);
    int now = 0;
    for (auto p : move) {
        now += p.second;
        // debug("%d %d\n", p.first, p.second);
        ans[now - 1].push_back(p.first);
    }
    for (auto p : ans) {
        print((int)p.size(), ' ');
        for (int v : p) {
            print(v, ' ');
        }
        putchar('\n');
    }
}

E - Road to 1600

题目传送门

题解

直接考虑一个很大的棋盘看上去非常难做。我们考虑首先将车和后延一条固定的、相同的路径引导至一个较小的棋盘内。

考虑到 \(n\le 2\) 时一定无解，我们只要将最后的棋盘控制在 \(3\times 3\) 的规模即可。

如何构造一个满足题目条件的 \(3\times 3\) 的棋盘？

一共只有 \(3\times 3=9\) 个数，我们可以直接暴力枚举所有棋盘！

注意这个棋盘的最小值所在的格子必须与路径的终点在同一行或同一列，这样才可以保证车和后在这个棋盘中的起点相同。

暴力代码

int a[5][5], p[15], vis[5][5];

bool rook(int x1, int y1, int x2, int y2) {
    return x1 == x2 || y1 == y2;
}

bool queen(int x1, int y1, int x2, int y2) {
    return x1 == x2 || y1 == y2 || x1 + y1 == x2 + y2 || x1 - y1 == x2 - y2;
}

template<typename T>
int work(T check) { // check 是一个判断两点是否可以互相到达的函数（上方 rook 和 queen 中的一种）
    int x = 0, y = 0;
    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= 3; ++j) {
            if (a[i][j] == 1) {
                x = i, y = j;
            }
            vis[i][j] = 0;
        }
    }
    vis[x][y] = 1;
    int res = 0;
    while (1) {
        int nx = 0, ny = 0, mn = 10, type = 2;
        for (int i = 1; i <= 3; ++i) {
            for (int j = 1; j <= 3; ++j) {
                if (!vis[i][j]) {
                    int tp = !check(x, y, i, j);
                    if (tp < type || (tp == type && a[i][j] < mn)) {
                        nx = i, ny = j, mn = a[i][j], type = tp;
                    }
                }
            }
        }
        if (type == 2) {
            break;
        }
        res += type, x = nx, y = ny, vis[x][y] = 1;
    }
    return res;
}

int main() {
    for (int i = 1; i <= 9; ++i) {
        p[i] = i;
    }
    while (1) {
        for (int i = 1; i <= 3; ++i) {
            for (int j = 1; j <= 3; ++j) {
                a[i][j] = p[(i - 1) * 3 + j];
            }
        }
        if (work(rook) < work(queen)) {
            for (int i = 1; i <= 9; ++i) {
                print(p[i], ' ');
                if (i % 3 == 0) {
                    putchar('\n');
                }
            }
            return 0;
        }
        if (!std::next_permutation(p + 1, p + 1 + 9)) {
            break;
        }
    }
}

代码

const int N = 505;

int n, a[N][N];

void solve() {
    read(n);
    if (n <= 2) {
        print(-1);
        return;
    }
    int B = n * n - 9;
    a[1][1] = B + 1, a[1][2] = B + 2, a[1][3] = B + 4;
    a[2][1] = B + 5, a[2][2] = B + 3, a[2][3] = B + 8;
    a[3][1] = B + 9, a[3][2] = B + 6, a[3][3] = B + 7;
    int now = 0;
    for (int i = 4; i <= n; ++i) {
        if (i & 1) {
            for (int j = 1; j <= i; ++j) {
                a[i][j] = ++now;
            }
            for (int j = i - 1; j; --j) {
                a[j][i] = ++now;
            }
        } else {
            for (int j = 1; j <= i; ++j) {
                a[j][i] = ++now;
            }
            for (int j = i - 1; j; --j) {
                a[i][j] = ++now;
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            print(a[i][j], ' ');
        }
        putchar('\n');
    }
}

F - Kate and imperfection

题目传送门

题解

考虑依次求出 \(I_2,I_3,\cdots,I_n\)。

开始时集合大小为 \(1\)，我们强制集合中只包含 \(1\)。我们贪心地往集合内加入元素。

由于我们需要使集合中两两 \(\gcd\) 的最大值最小，一开始我们一定是考虑依次加入所有质数。

加入完所有质数后，我们不可能再保证答案为 \(1\)，我们考虑放宽限制，使得两两 \(\gcd\) 的最大值为 \(2\)。

显然，我们可以加入 \(4=2\times 2\)，但不可以加入 \(6=2\times 3,8=2\times 4,\cdots\)。

然后我们考虑使得最大值为 \(3\)，那么我们可以加入 \(6=2\times 3,9=3\times 3\)，但不能加入 \(12=4\times 3,\cdots\)。

接下来考虑使得最大值为 \(4\)，我们可以加入 \(8=2\times 4\)，可是我们不能加入 \(12=3\times 4\)，因为之前已经加入了 \(6\)。

那么什么时候可以加入 \(12\)？在我们枚举最大值为 \(6\) 时才可以加入 \(12\)。

再往后模拟若干次，大胆猜想，一个数 \(x\) 会在枚举最大值为 \(x\) 的最大真因子（即不等于本身的因子）时被加入集合。

直接使用欧拉筛求出 \(2\) 到 \(n\) 每个数的最大真因子即可。

时间复杂度 \(O(n)\)。

（做题全靠猜结论.jpg）

上述做法的正确性可以参考官方题解。

代码

const int N = 500005;

int n, c[N];
int cnt, p[N], vis[N], minp[N];

void solve() {
    read(n);
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            p[++cnt] = i;
            minp[i] = i;
        }
        for (int j = 1; j <= cnt && 1ll * p[j] * i <= n; ++j) {
            vis[i * p[j]] = 1;
            minp[i * p[j]] = p[j];
            if (i % p[j] == 0) {
                break;
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        ++c[i / minp[i]];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= c[i]; ++j) {
            print(i, ' ');
        }
    }
    putchar('\n');
}

更新于：2020年4月10日

贪心

构造

数论

Educational Codeforces Round 85 (Rated for Div. 2)

罚时被 E 搞没了。 A - Level Statistics 题目传送门题解初始状态为 \(p_0=0,c_0=0\)。由于每进行一次游戏，\(p\) 一定会加 \(1\)...

Codeforces Round #630 (Div. 2) 被爆踩记

被神仙 Froggy 爆踩了。 A - Exercising Walk 题目传送门题意在二维平面上有一个矩形 \((x_1,y_1),(x_2,y_2)\)，你初始在 \((x,...