跳转至

ATC & CF 选做(23Sep,23Oct)

CodeTon Round 6 (CF1870)ψ(｀∇´)ψ

战报是拿到了 4 个 TON，应该有七八十块钱的样子。

看来早饭钱和之后出勤的钱又有了。

有惊无险的重回 CM，之后比赛出出来的时候也不至于那么尴尬。

题面暂略。

Aψ(｀∇´)ψ

就考虑先凑出 MEX，然后不断顶着上界放就行。

唯一要判的就是上界为 MEX 的情况。

然后无解条件是显然的。

Bψ(｀∇´)ψ

考虑到一个事情，直接按部就班的执行题中的操作显然是不行的。

我们冷静思考，发现他是对所有的 \(a_{i}\) 都按位或上 \(b_{j}\)。

于是我们可以对 \(xs = \bigoplus a_{i}\) 考虑 \(b_{j}\) 的影响。

注意到异或实际上只关心当前位 \(1\) 的个数，而每次对于 \(b_{j}\) 中的某一个非零位，它会让所有 \(a_{i}\) 的对应位变成 \(1\)。

那么 \(b_{j}\) 的影响就是和 \(n\) 的奇偶性相关的，如果 \(n\) 为奇数，那么 \(b_{j}\) 的每次操作可以让答案不变小，所以全部丢上去就行，这就是最大值，最小值显然是不操作。

\(n\) 为偶数的情形是反过来的。

Cψ(｀∇´)ψ

显然矩形的大小是单调的，随便双指针扫一下就行了。

Dψ(｀∇´)ψ

贪心的考虑，显然我们希望在次数相同的情况下让前面更大，前面相同的情况下尽量选靠后的。

于是维护一下后缀最小值，贪一下就可以了。

Eψ(｀∇´)ψ

怎么感觉这题很 OI Style。

首先一个简单的 \(O(n^3)\) 的 dp 应该不难想到。

考虑 \(dp(i, j)\) 表示前 \(i\) 个位置中，是否能找到一种划分方案使得这些子数组的 MEX 的异或和为 \(j\)。

考虑转移，就是枚举 \(i, j\)，然后枚举上一个分段的位置计算一下 MEX，这里钦定转移的时候只考虑结尾为 \(i\) 的，其它的情况可以继承之前的状态。

然后我们有一个很 OI 的想法，我们发现复杂度 \(O(n^2)\) 才能过，我们考虑有没有什么性质。

大胆猜测内层有用的区间只有 \(O(n)\) 个，可以发现我们决策的过程实际上是固定右端点 \(i\) 枚举左端点 \(k\)。

可以发现每个位置可能会更新多个 MEX，我们考虑对于每个左端点，每个 MEX 只更新一次，并且只在 MEX 变化的时候更新。

感觉上来说 MEX 的数量级应该在 \(O(n)\) 个，然后这个好像就是 \(O(n^2)\) 的，我们把他拿来和暴力对拍一下，于是就过了。

Fψ(｀∇´)ψ

可能是我题做少了，愤怒，我咋想不到这个！！

首先全部写成 \(k\) 进制，考虑插入进一颗 trie 树。

那么一个节点的 dfs 序就是它的字典序排名，bfs 序就是原排名。

记 dfs 序为 \(dfn(x)\)，bfs 序同理为 \(bfn(x)\)。

那么要找到的就是 \(dfn(x) = bfn(x)\) 的 \(x\) 的个数，可以注意到同一层内 \(bfn\) 的变化一定是从左往右增加，\(dfn\) 的变化也是同理。

并且可以发现 \(dfn\) 的变化速率不小于 \(bfn\)，于是 \(dfn(x) - bfn(x)\) 按层单调递增。

于是可以二分每层有多少个 \(0\)，\(bfn\) 是好计算的，\(dfn\) 需要做一个数位 dp。

可以发现树高是 \(\log\) 的，于是这题就做完了。

Atcoderψ(｀∇´)ψ

ABC321F - #(subset sum = K) with Add and Eraseψ(｀∇´)ψ

这东西怎么看怎么背包啊，看起来就很 NPC 的样子。

那咋 \(O(QK)\) 做？？？

感觉可能就是，先对已有的做一个 dp，然后考虑每次修改对 dp 的影响。

但是这样还是 \(O(Q^2K)\) 的。

不过冷静一下，注意到我们并不需要对已有的做 dp，因为这里是一个一个加入，所以，

我们直接设 \(dp(i)\) 表示凑出 \(i\) 的方案数，转移则是每次加入/删除的时候考虑更新影响。

复杂度就是 \(O(QK)\) 了，需要稍微注意一下顺序。

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// author : black_trees
// want more regrets?

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 5e3 + 10;
const int mod = 998244353;

int n, k;
int dp[si];

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    dp[0] = 1;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        char op; int x;
        cin >> op >> x;

        if(op == '+') {
            for(int i = k; i >= x ; --i) {
                (dp[i] += dp[i - x]) %= mod;
            }
        }
        else {
            for(int i = x; i <= k; ++i) {
                (dp[i] += (mod - dp[i - x])) %= mod;
            }
        }

        cout << dp[k] << endl;
    }

    return 0;
}
最后更新: October 12, 2023