grape_king

发布于 03-28 21:09 广东

小白月赛113题解

A题 2025

考察循环遍历

题解：遍历一遍即可

代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int sum = 1;
string s, ans = "NO";
void solve() {
    cin >> s;
    for (auto c : s) {
        if (c == '-') sum--;
        else sum *= 2;
        if (sum >= 2025) {
            ans = "YES";
            break;
        }
    } cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

B题好字符串

考察思维

题意：是否能够删除某个字符或者不删除，使得字符串的相邻每位的字符都不相同。

题解：枚举每一位字符，统计下有相邻字符相同的数目，如果小于等于 $1$ ，则输出 YES，否则输出 NO。

代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
string s;
int n, sum;
void solve() {
    cin >> n >> s;
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) sum++;
    } cout << (sum <= 1 ? "YES" : "NO") << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

C题连续数组

考察思维

题意：给你 $q$ 个数组，现在需要将这 $q$ 个数组进行组合，但要保持每个数在原有的数组中的相对顺序不变，问是否能组成一个连续数组。

题解：首先要想组合成连续数组，就得保证原有的每个数组是严格升序的，然后只需要将所有数放到一个数组中，排个序，如果是一个连续的，则说明是个连续数组。

代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int sum, k, q, pre, x;
set<int> A;
string s = "YES";
void solve() {
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> k; pre = 0; sum += k;
        for (int i = 1; i <= k; i++) {
            cin >> x;
            if (x <= pre) s = "NO";
            pre = x; A.insert(x);
        }
    }
    if (sum != A.size() || *A.rbegin() - *A.begin() + 1 != A.size()) s = "NO";
    cout << s << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

D题 mex

考察思维 / 模拟能力

题意：有一种操作，每次可以将数组中的每个元素减去数组的 $\operatorname{mex}$ ，问需要多少次才能将数组中的每个数都变为一样的数。

题解：首先如果一开始数组中所有数都是一样的，则直接输出 $0$ 即可；其次就是一开始数组中没有 $0$ ，那数组的初始 $\operatorname{mex}=0$ ，则数组永远都不肯变为一样的数，输出 $-1$ 即可；现在如果初始值 $\operatorname{mex}$ 不为 $0$ 该怎么得到答案呢，因为 $\operatorname{mex}$ 是在某处没出现断开的数，所以一开始可以将数组分为几部分连续的数组成的数组，如 $[0,1,3,4,7]$ ，可以分为 $[0,1]、[3,4]、[7]$ ，一开始 $\operatorname{mex}=2$ ，那么就变为 $[0,0]、[1,2]、[5]$ ，然后下一个 $\operatorname{mex}=3$ ，变为 $[0,0]、[0,0]、[2]$ ，那么接下来 $\operatorname{mex}=1$ ，变为 $[0,0]、[0,0]、[1]$ ，最后全变为 $0$ ，可以发现每段里面的数其实是同时变为 $0$ 的，那么答案就是统计当前段的第一个数值减去上一段的结尾数值减一的总和。

所以只需要先对数组排序，然后特判下，记住特判顺序一定是先特判 $0$ 的情况，再特判 $-1$ 的情况，最后 $for$ 循环一遍统计答案即可。
不过这题有个结论，答案就是数组中的 $\max + 2$ 减去数组中值的种类数，手推一下就能发现。

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

代码一：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 n, pd, ans;
i64 a[100005];
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        if (a[i] != a[1]) pd = 1;
    }
    if (!pd) cout << "0\n", exit(0);
    if (a[1]) cout << "-1\n", exit(0);
    for (int i = 2; i <= n; i++) ans += max(0LL, a[i] - a[i - 1] - 1);
    cout << ans + 1 << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

代码二：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 n, ans;
set<i64> s;
void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        i64 x; cin >> x;
        s.insert(x);
    }
    if (s.size() == 1) cout << "0\n", exit(0);
    if (*s.begin() != 0) cout << "-1\n", exit(0);
    cout << *s.rbegin() + 2 - s.size() << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

E题可划分数组

考察 $dp$

题意：将数组划分为 $k$ 段区间，要求 $k$ 段区间内的每个数都能在此区间内至少找到一个非自身的数与之不互质，问这个 $k$ 最大为多少。

方法一：

纯 $dp$ 写法

对于每个位置 $i$ ，我们用 $pre$ 数组记录左侧与 $a_i$ 不互质的最近的 $j$ ( $1\leqq j<i$ )，用 $nxt$ 数组记录右侧与 $a_i$ 不互质的最近的 $j$ ( $i<j\le n$ )，然后再双指针的形式遍历每个区间，来判断此区间是否符合要求，而对于一个区间 $[l,r]$ 若要满足要求，则需要保证 $\forall l\leqq i\leqq r$ ，都有 $nxt_i\le r\ or\ pre_i\geqq l$ ，如果满足则合法，不满足则不合法，然后进行 $dp$ 转移，另外还要保证 $dp_{l-1}$ 存在，否则不能转移， $dp_r=\max(dp_r,dp_{l-1}+1)$ 。

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

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int n, a[2005], dp[2005], pre[2005], nxt[2005];
void solve() {
    cin >> n;
    memset(nxt, 0x3f, sizeof nxt);
    memset(dp, -1, sizeof dp); dp[0] = 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (__gcd(a[i], a[j]) != 1) {
                nxt[j] = min(nxt[j], i);
                pre[i] = max(pre[i], j);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int mn = 1e9;
        for (int j = i; j >= 1; j--) {
            if (nxt[j] > i) mn = min(mn, pre[j]);
            else if (mn >= j && dp[j - 1] != -1) dp[i] = max(dp[i], dp[j - 1] + 1);
        }
    } cout << dp[n] << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

方法二：

质因数分解+双指针

题解：由于 $n\le 2\times 10^3$ ，所以我们可以直接双指针形式暴力枚举每个区间是否满足条件，由于每个数最大才 $10^9$ ，所以可以先预处理出每个数的质因子，一个数质因子不超过 $9$ 个，可以直接暴力质因数分解，现在枚举每个 $r$ ，即区间的右端点，然后左端点从右往左移，每次把未匹配到与之不互质的数存起来，用 $sum$ 来记录有多少数匹配到了，如果 $sum=r-l+1$ ，那么这部分值就可以进行转移，一样要保证 $dp_{l-1}$ 存在，即 $dp_r=\max(dp_r,dp_{l-1}+1)$ ，记住一定要全部遍历进行转移，不能直接贪心的找到最短区间，然后进行转移，这样并不是最优的，样例二就是个例子。

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

这种写法显然比较过于麻烦了，还是方法一好写些。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> pi;

vector<int> stk;
vector<int> g[2005], f[20005];
int a[2005], dp[2005], vis[20005], vis2[2005];
void ft(int id) {// 质因数分解
    for (int i = 2; i <= a[id] / i; i++) {
        if (a[id] % i == 0) {
            while (a[id] % i == 0) a[id] /= i;
            g[id].push_back(i);
            stk.push_back(i);
        }
    }
    if (a[id] > 1) {
        g[id].push_back(a[id]);
        stk.push_back(a[id]);
    }
}

int get_id(int x) {
    return lower_bound(stk.begin(), stk.end(), x) - stk.begin();
}
void solve() {
    int n; cin >> n;
    memset(dp, -1, sizeof dp); dp[0] = 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) ft(i);
    sort(stk.begin(), stk.end());
    stk.erase(unique(stk.begin(), stk.end()), stk.end());
    for (int i = 1; i <= n; i++)
        for (int &v : g[i])
            v = get_id(v);

    for (int r = 1; r <= n; r++) {
        int sum = 0;
        for (int l = r; l >= 1; l--) {
            bool fg = false;
            for (auto p : g[l]) {
                if (vis[p]) fg = true;
                vis[p] = 1;
                for (auto id : f[p]) {
                    if (!vis2[id]) {
                        sum++; vis2[id] = 1;
                    }
                }
                f[p].clear(); f[p].push_back(l);
            }
            if (fg) {
                sum++;
                vis2[l] = 1;
            }
            if (sum == r - l + 1 && dp[l - 1] != -1) dp[r] = max(dp[r], dp[l - 1] + 1);
        }
        for (int l = 1; l <= r; l++) {
            vis2[l] = 0;
            for (auto p : g[l]) {
                f[p].clear();
                vis[p] = 0;
            }
        }
    } cout << dp[n] << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

F题最小差值

考察数学

题意：大体就是给你两个数组 $a$ 和 $b$ ，需要我们找到一个数 $k$ ，使得 $\left | (\sum_{i=1}^{n}\left | a_i - x \right |) - (\sum_{j=1}^{m}\left | b_j - x \right |) \right |$ 值最小，如果有多个满足最小，则 $k$ 要最小。

题解：假设我们有个数组为 $[1,3,5,7]$ ，那么我们可以将其看为几段区间，即分为 $[-2e9,1]$ ， $[1,3]$ ， $[3,5]$ ， $[5,7]$ ， $[7,2e9]$ 五段区间，假设我们 $x$ 在区间 $[3,5]$ 内选，那么对于任意的 $x$ ，数组中都有 $2$ 个数小于等于 $x$ 、两个数大于等于 $x$ ，这样我们就可以确定数组内所有数所产生的贡献了，然后我们就可以在这段区间内选取我们所需要的 $x$ 值。

回归题目来看，多了一个数组，那么我们其实可以将两个数组整合到一起，排序后，便一样能得到一些区间，然后对每段区间都单独处理，假设在当前区间内，数组 $a$ 有 $c1$ 个小于等于 $x$ 的数， $c2$ 个大于等于 $x$ 的数，数组 $b$ 有 $c3$ 个小于等于 $x$ 的数，有 $c4$ 个大于等于 $x$ 的数，令 $prea$ 为数组 $a$ 的前缀和数组， $preb$ 为数组 $b$ 的前缀和数组， $nxta$ 为数组 $a$ 的后缀和数组， $nxtb$ 为数组 $b$ 的后缀和数组，那么上述的式子便转化为 $(x\times (c1-c2) - \operatorname{prea(c1)}+\operatorname{nxta(c2)})-(x\times (c3-c4) - \operatorname{preb(c3)}+\operatorname{nxtb(c4)})=x\times (c1+c4-c2-c3)+\operatorname{nxta(c2)})+\operatorname{preb(c3)}-\operatorname{prea(c1)}-\operatorname{nxtb(c4)}$ 。

我们令 $k=(c1+c4-c2-c3)，b=\operatorname{nxta(c2)})+\operatorname{preb(c3)}-\operatorname{prea(c1)}-\operatorname{nxtb(c4)}$ ，最后就可以看成是 $\left | k\times x+b \right |$ 的一个带绝对值的一次函数，因为是取绝对值，所以极小值应该取在 $x=(\frac{-b}{k})\ or\ (\frac{-b}{k}+1)\ or\ (\frac{-b}{k}-1)\ or\ l\ or\ r$ ，我们只需要对这五个位置处理下即可。

不过这题也可以三分写，因为对于每个区间都只有一个极小峰值。

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

代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PI;
vector<PI> st;
i64 n, m, ans, x, val, val2, k, b, c1, c2, l = -2000000000;
void solve() {
	cin >> n >> m; k = m - n;
    st.reserve(n + m + 1);
    st.push_back({-l, 0});
    while (n--) {
        cin >> x; b += x;
        st.push_back({x, 2});
    }
    while (m--) {
        cin >> x; b -= x;
        st.push_back({x, -2});
    }
    ans = l; val = abs(k * l + b);
    sort(st.begin(), st.end());
    for (auto &[r, x] : st) {
        if (k != 0) {
            c1 = -b / k;
            for (int i = -1; i <= 1; ++i) {
                c2 = c1 + i;
                if (c2 < l) c2 = l;
                if (c2 > r) c2 = r;
                val2 = abs(k * c2 + b);
                if (val2 < val) ans = c2, val = val2;
            }
        }
        k += x; b -= x * r; l = r;
    } cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

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

大家都在关注

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

已采纳

采纳

精彩回帖

精彩

全部评论

(5) 回帖

加载中...

话题同步到我的动态回帖

小白月赛113题解

A题 2025

B题好字符串

C题连续数组

D题 mex

E题可划分数组

F题最小差值

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐

小白月赛113题解

A题 2025

B题 好字符串

C题 连续数组

D题 mex

E题 可划分数组

F题 最小差值

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐

B题好字符串

C题连续数组

E题可划分数组

F题最小差值