题解 | #“范式杯”2023牛客暑期多校训练营1#

A

考虑固定最左边的 $1$ 和最右边的 $0$ ，对其他的先排序然后再进行操作使 $s$ 执行操作后变为形如 $0\dots 001011\dots 1$ 。

和题解方法好像一样。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int l = -1, r = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            l = i;
            break;
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '0') {
            r = i;
            break;
        }
    }
    int c0 = 0, c1 = 0;
    vector<pair<int, int>> ans;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            if (i != r) {
                ans.push_back({i, r});
            }
            c0++;
        }
    }

    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            if (i != l) {
                ans.push_back({l, i});
            }
            c1++;
        }
    }

    for (int i = 0; i < n; i++) {
        if (i == l || i == r) {
            continue;
        }
        for (int j = i + 1; j < n; j++) {
            if (j == l || j == r) {
                continue;
            }
            ans.push_back({i, j});
        }
    }
    for (int i = c0; i < r; i++) {
        ans.push_back({i, r});
    }
    for (int i = n - 1; i > r; i--) {
        ans.push_back({r, i});
    }
    for (int i = c0 - 1; i > l; i--) {
        ans.push_back({l, i});
    }
    for (int i = 0; i < l; i++) {
        ans.push_back({i, l});
    }
    cout << ans.size() << '\n';
    for (auto &[x, y] : ans) {
        cout << x + 1 << ' ' << y + 1 << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

H

提供一种赛时想到的 $n\log n$ 的方法，记 $p_i=(\min(a_i,b_i),\max(a_i,b_i))$ ，将 $p_i$ 看成一个区间，若 $a_i<b_i$ ，将 $p_i$ 放入集合 $s$ ，若 $a_i>b_i$ ，将 $p_i$ 放入集合 $t$ 。

题意转变为在 $s$ 集合中找一个区间，在 $t$ 集合中找一个区间，并使这两个区间交集长度最大，记该最大长度为 $\text{mx}$ ， $\sum\limits_{i=1}^{n}|a_i-b_i|-2\cdot \text{mx}$ 即为答案，实现上用了两个支持单点修改，区间查询的线段树分别维护 $s,t$ 集合。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

template<class Info,
        class Merge = plus<Info>>
struct SegmentTree {
    const int n;
    const Merge merge;
    vector<Info> info;
    SegmentTree(int n = 0) : n(n), merge(Merge()), info(2 * n) {}
    SegmentTree(vector<Info> init) : SegmentTree(init.size()) {
        for (int i = 0; i < n; i++) {
            modify(i, init[i]);
        }
    }
    void pull(int p) {
        info[p] = merge(info[2 * p], info[2 * p + 1]);
    }
    void modify(int p, const Info &v) {
        for (info[p += n] = v; p /= 2; ) {
            pull(p);
        }
    }
    Info rangeQuery(int l, int r) {
        Info res = Info();
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l % 2) {
                res = merge(res, info[l++]);
            }
            if (r % 2) {
                res = merge(res, info[--r]);
            }
        }
        return res;
    }
};

struct Max {
    int x;
    Max(const int &x = -1E9) : x(x) {}
};
 
Max operator+(const Max &a, const Max &b) {
    return max(a.x, b.x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
       
    int n;
    cin >> n;
    
    i64 ans = 0; 
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        ans += abs(a[i] - b[i]);
    }

    vector<pair<int, int>> s, t;

    for (int i = 0; i < n; i++) {
        if (a[i] < b[i]) {
            s.push_back({a[i], b[i]});
        } else if (a[i] > b[i]) {
            t.push_back({b[i], a[i]});
        }
    }
    const int N1 = s.size(), N2 = t.size();
    vector<int> v1(N1), v2(N2);
    for (int i = 0; i < N1; i++) {
        v1[i] = s[i].first;
    }
    for (int i = 0; i < N2; i++) {
        v2[i] = t[i].first;
    }

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    v1.erase(unique(v1.begin(), v1.end()), v1.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());
    const int M1 = v1.size(), M2 = v2.size();
    SegmentTree<Max> seg1(M1), seg2(M2);
    for (int i = 0; i < N1; i++) {
        int j = lower_bound(v1.begin(), v1.end(), s[i].first) - v1.begin();
        seg1.modify(j, max(seg1.get(j).x, s[i].second));
    }

    for (int i = 0; i < N2; i++) {
        int j = lower_bound(v2.begin(), v2.end(), t[i].first) - v2.begin();
        seg2.modify(j, max(seg2.get(j).x, t[i].second));        
    }

    int mx = 0;

    for (int i = 0; i < N1; i++) {
        int j = upper_bound(v2.begin(), v2.end(), s[i].first) - v2.begin();

        j = min(M2, j);
        int res = seg2.rangeQuery(0, j).x;
        mx = max(mx, min(res, s[i].second) - s[i].first);
    }
    for (int i = 0; i < N2; i++) {
        int j = upper_bound(v1.begin(), v1.end(), t[i].first) - v1.begin();
        
        j = min(M1, j);
        int res = seg1.rangeQuery(0, j).x;
        mx = max(mx, min(res, t[i].second) - t[i].first);   
    }
    cout << ans - 2LL * mx << '\n';

    return 0;
}

赛后考虑到只需要一个前缀最大右端点，那就不用线段树了，排个序二分一下就行了。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
       
    int n;
    cin >> n;
    
    i64 ans = 0; 
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        ans += abs(a[i] - b[i]);
    }

    vector<pair<int, int>> s, t;

    for (int i = 0; i < n; i++) {
        if (a[i] < b[i]) {
            s.push_back({a[i], b[i]});
        } else if (a[i] > b[i]) {
            t.push_back({b[i], a[i]});
        }
    }

    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    const int N1 = s.size(), N2 = t.size();
    vector<int> smx(N1 + 1, -1E9), tmx(N2 + 1, -1E9);

    for (int i = 0; i < N1; i++) {
        smx[i + 1] = max(smx[i], s[i].second);
    }
    for (int i = 0; i < N2; i++) {
        tmx[i + 1] = max(tmx[i], t[i].second);
    }
    int mx = 0;
    for (int i = 0; i < N1; i++) {
        int j = upper_bound(t.begin(), t.end(), s[i]) - t.begin();
        j = min(j, N2);
        mx = max(mx, min(tmx[j], s[i].second) - s[i].first);
    }
    for (int i = 0; i < N2; i++) {
        int j = upper_bound(s.begin(), s.end(), t[i]) - s.begin();
        j = min(j, N1);
        mx = max(mx, min(smx[j], t[i].second) - t[i].first);
    }
    cout << ans - 2LL * mx << '\n';
    
    return 0;
}

J

考虑输输输输...输赢之后可以赢一块钱，现在有 $n$ 块钱，最多能输 $k=\log_2 (n 1)$ 次，成功的概率为 $1-\frac{1}{2^k}$ ，从 $n$ 块钱要变为 $n m$ 块钱，概率为 $\prod\limits_{i=n 1}^{n m}1-\frac{1}{2^{\log_2(i)}}$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int P = 998244353;

i64 power(i64 a, i64 b, int p = P) {
    i64 res = 1;
    for (; b; b >>= 1, a = a * a % p) {
        if (b & 1) {
            res = res * a % p;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;

    i64 ans = 1;
    const int inv_2 = (P + 1) / 2;
    for (int i = n + 1; i <= n + m; ) {
        int lg = __lg(i);
        i64 v = (1 - power(inv_2, lg) + P) % P;
        int j = min(m + n, (1 << (lg + 1)) - 1);
        ans = ans * power(v, j - i + 1) % P;
        i = j + 1;
    }   
    cout << ans << '\n';

    return 0;
}

K

先从 $1$ 开始 $\text{bfs}$ ，同时求出每个点到 $1$ 的最短路。

考虑选什么边来加点，两种情况：

第一种，删除该边不影响任何一个点到 $1$ 的最短距离。

第二种，删除该边影响某点到 $1$ 的最短路，那么这样的整一段最多为答案提供 $k$ 的贡献。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> g(n);
    vector<int> deg(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }

    queue<int> q;
    vector<int> dis(n, -1);
    q.push(0);
    dis[0] = 0;
    while (!q.empty()) {
        auto u = q.front();
        q.pop();

        for (auto &v : g[u]) {
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    i64 ans = 1 + 1LL * k * deg[0];
    for (int i = 1; i < n; i++) {
        if (deg[i] >= 2 && dis[i] != -1 && dis[i] <= k) {
            ans += 1LL * (k - dis[i]) * (deg[i] - 2);
        }
    }
    cout << ans << '\n';
    
    return 0;
}

L

三秒后 $x\rightarrow f(x),y\rightarrow g(y),z\rightarrow t(z)$ 。

$\text{crt}$ ， $O(q\cdot \log n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr i64 inf = 1E18;

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    i64 g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

i64 crt(const vector<i64> &r, const vector<i64> &m) {
    int n = r.size();
    i64 r0 = 0, m0 = 1;
    for (int i = 0; i < n; i++) {
        i64 m1 = m[i];
        i64 r1 = r[i] % m1;
        if (r1 < 0) {
            r1 += m1;
        }
        if (m0 < m1) {
            swap(r0, r1);
            swap(m0, m1);
        }
        if (!(m0 % m1)) {
            if (r0 % m1 != r1) {
                return -1;
            }
            continue;
        }
        i64 x, y;
        i64 g = exgcd(m0, m1, x, y);  
        if ((r1 - r0) % g) {
            return -1;
        }
        i64 u1 = m1 / g;
        r0 += (r1 - r0) / g % u1 * x % u1 * m0;
        m0 *= u1;
        if (r0 < 0) {
            r0 += m0;
        }
    }
    return r0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
     
    vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        b[i]--;
    }
    for (int i = 0; i < n; i++) {
        cin >> c[i];
        c[i]--;
    }
    
    auto f = [&](int x, int i) {
        if (x == 0) {
            return a[b[c[i]]]; // f(x)
        }  else if (x == 1) {
            return b[c[a[i]]]; // g(y)
        } else {
            return c[a[b[i]]]; // t(z)
        }
    };

    vector<vector<int>> pos(3, vector<int>(n, -1));
    auto bel = pos;
    auto len = pos;
     
    for (int t = 0; t < 3; t++) {
        for (int i = 0; i < n; i++) {
            if (pos[t][i] == -1) {
                vector<int> cir;
                int l = 0;
                for (int j = i; pos[t][j] == -1; j = f(t, j)) {
                    cir.push_back(j);
                    pos[t][j] = l;
                    bel[t][j] = i;
                    l++;
                }
                for (auto &xi : cir) {
                    len[t][xi] = l;
                }
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;
        x--, y--, z--;

        i64 ans = inf;
        int sx = 0, sy = 0, sz = 0;
        for (int t = 0; t < 3; t++) {
            if (bel[0][sx] == bel[0][x] && bel[1][sy] == bel[1][y] && bel[2][sz] == bel[2][z]) {
                vector<i64> m{len[0][sx], len[1][sy], len[2][sz]};
                vector<i64> a{pos[0][x] - pos[0][sx], pos[1][y] - pos[1][sy], pos[2][z] - pos[2][sz]};
                
                i64 N = crt(a, m);
                if (N != -1) {
                    ans = min(ans, t + 3 * N);               
                }
            }
            int tx = a[sy], ty = b[sz], tz = c[sx];
            sx = tx, sy = ty, sz = tz;
        }
        cout << (ans == inf ? -1 : ans) << '\n';
    }
    
    return 0;
}

M

考虑 $\text{exgcd}$ ，设 $r\cdot a s\cdot b=x$ ，若 $r\ge 0,s\ge 0$ ， $ans=2\cdot(r s)$ ；否则 $ans=2\cdot |r-s|-1$ 。

先 $\text{exgcd}$ 求出一组解，然后求出离原点最近的 $(k_1,k_2)$ 满足 $k_1\cdot a k_2\cdot b=x$ ，对附近的 $(k_1 t\cdot b,k_2-t\cdot a)$ 求 $\min$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    i64 g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

void solve() {
    i64 a, b, x;
    cin >> a >> b >> x;

    i64 k1, k2;
    i64 g = exgcd(a, b, k1, k2);
    if (x % g) {
        cout << "-1\n";
        return;
    }
    a /= g;
    b /= g;
    x /= g;
    k1 = (k1 * x % b + b) % b;
    k2 = (x - k1 * a) / b;

    i64 ans = 1E18;
    for (int t = -10; t <= 10; t++) {
        i64 r = k1 + b * t, s = k2 - a * t;
        if (r >= 0 && s >= 0) {
            ans = min(ans, 2 * (r + s));
        } else {
            ans = min(ans, 2 * abs(r - s) - 1);
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}