2024-09-06 13:00 已编辑广西师范大学 golang 发布于广西

关注

23级选拔赛题解

easy : C H K

easy-medium : A F I

medium-hard : B E L

hard : D G J

A.提示：题目不是按照难易程度排，所以本题有可能是最难的题

定义 $f_i$ 为以下标 $i$ 为结尾的最长合法区间的长度。那么对于一次询问，如果 $r-l+1\le f_r$ 那么该区间一定是合法区间，反之不是。

关于 $f_i$ 的计算：

初始化 $f_i = 1$ ，如果 $a_i \% a_{i - 1} \ne 0$ ，那么 $f_i = f_{i - 1} + 1$ .

由于每次询问的时间复杂度是 $O(1)$ ，所以总的时间复杂度 $O(\max (n,q))$ .

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int> f(n + 1, 1);
    for (int i = 2; i <= n; i++) {
        if (a[i] % a[i - 1] != 0) {
            f[i] = f[i - 1] + 1;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << (r - l + 1 <= f[r] ? "YES\n" : "NO\n");
    }
}

B.Chocolate

以 $(x,y)$ 为中心点，Alice 和 Bob 只能吃中心点上边的巧克力，右边的巧克力，下边的巧克力和左边的巧克力，所以可以抽象为一共有4堆石子，每人可以拿任意一堆石子的任意数目，对于每一堆石子，打表发现 $SG(i)=i$ ，即可解答本题。

时间复杂度 $O(t)$ .

void solve() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    int a1 = x - 1, a2 = n - x, a3 = y - 1, a4 = m - y;
    if ((a1 ^ a2 ^ a3 ^ a4) == 0) {
        cout << "Bob\n";
    } else {
        cout << "Alice\n";
    }
}

C.青蛙1

注意当 $n \le d$ 时，所有青蛙都可以跳到对岸，所以答案为 $2^{60}$ 。

当 $n > d$ 时，容易想到要使跳到对岸的青蛙数量最多，每只青蛙都要跳最远的距离 $d$ ，所以每只青蛙跳到的地方都一样，我们只需要在青蛙跳到的地方放上石头即可。

时间复杂度 $O(1)$ .

void solve() {
    int n, m, d;
    cin >> n >> m >> d;

    if (d >= n) {
        cout << (1ll << 60) << "\n";
        return;
    }

    int num = ((n + d - 1) / d - 1);
    cout << m / num << "\n";
}

D.青蛙2

当 $n \le d$ 时，和青蛙1一样，答案为 $2^{60}$ 。

当 $n > d$ 时，显然跳到对岸的青蛙数量上限是 $m$ ，下限是 $0$ ，并且满足单调性，所以我们可以二分答案。

我们把起点和终点也看作一块石头，并将所有石头从小到大排序。如果当前答案为 $x$ ，对于一只青蛙，如果它当前所在的石头为 $a_i$ ，我们可以强制让这只青蛙跳到最右边的石头 $a_{i + x}$ ，如果它不能跳到 $a_{i+x}$ 这块石头上，说明当前答案一定是不合法的。

证明：如果一只青蛙当前所在的石头为 $a_i$ ，而这只青蛙最远只能跳到 $a_{i+x-j},1 \le j < x$ ，那么 $a_i$ 和 $a_{i+x-j}$ 之间的石头数量为 $x-j-1$ . 考虑另外一只青蛙所在的石头为 $a_l, l < i$ ，所以这只青蛙只能跳到 $a_i$ 和 $a_{i+x-j}$ 之间的石头，当 $a_i$ 和 $a_{i+x-j}$ 之间的石头全部都被用过时， $a_l$ 就不可能跳到比 $a_{i+x-j}$ 还远，所以只可能会有 $x-j$ 只青蛙跳到对岸。

我们可以发现青蛙一直是连续的一段，长度为 $x$ . 所以每次二分时我们只需要计算 $\max(a_{i+x} - a_i)$ 和 $d$ 的大小关系即可。

时间复杂度 $O(m \log m)$

void solve() {
    int n, m, d;
    cin >> n >> m >> d;
    
    vector<int> a(m + 1);
    a[0] = 1;
    for (int i = 1; i <= m; i++) {
        int k;
        cin >> k;
        k++;
        a[i] = k;
    }
    a.push_back(n + 1);
    sort(a.begin(), a.end());

    if (d >= n) {
        cout << (1ll << 60) << "\n";
        return;
    }
    
    auto check = [&](int x) ->bool {
        int cnt = 0;
        for (int i = 0; i < m + 2 - x; i++) {
            cnt = max(cnt, a[i + x] - a[i]);
        }
        return d < cnt;
    };
    
    int l = 0, r = m, ans = l;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid) <= 0) {
            l = mid + 1;
            ans = mid;
        }
        else r = mid - 1;
    }
    cout << ans << '\n';
}

E.偶像选秀节目

先看 $n=1$ 的情况，这是所有位置存活到最后的概率为 $(1)$ .

然后手搓几个样例发现：

$n=2$ 时： $(0, 1)$ .

$n=3$ 时： $(0, 1/2, 1/2)$ .

$n=4$ 时： $(0, 1/4,1/4,1/2)$ .

$n=5$ 时： $(0, 1/6,1/6,1/3,1/3)$ .

$n=6$ 时： $(0, 1/9,1/9,2/9,2/9,1/3)$ .

我们猜测每个位置存活概率的比例为： $0:1:1:2:2:3:3:...$ .

证明：考虑使用数学归纳法证明，假设到 $n=k$ 时都符合上述规律，那么当 $n=k+1$ 时，

如果 $k$ 为奇数， $n=k$ 时每个位置存活的概率为： $(0,\frac{8}{k^2-1},\frac{8}{k^2-1},\frac{16}{k^2-1},\frac{16}{k^2-1},...,\frac{4}{k+1}, \frac{4}{k+1})$ ，

$n=k+1$ 时，由于 $k+1$ 是偶数，所以第一轮位置在 $k+1$ 的人一定不会被淘汰，然后位置变为 $k$ ，这时最后一个人存活的概率为 $\frac{4}{k+1}$ . 第一轮位置在 $k$ 的人有 $\frac{2}{k+1}$ 的概率被淘汰掉，如果没被淘汰掉第二轮会在位置 $k-1$ ，位置 $k-1$ 存活到最后的概率为 $\frac{4}{k+1}$ ，所以一开始位置在 $k$ 的人存活的概率为 $(1 - \frac{2}{k+1})*\frac{4}{k+1}=\frac{4(k-1)}{(k+1)^2}$ ，因为 $\frac{4(k-1)}{(k+1)^2}:\frac{4}{k+1}=\frac{k-1}{2}:\frac{k+1}{2}$ 符合上式，所以猜测成立。

如果 $k$ 为偶数，仿造上面的证明过程也可以得到此结果。

所以当 $n$ 是偶数，最后一个位置的人活下来的概率最大。当 $n$ 是奇数最后倒数两个人活下来的概率最大，注意特判 $n=1$ .

int qpow(int a, int b, int MOD = mod) {
    a %= MOD;
    int res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void solve() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << "1\n1\n1";
        return;
    }
    int fz = n / 2;
    int fm = (n / 2) * (n / 2 + n % 2);
    if (n & 1) {
        cout << "2\n";
        cout << n << " " << n - 1 << "\n";
    } else {
        cout << "1\n";
        cout << n << "\n";
    }
    cout << fz * qpow(fm, mod - 2) % mod;
}

F.Defile

通过手搓几个样例发现，对于一个确定血量的序列，设序列中的最大值为 $m$ ，那么至少使用亵渎的次数为 $1\sim m$ 中未出现的数的数量 $+1$ . 比如序列为 $[3,5,6,9]$ 那么总共需要使用 $6$ 次亵渎（有 $5$ 个数没有出现，分别是： $1,2,4,7,8$ ）。简单来说就是使“空位”尽可能的少，所以当你抽到一张血量为 $x$ 的随从牌时，如果 $x>m$ ，你使用这张随从牌后会使“空位”变多或者不变（ $x=m+1$ 时不变），为了使用亵渎的次数最少，不会使用这个随从牌。如果 $x<=m$ ，为了使“空位”变少，就要将场上血量最大的消灭，然后注意细节即可。

aivoid solve() {
    int n;
    cin >> n;
    map<int, int> mp;
    std::vector<int> a(n);
    for (auto& it : a) {
        cin >> it;
        mp[it]++;
    }
    sort(a.begin(), a.end());
    int mx = a[n - 1];
    int cimx = 0;
    if (n != 1) cimx = a[n - 2];
    a.erase(unique(a.begin(), a.end()), a.end());
    int m = a.size();
    bool flag = false;
    if (mp[mx] >= 2) {
        flag = true;
    }
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        if (x > mx) {
            cout << mx - m + 1 << "\n";
        } else {
            if (flag) {//出现多次
                if (mp.count(x)) {
                    cout << mx - m + 1 << "\n";
                } else {
                    cout << mx - m << "\n";
                }
            } else { //出现一次
                if (x == mx) {
                    cout << mx - m + 1 << "\n";
                } else if (mp.count(x)) {
                    cout << max(x, cimx) - m + 2 << "\n";
                } else {
                    cout << max(x, cimx) - m + 1 << "\n";
                }
            }
        }
    }
}

G.xor

因为 $10^6 < 2^{20}$ ，所以我们可以对每一位都开一棵线段树维护。

#define GL (k << 1)
#define GR (k << 1 | 1)
struct Segt {
    struct node {
        int l, r;
        int w[N], lazy;
    };
    vector<int> base;
    vector<node> t;

    Segt(vector<int> in) : base(in) {
        int n = in.size() - 1;
        t.resize(n * 4 + 1);
        auto build = [&](auto self, int l, int r, int k = 1) {
            t[k] = {l, r};
            if (l == r) {
                for (int i = 0; i < N; i++) {
                    t[k].w[i] = base[l] >> i & 1;
                }
                return;
            }
            int mid = (l + r) / 2;
            self(self, l, mid, GL);
            self(self, mid + 1, r, GR);
            pushup(k);
        };
        build(build, 1, n);
    }
    void pushdown(node &p, int lazy) {
        int len = p.r - p.l + 1;
        for (int i = 0; i < N; i++) {
            if (lazy >> i & 1) {
                p.w[i] = len - p.w[i];
            }
        }
        p.lazy ^= lazy;
    }
    void pushdown(int k) {
        if (t[k].lazy == 0) return;
        pushdown(t[GL], t[k].lazy);
        pushdown(t[GR], t[k].lazy);
        t[k].lazy = 0;
    }
    void pushup(int k) {
        auto pushup = [&](node &p, node &l, node &r) {
            for (int i = 0; i < N; i++) {
                p.w[i] = l.w[i] + r.w[i];
            }
        };
        pushup(t[k], t[GL], t[GR]);
    }
    void modify(int l, int r, int val, int k = 1) {
        if (l <= t[k].l && t[k].r <= r) {
            pushdown(t[k], val);
            return;
        }
        pushdown(k);
        int mid = (t[k].l + t[k].r) / 2;
        if (l <= mid) modify(l, r, val, GL);
        if (mid < r) modify(l, r, val, GR);
        pushup(k);
    }
    i64 ask(int l, int r, int k = 1) {
        if (l <= t[k].l && t[k].r <= r) {
            i64 ans = 0;
            for (int i = 0; i < N; i++) {
                ans += t[k].w[i] * (1LL << i);
            }
            return ans;
        }
        pushdown(k);
        int mid = (t[k].l + t[k].r) / 2;
        i64 ans = 0;
        if (l <= mid) ans += ask(l, r, GL);
        if (mid < r) ans += ask(l, r, GR);
        return ans;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    Segt segt(a);
    int m;
    cin >> m;
    while (m--) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r;
            cin >> l >> r;
            cout << segt.ask(l, r) << "\n";
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            segt.modify(l, r, x);
        }
    }
}

H.Sequence

序列中的每一个数的出现次数为 $2^{n-1}$ 次，所以每一个数对答案的贡献为 $a_i \times 2^{n-1}$ ，所以最后答案就是 $2^{n-1} \times \sum_{i=1}^{n}a_i$ .

int qpow(int a, int b, int MOD = mod) {
    a %= mod;
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void solve() {
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        sum = (sum + k) % mod;
    }
    cout << sum * qpow(2, n - 1) % mod << "\n";
}

I.Genshin数1

定义 $dp_{i,j}$ 为当前有 $i$ 位数，且最后一位为 $j$ 的方案数。可以轻松的得到转移方程。可以提前处理 $10 \sim 99$ 以内的质数。

void solve() {
    int n;
    cin >> n;
    vector dp(n + 1, vector<int>(10));
    for (int j = 1; j <= 9; j++) {
        dp[1][j] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= 9; j++) {
            for (int k = 1; k <= 9; k++) {
                int x = 10 * k + j;
                if (minp[x] == x) { // x为质数
                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
                }
            }
        }
    }
    int ans = 0;
    for (int j = 1; j <= 9; j++) {
        ans = (ans + dp[n][j]) % mod;
    }
    cout << ans << "\n";
}

J.Genshin数2

由于 $k$ 很大，我们不能遍历 $k$ ，通过观察 $dp$ 方程发现每一遍 $dp$ 转移都是一样的，所以我们可以构造出一个转移矩阵，然后跑一遍矩阵快速幂即可得到答案。

const int SIZE = 9;
struct Matrix {
    int M[SIZE + 5][SIZE + 5];
    void clear() { memset(M, 0, sizeof(M)); }
    Matrix friend operator*(const Matrix &A, const Matrix &B) {
        Matrix Ans;
        Ans.clear();
        for (int i = 1; i <= SIZE; ++i)
            for (int j = 1; j <= SIZE; ++j)
                for (int k = 1; k <= SIZE; ++k)
                    Ans.M[i][j] = (Ans.M[i][j] + A.M[i][k] * B.M[k][j]) % mod;
        return Ans;
    }
};

void solve() {
    int n;
    cin >> n;
    Matrix a;
    a.clear();
    for (int i = 11; i <= 99; i++) {
        if (minp[i] == i) {
            a.M[i / 10][i % 10]++;
        }
    }
    n -= 2;
    Matrix res = a;
    while (n) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    int sum = 0;
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            sum = (sum + res.M[i][j]) % mod;
        }
    }
    cout << sum << "\n";
}

K.本题需要你设计一个高级算法解决

使用 getline 或者 while (cin >> s) 都可以。

#include <iostream>
using namespace std;
int main() {
    string s;
    while (cin >> s) {
        for (auto it : s) {
            if (it >= 'A' && it <= 'Z') {
                cout << (char)(it - 'A' + 'a');
            } else {
                cout << it;
            }
        }
        cout << " ";
    }
    return 0;
}

L.本题需要你设计一个乱搞算法解决

可以发现，一个长度为 $n$ 的严格递增序列共有 $2^n$ 个严格递增子序列，下面给出本题的一个（不是唯一）构造方法。

考虑通过二进制来构造，先将 $k$ 进行二进制分解，得到 $k$ 的最高位，我们先将 $k$ 的最高位填进去，假设 $k$ 的二进制共有 $n+1$ 位，那么这时候答案数组为： $[1,2,3,...,n]$ 一共 $n$ 个数。

我们先来看在这 $n$ 个数插入一些数会对答案造成什么影响。如果在第一个数和第二个数的中间插入 $n+1$ 变成 $[1,n+1,2,3,...,n]$ ，因为 $n+1$ 比后面的数都要大，所以 $n+1$ 后面的数和 $n+1$ 组合起来并不会使答案发生变化，对答案造成影响的只有 $n+1$ 前面的数，前面共有 $1$ 个数，跟前面的数组合起来就有两种严格递增子序列（ $[1,n+1]$ 和 $[n+1]$ ），答案会比原来多 $2$ ，如果前面有 $x$ 个数比 $n+1$ 还要小，答案就会比原来多 $2^x$ 个。这就告诉我们可以通过在这 $n$ 个数的中间插入一些数来补齐 $k$ 的二进制位。

为了使插入的数不受后面的数的影响，我们从 $k$ 的次高位到最低位插数。例如，假设 $k$ 的二进制为： $1011010$ ，先填入 $k$ 的最高位，答案为： $[1,2,3,4,5,6]$ ，从次高位开始遍历，当 $k$ 的二进制出现 $1$ 时，就代表要往数组中插入一个新的数，遍历到第三位时出现了 $1$ ，这时候答案应该增加 $2^4$ ，所以我们就往 $4$ 和 $5$ 的中间插入一个新的数（因为前面有 $4$ 个数），变为： $[1,2,3,4,7,5,6]$ ，到第四位也出现了 $1$ ，答案应该增加 $2^3$ ，所以就在 $3$ 和 $4$ 的中间插入一个新的数，变为： $[1,2,3,8,4,7,5,6]$ ，可以看到，我们新插入的数是递增的，并且都是从右边往左边加入，所以这些数并不会互相影响。最后结果为： $[1,9,2,3,8,4,7,5,6]$ 。因为 $k\le 10^{18} < 2^{60}$ ，所以最多会插入 $60 \times 2=120$ 个数，不会超过题目要求的 $150$ 个数.

写代码时，为了方便插入，一开始填入 $k$ 的最高位时可以隔一位填入。

void solve() {
	int k;
	cin >> k;
	string s = "";
	int n = k;
	while (n) {
        s.push_back(n % 2 + '0');
		n /= 2;
	}
	vector<int> ans(130);
	int x = s.size();
	int cnt = 0;
	int idx = 1;
	for (int i = 1; i < x; i++) {
		ans[2 * i - 1] = idx++;
		cnt++;
	}
	for (int i = x - 2; i >= 0; i--) {
		if (s[i] == '1') {
			ans[2 * i] = idx++;
			cnt++;
		}
	}
	cout << cnt << "\n";
	for (auto it : ans) {
		if (!it) continue;
		cout << it << " ";
	}
	cout << "\n";
}