Codeforces Global Round 7 上 IM 记

AutumnKite

题解Codeforces

发布于：2020年3月25日

次浏览

终于上 IM 了（

A - Bad Ugly Numbers

题目传送门

题解

为什么您们都能想到构造 \(2333\cdots 333\) 啊 QAQ

显然一个能被 \(p\) 整除的数，加或减一个不能被 \(p\) 整除的数后，不能被 \(p\) 整除。

我们考虑 \(777\cdots 777\) 能被 \(7\) 整除，而 \(777\cdots 77x\)（\(x > 0\)）不能被 \(7\) 整除。

又~~根据小学数学知识~~，能被 \(4\) 整除的数的特征是最后两位能被 \(4\) 整除，由于 \(74\bmod 4\ne 0\)，所以我们构造 \(777\cdots 774\) 即可。

注意需要特判 \(n=1\)。

代码

int n;
void solve(){
    read(n);
    if (n == 1) return print(-1), void(0);
    for (register int i = 1; i < n; ++i) putchar('7');
    putchar('4'), putchar('\n');
}

B - Maximums

题目传送门

题解

由 \(c_i\) 的定义可得 \[\begin{aligned} b_i&=a_i-c_i \\&=a_i-\max\{0,\max\limits_{j=1}^{i-1} a_j\} \end{aligned}\]

移项后可得 \[a_i=b_i+\max\{0,\max\limits_{j=1}^{i-1}a_j\}\]

我们只要在递推的同时维护 \(a_1,a_2,\cdots,a_{i-1}\) 的最大值即可。

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

代码

const int N = 200005;
int n, a[N];
void solve(){
    read(n);
    for (register int i = 1; i <= n; ++i) read(a[i]);
    long long now = 0;
    for (register int i = 1; i <= n; ++i)
        if (a[i] > 0) now += a[i], print(now, ' ');
        else print(now + a[i], ' ');
    putchar('\n');
}

C - Permutation Partitions

题目传送门

题解

考场上我看到本题一脸懵逼，我发现我好像不会第一问...

冷静一下，发现显然答案的上界是取最大的 \(k\) 个数，即 \((n-k+1)+(n-k+2)+\cdots+n=\frac{(2n-k+1)k}{2}\)。

我们可以在原排列中标记出这最大的 \(k\) 个数，记从左往右第 \(i\) 个被标记的位置为 \(x_i\)。

我们要把原排列划分成 \(k\) 段意味着我们要找到 \(k-1\) 个分界点，并且我们现在要求两个分界点之间恰好包含一个被标记的数。

那么显然第 \(i\) 个分界点应该选在 \(x_i\) 到 \(x_{i+1}\) 之间。

每个分界点的选择是独立的（即不会影响其他分界点的选择），所以根据乘法原理，把每个分界点的方案数相乘即可。

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

代码

const int N = 200005, P = 998244353;
int n, k, a[N];
void solve(){
    read(n), read(k);
    long long sum = 0;
    int lst = 0, ans = 1;
    for (register int i = 1; i <= n; ++i){
        read(a[i]);
        if (a[i] > n - k){
            sum += a[i];
            if (lst) ans = 1ll * ans * (i - lst) % P;
            lst = i;
        }
    }
    print(sum, ' '), print(ans);
}

D2 - Prefix-Suffix Palindrome (Hard version)

题目传送门

题解

考场上看到本题的第一想法是枚举前后缀匹配的长度 \(l\)，然后要求从 \(l+1\) 开始的最长回文串或者以 \(n-l\) 结尾的最长回文串。

刚打算去隔壁最长双回文串复制一个代码，意识到了不对...

如果求出来的回文串与前后缀有重叠怎么办？

考虑上面这个想法用暴力怎么实现。在我们将原串中间插入 # 后，用 manacher 算法以 \(i\) 为回文中心的回文半径 \(d_i\)。

然后我们枚举前后缀匹配长度 \(l\)，分两种情况：

对于所有 \(l+1\le i\le \frac{|s|+1}{2}\) 且 \(i-d_i+1\le l+1\)，求出 \(i\) 的最大值；
对于所有 \(\frac{|s|+1}{2}\le i\le n-l\) 且 \(i+d_i-1\ge n-l\)，求出 \(i\) 的最小值。

可以发现，\(l\) 越大，越容易满足限制，越容易使得 \(i\) 取到极值。

所以我们求出最大的 \(l\) 以后用上面的暴力实现即可。

~~如果你不怕被 hack 的话~~ manacher 也可以用哈希实现。

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

代码

const int N = 2000005; // 注意数组开大一倍
int n, d[N];
char s[N];
void manacher(int *d, char *s, int n){
    for (register int i = 1, m = 0, r = 0; i <= n; ++i){
        d[i] = i > r ? 0 : std::min(r - i + 1, d[m - (i - m)]);
        while (i - d[i] > 0 && i + d[i] <= n && s[i - d[i]] == s[i + d[i]]) ++d[i];
        if (i + d[i] - 1 > r) m = i, r = i + d[i] - 1;
    }
}
void solve(){
    n = reads(s + 1);
    for (register int i = n; i; --i) s[i << 1] = s[i], s[i << 1 | 1] = '#';
    s[1] = '#', n = n * 2 + 1;
    manacher(d, s, n);
    // for (register int i = 1; i <= n; ++i) debug("%d ", d[i]); debug("\n");
    int len = 0;
    for (register int i = 1; i <= n / 2; ++i)
        if (s[i] != s[n - i + 1]) break;
        else ++len;
    // debug("%d\n", len);
    int d1 = 0, d2 = 0;
    for (register int i = len + 1; i <= (n + 1) / 2; ++i)
        if (i - d[i] + 1 <= len + 1) d1 = std::max(d1, (i - len) * 2 - 1);
    for (register int i = (n + 1) / 2; i <= n - len; ++i)
        if (i + d[i] - 1 >= n - len) d2 = std::max(d2, (n - len - i + 1) * 2 - 1);
    if (d1 > d2){
        for (register int i = 1; i <= len + d1; ++i)
            if (s[i] != '#') putchar(s[i]);
        for (register int i = n - len + 1; i <= n; ++i)
            if (s[i] != '#') putchar(s[i]);
    }
    else{
        for (register int i = 1; i <= len; ++i)
            if (s[i] != '#') putchar(s[i]);
        for (register int i = n - len - d2 + 1; i <= n; ++i)
            if (s[i] != '#') putchar(s[i]);
    }
    putchar('\n');
}

E - Bombs

题目传送门

题解

发现答案单调递减，可以考虑枚举答案 \(x\)。

将 \(> x\)（即必须炸掉的数）的位置置为 \(1\)，炸弹置为 \(-1\)，其他位置置为 \(0\)。

则合法的条件是所有后缀和 \(\le 0\)。

用线段树维护即可。

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

别问我为什么对，感觉挺对的就行了（雾

代码

const int N = 300005;
int n, p[N], q[N], pos[N];
struct Segment_Tree{
    int mx[N << 2], lz[N << 2];
    void add(int u, int v){ mx[u] += v, lz[u] += v; }
    void down(int u){
        add(u << 1, lz[u]), add(u << 1 | 1, lz[u]), lz[u] = 0;
    }
    void modify(int u, int l, int r, int L, int R, int v){
        if (L <= l && r <= R) return add(u, v), void(0);
        int md = (l + r) >> 1;
        down(u);
        if (L <= md) modify(u << 1, l, md, L, R, v);
        if (R > md) modify(u << 1 | 1, md + 1, r, L, R, v);
        mx[u] = std::max(mx[u << 1], mx[u << 1 | 1]);
    }
}T;
void solve(){
    read(n);
    for (register int i = 1; i <= n; ++i) read(p[i]), pos[p[i]] = i;
    for (register int i = 1; i <= n; ++i) read(q[i]);
    print(n, ' ');
    int now = n;
    T.modify(1, 1, n, 1, pos[n], 1);
    for (register int i = 1; i < n; ++i){
        T.modify(1, 1, n, 1, q[i], -1);
        while (T.mx[1] <= 0) --now, T.modify(1, 1, n, 1, pos[now], 1);
        print(now, ' ');
    }
}

F1 - Wise Men (Easy Version)

题目传送门

题解

考场上看到 Easy Version \(n\le 14\)，Hard Version \(n\le 18\)，莫名就想到了 meet in middle...

可以预处理出 \(f_{S,T,i}\) 表示当前排列中数的集合为 \(S\)，导出的 01 字符串为 \(T\)，且排列中最后一个数为 \(i\) 的方案数。

然后考虑 meet in middle，合并两边的方案。

问题来了，我好像不会快速合并两边的方案 QAQ

但是问题不大，我们可以 暴力合并！

直接枚举左边的数集 \(S\)，最后的 01 串 \(T\)，以及中间相邻的两个数，显然方案数可以利用 \(f\) 进行计算。

但是，你可能需要一些卡常技巧（设两边的大小分别为 \(B_1,B_2\)）：

\(f\) 数组只需要预处理所有 \(|S|=B_1\) 或 \(|S|=B_2\) 的位置，可以直接枚举所有排列进行统计，不需要进行 DP。
显然 01 串反转以后答案是不变的，所以我们只计算 \(T\le \operatorname{rev}(T)\) 的位置即可。
可以预处理 \(2^n-1,2^{B_1-1}-1,2^{B_2-1}-1\) 的值来减少运算次数。
由于枚举 \(T\) 以后我们可以知道中间相邻两个数是否有边，我们可以预处理出与一个点有边/无边的点来快速枚举。
根据代码常数调整 \(B_1,B_2\) 的大小。

为了保险，你可以再加上 Ofast 和 O3 优化。

理论时间复杂度 \(O(C_{n}^{B_1}(B_1!+B_2!+2^n n^2))\)，事实上有好几个 \(\frac{1}{2}\) 的常数。

代码

int n, E[14][14], bitcnt[1 << 14], rev[1 << 14], p[14], f[1 << 14][1 << 6][14];
long long ans[1 << 14];
std::vector<int> G[14][2];
void solve(){
    read(n);
    for (register int i = 0; i < n; ++i)
        for (register int j = 0; j < n; ++j){
            while (!isdigit(E[i][j] = getchar())) ;
            E[i][j] ^= '0';
            G[i][E[i][j]].push_back(j);
        }
    bitcnt[0] = 0;
    for (register int i = 1; i < (1 << n); ++i) bitcnt[i] = bitcnt[i >> 1] + (i & 1);
    rev[0] = 0;
    for (register int i = 1; i < (1 << (n - 1)); ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << (n - 2);
    int B1 = n >> 1, B2 = n - B1;
    for (register int S = 0; S < (1 << n); ++S)
        if (bitcnt[S] == B1 || bitcnt[S] == B2){
            int cnt = 0;
            for (register int i = 0; i < n; ++i)
                if (S >> i & 1) p[cnt++] = i;
            while (1){
                int T = 0;
                for (register int i = 0; i < cnt - 1; ++i)
                    if (E[p[i]][p[i + 1]]) T |= 1 << i;
                ++f[S][T][p[cnt - 1]];
                if (!std::next_permutation(p, p + cnt)) break;
            }
        }
    int U = (1 << n) - 1, U1 = (1 << (B1 - 1)) - 1, U2 = (1 << (B2 - 1)) - 1;
    for (register int S = 0; S < (1 << n); ++S)
        if (bitcnt[S] == B1){
            for (register int T = 0; T < (1 << (n - 1)); ++T)
                if (T <= rev[T]){
                    int T1 = T & U1, T2 = rev[T] & U2, t = (T >> (B1 - 1)) & 1, _S = U ^ S;
                    for (register int i = 0; i < n; ++i)
                        if (f[S][T1][i])
                            for (int j : G[i][t])
                                ans[T] += f[S][T1][i] * f[_S][T2][j];
                }
        }
    for (register int T = 0; T < (1 << (n - 1)); ++T)
        if (T <= rev[T]) print(ans[T], ' '); else print(ans[rev[T]], ' ');
    putchar('\n');
}

最后一分钟绝杀的感觉真的非常舒适（

F2 - Wise Men (Hard Version)

题目传送门

来了来了，来填坑了。

题解

发现既有有边又有没边的限制非常难搞，于是我们考虑容斥，即计算 \(ans_A\) 为对于所有 \(A\) 中为 \(1\) 的位置 \(i\)，满足 \(p_i\) 与 \(p_{i+1}\) 有边的排列 \(p\) 的数量（对于 \(0\) 的位置没有限制）。

计算出 \(ans_A\) 后，只要用类似于「逆高维前缀和」的方法，就可以在 \(O(2^nn)\) 求出真正的答案。

考虑如何计算 \(ans_A\)。发现 \(ans_A\) 的值只与 \(A\) 中 \(1\) 连续段的长度形成的可重集合有关。如 \(A=\{0,1,1,1,0,0,1\}\) 时，所有 \(1\) 连续段长度形成的集合就是 \(\{1,1,2,4\}\)（原长加 \(1\)）。

可以发现，对于任意 \(A\)，对应的 \(1\) 连续段长度形成的可重集合中所有元素的和一定恰好为 \(n\)。这意味着不同的集合数量等于 \(n\) 的划分数。

对于一个划分 \(P=\{a_1,a_2,\cdots,a_k\}\)，可以发现对应的方案数实质上是在原图中选出 \(k\) 条不相交的简单路径，满足第 \(i\) 条路径的点数为 \(a_i\) 的方案数。

那么我们先考虑选 \(1\) 条路径。可以用 DP 求出 \(f_{u,S}\) 表示当前在节点 \(u\)，经过的点集为 \(S\) 时的路径条数，进而求出 \(g_S\) 表示经过的点集为 \(S\) 的路径条数。

那么对于一个划分 \(P=\{a_1,a_2,\cdots,a_k\}\)，答案即为 \[\sum_{S_1,S_2,\cdots,S_k} \left[|S_i|=a_i\right]\left[\forall i\ne j:S_i\cap S_j=\varnothing\right]\left[\bigcup\limits_{i=1}^{k}S_i=U\right]\prod\limits_{i=1}^{k} g_{S_i}\]

其中 \(U\) 表示全集。

注意到由于 \(\sum\limits_{i=1}^{k} a_i=n\)，后面两个条件只需要保留一个即可。第二个条件很难处理，我们考虑保留第三个。若不考虑前两个条件，只考虑第三个条件，只需要用 FWT 即可方便地求出答案。

存在第一个条件时，我们只要将 \(g\) 加上一维，\(g_{l,S}\) 表示长度为 \(l\)，经过点集为 \(S\) 的简单路径数量。对于 \(|S|\ne l\) 的位置就置为 \(0\)。那么答案式子变成了 \[\sum_{S_1,S_2,\cdots,S_k} \left[\bigcup\limits_{i=1}^{k}S_i=U\right]\prod\limits_{i=1}^{k} g_{a_i,S_i}\]

直接将所有 \(g_i\) 进行一次 FWT 后，枚举划分时直接点乘。由于我们实际只需要卷积结果中 \(2^n-1\) 位置的值，所以我们不需要每次 IFWT，直接根据实际意义用容斥就可以 \(O(2^n)\) 求出这个值。

总时间复杂度 \(O(2^n(P(n)+n^2))\)，其中 \(P(n)\) 表示 \(n\) 的划分数。

实现得不好可能会变成 \(O(2^n(S(n)+n^2))\) 或 \(O(2^nn(P(n)+n))\)，其中 \(S(n)\) 表示 \(n\) 的所有划分的大小之和。

代码

int n;
std::vector<int> bitcnt;
std::vector<std::vector<long long>> f;
std::vector<std::vector<long long>> g;
std::map<std::vector<int>, std::vector<int>> part;
std::vector<long long> ans;
void dfs(int r, const std::vector<int> &l, const std::vector<long long> &s){
    if (!r){
        long long res = 0;
        int mask = (1 << n) - 1;
        for (register int i = 0; i < (1 << n); ++i)
            if (bitcnt[mask ^ i] & 1) res -= s[i]; else res += s[i];
        const std::vector<int> &p = part[l];
        for (int v : p) ans[v] += res;
        return;
    }
    int lst = l.empty() ? 1 : l.back();
    for (register int k = lst; k <= r; ++k){
        if (k < r && r - k < k) continue;
        std::vector<int> nl(l);
        std::vector<long long> ns(s);
        nl.push_back(k);
        for (register int i = 0; i < (1 << n); ++i) ns[i] *= g[k - 1][i];
        dfs(r - k, nl, ns);
    }
}
void solve(){
    read(n);
    std::vector<std::vector<int>> E(n);
    for (register int i = 0; i < n; ++i)
        for (register int j = 0; j < n; ++j){
            char ch;
            while (!isdigit(ch = getchar())) ;
            if (ch == '1') E[i].push_back(j);
        }
    bitcnt.resize(1 << n);
    bitcnt[0] = 0;
    for (register int i = 1; i < (1 << n); ++i) bitcnt[i] = bitcnt[i >> 1] + (i & 1);
    f.resize(n, std::vector<long long>(1 << n, 0));
    g.resize(n, std::vector<long long>(1 << n, 0));
    for (register int i = 0; i < n; ++i) f[i][1 << i] = 1;
    for (register int S = 1; S < (1 << n); ++S)
        for (register int i = 0; i < n; ++i)
            if (f[i][S]){
                g[bitcnt[S] - 1][S] += f[i][S];
                for (int v : E[i]) if (!(S >> v & 1)) f[v][S | (1 << v)] += f[i][S];
            }
    for (register int k = 0; k < n; ++k)
        for (register int i = 0; i < n; ++i)
            for (register int S = 0; S < (1 << n); ++S)
                if (S >> i & 1) g[k][S] += g[k][S ^ (1 << i)];
    for (register int S = 0; S < (1 << (n - 1)); ++S){
        std::vector<int> p;
        int x = 1;
        for (register int i = 0; i < n - 1; ++i)
            if (S >> i & 1) ++x; else p.push_back(x), x = 1;
        p.push_back(x);
        std::sort(p.begin(), p.end());
        part[p].push_back(S);
    }
    ans.resize(1 << (n - 1), 0);
    dfs(n, std::vector<int>(), std::vector<long long>(1 << n, 1));
    for (register int i = 0; i < n - 1; ++i)
        for (register int S = 0; S < (1 << (n - 1)); ++S)
            if (S >> i & 1) ans[S ^ (1 << i)] -= ans[S];
    for (long long v : ans) print(v, ' ');
    putchar('\n');
}

G - Spiderweb Trees

题目传送门

tourist 都没过的题，鸽了鸽了。

更新于：2020年4月1日

贪心

构造

manacher

线段树

递推

meet in middle

Educational Codeforces Round 84 (Rated for Div. 2) 自闭记

自闭了。 A - Sum of Odd Integers 题目传送门题解首先，我们尝试取出最小的 \(k\) 个正奇数：\(1,3,5,7,\cdots,2k-1\)。这些奇...

Codeforces Round #628 (Div. 2) 爆蛋记

完全爆蛋，小号三场上橙无望 /kk 爆蛋链接 A - EhAb AnD gCd 题目传送门题意构造正整数 \(a,b\) 满足 \(\gcd(a,b)+\operatornam...