跳转至

CF2097

alt text

CF2097A Sports Betting

可以进行手玩，首先观察到如果在同一个地方有 \(4\) 个 \(a_i\)，那么一定有解。

然后又观察到 22 和 212 也是有解的，发现可以推广到 211..1112 的情况。别的没了

CF2097B Baggage Claim

给定一个网格图，定义传送带是网格图上的一条四联通简单路径。现在给定一条长度为奇数的传送带删掉偶数位置剩下的点的位置（顺序也给定），问原来的传送带有多少种可能。

\(n,m\le 1000\)

首先给定的序列 \(p\) 必须满足相邻的点的曼哈顿距离恰好为 \(2\) 否则无解。对于向同一个方向移动两格的情况，它们中间的那个格子会被占用；对于向斜方向移动的情况，对角的两个格子中有一个会被占用。

为了刻画“两个格子会有一个被占用”，我们考虑将两个格子连边建出一个无向图。答案即转化为统计给无向图定向，且每个点入度不超过 \(1\) 的方案数。

注意到一条边会贡献 \(1\) 的度数，因此同一连通块内边的数量 \(m\) 不能超过点的数量 \(n\)。此时，若图是一棵树，那么任选一个点出发都能得到一种方案，贡献等于连通块大小；若图是一个基环树，那么必须从环上出发，发现环有两种方案，下面的树都只有一种方案，贡献为 \(2\)。

CF2097C Bermuda Triangle

给定一个平面直角坐标系，其上有一个等腰直角三角形，三个顶点分别是 \((0,0),(0,n),(n,0)\)（\(n\) 是给定的正整数）。

你初始位于 \(x,y\)（\(2\le x+y< n\)，\(x,y\) 都是正整数），你有速度矢量 \((v_x,v_y)\)（也都是正整数）。当碰到三角形的边时，你会发生镜面反射；当你碰到顶点，你就成功逃离了。问你能否成功逃离，以及需要反射多少次。

考虑经典 Trick：将三角形不断沿三条边对称，最终覆盖整个平面，所有横纵坐标都是 \(n\) 整数倍的点都是出口。

现在判断你能否走出是容易的：先把速度矢量约分变成互质，然后你走到出口的时间一定是整数，因此列两个同余式然后再跑 excrt 合并即可。

至于反射次数，发现三角形的边在折叠后形如一些直线。直线分为：横着的，竖着的，\(45\degree\) 的，\(135\degree\) 的。分别计算四种直线的贡献即可。

代码 
 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// 感受绝望吧
// 一整页代码没有一个数组和循环
#include<iostream>
#include<cassert>
#include<cmath>
#define ld long double
#define int long long
using namespace std;

int T;
int n, bx, by, vx, vy;

int gcd(int a, int b) {
    if(a < b) swap(a, b);
    if(!b) return a;
    return gcd(b, a % b);
}

int exgcd(int a, int b, int &x, int &y) {
    if(a < b) { return exgcd(b, a, y, x); }
    if(!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    assert(a * x + b * y == d);
    return d;
}

int fl(int a, int b) {
    if(a < 0) return (a - b + 1) / b;
    return a / b;
}

int ce(int a, int b) {
    if(a < 0) return a / b;
    return (a + b - 1) / b;
}

signed main() {

    cin >> T;
    while(T--) {
        cin >> n >> bx >> by >> vx >> vy;
        int d = gcd(vx, vy);
        vx /= d, vy /= d;
        int x, y;
        int r1, p1, r2, p2;
        d = exgcd(vx, n, x, y);
        if(bx % d) { cout << "-1\n"; continue; }
        r1 = -x * (bx / d);
        p1 = n / d;
        r1 = (r1 % p1 + p1) % p1;
        d = exgcd(vy, n, x, y);
        if(by % d) { cout << "-1\n"; continue; }
        r2 = -x * (by / d);
        p2 = n / d;
        r2 = (r2 % p2 + p2) % p2;
        int b = r2 - r1;
        d = exgcd(p1, p2, x, y);
        if(b % d) { cout << "-1\n"; continue; }
        int p = p1 * p2 / d;
        x = (__int128)x * (b / d) % p;
        int res = (((__int128)x * p1 + r1) % p + p) % p;
        int ex = bx + res * vx, ey = by + res * vy;
        int ans = (res * abs(vx) / n) + (res * abs(vy) / n);
        int b1 = bx + by - n, b2 = ex + ey - n;
        if(b1 > b2) ++b2, swap(b1, b2);
        else --b2;
        ans += fl(b2, 2 * n) - ce(b1, 2 * n) + 1;
        b1 = bx - by - n, b2 = ex - ey - n;
        if(b1 > b2) ++b2, swap(b1, b2);
        else --b2;
        ans += fl(b2, 2 * n) - ce(b1, 2 * n) + 1;
        cout << ans << '\n';
    }

    return 0;
}

CF2097D Homework

给定两个长为 \(n\)（\(n\) 是偶数）的 01 串 \(s,t\)，你可以对 \(s\) 进行任意次如下操作：

  • 先把 \(s\) 划分为长度相等的两端 \(x,y\)；
  • 你可以选择执行 \(x_i\gets x_i\oplus y_i\)；
  • 你可以选择执行 \(y_i\gets x_i\oplus y_i\)；
  • 你可以选择对 \(x\) 或者 \(y\) 递归进行操作（包括继续递归）；

问能否使 \(s\) 变成 \(t\)。

\(n\le 10^6\)

不妨将 \(n\) 表示为 \(n=k\times m\)，其中 \(k\) 是 \(2\) 的整数次幂，\(m\) 是一个奇数。将序列平分成 \(k\) 段，不难发现每段内部的元素是相互独立的。

发现一次操作会连着好几段一起改，这显然不是我们想要的，我们希望任选两小段 \(x,y\) 都可以执行 \(y\gets x\oplus y\) 而不影响其他段。考虑能否构造这一点。发现只需对 \(2^k\) 构造出：\(s_{i+2^k}\gets s_{i+s^k}\oplus s_i\) 操作即可：

\[ \begin{bmatrix} s_{0,0}\\s_{0,1}\\s_{0,2}\\s_{0,3}\\s_{1,0}\\s_{1,1}\\s_{1,2}\\s_{1,3}\\ \end{bmatrix} \to \begin{bmatrix} s_{0,0}\\s_{0,1}\\\textcolor{orange}{s_{0,3}}\\\textcolor{orange}{s_{0,2}}\\s_{1,0}\\s_{1,1}\\s_{1,2}\\s_{1,3}\\ \end{bmatrix} \to \begin{bmatrix} s_{0,0}\\s_{0,1}\\\textcolor{orange}{s_{0,3}\oplus s_{0,2}}\\s_{0,2}\\s_{1,0}\\s_{1,1}\\s_{1,2}\\s_{1,3}\\ \end{bmatrix} \to \begin{bmatrix} s_{0,0}\\s_{0,1}\\s_{0,3}\oplus s_{0,2}\\s_{0,2}\\\textcolor{orange}{s_{1,0}\oplus s_{0,0}}\\\textcolor{orange}{s_{1,1}\oplus s_{0,1}}\\\textcolor{orange}{s_{1,2}\oplus s_{0,3}\oplus s_{0,2}}\\\textcolor{orange}{s_{1,3}\oplus s_{0,2}}\\ \end{bmatrix} \to\\~\\ \begin{bmatrix} s_{0,0}\\s_{0,1}\\\textcolor{orange}{s_{0,3}}\\\textcolor{orange}{s_{0,2}}\\s_{1,0}\oplus s_{0,0}\\s_{1,1}\oplus s_{0,1}\\s_{1,2}\oplus s_{0,3}\oplus s_{0,2}\\s_{1,3}\oplus s_{0,2}\\ \end{bmatrix} \to \begin{bmatrix} s_{0,0}\\s_{0,1}\\s_{0,3}\\s_{0,2}\\\textcolor{orange}{s_{1,0}}\\\textcolor{orange}{s_{1,1}}\\\textcolor{orange}{s_{1,2}\oplus s_{0,2}}\\\textcolor{orange}{s_{1,3}}\\ \end{bmatrix} \to \begin{bmatrix} s_{0,0}\\s_{0,1}\\\textcolor{orange}{s_{0,2}}\\\textcolor{orange}{s_{0,3}}\\{s_{1,0}}\\{s_{1,1}}\\{s_{1,2}\oplus s_{0,2}}\\{s_{1,3}}\\ \end{bmatrix} \]

就是两次异或，前半段的对应位置相差一个 \(s_{0,2}\)，就可以将其异或到后半段。

据此，我们可以对任意的两段进行异或、交换。将序列填到矩阵里，每一段是一行，能够得到一个 \(k\times m\) 的矩阵。现在题目操作等价于这个矩阵的初等行变换。

要判定一个矩阵能否通过初等行变换得到另一个矩阵，可以比较两个矩阵高消之后的结果是否相同，因为一个等价类内的矩阵高消之后的结果是相同的。

那么 \(10^6\) 如何跑高消呢？注意到高消的复杂度是 \(O\big(nm\min(n,m)\big)\)，不超过 \(O(nm\sqrt{nm})\)，因此可以通过本题。直接在原数组上高消即可实现线性空间。如果要用 bitset 优化就必须手写 bitset，否则空间 \(O(n\sqrt n)\) 过不了。

代码 
 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<bitset>
#include<vector>
using namespace std;
const int N = 1e6 + 10;

int T, n;
int k, m;
int s[N], t[N];

void gauss(int a[]) {
    int cur = 0;
    for(int i = 0; i < m; i++) {
        int mx = -1;
        for(int j = cur; j < k; j++) {
            if(a[j * m + i]) { mx = j; break; }
        }
        if(mx == -1) continue;
        for(int j = i; j < m; j++) swap(a[cur * m + j], a[mx * m + j]);
        for(int j = 0; j < k; j++) {
            if(j == cur) continue;
            if(a[j * m + i]) for(int k = i; k < m; k++) a[j * m + k] ^= a[cur * m + k];
        }
        ++cur;
    }
}

void work() {
    k = n & -n;
    m = n / k;
    gauss(s);
    gauss(t);
    bool flag = true;
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < m; j++) {
            if(s[i * m + j] != t[i * m + j]) { flag = false; break; }
        }
    }
    cout << (flag ? "Yes\n" : "No\n");
}

int main() {

    cin >> T;
    while(T--) {
        cin >> n;
        for(int i = 0; i < n; i++) {
            char c;
            cin >> c;
            s[i] = c == '1';
        }
        for(int i = 0; i < n; i++) {
            char c;
            cin >> c;
            t[i] = c == '1';
        }
        work();
    }

    return 0;
}

CF2097E Clearing the Snowdrift

注意到最优策略形如用一堆区间盖住序列上的所有最大值，然后最大值减 \(1\)，还可能有新的最大值加入。每次覆盖都是一次线段覆盖的贪心（每次找到最左边没被覆盖的点，然后左端点卡着它覆盖即可）。离散化之后容易做到 \(O(n^2)\)。

考虑优化，注意到 \(n\) 次贪心是离线的，因此可以一起跑。记录 \(n\) 个指针 \(p_1,p_2,\cdots p_n\) 表示第 \(i\) 个贪心已经覆盖到了 \(p_i\) 位置（称第 \(i\) 次贪心表示最大值为 \(i\) 时的那次贪心）。考虑从左往右扫描序列，设当前扫到第 \(i\) 个数字，那么对于所有 \(j\le a_i\) 且 \(p_j\le i\) 的 \(j\)，执行 \(p_j\gets i+d\) 并计算对应代价。

代码中，我们可以维护一个集合 \(S\) 表示 \(p_j\le i\) 的全体 \(j\)。每扫到一个数字，就把集合中 \(\le a_i\) 的数字都拿出来扔到 \(i+d\) 位置。这里可以用 FHQ Treap 维护（据说可以分析到单 \(\log\) 但是我没看懂），也可以用线段树分裂&合并维护（单 \(\log\)，但我不会）。