Codeforces Global Round 28

比赛链接

Problems	AC	Note
A. Kevin and Combination Lock	○
B. Kevin and Permutation	○
C. Kevin and Binary Strings	○
D. Kevin and Competition Memories	○
E. Kevin and Bipartite Graph	⊕	二分图、构造
F. Kevin and Math Class	⊕	笛卡尔树、树形 DP
G. Kevin and Matrices
H. Kevin and Strange Operation
I1. Kevin and Puzzle (Easy Version)
I2. Kevin and Puzzle (Hard Version)

A

直接蜘蛛感应出做法了，懒得证了。

Code >folded

void solve() {
    int n = read();
    if (n % 33 == 0) {
        puts("YES");
    } else {
        puts("NO");
    }
}

B

最优一定是间隔放置，很典

Code >folded

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

    vector<int> a(n + 1);
    int cnt = 1;
    for (int i = k; i <= n; i += k) {
        a[i] = cnt++;
    }
    for (int i = 1; i <= n; i++) {
        if (!a[i]) a[i] = cnt++;
    }

    for (int i = 1; i <= n; i++) {
        cout << a[i] << " \n"[i == n];
    }
}

C

赛时做法是把所有字符串扔到 Trie 里面，然后在 Trie 上面 dfs，似乎是写复杂了

Code >folded

void solve() {
    string s;
    cin >> s;
    int n = s.size();

    int p = -1;
    for (int i = 1; i < n; i++) {
        if (s[i] == '0') {
            p = i;
            break;
        }
    }

    if (p == -1) {
        cout << "1 1 1 " << n << '\n';
        return;
    }

    int len = n - 1 - p + 1;
    int nod = 0;
    std::unordered_map<int, int> ch[2], info;

    pii ans;
    for (int i = 0; i + len - 1 < n; i++) {
        int cur = 0;
        for (int j = i; j <= i + len - 1; j++) {
            int x = s[j] - '0';
            if (!ch[x][cur]) {
                ch[x][cur] = ++nod;
            }
            // assert(cur < ch.size());
            cur = ch[x][cur];
        }
        info[cur] = i + 1;
    }

    int cur = 0;
    for (int i = p; i < n; i++) {
        int x = s[i] - '0';
        if (ch[x ^ 1][cur]) {
            cur = ch[x ^ 1][cur];
        } else {
            cur = ch[x][cur];
        }
    }

    cout << "1 " << n << ' ';
    cout << info[cur] << ' ' << (info[cur] + len - 1) << '\n';
}

D

随便写写就过了。

Code >folded

void solve() {
    int n = read();
    int m = read();
    vector<int> a(n + 1);
    vector<int> b(m + 1);
    for (int i = 1; i <= n; i++) a[i] = read();
    std::sort(a.begin() + 2, a.end());
    for (int i = 1; i <= m; i++) b[i] = read();
    std::sort(b.begin() + 1, b.end());

    int cnt = 0;
    int le = 0, ri = -1;
    for (int i = 1; i <= m; i++) {
        if (b[i] <= a[1] or b[i] > a[n]) {
            cnt++;
        } else {
            if (le == 0) {
                le = i;
            }
            ri = i;
        }
    }

    vector<int> c(m + 1);
    for (int i = le; i <= ri; i++) {
        for (int L = 2, R = n; L <= R; ) {
            int mid = L + R >> 1;
            if (a[mid] >= b[i]) {
                c[i] = n - mid + 1;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
    }

    for (int k = 1; k <= m; k++) {
        int tot = m / k;
        int tcnt = cnt;

        int ans = 0;
        int l = le, r = ri;

        for (int i = 1; i <= tot; i++) {
            int need = k;
            int rk = 1;
            
            int tmp = min(tcnt, need);
            tcnt -= tmp, need -= tmp;

            tmp = min(need, r - l + 1);
            r -= tmp, need -= tmp;
            if (r + 1 <= m) rk = 1 + c[r + 1];
            ans += rk;
        }

        cout << ans << " \n"[k == m];
    }
}

E

一个完全二分图，左部有 $2n$ 个点，右部有 $m$ 个点，给每个边染上 $[1,n]$ 的颜色，使得没有同色简单环。

唉又被构造单杀了。前几天刚 VP 完 2022 ICPC 澳门，这个题关键点和那个差不多，都是算边数限制的。

由 $2nm \le n(2n + m - 1)$ 得 $m \le 2n - 1$。

$m$ 越大时限制越紧，尝试构造 $m = 2n - 1$ 的解。

此时每个右部点度数是 $2n$，一共有 $n$ 中颜色，令每种颜色的边恰好 $2$ 条。那么对于每个颜色，就相当于通过这个右部点，使两个左部点连通。最后经过 $m = 2n - 1$ 次连接，左部点需要形成树。可以让左边直接形成一条链，每次 shift 一下颜色即可。

在这种情况下，边 $(i, j)$ 的颜色为 $\lfloor \frac{(i + j) \bmod 2n}{2} \rfloor + 1$

Code >folded

void solve() {
    int n = read();
    int m = read();
    
    if (m >= n * 2) {
        puts("NO");
        return;
    }

    puts("YES");
    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; j <= m; j++) {
            int t = (i + j) % (2 * n) / 2 + 1;
            cout << t << " \n"[j == m];
        }
    }
}

F

Kevin 是 Eversleeping Town 的一名学生，目前正在上数学课，老师正在给他布置除法练习。

黑板上写着两行正整数，每行包含 $ n $ 个数字。第一行是 $ a _ 1, a _ 2, \ldots, a _ n $ ，第二行是 $ b _ 1, b _ 2, \ldots, b _ n $ 。

对于每个除法练习，Kevin 可以选择任意段 $ [l, r] $ ，并在 $ b _ l, b _ {l+1}, \ldots, b _ r $ 中找到最小值 $ x $ 。然后，他将 $ l \leq i \leq r $ 中的每个 $ a _ i $ 修改为 $ a _ i $ 除以 $ x $ 的上限。

正式来说，他选择了两个整数 $ 1 \leq l \leq r \leq n $ ，设置了 $ x = \min _ {l \leq i \leq r} b _ i $ ，并将所有 $ a _ i $ 中的 $ l \leq i \leq r $ 更改为 $ \lceil \frac{a _ i}{x} \rceil $ 。

当所有 $ a _ i $ 都变为 $ 1 $ 时，Kevin 就可以下课回家了。他很想离开，想知道实现这一目标所需的最少除法练习次数。

前两天 VP icpc 杭州刚做过类似的。首先显然你要搞个笛卡尔树，考虑在笛卡尔树上面 DP。

令 $f(u, i)$ 代表 $u$ 这个点操作 $i$ 次后，区间内的 $a$ 的最大值最小是多少。

因为 $b \ge 2$，所以最多 $\log$ 次操作。那么应该可以类似树形背包，枚举左右子树选了多少个，然后做合并。

然而这道题卡 2log。观察发现 $f(u, i)$ 是单调不增的。因此做 $\min - \max$ 卷积等价于对两个序列做归并排序。那么就是一只 log 了。

Code

const int K = 61;
int ceil_div(int x, int y) { return x / y + (x % y != 0); }
void solve() {
    int n = read();
    
    vector<int> a(n), b(n);
    for (auto &x : a) x = read();
    for (auto &x : b) x = read();

    vector<int> lc(n, n), rc(n, n);
    vector<int> stk;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() and b[i] < b[stk.back()]) {
            rc[stk.back()] = lc[i];
            lc[i] = stk.back();
            stk.pop_back();
        }
        stk.eb(i);
    }
    while (stk.size() > 1) {
        int x = stk.back();
        stk.pop_back();
        rc[stk.back()] = x;
    }


    vector<std::array<int, K>> dp(n + 1);
    auto dfs = [&](this auto &&self, int x, int l, int r) {
        if (x == n) return;
        self(lc[x], l, x);
        self(rc[x], x + 1, r);
        auto &L = dp[lc[x]];
        auto &R = dp[rc[x]];
        auto &f = dp[x];
        int i = 0, j = 0;
        f[0] = std::max({L[0], R[0], a[x]});
        while (i + j + 1 < K) {
            if (L[i] > R[j]) {
                i++;
            } else {
                j++;
            }
            f[i + j] = max({L[i], R[j], a[x]});
        }
        for (int i = 1; i < K; i++) {
            f[i] = min(f[i], ceil_div(f[i - 1], b[x]));
        }
    };
    dfs(stk[0], 0, n);

    auto &f = dp[stk[0]];
    int ans = std::find(f.begin(), f.end(), 1) - f.begin();
    cout << ans << "\n";
}