坑一堆（

A. 小L的三则运算

题意

给定一个大于 $1$ 的正整数 $x$ 和一个二元运算符（加减乘之一），输出两个正整数，满足使用该二元运算符计算得到的结果为 $x$ 。

思路

钦定其中一个正整数为 $1$ 即可。

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

对应AC代码

void solve() {
    int x;
    string op;
    cin >> x >> op;
    if(op == "*") cout << x << ' ' << 1 << '\n';
    else if(op == "+") cout << x - 1 << ' ' << 1 << '\n';
    else cout << x + 1 << ' ' << 1 << '\n';
}

签到

B. 小L出师了

题意

给定三个正整数 $n, t, k$ ，删去长度为 $n$ 的数组中的 $k$ 个不同的位置对应的元素，分割得到若干段，输出长度大于等于 $t$ 的最多段落数量。

思路

因为我们可以随意选择删除的位置，所以我们可以先全都放在最后，求出段数后再把要删除的位置往前挪，那么显然我们最多可以得到 $\lfloor \frac{n - k}{t} \rfloor$ 个长度为 $t$ 的段落。

可是需要注意我们最多只能分得 $k + 1$ 个段落，需要跟边界取最小值。

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

对应AC代码

void solve() {
    int n, t, k;
    cin >> n >> t >> k;
    cout << min(k + 1, (n - k) / t) << '\n';
}

简化了一下题意

C. 小L的位运算

题意

给定三个 $n$ 位二进制数 $a, b, c$ ，定义一次操作为下面四种操作任选其一：

花费 $x$ 元，反置二进制数 $a$ 的任意一位；
花费 $x$ 元，反置二进制数 $b$ 的任意一位；
花费 $y$ 元，交换二进制数 $a$ 的任意两个数位；
花费 $y$ 元，交换二进制数 $b$ 的任意两个数位。

在可以进行任意次操作的情况下，输出使得 $a \oplus b = c$ 需要的最小花费。

思路

我们先不考虑花费，那么不难发现 $a \oplus b$ 和 $c$ 的任意一位不对应时， $a$ 和 $b$ 在该位的值只有四种可能，分别为 $00, 01, 10, 11$ 。而有趣的是任意一对都有至少一个元素不同，所以我们只需配对交换即可。通过一些贪心策略可以发现，当四种可能的数量中的最大值超过总和的一半时，多余的将无法配对，那么我们将多余的反置即可。

那么如果要考虑花费呢？因为我们上面的操作本质上是两两配对交换，那么这其实等价于分别反置需要交换的两位。所以我们可以比较一下两次反置和一次交换的大小关系，如果前者更小那么全都反置即可，否则采取前面的策略是最优的。

时间复杂度： $O(n)$

对应AC代码

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    string a, b, c;
    cin >> a >> b >> c;
    vector<int> cnt(4);
    for(int i=0;i<n;i++) {
        int p = a[i] - '0', q = b[i] - '0', r = c[i] - '0';
        if(!(p ^ q ^ r)) continue;
        cnt[p * 2 + q] ++;
    }
    int sum = accumulate(cnt.begin(), cnt.end(), 0ll), mx = *max_element(cnt.begin(), cnt.end());
    cout << min(x * sum, x * ((mx % 2 == 0 && sum % 2 == 1) + max(0ll, mx - sum / 2)) + y * (sum / 2)) << '\n';
}

要输出方案就头大了

D. 小L的字符串翻转

题意

给定一个长为 $n$ 的二进制串，将其按照 $k$ 个元素一段从左到右依次分段，最后一段元素个数可能小于 $k$ 。定义一次操作为选定一段，对整段执行反置或重排列。

在可以任意次操作的情况下，操作完成后将段落重新拼接，并将得到的二进制串中连续的 $0$ 替换为一个 $0$ ，连续的 $1$ 替换为一个 $1$ ，记 $ans_k$ 为替换完成后的长度。输出下式的值：

$\displaystyle \bigoplus_{k=1}^{n} ans_k$

思路

首先， $ans$ 即为拼接完成后 $01, 10$ 的个数 $+ 1$ 。

如果我们只有一段，那么显然将 $0$ 和 $1$ 分开放在两端是最合适的。所以说在一个段落内，最多只会有一个 $01, 10$ ，这取决于段落内是否同时包含 $0$ 和 $1$ 。

那么答案如果段落变多，那么我们会希望拼接的时候两端都是 $0$ 或都是 $1$ 。但显然这个是可控的，钦定第一段的右端点为 $1$ ，第二段的左端点完全可以通过反置和重排列变为 $1$ ，而后面也是一样的。

所以说，拼接对我们来说毫无影响，我们只需累加每一段的答案即可。

至于如何检查段落内是否同时包含 $0$ 和 $1$ ，这可以用前缀和实现，因为我们完全可以做到枚举每一段的左端点，复杂度是调和级数。

时间复杂度： $O(n \log n)$

对应AC代码

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    vector<int> pre(n + 1);
    for(int i=1;i<=n;i++) pre[i] = pre[i - 1] + (s[i] - '0');
    int ans = 0;
    for(int k=1;k<=n;k++) {
        int now = 1;
        for(int l=1;l<=n;l+=k) {
            if(pre[min(n, l + k - 1)] - pre[l - 1] == 0 || pre[min(n, l + k - 1)] - pre[l - 1] == min(n, l + k - 1) - l + 1) continue;
            now ++;
        }
        ans ^= now;
    }
    cout << ans << '\n';
}

差点以为复杂度是平方（

E. 小L的井字棋

题意

给定一个井字棋残局，约定残局合法且双方落子数量相同，在残局基础上，先手当前可以连下两个棋，然后继续正常比赛。在两人足够聪明的条件下，判断先手是否有必胜策略。

思路

首先我们无法找出一个通用的解法，比较无脑的是写搜索，但是没必要。

我们对落子数量进行分讨：

数量为 $0$ ，此时下在中央和任意位置，先手必胜，可以手动模拟验证先手的必胜策略。
数量为 $2$ ，此时先手的棋子只有一条线被封锁，任选一条没被封锁的线填满即可，先手必胜。
数量为 $4$ ，此时先手的棋子最多只有一个被完全封锁，任选一条没被封锁的线填满即可，先手必胜。

而剩下的我们只需暴力填充，因为要么先手只能填入一个，要么后手只能填入一个。

时间复杂度： $O(能过)$

对应AC代码

void solve() {
    vector<string> s(3);
    for(auto &it : s) cin >> it;
    vector<vector<pii>> ls = {
        {{0, 0}, {1, 0}, {2, 0}},
        {{0, 1}, {1, 1}, {2, 1}},
        {{0, 2}, {1, 2}, {2, 2}},
        {{0, 0}, {0, 1}, {0, 2}},
        {{1, 0}, {1, 1}, {1, 2}},
        {{2, 0}, {2, 1}, {2, 2}},
        {{0, 0}, {1, 1}, {2, 2}},
        {{0, 2}, {1, 1}, {2, 0}}
    };
    int cnt = 0;
    for(auto &it : s) cnt += count(it.begin(), it.end(), 'G');
    cnt = 9 - cnt;
    if(cnt <= 4) {
        cout << "Yes\n";
        return;
    }
    for(int i1=0;i1<3;i1++) {
        for(int j1=0;j1<3;j1++) {
            if(s[i1][j1] != 'G') continue;
            for(int i2=0;i2<3;i2++) {
                for(int j2=0;j2<3;j2++) {
                    if(s[i2][j2] != 'G') continue;
                    auto ss = s;
                    ss[i1][j1] = ss[i2][j2] = 'X';
                    bool ok = false;
                    for(auto &l : ls) {
                        bool now = true;
                        for(auto &[x, y] : l) {
                            if(ss[x][y] != 'X') now = false;
                        }
                        ok |= now;
                    }
                    if(ok) {
                        cout << "Yes\n";
                        return;
                    }
                }
            }
        }
    }
    cout << "No\n";
}

如果去找规律这题就完蛋了（x

F. 小L的抽卡

待补充

G. 小L的三元组

待补充

H. 小L的min-max问题

题意

给定一个长为 $n$ 的数组，将其切成 $k$ 段，切法的权值为所有段落最小值与最大值之积的总和。输出所有切法的权值总和。

思路

首先，我们可以单独计算每一段的权值，并计算这一段会出现多少次，相乘累加即可得到题目所求。

因而我们只需考虑每一段会出现多少次。假设本段左边有 $x$ 个元素，右侧有 $y$ 个元素，那么我们可以枚举左边分割为 $i$ 段，右侧即为 $k - 1 - i$ 段。

将 $n$ 个元素分成 $m$ 段，且每段内至少有一个元素，这相当于在 $n$ 个元素之间插板，也就是 $n - 1$ 个空隙中选择 $m - 1$ 个，用组合数表示即为：

$\displaystyle \binom{n - 1}{m - 1}$

那么如果 $x = 0$ 或 $y = 0$ ，用这个组合数即可得到答案，否则我们可以将出现次数表示为：

$\displaystyle \sum_{i=1}^{k-2} \binom{x - 1}{i - 1} \binom{y - 1}{k - i - 2}$

我们稍微变一下式子，将 $i - 1$ 整体替换：

$\displaystyle \sum_{i=0}^{k-3} \binom{x - 1}{i} \binom{y - 1}{k - 3 - i}$

这是经典的范德蒙德卷积，我们可以直接得出答案：

$\displaystyle \sum_{i=0}^{k-3} \binom{x - 1}{i} \binom{y - 1}{k - 3 - i} = \binom{x + y - 2}{k - 3}$

至于权值，在遍历的时候顺便更新区间最小最大即可，不过用 ST 表自然也是可以的。

时间复杂度： $O(n ^ 2)$

对应AC代码

constexpr int P = 998244353;
using Z = MInt<P>;

//线性求阶乘，逆元，阶乘逆元
static void get_fact_inv(const int n, int fac[], int inv[], int fac_inv[], const int p = mod) {
    fac[0] = fac_inv[0] = inv[0] = fac[1] = fac_inv[1] = inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        fac[i] = fac[i - 1] * i % p;
        inv[i] = (p - p / i * inv[p % i] % p) % p; //线性求逆元
        fac_inv[i] = fac_inv[i - 1] * inv[i] % p;
    }
}

int fac[N], inv[N], fac_inv[N];

void init() {
    get_fact_inv(1e4, fac, inv, fac_inv);
}

Z C(int n, int m) {
    if(n < m) return {0};
    return Z{fac[n]} * fac_inv[m] * fac_inv[n - m];
}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    Z ans = 0;
    for(int l=1;l<=n;l++) {
        int mx = -inf, mn = inf;
        for(int r=l;r<=n;r++) {
            if(n - (r - l + 1) < k - 1) break;
            mx = max(mx, a[r]);
            mn = min(mn, a[r]);
            Z now = 1;
            if(l > 1 && r < n) now = C(l - 1 + n - r - 2, k - 3);
            if(l == 1 && r < n) now = C(n - r - 1, k - 2);
            if(l > 1 && r == n) now = C(l - 2, k - 2);
            ans += now * mx * mn;
        }
    }
    cout << ans << '\n';
}

怎么感觉老是能在牛客看到范德蒙德卷积

I. 小L的数学题

题意

给定两个整数 $n, m$ ，定义一次操作为下面二者任选其一：

将数字乘 $2$ ；
将数字开平方根后下取整

判断能否经过任意次操作，将 $n$ 变为 $m$ 。

思路

我们先处理 $0$ 的情况，因为正整数不可能开平方根到 $0$ ，所以如果两者其一为 $0$ ，其一非 $0$ ，就是无解。而显然相等有解。

接下来考虑正整数之间的变化。首先任何正整数经过有限次开平方根操作后都会变成 $1$ ，我们来考虑怎么从 $1$ 通过上述操作到达任意数字。

首先，显然存在 $x, k$ ，满足 $k^{2^j} \leq x < (k + 1)^{2^j}$ ，那么我们可以通过开 $j$ 次平方根从 $x$ 变成 $k$ 。

我们将式子两边取以 $2$ 为底的对数，有 $2^j \log_2 k \leq \log_2 x < 2^j \log_2 (k + 1)$ 。

我们将左右两端点作差，得到 $2^j \log_2 \frac{k + 1}{k}$ ，显然只要 $j$ 足够大，结果就会大于等于 $1$ 。所以一定存在整数 $p$ 满足 $2^j \log_2 k \leq p < 2^j \log_2 (k + 1)$ 。回到原式，可得 $k^{2^j} \leq 2^p < (k + 1)^{2^j}$ 。

所以我们只需将 $n$ 先开平方根到 $1$ ，然后一定可以找出整数 $p, j$ 满足 $2^j \log_2 m \leq p < 2^j \log_2 (m + 1)$ ，乘 $p$ 次 $2$ 之后，开 $j$ 次平方根得到 $m$ 。

所以当且仅当两者其一为 $0$ ，其一非 $0$ ，就是无解。否则一定有解。

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

对应AC代码

void solve() {
    int n, m;
    cin >> n >> m;
    cout << ((n != m && (n == 0 || m == 0)) ? "No\n" : "Yes\n");
}

证明参考了出题人题解

J. 小L的汽车行驶问题

题意

给定一个整数 $n$ ，在 $n$ 秒内，每秒的时刻初可以进行三种操作：

踩油门，速度瞬间增大 $10$ ；
踩刹车，速度瞬间降低 $5$ ；
踩离合，当前时刻速度降低 $10$ ，时刻末恢复原速度

在速度不低于 $0$ 的前提下，给定每秒的操作，计算位移。

思路

模拟即可。

时间复杂度： $O(n)$

对应AC代码

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0, v = 0;
    for(auto &it : s) {
        if(it == '0') {
            v += 10;
            ans += v;
        }else if(it == '1') {
            v = max(0ll, v - 5);
            ans += v;
        }else {
            ans += max(0ll, v - 10);
        }
    }
    cout << ans << '\n';
}

好直白

K. 小L的几何

待补充

L. 小L的构造

题意

给定一个整数 $n$ ，在每个数最多可以使用一次的情况下，输出最多能构造的三元组 $(x, y, z)$ 数量，满足刚好有两对数互质。

思路

首先，注意到存在下面的周期为 $6$ 的构造方案：

$(i, i + 1, i + 3), (i + 2, i + 4, i + 5)$

因为周期为偶数，所以奇偶性不变，而由于偶数一定不互质，所以 $(i + 1, i + 3)$ 不互质。

其次，相邻数一定互质，所以 $(i, i + 1), (i + 4, i + 5)$ 互质。

接着，相邻奇数一定互质，因为最小的奇质数大于 $2$ ，所以 $(i + 2, i + 4)$ 互质。

然后，根据辗转相除法可知，两个数的最大公因数如果不是其中的某个数，就一定小于两个数的差的绝对值。而由于 $i$ 和 $i + 3$ 相差为 $3$ ，且 $i$ 模 $6$ 为 $1$ ，所以两者的最大公因数只能小于 $3$ ，即 $2$ 或互质。由于 $i$ 为奇数，所以不可能出现偶数因子，所以 $(i, i + 3)$ 互质。同理可得 $(i + 2, i + 5)$ 不互质，因为 $i + 2$ 为 $3$ 的倍数。

但是当 $n \bmod 6 \geq 3$ 时，可能存在漏解。我们考虑构造 $n = 9$ 的情况，如下：

$(1, 2, 4), (3, 5, 9), (6, 7, 8)$

因为为固定数字，可以通过注意力得出正确性。

而后续的方案需要换成下面的样子（不唯一）：

$(i, i + 1, i + 4), (i + 2, i + 3, i + 5)$

通过类似的方法可以证明正确性。

时间复杂度： $O(n)$

对应AC代码

void solve() {
    int n;
    cin >> n;
    if(n <= 3) {
        cout << 0 << '\n';
        return;
    }
    if(n <= 5) {
        cout << 1 << '\n' << 2 << ' ' << 3 << ' ' << 4 << '\n';
        return;
    }
    cout << n / 3 << '\n';
    int i = 1;
    if(n % 6 >= 3) {
        cout << i << ' ' << i + 1 << ' ' << i + 3 << '\n';
        cout << i + 2 << ' ' << i + 4 << ' ' << i + 8 << '\n';
        cout << i + 5 << ' ' << i + 6 << ' ' << i + 7 << '\n';
        i += 9;
        for(;i+5<=n;i+=6) {
            cout << i << ' ' << i + 1 << ' ' << i + 4 << '\n';
            cout << i + 2 << ' ' << i + 3 << ' ' << i + 5 << '\n';
        }
    }else {
        for(;i+5<=n;i+=6) {
            cout << i << ' ' << i + 1 << ' ' << i + 3 << '\n';
            cout << i + 2 << ' ' << i + 4 << ' ' << i + 5 << '\n';
        }
    }
}

全是注意力

2025牛客寒假算法基础集训营5 个人题解

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码