跳转至

251110 模拟赛

模板题 原题 水题 裸题

T1

模板 离线可过 动态图连通性

T2

双序列扩展

考虑 \(01\) 矩阵 \(A_{i,j}=[S_i\ge S_j]\)，发现行之间一定具有包含关系。考虑什么时候起点和终点不连通：一整行不通，一整列不通，一条路径把起点包起来了，一条路径把终点包起来了。根据上面的性质可知：选一些行，进行按位或，得到的值一定也在这些行中的一个。因此后两种情况的路径一定形如 L 形。

对第一列的每个位置维护最长障碍物连续段，其他四个方向同理，用前后缀 \(\min,\max\) 加二分即可。总之四种情况都是容易的。

T3

下文用 ABC 代替剪刀石头布。注意到一棵子树出 ABC 的方案数是相等的，因此空子树和满子树的贡献都是非常简单的。把 \(L\) 和 \(R\) 在树上跳一遍就行，是 \(O(n)\) 的。难点在于二进制拆分，手写 bitset 实现乘 \(10\) 和加 \(0\sim 9\)，时间复杂度 \(O(\frac{n^2}{\omega})\)。

记得判 \(L=R\)，没判挂 50pts。

手写 bitset 
 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
ull tmp1[M], tmp2[M];

struct bitset {
    ull data[M];
    inline bitset() { for(u32 i = 0; i < M; i++) data[i] = 0; }
    inline void mul10() {
        for(int i = M - 2; i >= 0; i--) {
            tmp1[i] = data[i] << 1;
            tmp1[i + 1] |= data[i] >> 63;
        }
        for(int i = M - 2; i >= 0; i--) {
            tmp2[i] = data[i] << 3;
            tmp2[i + 1] |= data[i] >> 61;
        }
        for(int i = 0, c = 0; i < M - 1; i++) {
            data[i] = tmp1[i] + tmp2[i] + c;
            c = data[i] < tmp1[i] || data[i] < tmp2[i];
        }
    }
    inline void add(ull x) {
        for(ull i = 0, c = x; i < M - 1; i++) {
            data[i] += c;
            c = data[i] < c;
        }
    }
    inline void m1() {
        for(ull i = 0, c = 0; i < M - 1 && !c; i++) {
            c |= (data[i] != 0), data[i]--;
        }
    }
    inline bool test(u32 i) { return (data[i >> 6] >> (i & 63)) & 1; }
};

T4

直接根号分治即可，时间复杂度 \(O(n\sqrt n\log n)\)。\(12\) 秒什么算法过不去。实测不超过三秒。