Educational Codeforces Round 106 回顾

七海

题解

发布于：2021年3月19日

次浏览

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

记录

一开始还是挺像模像样的，快速地切掉了 ABC 三个题，然后在 D 题处一直瞎想，看着通过人数从 30 涨到 600 左右直到比赛结束……这种感觉是真的不好（）到底是什么使得我变得总是做不出 D 呢…… 确实需要好好反思（

题解

A - Domino on Windowsill

不用管怎么摆放；因为只有两排，所以只需要看格子数够不够就行；

代码

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int T = scanner.nextInt();
    while (T --)
    {
        int n, k1, k2, w, b;
        scanner(n, k1, k2, w, b);
        int ww = (k1 + k2) / 2;
        int bb = (2 * n - k1 - k2) / 2;
        println(ww >= w && bb >= b ? "YES" : "NO");
    }
    return 0;
}

B - Binary Removals

数据规模很小；所以只需要遍历 0-1 分界点的位置，然后 \(O(n)\) 检查是否可行即可。

代码

const int N = 120;
char s[N];

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int T = scanner.nextInt();
    while (T --)
    {
        scanner(s);
        int n = strlen(s);
        bool ok = false;
        bitset<N> del;
        for (int i = 0; i <= n; ++ i)
        {
            del.reset();
            for (int j = 0; j < i; ++ j)
                if (s[j] == '1') del.set(j);
            for (int j = i; j < n; ++ j)
                if (s[j] == '0') del.set(j);
            bool _ok = true;
            for (int j = 1; j < n; ++ j)
                if (del[j] && del[j - 1]) _ok = false;
            if (_ok) ok = true;
        }
        println(ok ? "YES" : "NO");
    }
    return 0;
}

C - Minimum Grid Path

首先，你至少要转一次弯才能到达终点，所以你的路程段数至少是两段；因为只有两个方向，所以你每转一次弯就相当于在两种方向来回横跳；注意到题目说的是第 x 段路的费用是 \(c_x\)；所以显然偶数段的路和奇数段的路方向不同，且恰好占据了两个方向——且两个方向都需要走 \(n\) 的长度；

因为转方向之后至少要在这一段路之间走 1 个单位，所以如果在某个方向走了 \(x\) 段路，其中费用最小的为 \(c_x'\)，所有的这些路段的单价总和为 \(C_x\)，那么这个方向上最便宜的走法一定是花费 \(C_x + (n - x)c_x'\) 的：即在花费最小的路段尽可能地走，但是之前经过的不那么优的路段只走一段；

还需要注意的就是两个方向并不是独立的：因为是连贯的折线，所以在两个方向上走的段数差不能超过 1；一种比较优雅的遍历方法就是遍历所有的段数，然后分别处理两边的最优花费，求和取最小值。

代码

const int N = 1e5 + 5;
longs c[N];

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int T = scanner.nextInt();
    while (T --)
    {
        int n = scanner.nextInt();
        for (int i = 1; i <= n; ++ i)
            c[i] = scanner.nextInt();
        longs ans = c[1] * n + c[2] * n;
        longs odd = c[1], even = c[2];
        longs os = c[1], es = c[2];
        longs on = 1, en = 1;
        for (int i = 3; i <= n; ++ i)
        {
            ++ (i % 2 ? on : en);
            (i % 2 ? os : es) += c[i];
            minimize((i % 2 ? odd : even), c[i]);
            auto tmp = odd * (n - on) + os + even * (n - en) + es;
            minimize(ans, tmp);
        }
        println(ans);
    }
    return 0;
}

D - The Number of Pairs

给定三个整数 \(c\)， \(d\)，\(x\)；它们满足 \(1 \leq c, d, x \leq 10^7\)；现给定等式： \[ c \cdot \mathrm{lcm}(a, b) - d \cdot \mathrm{gcd}(a, b) = x \] 且 \(a, b\) 均为正整数；求出满足该等式的 \((a, b)\) 的对数。

这个等式首先一看就是要化简的：令 \(K = \mathrm{gcd}(a, b)\)；那么就可以将 a 和 b 表示为 \(a = nK, \ b = mK\)，其中的 n 和 m 显然满足 \(n,m \in N^+\) 和 \(\mathrm{gcd}(n, m) = 1\)；那么我们就可以进行如下的等价变换： \[ \begin{align} c \cdot \mathrm{lcm}(a, b) - d \cdot \mathrm{gcd}(a, b) &= x \\ c \cdot \frac{ab}{\mathrm{gcd}(a, b)} - d \cdot \mathrm{gcd}(a, b) &= x \\ c \cdot nmK - d \cdot K &= x \\ K &= \frac{x}{cnm - d} \end{align} \] 那么，记 \(y = cnm - d\)，这个问题就变成了求满足这个等式的互质的 \((n, m)\) 的对数。具体的做法就是枚举 \(x\) 的因子 \(y\)：如果满足 \(c \mid (d + y)\)，那么 \(nm = \frac{d + y}{c}\)；记 \(z = nm\)，因为 n 和 m 互质，所以 \(z\) 的每一个不同的质因子要不全部属于 n，要不全部属于 m；用 \(P_z\) 表示 z 的不同的质因子的数量，那么对于 z，满足条件的 (n, m) 一共有 \(2^{P_z}\) 对。

实际实现时，可以先用线性筛预处理数据范围内的 \(P\) 数组，然后根据输入计算答案。

代码

const int A = 2e7 + 7;

namespace linear_sieve { ... }

longs fastPow(longs a, ulongs b) { ... }

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int T = scanner.nextInt(), c, d, x;
    using linear_sieve::cnt;
    linear_sieve::start();
    const auto calc =
    [&](longs y) -> longs
    {
        if ((d + y) % c) return 0;
        const auto z = (d + y) / c;
        return fastPow(2, cnt[z]);
    };
    while (T --)
    {
        scanner(c, d, x);
        longs ans = 0, y;
        for (y = 1; y * y < x; ++ y)
            if (!(x % y))
                ans += calc(y) + calc(x / y);
        if (y * y == x) ans += calc(y);
        println(ans);
    }
    return 0;
}

需要注意的是：虽然数据范围是 1e7 的，但是 z 是有可能大于 1e7 的；所以预处理的数据范围要更广。

事后分析

虽然也确实推了式子，也至少推到了这份题解中提到的第二部；但是这实在是太像 \(\mathrm{exgcd}\) 了：如果假设 lcm 和 gcd 都为未知变量的话；但是就像刚才所推导的那样，这两个未知变量之间本就有所联系，并且这个联系的关系也是不定的（lcm 是 gcd 的倍数），求出了倍数还是要进行这样的拆分，就非常的不合理。