cbyyx

编辑于 2023-12-22 22:02

+ 关注

小白月赛84出题人题解

update: E题python选手读入可能会出问题，现已对赛时提交返回错误代码重测，由于出题人不会python，对于赛时这个问题无法解决，对此深感抱歉orz。

对于 $F$ 题由于数据问题导致了极少数人本应返回答案错误却返回答案正确，对此出题人深表抱歉，数据已更新，给大家带来的不便敬请谅解。

A.打靶

判断一下是否 $𝑛 − 𝑚 \geq 𝑌 − 𝑋$ 即可，注意判断 $𝑌 \geq 𝑋$ 。

复杂度 $𝑂(1)$ 。

#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        long long n, m, X, Y;
        cin >> n >> m >> X >> Y;
        if (n - m >= Y - X && Y >= X)cout << "Yes\n";
        else cout << "No\n";
    }
}

B.小蓝的疑惑

第一种解法（常规解法）：

前置知识：对于任意两个正整数 $𝑎, 𝑏$ 都有 $𝑎 ∗ 𝑏 = gc𝑑(𝑎, 𝑏) ∗ 𝑙𝑐𝑚(𝑎, 𝑏)$ 。

设 $𝑥 = 𝑔𝑐𝑑(𝑎, 𝑏) ∗ 𝑙𝑐𝑚(𝑎, 𝑏)$ ，对 $𝑥$ 进行因数分解，可以找出所有的 $𝐴, 𝐵$ 使得 $𝐴 ∗ 𝐵 = 𝑥$ 。

对所有的 $𝐴, 𝐵$ 判断是否满足 $𝑔𝑐𝑑(𝐴,𝐵) = 𝑔𝑐𝑑(𝑎, 𝑏)$ 且 $𝑙𝑐𝑚(𝐴, 𝐵) = 𝑙𝑐𝑚(𝑎, 𝑏)$ 即可。

复杂度 $𝑂(\sqrt{x})$ 。

#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        long long x, y;
        cin >> x >> y;
        long long res = x * y;
        bool f = 0;
        for (long long i = 1; i * i <= res; i++) {
            if (res % i == 0) {
                long long j = res / i;
                if (gcd(i, j) == x && lcm(i, j) == y) {
                    cout << i << ' ' << j << '\n';
                    f = 1;
                    break;
                }
            }
        }
        if (!f)cout << -1 << '\n';
    }
}

第二种解法：

前置知识：对于任意两个正整数 $𝑎, 𝑏$ 都有 $𝑔𝑐𝑑(𝑎, 𝑏) | 𝑙𝑐𝑚(𝑎, 𝑏)$ 。

由于上述条件在，只需要判断一下给定的 $𝑋, 𝑌$ 是否符合 $𝑋 | 𝑌$ 的条件，若满足直接输出 $𝑋, 𝑌$ 即为答案，否则输出 $−1$ 。

复杂度 $𝑂(1)$ 。

#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        long long x, y;
        cin >> x >> y;
        if (y % x == 0)cout << x << ' ' << y << '\n';
        else cout << -1 << '\n';
    }
}

以上两种解法复杂度均能通过。

C.𝑘级序列

假设 $𝑏0 = −𝐼𝑁𝐹$ ，对于 $∀1 ≤ 𝑖 ≤ 𝑛$ ，设 $𝑐𝑖 = 𝑎𝑖 − 𝑘, 𝑑𝑖 = 𝑎𝑖 + 𝑘$ ，判断是否 $𝑑𝑖 ≥ 𝑏𝑖−1$ 即可，如果满足则令 $𝑏𝑖 = 𝑚𝑎𝑥(𝑏𝑖−1, 𝑐𝑖)$ ，否则输出 $𝑁𝑜$ 。

复杂度 $𝑂(𝑛)$ 。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
long long a[N];
long long b[N];
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        b[0] = -0x3f3f3f3f3f3f3f3f;
        bool f = 1;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            long long c = a[i] - k, d = a[i] + k;
            if (d >= b[i - 1])b[i] = max(b[i - 1], c);
            else f = 0;
        }
        if (!f)cout << "No\n";
        else cout << "Yes\n";
    }
}

D.Reverse

可以发现翻转的区间有一部分贡献的答案和翻转前贡献的答案一样。

已知每次询问独立，对于每次询问，快速查询区间 $[1, 𝑙 − 1]$ 和 $[𝑟 + 1, 𝑛]$ 中有多少段连续的 $1$ 。

设 $𝑝𝑟𝑒[𝑖]$ 为第 $𝑖$ 个字符前面(包括第 $𝑖$ 个字符)中最近的 $0$ 出现的位置。

设 $𝑠𝑢𝑓[𝑖]$ 为第 $𝑖$ 个字符后面(包括第 $𝑖$ 个字符)中最近的 $0$ 出现的位置。

设 $𝐿 = 𝑙，𝑅 = 𝑟$ 。

若 $𝑠[𝑙 − 1] = ' 1'$ ，则更新 $𝑅 = 𝑝𝑟𝑒[𝑅]$ 。

若 $𝑠[𝑟 + 1] = ' 1'$ ，则更新 $𝐿 = 𝑠𝑢𝑓[𝐿]$ 。

然后对结果加上区间 $[𝐿, 𝑅]$ 中贡献的答案即可。

注意一些代码上的细节。

其中快速查询区间的贡献可以通过前缀和预处理做出。

复杂度 $𝑂(𝑛 + 𝑞)$ 。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int pre[N], suf[N];
int dp[N][2];
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    s = "0" + s + "0";
    int last = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '0')last = i;
        pre[i] = last;
        dp[i][0] = dp[i - 1][0];
        if (s[i] == '1' && s[i - 1] == '0')dp[i][0]++;
    }
    dp[n + 1][1] = 0;
    last = n + 1;
    for (int i = n; i >= 0; i--) {
        if (s[i] == '0')last = i;
        suf[i] = last;
        dp[i][1] = dp[i + 1][1];
        if (s[i] == '1' && s[i + 1] == '0')dp[i][1]++;
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        int L = l, R = r;
        int res = dp[l - 1][0] + dp[r + 1][1];
        if (s[l - 1] == '1')R = pre[R];
        if (s[r + 1] == '1')L = suf[L];
        if (R >= L) {
            if (s[L] == '0')res += dp[R][0] - dp[L - 1][0];
            else res += dp[L][1] - dp[R + 1][1];
        }
        if (s[l - 1] == '1' && s[r + 1] == '1' && R < L)res--;
        cout << res << '\n';
    }
}

E.Dog vs Cat

如果序列长度为 $1$ ，那么看操作次数即可判断谁胜谁负。

如果序列长度为 $2$ ，可以发现：

如果序列是形如 $\lbrace 𝑥, 𝑥 + 1\rbrace$ 的形式，那么第一个操作的人为了不败，只能选择第二个元素进行操作，此时若 $𝑥 = 0$ ，则第一个人输掉了比赛，否则序列将会变成 $\lbrace 𝑥, 𝑥\rbrace$ 的形式，此时第二个人必败。

否则第一个人必败。

如果序列长度大于 $2$ ，则仅有当 $𝑥 = 0$ 才会分出胜负，否则比赛将一直进行。

证明：若当 $𝑥 ! = 0$ 时就分出胜负，我们不妨回到最后一步，此时行动的人如果选择序列中的某一个 $𝑥$ 进行操作，则 $𝑥$ 更新为 $𝑥 − 1$ ，且 $𝑐𝑛𝑡[𝑥] = 1$ ，已知区间长度大于 $2$ ，因此此时行动的人并不会被判负，因此当 $𝑥 ! = 0$ 时就分出胜负是不可能的。

由上述可知，最终 $0$ 的个数为 $\lfloor \frac{n-1}{2} \rfloor$ ，其余元素全为 $1$ 时为最终状态，计算总行动次数，判断奇偶即可获得答案。

复杂度 $𝑂(𝑛)$ 。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)cin >> a[i];
        if (n == 1) {
            if (a[1] == 0 || a[1] & 1)cout << "Dog\n";
            else cout << "Cat\n";
        } else if (n == 2) {
            if (a[1] > a[2])swap(a[1], a[2]);
            if (a[2] == 0)cout << "Dog\n";
            else {
                if (a[2] == a[1] + 1) {
                    if (a[1] == 0)cout << "Dog\n";
                    else cout << "Cat\n";
                } else cout << "Dog\n";
            }
        } else {
            int i = (n - 1) / 2;
            int j = n - i;
            long long res = 0;
            int cnt0 = 0;
            for (int i = 1; i <= n; i++)res += a[i], cnt0 += (a[i] == 0);
            if (res == 0 || n - cnt0 <= cnt0)cout << "Dog\n";
            else {
                res -= j;
                if (res & 1)cout << "Cat\n";
                else cout << "Dog\n";
            }
        }
    }
}

F.小蓝的构造

对于本题，首先我们可以知道，当且仅当 $𝑡[1] = ′0′$ 且 $𝑡[𝑛] == ′1′$ 时, $𝑓(𝑡, 𝑛 − 1) = 1$ ，否则， $𝑓(𝑡, 𝑛 − 1) = 0$ ，那么，当题目中给定的 $𝑓(𝑡, 𝑛 − 1) = 0$ 时，我们可以直接构造出 $𝑡[𝑛] = 0$ ，并且认为 $𝑛 − = 1$ ，综上所述，我们可以找到一个新的 $𝑛$ 使得 $𝑓(𝑡, 𝑛 − 1) = 1$ ，此时则必有 $𝑡[1] = ′0′$ && $𝑡[𝑛] = ′1′$ 才能使得题目有解，于是我们可以知道，两端端点，即此时的 $𝑡[1],𝑡[𝑛]$ 的值是定的。

假设现在 $𝑙 = 1, 𝑟 = 𝑛$ ， $𝑑𝑝[1]~𝑑𝑝[𝑛 − 1]$ 表示当前构造出的串中 $𝑓(𝑡^1 , 1)$ ~ $𝑓(𝑡^1, 𝑛 − 1)$ 。

接着考虑从第 $𝑙, 𝑟$ 个位置转移到第 $𝑙 + 1$ ， $𝑟 − 1$ 个位置造成的影响（即从两端往中间构造），当 $𝑙 + 1$ 并且 $𝑟 − 1$ 之后，将不会对 $𝑑𝑝[𝑛 − 𝑙]$ 造成贡献，并且由于串 $t^1$ 的两端一定是 $′0′, ′1′$ ，所以我们不管第 $𝑙, 𝑟$ 个位置填什么，最终只会使得 $𝑑𝑝[𝑛 − 𝑙]$ 的值增加不超过 $2$ 。于是我们可以考虑从两端向里的过程中维护 $𝑑𝑝[1]$ ~ $𝑑𝑝[𝑛 − 1]$ ，当我们左端点更新为 $𝐿$ 时， $𝑑𝑝[𝑛 − 𝐿] + 2 < 𝑓(𝑡, 𝑛 − 𝐿)$ 则一定无解。

接下来考虑三种情况

$1$ 、 $𝑓(𝑡, 𝑛 − 𝐿) − 𝑑𝑝[𝑛 − 𝐿] = 0$ ，此时第 $𝑙$ 个位置一定为 $′1′$ ，第 $𝑟$ 个位置一定为 $′0′$ 。

$2$ 、 $𝑓(𝑡, 𝑛 − 𝐿) − 𝑑𝑝[𝑛 − 𝐿] = 1$ , 此时第 $𝑙, 𝑟$ 个位置要么都是 $′0′$ ,要么都是 $′1′$ 。两种情况分别维护即可

$3$ 、 $𝑓(𝑠, 𝑛 − 𝐿) − 𝑑𝑝[𝑛 − 𝐿] = 2$ , 此时第 $𝑙$ 个位置一定为 $′0′$ ，第 𝑟 个位置一定为 $′1′$ 。

综上递归维护即可，最终时间复杂度 $𝑂(𝑛 ∗ 2^{\frac{n}{2}})$ 。

#include<bits/stdc++.h>
using namespace std;
int f[50];//表示f(t,1)~f(t,n-1)
int a[50];//表示dp(1)~dp(n-1)
int res[50];
int ans[50];//最终输出的答案
int n;
void updatel(int l, int d, int v,
             int op) {//更新第[1,d-1]和第 l 位产生的贡献
    for (int i = 1; i < d; i++) {
        if (res[i] == v)a[l - i] += op;
    }
}
void updater(int r, int d, int v,
             int op) {//更新第[d+1,n]和第 r 位产生的贡献
    for (int i = d + 1; i <= n; i++) {
        if (res[i] == v)a[i - r] += op;
    }
}
void dfs(int l, int r) {
    for (int i = 1; i <= n; i++) {
        if (a[i] > f[i])return ;
    }
    if (l > r) {
        for (int i = 1; i < n; i++) {
            if (a[i] != f[i])return;
        }//不合法
        for (int i = 1; i <= n; i++)ans[i] = res[i]; //更新答案
        return;
    }
    if (l == r) { //若L=R,暴力判断此时第L个位置填1还是0即可
        res[l] = 1;
        updatel(l, l, 0, 1);
        dfs(l + 1, r - 1);
        updatel(l, l, 0, -1);
        res[l] = 0;
        updater(l, l, 1, 1);
        dfs(l + 1, r - 1);
        updater(l, l, 1, -1);
        return;
    }

    if (l == 1) {
        res[l] = 0, res[r] = 1;
        a[n - l] = 1;
        dfs(l + 1, r - 1);
    } else {
        int len = n - l;
        if (a[len] + 2 < f[len])return;

        if (a[len] == f[len]) {
            res[l] = 1, res[r] = 0;
            updatel(l, l, 0, 1);
            updater(r, r, 1, 1);
            dfs(l + 1, r - 1);
            updatel(l, l, 0, -1);
            updater(r, r, 1, -1);
        } else if (a[len] + 1 == f[len]) {
            res[l] = res[r] = 1;
            updatel(l, l, 0, 1);
            updatel(r, l, 0, 1);
            dfs(l + 1, r - 1);
            updatel(l, l, 0, -1);
            updatel(r, l, 0, -1);
            res[l] = res[r] = 0;
            updater(l, r, 1, 1);
            updater(r, r, 1, 1);
            dfs(l + 1, r - 1);
            updater(l, r, 1, -1);
            updater(r, r, 1, -1);
        } else {
            res[l] = 0, res[r] = 1;
            updatel(r, l, 0, 1);
            updater(l, r, 1, 1);
            a[r - l]++;
            dfs(l + 1, r - 1);
            updatel(r, l, 0, -1);
            updater(l, r, 1, -1);
            a[r - l]--;
        }
    }
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++)cin >> f[i];
    memset(ans, -1, sizeof ans);
    int m = n;
    while (n > 1 && f[n - 1] == 0)ans[n] = 0, n--;
    dfs(1, n);
    if (ans[1] != -1) {
        for (int i = 1; i <= m; i++)cout << ans[i];
        cout << '\n';
    } else cout << -1 << '\n';
}

2024最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(1) 回帖

加载中...

话题同步到我的动态回帖

小白月赛84出题人题解

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐