算法竞赛比赛记录: AtCoder Regular Contest 203 (Div. 2)

A - All Winners

考虑第 $i$ 组有 $a_i$ 个全胜者，那么考虑任意两组之间的 PK，应该有

a_i+a_j\le M, i,j\in[1,n]

我们要在这个约束下，求出 $\max\sum_i a_i$ .

考虑 $a_1$ 的取值和 $n-1$ 个与之有关的不等式，可以发现 $\sum_i a_i$ 和 $a_i$ 也需要满足不等式：

\sum_i a_i\le a_1+(n-1)(M-a_1)=(n-1)M-(n-2)a_1\\ 2(M-a_1)\le M

所以 $a_1$ 应该取最小值，即 $a_1=\lceil\frac{M}{2}\rceil$ ，于是 $a_i=\lfloor\frac{M}{2}\rfloor, i\gt 1$

AC Code

#include <bits/stdc++.h>

void run() {
    long long n, m;
    std::cin >> n >> m;
    if (m % 2 == 0) std::cout << m / 2 * n << "\n";
    else std::cout << (m + 1) / 2 + (m - 1) / 2 * (n - 1) << "\n";
}

int main() {
    int t;
    std::cin >> t;
    while (t--) run();
}

C - Destruction of Walls

因为从左上到右下至少需要经过 $H+W-1$ 个格子，那么就需要至少开 $H+W-2$ 堵墙，所以当 $K\lt H+W-2$ 时答案为 $0$ 。

当 $K=H+W-2$ 的时候，刚好够左上到右下，因此开墙的方案数等于从左上到右下的路径数量。因为 $h$ 方向上要走 $H-1$ 步，而总共能走 $H+W-2$ 步，所以从 $H+W-2$ 里选出任意的 $H-1$ 步向右走就是方案数，此时答案为 $\binom{H+W-2}{H-1}$ .

当 $K=H+W-1$ 时，虽然能多开一堵墙，但是新开的这堵墙却不能形成任何新的路径，因此答案就是上一种情况下的每条路径再选另外的一堵墙开。选完路径后还剩 $H(W-1)+(H-1)W-(H+W-2)$ 堵墙可选，选一堵墙即可。答案为 $\binom{H+W-2}{H-1}\cdot \Big( H(W-1)+(H-1)W-(H+W-2) \Big)$

当 $K=H+W$ 时情况就变得有点复杂了。按照相同的思路，在剩下的墙里任选两堵墙，但是新开的两堵墙却有可能产生新的路径，从而导致重复/漏数. 可能重复的情况是“开墙后，有两条长度为 $H+W-1$ 的路径”，漏数的情况是“开墙后，产生一条长度为 $H+W+1$ 的路径”

有多少种情况会有两条长度为 $H+W-1$ 的路径呢？有两条路径，就说明在某个格子 $(i,j)$ ，从它出发有两条路径到达 $(i+1,j+1)$ ，而且恰好形成 $2\times 2$ 的区域。对于这个 $2\times 2$ 的区域来说，路径必须从 $(i,j)$ 的上方或左侧进入 $(i,j)$ ，也必须从 $(i+1,j+1)$ 的下方或右侧离开。所以，我们考虑先构造一条长度为 $H+W-3$ 的路径，然后，我们把这个路径上的一个格子换成这样的 $2\times 2$ 区域然后和剩下的部分接通，就能得到符合条件的、有两条长度为 $H+W-1$ 路径的方案了。由于要保证替换完的路径需要是 $H\times W$ 的对角线，而替换则相当于构造的路径在横向、纵向都多了一格，因此，需要保证构造的路径的横向格子数和纵向格子数为 $W-1,H-1$ ，相当于在 $(H-1)\times (W-1)$ 的网格里。这样的方案数是

\binom{H+W-4}{H-2}\cdot (H+W-3)

接着考虑漏数的情况。这种情况产生的路径可以这样看：考虑最短路径长度为 $H + W$ 的情况。在垂直或水平方向上仅一次远离 $(H,W)$ 的移动，且其前后的所有操作应该都是向右或向下。

考虑枚举远离目标的这一步，假设为向上，则其前后的一个操作必须都为水平（向右）。

前后的一步动作不能是向下，不然就说明从这个格子走回去/走回来了。

这个向上导致在它之后需要多出一个向下的动作，而向右的动作数量仍然不变，相当于现在需要在 $H+W$ 的位置上放置 $1$ 个向上、 $H$ 个向下、 $W-1$ 个向右，并且向上的动作后面至少要有 $1$ 个向下（不然会是从第 $H+1$ 行走到第 $H$ 行，不合法）、前面至少有一个向下（不然会从第 $1$ 行走到第 $0$ 行）、其前后一步都是向右。

所以考虑使用打包法，先把“向右、向上、向右”打包为 $X$ ，这样就是 $1$ 个 “X”、 $H$ 个向下、 $W-3$ 个向右放一起排列组合。我们先把 “X” 也看成向下，进行排列组合，然后再将第 $2\sim H$ 个向下换成 “X”（注意不能是第 $1$ 个和第 $H+1$ 个，原因见上一段）。所以方案数是

\binom{H+W-2}{H+1}\cdot(H-1)

当远离的那一步是向左的时候，也是同理，方案数是 $\binom{H+W-2}{W+1}\cdot(W-1)$

AC Code

#include <bits/stdc++.h>
using i64       = long long;
constexpr i64 P = 998244353;
constexpr int N = 2e5 + 10;

i64 fpow(i64 b, i64 p) {
    i64 res = 1;
    while (p) {
        if (p & 1) res = res * b % P;
        b = b * b % P;
        p >>= 1;
    }
    return res;
}

template <int M = P>
struct mint {
    int v;

    mint(i64 x = 0) : v{int((x % P + P) % P)} {}
    mint operator+(mint rhs) const { return v + rhs.v >= P ? v + rhs.v - P : v + rhs.v; }
    mint operator-(mint rhs) const { return v >= rhs.v ? v - rhs.v : v - rhs.v + P; }
    mint operator*(mint rhs) const { return 1ll * v * rhs.v % P; }
    mint operator/(mint rhs) const { return 1ll * v * fpow(rhs.v, P - 2) % P; }
    mint operator+=(mint rhs) { return *this = *this + rhs; }
    mint operator-=(mint rhs) { return *this = *this - rhs; }
    mint operator*=(mint rhs) { return *this = *this * rhs; }
    mint operator/=(mint rhs) { return *this = *this / rhs; }
    mint inv() const { return fpow(v, P - 2); }
    friend std::ostream &operator<<(std::ostream &os, mint rhs) { return os << rhs.v; }
};
using Z = mint<P>;

Z F[N * 2], iF[N * 2];
void init() {
    F[0] = 1;
    for (int i = 1; i < N * 2; i++) F[i] = F[i - 1] * i;
    iF[N * 2 - 1] = F[N * 2 - 1].inv();
    for (int i = N * 2 - 2; i >= 0; i--) iF[i] = iF[i + 1] * (i + 1);
}
Z C(i64 n, i64 m) {
    if (m < 0 || m > n) return 0;
    if (m == 1) return n;
    if (m == 2) return iF[2] * n * (n - 1);
    return F[n] * iF[m] * iF[n - m];
}
Z A(i64 n, i64 m) {
    if (m < 0 || m > n) return 0;
    return F[n] * iF[n - m];
}

void run() {
    i64 h, w, k;
    std::cin >> h >> w >> k;
    if (k < h + w - 2) return std::cout << 0 << "\n", void();

    i64 tot = (h - 1) * w + h * (w - 1), rest = tot - (h + w - 2);
    k -= (h + w - 2);

    if (k == 0) std::cout << C(h + w - 2, h - 1) << "\n";
    else if (k == 1) {
        std::cout << C(h + w - 2, h - 1) * rest << "\n";
    } else {
        mint path = C(h + w - 2, h - 1) * C(rest, 2);
        path -= C(h + w - 4, h - 2) * (h + w - 3);
        path += C(h + w - 2, h + 1) * (h - 1) + C(h + w - 2, w + 1) * (w - 1);
        std::cout << path << "\n";
    }
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);
#endif
    init();

    int t;
    std::cin >> t;
    while (t--) run();
}

D - Insert XOR

重要观察：

$B=(0,0)$ 可以生成全零序列
$B=(1,0)/(0,1)$ 可以生成的序列满足：
1. $A_1=1,A_m=0$ 或者 $A_1=0,A_m=1$
2. 中间不能出现连续的 $0$
$B=(1,1)$ 可以生成的序列满足
1. $A_1=1,A_m=1$
2. 中间不能出现连续的 $0$

所以我们观察到只要一段序列没有连续的 $0$ ，我们就可以把这段序列压缩成 $2$ 个数。这提示我们需要记录所有长度 $\ge 2$ 全 $0$ 的连续段才能计算答案。

先考虑怎么计算答案，对应代码里的 compute() 函数。这些全 $0$ 的连续段（记为 $S_i$ ）将整个序列划分成几个 minor segments，这几个 minor segment 根据定义一定至少包含 $1$ 个 $1$ . 所以，对于这些夹在 $S_i,S_{i+1}$ 之间的 minor segments，我们只需要要用 $1$ 个 $1$ ，表示这条线段；再用 $(0,0)$ 表示 $S_i$ 那么这些 minor segments 一定可以被 $(1,0)$ 或者 $(0,1)$ 生成出来。

接着考虑边界情况. 有可能在 $S_1$ 的左侧还有若干个数字连续段，那么这些数字连续段必然要么是连续的 $1$ ，要么是单个 $0$ . 我们只关心从前往后数第一个 $1$ 的左侧是否还有 $0$ 即可. 如果有的话，那么就说明必然是 $a_1=0,a_2=1$ ，就必须要 $b_1=0,b_2=1$ 才能表示出 $[a_2,S_1]$ 这一段；若没有，则必然 $a_1=1$ ，这个时候只需要令 $b_1=1$ 即可生成 $[a_1, S_1]$ 这段区间. 位于 $S_{last}$ 右侧的也是同理

一个特殊情况是，没有 $\ge 2$ 的全零连续段。根据我们刚刚分析的，序列必然是要么单个 $0$ ，要么是连续的 $1$ ，所以只要头尾不是 $0,0$ 就只需要两个数，否则需要三个数 $(0,1,0)$

另一个特殊情况是全 $1$ ，这个时候答案就是 $n$ .

接下考虑怎么维护这样的全 $0$ 连续段。我们可以开一个 std::map[l] = r：若 $a_i=0$ ，则尝试分裂区间；若 $a_i=1$ ，则需要考虑是不是需要和两侧的 $0$ 连续段合并起来。

时间复杂度 $O(n+q\log n)$

AC Code

#include <bits/stdc++.h>
#define sz(x) int(x.size())
constexpr int N = 2e5 + 10;

int n, q;
int a[N];
std::map<int, int> map; // [l, r]
int single{0};

int compute() {
    int ge2 = sz(map) - single;
    int ans = 0;

    if (ge2 > 0) {
        ans += 2 * ge2; // 0s to represent 00...00
        ans += ge2 - 1; // 1, to represent blocks between 2 len>=2 zero blocks.

        auto b = map.begin();
        if (a[1] == 0 && a[2] == 1) ans += 2; // extra 0, extra 1
        else if (b->first != 1) ans++;        // extra 1

        auto e = map.rbegin();
        if (a[n] == 0 && a[n - 1] == 1) ans += 2;
        else if (e->second != n) ans++;
    } else if (single > 0) { // must contain 1; a[1] and a[2] cannot both be 0.
        ans = 2;
        ans += (a[1] == 0 && a[n] == 0);
    } else ans = n; // all 1s

    return ans;
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);
#endif

    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> a[i];

    for (int i = 1, j; i <= n;) {
        j = i;
        while (j <= n && a[j] == a[i]) j++;
        if (a[i] == 0) {
            map[i] = j - 1;
            if (j - i == 1) single++;
        }
        i = j;
    }

    std::cin >> q;
    for (int idx; q; q--) {
        std::cin >> idx;
        // maintain
        if (a[idx] == 0) {
            auto it     = std::prev(map.upper_bound(idx));
            auto [l, r] = *it;

            if (l == r) map.erase(it), single--;
            else {
                if (l <= idx - 1) map[l] = idx - 1, single += (l == idx - 1);
                else map.erase(l);

                if (idx + 1 <= r) map[idx + 1] = r, single += (idx + 1 == r);
            }
        } else { // 1 -> 0
            auto it = map.lower_bound(idx);

            if (idx != 1 && a[idx - 1] == 0 && idx != n && a[idx + 1] == 0) {
                auto R  = map[idx + 1];
                auto it = std::prev(map.upper_bound(idx - 1));
                assert(it->second == idx - 1);
                map.erase(idx + 1);
                if (R == idx + 1) single--;
                if (it->first == idx - 1) single--;
                it->second = R;
            } else if (idx != 1 && a[idx - 1] == 0) { // merge to left
                auto it = std::prev(map.upper_bound(idx));
                if (it->second == it->first) single--;
                it->second = idx;
            } else if (idx != n && a[idx + 1] == 0) { // merge to right
                auto it = map.lower_bound(idx);
                assert(it->first == idx + 1);
                if (it->second == it->first) single--;
                auto R = it->second;
                map.erase(it);
                map.insert({idx, R});
            } else {
                map.insert({idx, idx});
                single++;
            }
        }

        a[idx] = 1 - a[idx];

        // compute
        std::cout << compute() << "\n";
    }
}

AtCoder Regular Contest 203 (Div. 2)

A - All Winners

B - Swap If Equal Sum

C - Destruction of Walls

D - Insert XOR