Codeforces Round#714 div.2 回顾

七海

题解

发布于：2021年4月12日

次浏览

补题链接：https://codeforces.com/contest/1513

记录

总算是最后勉勉强强地成为了 ABCD 选手，，但是因为失明不长脑子以及没有手等众多因素，导致我这场比赛的罚时高的离谱，，四个题都会做甚至排名 500+（

当然，这场的题目比昨天发的那篇文章的那套题还要水的多，，只能说…什么也说不出（

然后吃午饭的时候看一 20 级学弟在群里装杯，一查 CF 结果昨天这场他做了五个题，罚时也把我吊起来打……老年人的眼泪不争气地掉了下来（

题解

A - Array and Peaks

没什么好说的，由手就行，没手也行（

const int N = 110;
int a[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int T = $.nextInt(), n, k;
    while (T --) {
        input, n, k;
        if (k > (n - 1) / 2)
            output, -1, endl;
        else {
            memset(a, 0, sizeof a);
            for (int i = 0; i < k; ++ i)
                a[i * 2 + 2] = n - i;
            int cur = 0;
            for (int i = 1; i <= n; ++ i)
                if (!a[i]) a[i] = ++ cur;
            $.putArray(a + 1, a + 1 + n);
        }
    }

    return 0;
}

B - AND Sequences

显然，考虑极端情况 \(a_1 \& a_2 \& \cdots \& a_{n - 1} = a_n\) 是成立的，那么显然有 \(\&_{i = 1}^n a_i = a_n\)；同理也可以证明 \(\&_{i = 1}^n a_i = a_1\)；因此只需要先对数组求按位与的和，然后查找这个数字在数组里出现的次数；从中选择两个放在头尾，剩下的数字放在中间随便摆。

很简单的一个题，思路也很清晰……

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int a[N], fact[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    fact[0] = fact[1] = 1;
    for (longs i = 2; i < N; ++ i)
        fact[i] = int(fact[i - 1] * i % mod);

    int T = $.nextInt(), n;
    while (T --) {
        $(n).nextArray(a + 1, a + 1 + n);
        uint mask = ~0u;
        for (int i = 1; i <= n; ++ i)
            mask &= (uint) a[i];
        longs cnt = 0;
        for (int i = 1; i <= n; ++ i)
            if (mask == a[i]) ++ cnt;
        cnt = cnt * (cnt - 1) % mod;
        output, cnt * fact[n - 2] % mod, endl;
    }

    return 0;
}

本来应该是这样的，，但是因为我最开始预处理的时候没有赋值 fact[0] = 1，导致我 WA 的生活不能自理直接放弃，直到最后面才意识到这个问题的，，，我是傻逼嘛（

C - Add One

显然，对于一个具体的数字，我们进行 \(n\) 次变换的结果时独立确定的，也可以表现为 10 个数字的个数。因为变换的上线也只有 \(2 \times 10^5\) 级别，所以完全可以预处理后，对于具体的数字变形后查询得到答案：

const int mod = 1e9 + 7;
const int N = 2e5 + 5;

int dp[10][N], f[10][10], tmp[10], cnt[10];
char s[100];

int transfer(int id) {
    memset(tmp, 0, sizeof tmp);
    for (int i = 0; i < 9; ++ i)
        tmp[i + 1] = f[id][i];
    tmp[1] += f[id][9], tmp[0] += f[id][9];
    tmp[1] %= mod, tmp[0] %= mod;
    longs ret = 0;
    for (auto i : tmp) ret += i;
    memcpy(f[id], tmp, sizeof tmp);
    return int(ret %= mod);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    for (int i = 0; i < 10; ++ i)
        f[i][i] = dp[i][0] = 1;
    for (int i = 1; i < N; ++ i)
        for (int j = 0; j < 10; ++ j)
            dp[j][i] = transfer(j);

    int T = $.nextInt(), n, m;
    while (T --) {
        input, n, m;
        longs ans = 0;
        itoa(n, s, 10);
        char *st = s;
        memset(cnt, 0, sizeof cnt);
        while (*st) ++ cnt[*st - '0'], st ++;
        for (int i = 0; i < 10; ++ i) {
            ans += 1ll * dp[i][m] * cnt[i];
            ans %= mod;
        }
        output, ans, endl;
    }

    return 0;
}

显然，我这样写还是有点蠢的：实际上并不需要枚举每一个数字的变换，只需要枚举 0 的变换即可。

D - GCD and MST

一张图，有 \(n\) 个节点，每个点都有权值 \(a_i\)；相邻节点之间连接了权值为 \(p\) 的边（共 \(n - 1\) 条）；此外，对于下标 \(i\) 和 \(j\) 即 \(1 \leq i < j \leq n\)，如果满足 \(\gcd_{k = i}^j a_k = \min_{k = i}^j a_k\)，则 \(i \leftrightarrow j\) 之间连接一条权重为 \(\min_{k = i}^j a_k\) 的边；
现在要求求出这张图的最小生成树的边权值之和。

看到最小值，就联想到要考虑最小值的区间；先对于 \(a[i]\) 排序，然后对于每个最小值，向左向右尝试找到包含这个最小值的连续区间；显然，这个连续区间中的每一个节点都可以互相连接边权为这个最小值的边；对于长度为 \(l\) 的这样的区间，我们只需要连接 \(l - 1\) 条这样的边即可。

这样虽然解决了最小值区间内的问题，但是最小值区间之间也可能连边；所以最小值探边界的时候，如果遇到了已经被之前的（更小的）最小值占领的区间，仍需要额外考虑一次来判断是否可以连边来连接两个区间。

const int N = 2e5 + 5;
int a[N], vis[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int T = $.nextInt(), n, p;
    memset(vis, -1, sizeof vis);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;
    while (T --) {
        $(n, p).nextArray(a + 1, a + n + 1);
        while (!heap.empty()) heap.pop();
        for (int i = 1; i <= n; ++ i)
            heap.emplace(a[i], i);
        int res = n - 1;
        longs ans = 0;
        while (!heap.empty()) {
            auto [x, ii] = heap.top();
            if (x >= p) break;
            else heap.pop();
            if (vis[ii] == T) continue;
            else vis[ii] = T;
            int g = x, l = ii - 1, r = ii + 1;
            while (l > 0) {
                auto gg = gcd(x, a[l]);
                if (gg == g) {
                    if (vis[l] == T) {
                        -- l; break;
                    } else vis[l --] = T;
                } else break;
            }
            while (r <= n) {
                auto gg = gcd(x, a[r]);
                if (gg == g) {
                    if (vis[r] == T) {
                        ++ r; break;
                    } else vis[r ++] = T;
                } else break;
            }
            ans += longs(r - l - 2) * x;
            res -= r - l - 2;
        }
        ans += 1ll * res * p;
        output, ans, endl;
    }

    return 0;
}

想通了实际上也就这么一回事，但是我却还是白给了两发…… 因为我认为我的手会敲出和我脑子想象中一样的代码，但是实际上手没有，，导致我一度以为我想错了开始胡思乱想，，还是菜的离谱了点（

E - Cost Equilibrium

有一个长度为 \(n\) 的数组，每个位置都有值 \(a_i\)；现在你可以花费 \(x \cdot |i - j|\) 的成本，使得 \(a_i\) 减少 \(x\) 并使得 \(a_j\) 增加 \(x\)，操作中不能有任何值变为负数；每个点只能进行一类操作（减少操作和增加操作不能出现在同一个节点上）；将数组中的所有值全部变为相等而进行的操作带来的成本和定义为数组的成本。
现在要求你重新排列数组，使得数组的成本的最小值和最大值相等。求出这样重新排列后的数组的个数。

题目一通花里胡哨完了之后实际上没啥内容；首先排除 \(\sum a_i \mod n \neq 0\) 的情况。那么剩下来的情况就都满足 \(n \ | \sum a_i\)；令 \(x = \sum a_i \div n\)。

然后考虑：因为每个节点只能承担一种角色，所以

\(a_i > x\) 的节点只能是出点，\(a_i < x\) 的节点只能是入点
\(a_i \neq x\) 的节点不能参与任何操作

失明的我一开始把这个限制条件看成了每个节点只能运入一次运出一次，然后鼓捣了个假做法，发现和题解完全不同~~但是过了样例，要是比赛中这样那我大概也是个假人了~~，不过似乎可以出个新题（？）

我们记小于平均值的节点的数量为 \(l\)，大于平均值的节点数量为 \(g\)；那么可以进行下面的猜想：

\(l = 0\) 并且 \(g = 0\)：显然，全数组已经相同，只有 \(1\) 种排列满足要求
\(l = 1\) 或 \(g = 1\)：出点/入点是确定的，所以运输方案只有一种；任何排列都满足要求
否则：出点们和入点们分布在数组的两侧且互不相交时才可以满足要求

关于第三条，很显然如果出入点之间产生了交错，那么中间节点的运输方向的改变会影响到答案。

又因为输出的是重排后的序列的种类数，所以在直接求排列数之后需要特殊处理出现了相同数字的位置：将它们的排列数从总的排列数中除掉；而等于平均值插入到排序中可以使用组合数求出。

补题代码

因为涉及到了排列组合，并且是模意义下运算，所以需要预处理阶乘和阶乘的逆元。

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int a[N], n, fact[N], inv[N];

namespace Inverse {
    longs fastPow(longs a, longs b, longs mod) {
        longs ans = 1;
        while (b) {
            if (b & 1u) ans = (ans * a) % mod;
            a = (a * a) % mod;
            b >>= 1u;
        }
        return ans % mod;
    }

    longs inverse(longs a, longs p) {
        if (a > p || a <= 0) return -1;
        else if (a == 1 && p) return 1;
        else return fastPow(a, p - 2, p) % p;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    fact[0] = fact[1] = 1;
    for (longs i = 2; i < N; ++i)
        fact[i] = int(fact[i - 1] * i % mod);
    inv[N - 1] = (int)Inverse::inverse(fact[N - 1], mod);
    for (longs i = N - 2; i >= 0; --i)
        inv[i] = (int)(inv[i + 1] * (i + 1) % mod);
    const auto nCr = [](int a, int b) {
        if (b < 0 || b > a) return 0;
        longs ret = fact[a];
        ret = (ret * inv[a - b]) % mod;
        ret = (ret * inv[b]) % mod;
        return (int)ret;
    };

    $(n).nextArray(a + 1, a + 1 + n);
    lll sum = accumulate(a + 1, a + 1 + n, (lll) 0);
    if (sum % n) {
        output, 0, endl;
        return 0;
    }
    auto x = sum / n;
    int less = 0, greater = 0, equal = 0;
    unordered_map<int, int> cnt;
    cnt.reserve(N * 2);
    for (int i = 1; i <= n; ++i)
        ++cnt[a[i]];
    for (int i = 1; i <= n; ++i)
        if (a[i] > x) ++greater;
        else if (a[i] < x) ++less;
        else ++equal;
    if (!less && !greater) {
        output, 1, endl;
    } else if (less == 1 || greater == 1) {
        lll ans = fact[n];
        for (auto [k, v] : cnt)
            ans = (ans * inv[v]) % mod;
        output, ans, endl;
    } else {
        auto ans = (lll)fact[less] * fact[greater] % mod;
        for (auto [k, v] : cnt)
            if (k != x)
                ans = (ans * inv[v]) % mod;
        ans *= 2, ans %= mod;
        ans = (ans * nCr(n, equal)) % mod;
        output, ans, endl;
    }
    return 0;
}

因为最开始没有特判全数组相等的情况，所以白给了一发（

F - Swapping Problem

现在你有两个长度为 \(n\) 的数组 \(a\) 和 \(b\)；数组的权值之和是 \(\sum|a_i - b_i|\)；你现在可以进行最多 1 次的交换：将 \(b\) 中的两个数字交换位置；问可以求得的最小权值是多少。

对于每个位置 \(i\)，我们可以将它看作一个区间；那么权值和就是所有的区间大小的和。我们能做的是交换其中某两个区间的特定端点，从而使得总区间大小变小。要想实现这种交换，我们交换的两个端点在对应的区间中的角色必须不同（显然，如果角色相同，交换了没有任何意义）；

而进行简单的推导我们可以得出猜想：交换了两个在对应区间中角色不同的端点，带来的贡献是两个区间重复部分的 2 倍；如果两个区间没有重叠，那么就会造成两个区间间隔的两倍的负贡献。因此，我们只要找到来自两个部分的，且有最大覆盖的区间，就可以求出最小的权值。

我们将所有的区间分成两类：\(I\) 类以 \(a_i\) 为左端点，而 \(II\) 类以 \(b_i\) 为左端点；因此，交换的两个区间必须一个来自 \(I\)，另一个来自 \(II\)；在按照左边界排序之后，维护每组的前缀的最大右边界；这样我们就可以快速的查找对于某个区间而言，可能形成最大覆盖的来自另一组的区间；遍历一组，查找另一组，更新答案即可。

补题代码

当然，这个经典的问题也可以使用双指针来解决，就像下面这样；

const int N = 2e5 + 5;
int a[N], b[N], n;

template <typename T>
void sortVector(vector<T> &vec) {
    sort(vec.begin(), vec.end());
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    $(n).nextArray(a + 1, a + 1 + n)
        .nextArray(b + 1, b + 1 + n);
    lll ans = 0, origin = 0, pp = 0;
    vector<pair<int, int>> I, II;
    for (int i = 1; i <= n; ++ i) {
        if (a[i] < b[i]) {
            I.emplace_back(a[i], b[i]);
        } else {
            II.emplace_back(b[i], a[i]);
        }
        origin += abs(a[i] - b[i]);
    }
    const auto sizI = I.size(), sizII = II.size();
    sortVector(I), sortVector(II);
    priority_queue<int> heap;
    ans = origin, pp = 0;
    for (auto [L, R] : I) {
        while (pp < sizII && II[pp].first <= L) {
            heap.push(II[pp].second), ++ pp;
        }
        if (!heap.empty()) {
            auto lastR = heap.top();
            minimize(ans, origin - 2 * (min(lastR, R) - L));
        }
    }
    while (!heap.empty()) heap.pop();
    pp = 0;
    for (auto [L, R] : II) {
        while (pp < sizI && I[pp].first <= L) {
            heap.push(I[pp].second), ++ pp;
        }
        if (!heap.empty()) {
            auto lastR = heap.top();
            minimize(ans, origin - 2 * (min(R, lastR) - L));
        }
    }
    output, ans, endl;

    return 0;
}

老年人光是想着怎么维护这个区间的最大覆盖就想了半个上午，属实不行（

后记

唉，感觉这一场也没什么难的啊，只可惜前面罚时实在是太多了，，写代码的时候竟然连 \(0!=1\) 这种常识性的东西都能不注意，也算是重新认识了自己==

今晚还有 EDU 场，不废话了，好好打啊（

更新于：2021年4月12日

算法

ACM

Codeforces

使用 pandoc 正确渲染多行 MathJax 公式

随着 Hexo 的发展，有越来越多的小伙伴使用 Hexo 搭建技术博客，其中不乏大量包含数学公式的场合：为了满足这种需要，一般是在 Markdown 中使用部分 \(\LaTeX\) 语法书写数...

Codeforces Round#712 div.2 回顾

补题链接：https://codeforces.com/contest/1504 记录只能说进入四月一来一直颓的可以，，不仅没怎么训练没怎么准备考研，倒是莫名其妙地出去混了一天又一天，真的...