2024 CCPC 郑州 BCFLM

B - Rolling Stones（BFS）

折一个四面体，实际操作后发现，底面相同时，三个侧面的数字是确定的，因此每个位置只可能走过一次。BFS 即可。时间复杂度 $\Theta(n^{2})$。

#include <bits/stdc++.h>
using namespace std;

const int dx[2][3] = {
    { 0, 0, -1 },
    { 0, 0, 1 },
};
const int dy[2][3] = {
    { -1, 1, -1 },
    { -1, 1, 1 },
};
const int to[2][5][3] = {{
     {},
     { 2, 4, 3 },
     { 1, 3, 4 },
     { 4, 2, 1 },
     { 3, 1, 2 }
}, {
     {},
     { 4, 2, 3 },
     { 3, 1, 4 },
     { 2, 4, 1 },
     { 1, 3, 2 }
}};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;
    vector mp(n + 2, vector<int>(2 * n + 3));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 2 * i - 1; j++) {
            cin >> mp[i][j];
        }
    }

    queue<pair<int, int>> Q;
    Q.push({ 1, 1 });
    vector dis(n + 2, vector<int>(2 * n + 3, -1));
    dis[1][1] = 0;

    while (!Q.empty()) {
        auto [x, y] = Q.front(); Q.pop();
        bool op = y & 1;
        for (int i = 0; i < 3; i++) {
            int nx = x + dx[op][i], ny = y + dy[op][i];
            if (mp[nx][ny] == 0) continue;
            if (dis[nx][ny] != -1) continue;
            if (mp[nx][ny] == to[op][mp[x][y]][i]) {
                dis[nx][ny] = dis[x][y] + 1;
                Q.push({ nx, ny });
            }
        }
    }

    int x, y;
    cin >> x >> y;
    cout << dis[x][y] << endl;

    return 0;
}

C - Middle Point（模拟）

有解条件是 $\cfrac{x}{a}, \cfrac{y}{b}$ 约分后分母是二的幂次（需提前特判范围是一条线或一个点的情形，即 $a,b$ 可能为 $0$），最优操作次数是 $\log$。

正着不好做，但发现如果倒推答案就是唯一的。

（正确性：每倒推一步，$\cfrac{x}{a}, \cfrac{y}{b}$ 的分母上二的幂次就会少一，最终分母一定为 $1$，即回到了四个端点，且可以保证操作次数）

#include <bits/stdc++.h>
using namespace std;

// 判断正整数是不是二的幂
bool check(int x) {
    assert(x > 0);
    return (1ll << __lg(x)) == x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int a, b, x, y;
    cin >> a >> b >> x >> y;
    a = max(1, a);
    b = max(1, b);  // 避免d=0除零错误
    
    int d1 = gcd(a, x), d2 = gcd(b, y);
    if (check(a / d1) && check(b / d2)) {
        vector<array<int, 4>> res;
        while ((x != a && x != 0) || (y != b && y != 0)) {
            int nx = (x * 2 < a) ? 0 : a;
            int ny = (y * 2 < b) ? 0 : b;
            x = 2 * x - nx;
            y = 2 * y - ny;
            res.push_back({ x, y, nx, ny });
        }
        cout << res.size() << endl;
        for (auto [x1, y1, x2, y2] : vector(res.rbegin(), res.rend())) {
            cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
        }
    } else {
        cout << -1 << endl;
    }

    return 0;
}

F - Infinite Loop（简单数学）

只有两种情形，一种是第二天某个任务的开始时间和第一天相同，这样从这个任务开始，就会重复前一天的状态，是个循环；另一种是第二天和第一天任务开始时间完全不同，这样任务就会无限期拖延，且每天的拖延时间是相同的。两种都不难计算。

时间复杂度 $\Theta(n+q)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n, k, q;
    cin >> n >> k >> q;

    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }

    ll now = 0;
    vector<ll> a1(n), a2(n);
    for (int i = 0; i < n; i++) {
        now = a1[i] = max(now, a[i]);
        now += b[i];
    }

    bool flag = 1;  // all diff
    for (int i = 0; i < n; i++) {
        now = a2[i] = max(now, a[i] + k);
        now += b[i];
        if (a2[i] == a1[i] + k) {
            flag = 0;
        }
    }
    ll delta = a2.back() - a1.back();
 
    while (q--) {
        int x, i;
        cin >> x >> i;
        i--;

        ll res;
        if (x == 1) {
            res = a1[i] + b[i] - 1;
        } else {
            res = a2[i] + b[i] - 1;
            if (flag) {  // all diff
                res += (x - 2ll) * delta;
            } else {
                res += (x - 2ll) * k;
            }
        }

        ll d = res / k, h = res % k;
        if (h == 0) {
            h = k;
            d--;
        }
        cout << (++d) << " " << h << endl;
    }

    return 0;
}

L - Z-order Curve（签到）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        ll a, b;
        cin >> a >> b;
        ll x = 1;
        while (x <<= 1) {
            if (a / x == b / x) {
                cout << a % x << endl;
                break;
            }
        }
    }
    
    return 0;
}

和抽奖再来一次一个道理，可以认为选出的数在集合中没有出现过，选出 $k$ 个下标 $S=\lbrace s{1},s{2},\dots ,s{k} \rbrace$ 的概率为 $\alpha \prod\limits{i\in S} p{i}\prod\limits{i\notin S}(1-p{i})$，这个概率与权重 $\prod\limits{i\in S} a{i}$ 成正比，因此存在常数 $C$，满足 $p{i}=\cfrac{a{i}}{a{i}+C}$，结合题给的限制，得到

$\sum_{i=1}^{n}\frac{a_{i}}{a_{i}+C}=k.$

这个式子是关于 $C$ 的一个 $n$ 次多项式，不能直接求得。而左式关于 $C$ 是单调的，可以二分 $C$。

时间复杂度 $\Theta(n\log V)$。

特别注意，浮点数二分在 $l$ 和 $r$ 很大时，用 $r-l>\operatorname{eps}$ 是不可取的，因为小数部分的精度已经丢失，绝对差不可求。先给出 TLE 代码：

#include <bits/stdc++.h>
using namespace std;
using d64 = long double;
constexpr d64 eps = 1e-18;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cout << fixed << setprecision(12);

    int n;
    cin >> n;

    d64 k;
    cin >> k;

    vector<d64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    auto cal = [&](d64 c) {
        vector<d64> p(n);
        for (int i = 0; i < n; i++) {
            p[i] = a[i] / (a[i] + c);
        }
        return p;
    };

    auto check = [&](d64 mid) {
        auto p = cal(mid);
        return accumulate(p.begin(), p.end(), 0.0l) < k;
    };

    d64 l = 0, r = 1e15;
    while (r - l > eps) {
        d64 mid = (l + r) / 2;
        if (!check(mid)) l = mid;
        else r = mid;
    }

    auto p = cal(l);
    for (int i = 0; i < n; i++) {
        cout << p[i] << endl;
    }

    return 0;
}

有三种修改方案：

判断 $l$ 和 $r$ 的相对差：即判断 $\cfrac{r-l}{l}$ 是否在误差范围内；

#include <bits/stdc++.h>
using namespace std;
using d64 = long double;
constexpr d64 eps = 1e-18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cout << fixed << setprecision(12);

    int n;
    cin >> n;

    d64 k;
    cin >> k;

    vector<d64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    auto cal = [&](d64 c) {
        vector<d64> p(n);
        for (int i = 0; i < n; i++) {
            p[i] = a[i] / (a[i] + c);
        }
        return p;
    };

    auto check = [&](d64 mid) {
        auto p = cal(mid);
        return accumulate(p.begin(), p.end(), 0.0l) < k;
    };

    d64 l = 0, r = 1e15;
    while ((r - l) / l > eps) {
        d64 mid = (l + r) / 2;
        if (!check(mid)) l = mid;
        else r = mid;
    }

    auto p = cal(l);
    for (int i = 0; i < n; i++) {
        cout << p[i] << endl;
    }

    return 0;
}

控制二分次数：$V=10^{18}\cdot 10^{15}=10^{23}$，$\log_{2} V=76$，因此二分 $100$ 次足够。

#include <bits/stdc++.h>
using namespace std;
using d64 = long double;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cout << fixed << setprecision(12);

    int n;
    cin >> n;

    d64 k;
    cin >> k;

    vector<d64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    auto cal = [&](d64 c) {
        vector<d64> p(n);
        for (int i = 0; i < n; i++) {
            p[i] = a[i] / (a[i] + c);
        }
        return p;
    };

    auto check = [&](d64 mid) {
        auto p = cal(mid);
        return accumulate(p.begin(), p.end(), 0.0l) < k;
    };

    d64 l = 0, r = 1e15;
    for (int t = 0; t < 100; t++) {
        d64 mid = (l + r) / 2;
        if (!check(mid)) l = mid;
        else r = mid;
    }

    auto p = cal(l);
    for (int i = 0; i < n; i++) {
        cout << p[i] << endl;
    }

    return 0;
}

二分一个在 $[0,1]$ 之间的数，对于本题，可以二分 $p_{1}$。

#include <bits/stdc++.h>
using namespace std;
using d64 = long double;
constexpr d64 eps = 1e-18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    cout << fixed << setprecision(12);

    int n;
    cin >> n;

    d64 k;
    cin >> k;

    vector<d64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    auto cal = [&](d64 p0) {
        vector<d64> p(n);
        p[0] = p0;
        d64 c = a[0] / p[0] - a[0];
        for (int i = 1; i < n; i++) {
            p[i] = a[i] / (a[i] + c);
        }
        return p;
    };

    auto check = [&](d64 mid) {
        auto p = cal(mid);
        return accumulate(p.begin(), p.end(), 0.0l) < k;
    };

    d64 l = 0, r = 1;
    while (r - l > eps) {
        d64 mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    auto p = cal(l);
    for (int i = 0; i < n; i++) {
        cout << p[i] << endl;
    }

    return 0;
}

B - Rolling Stones（BFS）

C - Middle Point（模拟）

F - Infinite Loop（简单数学）

L - Z-order Curve（签到）

M - Rejection Sampling（二分）