2024 CCPC 郑州补题记录 (8 题 BCDEFGIJ)

CGAK 都是好题，尤其喜欢 C

The 3rd Universal Cup. Stage 22: Zhengzhou - Dashboard - Contest - QOJ.ac
https://codeforces.com/gym/543949/
https://codeforces.com/gym/105632

题目分区：LBFM / C / GK / AJDIEH
牌线：4 题快 / 5 题快 / 6 题快

A. A + B = C Problem（构造）【Hard】

给定三个正整数$p_{A},p_{B},p_{C}$，构造三个无穷长 01 串$A,B,C$，满足周期分别为$p_{A},p_{B},p_{C}$，且$A\oplus B=C$。$10^{6}$。

拿到这题的第一反应是设$p_{A} = dpq,\ p_{B} = dpr,\ p_{C} = dqr$，然后发现样例 2 并不能设为这种形式，就猜测不能表示便无解。（附：正确的设法是$p_{A} = dpqa,\ p_{B} = dprb,\ p_{C} = dqrc$）

事实上，有解的必要条件是

$$\begin{cases} p_{C} \mid \operatorname{lcm}(p_{A},p_{B}) \\ p_{A} \mid \operatorname{lcm}(p_{B},p_{C}) \\ p_{B} \mid \operatorname{lcm}(p_{C},p_{A}) \\ \end{cases} \iff p_{A} = dpq,\ p_{B} = dpr,\ p_{C} = dqr$$

简要证明如下：考虑$S = A\oplus B$，它的一个周期是$p_{S} = \operatorname{lcm}(p_{A},p_{B})$。题目要求$C=S$。也就是说已知一个串以$p_{S}$ 作为周期，那么最小周期$p_{C}$ 需要满足什么条件？显然是$p_{C} \mid p_{S}$，即$p_{C} \mid \operatorname{lcm}(p_{A},p_{B})$。

至于是否充分，我们只要能构造出来就是充分的。

首先判掉一些平凡的情形。

• 如果三个相等$p_{A}=p_{B}=p_{C}$：

  • If$p_{A}>2$，例如 (5, 5, 5) 构造 10000, 01000, 11000；
  • If$p_{A}=1$，全 0 或者 1, 1, 0；
  • If$p_{A}=2$，手玩枚举一下所有情形（其实就 1 种 10, 01），无解。

以下不妨设$d = \gcd(p_{A},p_{B},p_{C}) = 1$，否则构造之后在相邻两个数之间插$d-1$ 个 0。

• 如果存在恰好两个相等，不妨$p_{A}=p_{B}$，因为已经设$d = \gcd(p_{A},p_{B},p_{C}) = 1$，所以$p_{C}=1$。例如 (4, 4, 1) 构造 1000, 0111, 1。

• 剩下就是互不相同，设$p_{A} = pq,\ p_{B} = pr,\ p_{C} = qr$，其中$p \neq q \neq r$。分别构造周期为$p,q,r$ 的串，两两异或起来就好了。比如 (6, 10, 15)，先构造周期为 2,3,5 的 10, 100, 10000，异或之后得到$10'10'10\oplus 100'100=001110$，$10'10'10'10'10\oplus 10000'10000$，$100'100'100'100'100\oplus 10000'10000'10000$。

QED.

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

using ll = long long;
using ull = unsigned long long;
using ulll = unsigned __int128;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int pA, pB, pC;
        cin >> pA >> pB >> pC;

        if (lcm(pA, pB) % pC || lcm(pA, pC) % pB || lcm(pB, pC) % pA) {
            cout << "NO" << endl;
        } else if (pA == pB && pB == pC) {
            if (pA == 2) {
                cout << "NO" << endl;
            } else if (pA == 1) {
                cout << "YES" << endl;
                cout << 1 << endl;
                cout << 1 << endl;
                cout << 0 << endl;
            } else {
                cout << "YES" << endl;
                cout << "10" << string(pA - 2, '0') << endl;
                cout << "01" << string(pA - 2, '0') << endl;
                cout << "11" << string(pA - 2, '0') << endl;
            }
        } else {
            int d = gcd(gcd(pA, pB), pC);
            string a, b, c;

            pA /= d;
            pB /= d;
            pC /= d;

            if (pA == 1 || pB == 1 || pC == 1) {
                if (pA == 1) {
                    a = "1";
                    b = "1" + string(pB - 1, '0');
                    c = "0" + string(pC - 1, '1');
                } else if (pB == 1) {
                    a = "0" + string(pA - 1, '1');
                    b = "1";
                    c = "1" + string(pC - 1, '0');
                } else {
                    a = "1" + string(pA - 1, '0');
                    b = "0" + string(pB - 1, '1');
                    c = "1";
                }
            } else {
                int p = gcd(pA, pB);
                int q = gcd(pA, pC);
                int r = gcd(pB, pC);
                for (int i = 0; i < pA; i++) {
                    int x = (i % p == 0) ^ (i % q == 0);
                    a += x + '0';
                }
                for (int i = 0; i < pB; i++) {
                    int x = (i % p == 0) ^ (i % r == 0);
                    b += x + '0';
                }
                for (int i = 0; i < pC; i++) {
                    int x = (i % q == 0) ^ (i % r == 0);
                    c += x + '0';
                }
            }

            cout << "YES" << endl;
            for (auto& x : a) cout << x << string(d - 1, '0'); cout << endl;
            for (auto& x : b) cout << x << string(d - 1, '0'); cout << endl;
            for (auto& x : c) cout << x << string(d - 1, '0'); cout << endl;
        }
    }
 
    return 0;
}

B - Rolling Stones（模拟，BFS）【Medium】

折一个四面体，实际操作后发现，底面相同时，三个侧面的数字是确定的，因此每个位置只可能走过一次。BFS 即可。时间复杂度$\mathcal{O}(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（模拟）【Medium】

正着不好做，但如果倒推，操作就是唯一的。

从目标倒着模拟，得到一组答案，顺便得到了有解条件以及策略的正确性。

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

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

int main() {
    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)) {
        cout << -1 << endl;
        return 0;
    }

    stack<array<int, 4>> res;
    while ((X != A && X != 0) || (Y != B && Y != 0)) {  // 没有到达四个角 
        int cx = (X * 2 < A) ? 0 : A; 
        int cy = (Y * 2 < B) ? 0 : B;
        X = 2 * X - cx;
        Y = 2 * Y - cy;
        res.push({ X, Y, cx, cy });
    }

    cout << res.size() << endl;
    while (!res.empty()) {
        auto [x1, y1, x2, y2] = res.top(); 
        res.pop();
        cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl; 
    }

    return 0;
}

F - Infinite Loop（简单数学）【Easy】

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

时间复杂度$\mathcal{O}(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;
}

G. Same Sum（哈希 + 线段树）【Hard】

给定长为$N$ 的整数序列$A$ 及$Q$ 个操作：对于所有$i \in [L,R]$，更新$A_i \gets A_i + v$；并判断元素$A_L, A_{L+1}, \ldots, A_R$ 是否能被分成$(R-L+1)/2$ 对总和相同的整数对。$1 \leqslant N,Q,A_{i},v \leqslant 2 \times 10^{5}$。

设$c$ 是区间平均数，$f_{n}$ 表示区间内等于$n$ 的数的数量，需要满足

$$f_{c+n} = f_{c-n} \text{for all} n \in \mathbb{Z}$$

这就很有幂级数的味道了，考虑形式幂级数

$$F(z) = \sum_{n=-\infty}^{+\infty} z^{n} f_{n}$$

其中$z$ 是形式参量。需要判断

$$\dfrac{1}{z^{c}} F(z) = z^{c} F(z^{-1})$$

可以随机一个 ULL 哈希值$z=x$ 判定幂级数相等。

具体地，维护区间信息

$$M_+(z) = \sum_{i=L}^{R} z^{A_i}, \quad M_-(z) = \sum_{i=L}^{R} z^{-A_i}, \quad c = \dfrac{1}{R-L+1} \sum_{i=L}^{R} A_i$$

满足条件当且仅当$M_+(z) = z^{2 c} M_-(z)$。

线段树维护区间乘区间和，复杂度$\mathcal{O}(N + Q \log N)$。

// 取模类 + 线段树 

struct Lazy {
    i64 add{ 0 };   
    Z po{ 1 };  
    Z ne{ 1 };  
    void apply(const Lazy& o)& {
        add += o.add;
        po *= o.po;
        ne *= o.ne;
    }
};
struct Info {
    i64 sum{ 0 };
    Z po{ 0 };
    Z ne{ 0 };
    int len{ 1 };
    void apply(const Lazy& o)& {
        sum += o.add * len;
        po *= o.po;
        ne *= o.ne;
    }
};
Info operator + (const Info& L, const Info& R) {
    return { L.sum + R.sum, L.po + R.po, L.ne + R.ne, L.len + R.len };
}

constexpr int maxN = 4e5;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    
    Z po = u64(rnd());  // 随机数 
    Z ne = 1 / po;      // 随机数的倒数 

    vector<Z> powpo(maxN + 1), powne(maxN + 1);
    powpo[0] = 1;
    powne[0] = 1;
    for (auto i = 0; i < maxN; i++) {
        powpo[i + 1] = powpo[i] * po;
        powne[i + 1] = powne[i] * ne;
    }

    int N, Q;
    cin >> N >> Q;

    vector<Info> a(N);
    for (auto n = 0; n < N; n++) {
        int x;
        cin >> x;
        x *= 2;
        a[n] = { x, powpo[x], powne[x], 1 };
    }
    LazySegmentTree<Info, Lazy> seg(a);

    while (Q--) {
        int op;
        cin >> op;
    
        if (op == 1) {
            int L, R, v;
            cin >> L >> R >> v;
            L--;
            v *= 2;
            
            seg.update(L, R, { v, powpo[v], powne[v] });
        } else {
            int L, R;
            cin >> L >> R;
            L--;

            auto [sum, pores, neres, _] = seg.query(L, R);
            if (sum % (R - L) != 0) {
                cout << "NO\n";
            } else {
                auto c = sum / (R - L);  // 区间平均数 
                if (pores * qpow(ne, c) == neres * qpow(po, c)) {
                    cout << "YES\n";
                } else {
                    cout << "NO\n";
                }
            }
        }
    }
    
    return 0;
}

K. Brotato（期望 DP）【Master】

游戏有$n$ 个关卡，初始在第一关。每一关有$p$ 的概率失败，且每一关失败的概率相互独立。如果在某一关失败，需要从第一关重新开始。有$k$ 个特殊道具，失败后可以从当前关卡继续挑战（注意：这种情形下当前关卡被视作未通过）。求通关全部$n$ 个关卡所需要的最小期望挑战次数。$1 \leqslant n \leqslant 10^{5}$，$0 \leqslant k \leqslant 10^{9}$，$0<p \leqslant 0.5$，$np \leqslant 20$。

Notes1：观察

观察 1：

1. 如果我们拥有无限道具，并且采取一失败就立刻使用道具的策略，通关时道具的期望使用次数为$\dfrac{np}{1-p}$
2. 注意$np \leqslant 20$ 的限制，所以当$k$ 很大时我们可以认为采取上述策略是最优的
3. 事实上，当$k > 165$ 时，答案可以直接近似为$\dfrac{n}{1-p}$
   证明 1.1：
   对于每一关，我们通关的期望次数为$\dfrac{1}{1-p}$ ，那么道具的期望使用次数就为$\dfrac{1}{1-p}-1 = \dfrac{p}{1-p}$ ，因为有$n$ 关，所以期望总次数为$\dfrac{np}{1-p}$
   证明 1.3：
   $\dfrac{np}{1-p} + n = \dfrac{n}{1-p}$

观察 2：

1. 当 “道具数” 较小时，我们会尽可能将道具留到后面的关卡使用
2. 当挑战失败时，我们会决策 是 / 否 使用道具。当 “道具数” 确定时，这一决策是单调的：存在$t$ ，在$t$ 关之前失败我们会选择从头开始，在$t$ 关之后失败我们会选择使用道具

Notes2：不使用道具

当$k$ 较小时，考虑 DP。设$f_{i,j}$ 表示当前有$i$ 个道具，已通过$j$ 关的情况下，还需要的最小期望挑战次数。

如果当前已经通过第$j$ 关， 根据单调性，若在第$j$ 关失败时不使用道具，则失败后在到达$j + 1$ 关之前，都不会再使用道具。

从第$j$ 关，不使用道具直到通过第$j+1$ 关的期望次数为${\bigg(\dfrac{1}{1-p}\bigg)}^{j+1}$。

以下给出证明：

若第一次挑战时成功通关，那么次数为$1$ ，概率为$1-p$；若第一次挑战失败，问题则转化为求从第一关开始，不使用道具一直通到$j+1$ 关所需要的最小期望挑战次数。

整理一下，现在要求的是 “不使用道具，从第一关开始到第$k$ 关的最小期望挑战次数”（其实出题组很贴心，第一个样例就是这个，但赛时因不会求这个遂放弃）

设$T_{k}$ 为通到第$k$ 关的最小期望挑战次数，那么$T_{k-1}$ 就为通到$k - 1$ 关的最小期望挑战次数。假设我们已经通到$k-1$ 关，那么再挑战一次，有$p$ 的概率失败，还需要$T_{k}$ 的次数，有$1-p$ 的概率成功，还需要$0$ 次。得到

$$T_{k} = T_{k-1}+1+p T_{k}+(1-p) 0$$

解得

$$T_{k} = \dfrac{1-(1-p)^{k}}{p (1-p)^{k}}$$

所以从第$j$ 关，不使用道具通过$j+1$ 关的期望挑战次数为

$$1+0 (1-p)+p T_{j+1} = 1+p \dfrac{1-(1-p)^{j+1}}{p (1-p)^{j+1}}=\dfrac{1}{(1-p)^{j+1}}$$

所以在不使用道具的情况下，

$$f_{i,j}=\bigg(\dfrac{1}{1-p}\bigg)^{j+1}+f_{i,j+1}$$

Notes3：使用道具

$f_{i,j}$ 表示还剩$i$ 个道具，已通过$j$ 关，还需要的最小期望挑战次数。

那么当我们在这种状态下再挑战一次，有$p$ 的概率还需要$f_{i-1,j}$ 的挑战次数，有$1-p$ 的概率还需要$f_{i,j+1}$ 的挑战次数，所以

$$f_{i,j}-1 = p f_{i-1,j} + (1-p) f_{i,j+1}$$

我们也可以设其他状态，比如 “已经使用了$i$ 个道具，已经通过$j$ 关的情况下， 还需要的最小期望挑战次数 ，其关键在于要将已知量作为一个入度为$0$ 的节点

版本一：$f_{i,j}$ 表示 “还剩$i$ 个道具，已通过$j$ 关，还需要的最小期望挑战次数”

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

double qpow(double a, ll b) {
    double res = 1;
    while (b) {
        if (b & 1) {
            res *= a;
        }
        b >>= 1;
        a = a * a;
    }
    return res;
}

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

    int n, k;
    cin >> n >> k;
    double p, q;
    cin >> p;
    q = 1 - p;
    cout << fixed << setprecision(12);

    double ans;
    if (k > 165) {
        ans = n / (1 - p);
        cout << ans << endl;
        return;
    }

    vector<vector<double>> f(170, vector<double>(n + 1));

    for (int i = 0; i <= k; i++) {
        for (int j = n - 1; j >= 0; j--) {
            f[i][j] = qpow(1 / q, j + 1) + f[i][j + 1];
            if (i) f[i][j] = min(1 + p * f[i - 1][j] + q * f[i][j + 1], f[i][j]);
        }
    }
    ans = f[k][0];
    cout << ans << endl;

    return 0;
}

版本二：$f_{i,j}$ 表示 “已使用$i$ 个道具，已通过$j$ 关，还需要的最小期望挑战次数”

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

double qpow(double a, ll b) {
    double res = 1;
    while (b) {
        if (b & 1) {
            res *= a;
        }
        b >>= 1;
        a = a * a;
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, k;
    cin >> n >> k;
    double p, q;
    cin >> p;
    q = 1 - p;
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);

    double ans;
    if (k > 165) {
        ans = n / (1 - p);
        cout << ans << endl;
        return;
    }

    vector<vector<double>> f(170, vector<double>(n + 1));

    for (int i = k; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            f[i][j] = f[i][j + 1] + qpow(1 / q, j + 1);
            if (i != k) f[i][j] = min(f[i][j], 1 + (1 - p) * f[i][j + 1] + p * f[i + 1][j]);
        }
    }

    ans = f[0][0];
    cout << ans << endl;

    return 0;
}

L - Z-order Curve（签到）【Beginner】

周期是异或的 highbit，复杂度$\mathcal{O}(1)$。

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

int main() {
    int T;
    cin >> T;

    while (T--) {
        ull L, R;
        cin >> L >> R;
        ull x = 1ULL << std::__lg(L ^ R);
        cout << (L % x) << endl;
    }
 
    return 0;
}

M - Rejection Sampling（数学，二分）【Medium】

给定$N,K$ 和序列$A = (A_{1},A_{2},\dots, A_{N})$，构造一组概率$p_{1},p_{2},\dots, p_{N}$。一个随机抽奖机器每轮会以$P_{i}$ 的概率选择$i$，直到选到的集合大小恰好为$K$ 时输出。要求概率满足$\sum p_{i} = K$，且对于任意$K$ 元子集$S$，抽奖机器输出$S$ 的概率 proportional to$\prod_{i\in S} A_{i}$。$K<N \leqslant 10^{5}$，$A_{i} \leqslant 10^{9}$。

要求构造$p$ 满足

$$\prod\limits_{i\in S} p_{i}\prod\limits_{i\notin S}(1-p_{i}) \propto \prod\limits_{i\in S} A_{i}$$

等价于

$$\dfrac{p_{i}}{1 - p_{i}} \propto A_{i}$$

设比例系数为$c$，得到$p_{i}=\dfrac{A_{i}}{A_{i}+c}$，结合$\sum p_{i} = K$，就需要

$$\sum_{i=1}^{N}\frac{A_{i}}{A_{i}+c}=K.$$

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

复杂度$\mathcal{O}(N (\log V + \log \epsilon^{-1}))$。

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

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

signed main() {
    cout << fixed << setprecision(12);

    int N, K;
    cin >> N >> K;

    vector<double> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    auto calc = [&](double c) {
        vector<double> p(N);
        for (int i = 0; i < N; i++) {
            p[i] = A[i] / (A[i] + c);
        }
        return p;
    };

    double l = 0, r = 1e15;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        auto p = calc(mid);
        if (accumulate(p.begin(), p.end(), 0.0l) < K) {
            r = mid;
        } else {
            l = mid;
        }
    }

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

    return 0;
}

有三种修改方案：

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

2. 判断$l$ 和$r$ 的相对差：即判断$\dfrac{r-l}{l}$ 是否在误差范围内。

double l = 0, r = 1e15;
while ((r - l) / l > eps) {  // 修改这一行 
    double mid = (l + r) / 2;
    auto p = calc(mid);
    if (accumulate(p.begin(), p.end(), 0.0l) < K) {
        r = mid;
    } else {
        l = mid;
    }
}

3. 控制二分次数：$V \cdot \epsilon^{-1}=10^{15}\cdot 10^{18}=10^{23}$，$\log V + \log \epsilon^{-1}=76$，因此二分$100$ 次足够。

double l = 0, r = 1e15;
for (int _ = 0; _ < 100; _++) {
    double mid = (l + r) / 2;

}

这三种都能跑到 100ms 以内。