Educational Codeforces Round 106 回顾

补题链接：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{aligned} 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{aligned}

那么，记 $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 的倍数），求出了倍数还是要进行这样的拆分，就非常的不合理。