[WP] Codeforces Round 917 (Div. 2)

打喷3打到一半突然想起来cf好像有比赛，于是匆匆开始准备，还好赶上了

Account: CharmingLakesideJewel
Official Rank: 25
Performance: 2543
Rating Change: 1395 → 1819

Passed Tasks: A B D E

很可惜，C 写错了一点细节，最后 fst 了，导致没怎么涨分

A Least Product

如果起始的数中有 0，或者负数的个数为奇，那么不做任何操作是最好的

否则，让其中一个数变成 0 为最优

T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    have0 = 0 in a
    count_negative = sum([1 for i in a if i < 0])
    if count_negative % 2 == 1 or have0:
        print('0')
    else:
        print('1\n1 0')

B Erase First or Second Letter

可以发现，删到最后一定会留下原字符串的一个后缀以及（可选的）前面所有字符中的一个

假设留下的字符串长度为 $L$，那么必然留下长度为 $L-1$ 的后缀，以及前面字符中的一个。此时的情况数为前面字符中不同字符的个数

因此统计前面字符中有几个不同字符即可

T = int(input())
for _ in range(T):
    n = int(input())
    s = input()
    occur = set()
    ans = 0
    for i in range(n):
        occur.add(s[i])
        ans += len(occur)
    print(ans)

C Watering an Array

体感比 D 难想，但是比 D 好写

如果不考虑初始数组，那么不停的轮流执行操作 1 和操作 2 一定是最优的。原因：
执行完若干操作 1 后数组 a 的元素是不减的，同时数组 $b_i=i$ 的元素是单增的，因此最多有一个 $i$ 满足 $a_i=b_i$。即每个操作 2 最多有 1 的收益。
并且，考虑执行完一次操作 1 后，必有 $a_1=1$，即一定能获得这 $1$ 的收益。
得证

现在开始考虑初始数组。注意到，初始数组并不满足“执行完若干操作 1 后数组 a 的元素是不减的”的性质，因此确有可能产生更高的收益。
首先，如果基于初始数组执行了大于 $2n$ 次的操作 1，一定是不优的。这是因为，即使是初始数组，执行完操作 1 后操作 2 的收益仍然最高为 $n$，因此如果基于初始数组执行了大于 $2n$ 次的操作 1，那不如将这些操作 1 全部换成操作 1 和 操作 2 轮流进行。

因此我们的解法就确定了：枚举操作 1 的次数，维护当前状态，求得第一次操作 2 的收益，并将之后的操作全部设为操作 1 和 操作 2 轮流进行。取最大值即为答案。

时间复杂度 $O(n^2+k)$

const int N = 2e5 + 5, P = 998244353;

int T, n, k, d;
int a[N], v[N];

signed main() {
    kin >> T;
    while (T--) {
        kin >> n >> k >> d;
        for (int i = 1; i <= n; ++i) kin >> a[i];
        for (int i = 1; i <= k; ++i) kin >> v[i];
        int performDayMax = min(n * 2, d - 1);
        int equalZero = 0;
        for (int i = 1; i <= n; ++i) {
            a[i] -= i;
            if (a[i] == 0) equalZero++;
        }
        int ans = (d - 1) / 2 + equalZero;
        for (int passDay = 1; passDay <= performDayMax; ++passDay) {
            // Actual pass: passDay + 1
            int vi = v[(passDay - 1) % k + 1];
            for (int i = 1; i <= vi; ++i) {
                if (a[i] == 0) {
                    a[i] = 1;
                    --equalZero;
                } else if (a[i] < 0) {
                    if (++a[i] == 0) ++equalZero;
                }
            }
            int current = (d - passDay - 1) / 2 + equalZero;
            ans = max(ans, current);
        }
        kout << ans << '\n';
    }
    return 0;
}

fst：performDayMax 中的 n 写成了 k 了，k 比 n 小时会 WA

D Yet Another Inversions Problem

很好想，但是细节很多

首先，对于同一个 $p_i$，逆序对个数仅取决于 $\{q\}$ 的逆序对个数，此处贡献为 $n$ 乘以 $\{q\}$ 的逆序对个数

对于不同的 $p_i$，$\{q\}$ 的顺序已经无关了。

如果两个数 $p_{i_1}\cdot 2^{q_{j_1}}, p_{i_2}\cdot 2^{q_{j_2}}$ 是逆序对，那么有

$$\begin{aligned} p_{i_1}\cdot 2^{q_{j_1}} &> p_{i_2}\cdot 2^{q_{j_2}}\\ \frac{p_{i_1}}{p_{i_2}} &> \cdot 2^{q_{j_2}-q_{j_1}}\\ q_{j_2}-q_{j_1} &< \log_2\frac{p_{i_1}}{p_{i_2}} \end{aligned}$$

即具体的情况数只跟 $\log_2\frac{p_{i_1}}{p_{i_2}}$ 的整数部分有关。

考虑我们用树状数组求逆序对个数的过程。对该过程稍作修改，可以得到下面的算法：

• 对于每一个 $p_i$，求出其前面 $(\frac{p_i}{2},p_i), (\frac{p_i}{4},\frac{p_i}{2}), (\frac{p_i}{8},\frac{p_i}{4}), \dots$ 的数的个数，然后可以简单计算出每个区间因为 $\{q\}$ 产生的贡献
• 对于每一个 $p_i$，求出其前面 $(p_i,2p_i), (2p_i,4p_i), (4p_i,8p_i), \dots$ 的数的个数，然后可以简单计算出每个区间因为 $\{q\}$ 产生的贡献
• 将上述情况数和 $\{q\}$ 产生的贡献分别相乘，最后相加即为答案

const int N = 2e5 + 5, P = 998244353;

int T, n, k;

namespace nxd {
    int binarytr[N], _n;
    void init(int n) {
        _n = n;
        for (int i = 1; i <= n; ++i) binarytr[i] = 0;
    }
    void add(int u, int v) {
        for (; u <= _n; u += u & -u) binarytr[u] += v;
    }
    int query(int u) {
        int res = 0;
        for (; u; u -= u & -u) res += binarytr[u];
        return res;
    }
    int64 query(int n, int *a) {
        init(n);
        int64 res = 0;
        for (int i = n; i; --i) {
            res += query(a[i]);
            add(a[i] + 1, 1);
        }
        return res % P;
    }
}

namespace supernxd {
    int binarytr[N * 2], _n, _k;
    void init(int n, int k) {
        _n = n * 2;
        _k = k;
        for (int i = 1; i <= _n; ++i) binarytr[i] = 0;
    }
    void add(int u, int v) {
        for (; u <= _n; u += u & -u) binarytr[u] += v;
    }
    int query(int u) {
        int res = 0;
        for (; u; u -= u & -u) res += binarytr[u];
        return res;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
    int64 calc_offset(int64 offset) {
        if (offset < 0) {
            if (offset < -_k) return 0;
            return (_k + offset) * (_k + offset + 1) / 2 % P;
        } else {
            if (offset > _k) return (int64)_k * _k % P;
            return ((int64)_k * _k - (_k - offset) * (_k - offset + 1) / 2) % P;
        }
    }
    int64 query(int n, int k, int *a) {
        init(n, k);
        int64 res = 0;
        for (int i = 1; i <= n; ++i) {
            // lower part
            int rig = a[i], lef = rig / 2, step = -1;
            while (lef < rig) {
                int count = query(lef + 1, rig);
                res += calc_offset(step) * count % P;
                rig = lef;
                lef = lef / 2;
                --step;
            }
            // upper part
            rig = a[i] * 2, lef = a[i], step = 1;
            while (lef < _n) {
                int count = query(lef + 1, min(rig, _n));
                res += calc_offset(step) * count % P;
                lef = rig;
                rig = rig * 2;
                ++step;
            }
            // add
            add(a[i], 1);
        }
        return res % P;
    }

}


int p[N], q[N];

signed main() {
    kin >> T;
    while (T--) {
        kin >> n >> k;
        for (int i = 1; i <= n; ++i) kin >> p[i];
        for (int i = 1; i <= k; ++i) kin >> q[i];
        int64 ans = (nxd::query(k, q) * n + supernxd::query(n, k, p)) % P;
        kout << ans << '\n';
    }
    return 0;
}

E Construct Matrix

由于题目保证 $n$ 为整数，所以这道题变得十分简单（体感比 C D 简单）

下面给出我的一种构造方式：

首先，因为所有列的XOR的XOR显然为0（因为n为偶），因此所有数的XOR也为0，故 $k$ 不可能为奇数

如果 $k$ 是 4 的倍数，这种情况是比较简单的。易知一个 2x2 的全 1 矩阵可以在不破坏原矩阵的情况下被添加进去，那么我们不断添加这样的矩阵就可以了。

如果 $k\equiv 2\pmod 4$，
首先不妨假设 $k\le\frac{n^2}{2}$。如果不满足，令 $k'=n^2-k$，构造完再全部取反即可。
当 $k=2$ 是显然没有符合条件的矩阵的（手玩可知，特例是 n=2）
当 $k=6$ 时，我们可以构造出一个 3x3 的矩阵，如下：

1 1 0
1 0 1
0 1 1

当 $k \ge 6$ 时，考虑将上面这个矩阵放在前4行4列的位置，然后其他位置再通过添加 2x2 的全 1 矩阵来构造。

const int N = 1000 + 5;

int T, n, k;
bool mat[N][N];
int draw_first2block = 0;

void reset() {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            mat[i][j] = 0;
    draw_first2block = 0;
}

void draw6() {
    mat[1][1] = mat[1][2] = mat[2][1] = mat[2][3] = mat[3][2] = mat[3][3] = 1;
    draw_first2block = 1;
}

void add_block(int cnt) {
    int i = 1, j = 0;
    while (cnt) {
        if (++j > n / 2) {
            ++i;
            j = 1;
        }
        if (i <= 2 && j <= 2 && draw_first2block) continue;
        --cnt;
        mat[i * 2][j * 2] = mat[i * 2 - 1][j * 2] = mat[i * 2][j * 2 - 1] = mat[i * 2 - 1][j * 2 - 1] = 1;
    }
}

void reverse_mat() {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            mat[i][j] ^= 1;
}

signed main() {
    kin >> T;
    while (T--) {
        kin >> n >> k;
        if (n == 2 && k == 2) {
            kout << "Yes\n0 1\n1 0\n";
            continue;
        }
        bool success = false;
        if (k % 4 == 0) {
            success = true;
            reset();
            add_block(k / 4);
        } else {
            bool reversed = false;
            if (k * 2 > n * n) {
                reversed = true;
                k = n * n - k;
            }
            if (k % 4 == 2 && k != 2) {
                success = true;
                reset();
                draw6();
                add_block((k - 6) / 4);
                if (reversed) reverse_mat();
            }
        }
        if (success) {
            kout << "Yes\n";
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j)
                    kout << (mat[i][j] ? '1' : '0') << " \n"[j == n];
            }
        } else kout << "No\n";
    }
    return 0;
}

后记

这是我打开 cf 前的一场喷3结算画面：

喷喷喷的碰拳真的很可爱！

超级喜欢！

而且这一场大家的结算动作还恰好都是一样的！

---

如果没有 fst：

Official Rank: 17
Performance: 2640

很神奇，fst了但是没有Perf.没有少很多

---

codeforces.profile: CharmingLakesideJewel

关于代码模板：C++ 的代码都略去了代码模板，只保留了核心代码。代码模板即通常的快读快输，kin, kout 可以理解为 cin, cout 的快读快输版本