官方题解｜ACGO挑战赛#1

AC君

2024-03-11 14:31:51

发布于：浙江

123阅读

0回复

0点赞

直播预告

直播时间：3月2日（周六）下午4点-6点
直播地址： B站ACGO官方账号
直播内容：挑战赛#1复盘（欢迎观看大型翻车现场）
主讲人：小鱼老师

T1 - 算术排列

分析题目不难发现，大的数字能变小，小的数字不能变大，容易想到一个贪心的思路：

令当前数字为 $x$ ：

若 $x > n$ ，将 $x$ 整除 $2$ 。
若已经有数字 $y(1 \le y \le n, y = x)$ ，将 $x$ 整除 2。

重复以上操作直至 $x$ 变为 $0$ 或者找到一个没有得到的排列中的数字为止。

使用一个数组 $p$ 存储 $1$ 到 $n$ 一共 $n$ 个数字是否出现过。
若操作完整个数组 $p$ 后，以上条件满足则输出 $\tt{YES}$ 否则输出 $\tt{NO}$ 。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        vector<int> p(n + 1);
        for (int i = 0; i < n; ++i) {
            int x; cin >> x;
            while (x > 1 and (x > n or p[x]))
                x /= 2;
            p[x] = 1;
        }
        int cnt = 0;
        for (int i = 1; i <= n; ++i)
            if (p[i] == 1) ++cnt;
        cout << (cnt == n ? "YES" : "NO") << '\n';
    }
    return 0;
}

复杂度分析

对于数组中的每个数字，将其做处理的时间复杂度为 $\log{a_i}$ ，处理完整个数组时间复杂度为 $O(n\log{a_i}$ )。

T2 - 数组片段匹配

注意题目中标注要求满足条件的长度相同的子数组中，只需要 $\bf{存在}$ 数对 $p(x_i, y_i) (1 \le i \le k)$ 其中 $x_i = y_i$ 即可。

这点提示我们要关注相同的元素。那么对于两个相同的元素，各自形成的子数组，如果两者在原数组中距离较远，则包含其子数组长度越短，反之，包含其子数组的长度越长。

在原数组中令 $a_i = b_j(1 \le i < j \le n)$ 这个长度可以拆分成两个部分 $x$ 和 $y$ ，其中 $x = a_i, y = n - a_j$ ，那么最终我们要求的答案就是枚举数组中相邻的相同数字的位置 $x + y$ 即 $n - (a_j - a_i)$ 最大的就是答案。

若数组中没有重复数字，显然不存在满足条件的两个子片段。

AC代码

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 150000;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        int pre[N + 1], max_len = -1;
        memset(pre, -1, sizeof pre);
        for (int i = 0; i < n; ++i) {
            int x; cin >> x;
            if (pre[x] != -1)
                max_len = max(n - (i - pre[x]), max_len);
            pre[x] = i;
        }
        cout << max_len << '\n';
    }
    return 0;
}

复杂度分析

代码实现上，遍历数组 $a$ ，令外使用一个数组 $pre$ 记录数字 $x$ 在数组中出现的上一个位置，随着遍历不断更新，得到答案。时间复杂度为 $O(n)$ 。

T3 - 勇敢的冒险者

题目大意

冒险者在一条 $x$ 轴上，并处于点 $0$ ，假设当前的位置是 $y$ ,现在正在进行第 $k$ 次跳跃,有两种跳跃的方案

向前跳跃到 $y+k$
向后跳跃到 $y-1$

冒险者要到达点 $x$ 点

题意分析

问最少跳跃几次，冒险者就能到达 $x$ 点

解题思路

由于一开始冒险者一定是在点 $0$ 的，并且 $x$ 点一定是大于 $0$ 的，很容易看出一开始只要一直执行 【方案一】 即 $y+k$ 就一定能到达 $\ge x$ 的位置。

如果执行了 $k$ 次后正好能到达 $x$ 点那么答案为 $k$

那如果超过了 $x$ 点呢? 这个时候我们需要考虑用 【方案二】 来进行干预了。

接下来我们分类讨论一下：

进行 $k$ 次操作后，到达了 $x+1$ 的位置，那么我们只需要执行一次 【方案二】
进行 $k$ 次操作后，到达了 $x+p$ 的位置，其中 $p$ $(p\gt 1)$ 为超出 $x$ 的部分

这个时候可以有两种办法消除这个 $p$ 。

第一种选择执行 $p$ 次 【方案二】

第二种选择在之前跳跃的某次 【方案一】 将它改为 【方案二】

显然这里选择 【方案二】 是最优的

所以我们只需要关心，经历几次 $k$ 能跳到 $\ge x$ 的点上就行了，这里可以使用二分去快速找到 $k$

时间复杂度解析

对于每个 $x$ 都需要进行一次二分即复杂度为： $O(\log_{2} n)$

代码演示

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll getSum(ll r) {
    return (1 + r) * r / 2;
}
int main() {
    int t,x;
    cin >> t;
    while(t--) {
        cin >> x;
        int l = 0,r = x;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if (getSum(mid) >= x)r = mid - 1;
            else l = mid + 1;
        }
        ll s = getSum(l);
        if (s == x) {
            cout << l << endl;
        }else {
            if (s - 1 == x) {
                cout << l + 1 << endl;
            }else {
                cout << l << endl;
            }
        }
    }
    return 0;
}

T4 - 超能战士

题目大意

有 $n$ 只怪兽，每只怪兽都有生命值 $h_i$ 和攻击力 $p_i$ ，超能战士每次可以对所有活着的怪兽造成 $k$ 点伤害。

怪兽会在每次超能战士攻击后进行反击，活着最弱的怪兽会降低超能战士攻击伤害，降为 $k - p_i$

题意分析

求问超能战士能不能消灭所有的怪兽

解题思路

从题中可以发现，超能战士的攻击力 $k$ 同时可以看做是超能战士的血量，当 $k \le 0$ 的时候，如果场上还有怪兽，则不能消灭所有怪兽。

超能战士每进行一次攻击可以消灭所有当前血量 $\le k$ 的怪兽，我们可以模拟这个过程直到超能战士的攻击力 $\le 0$ ，所以重点考虑怎么去模拟这个过程，如果用暴力的方式，一遍一遍让怪兽的血量减去 $k$ ，那么复杂度为 $O(n \cdot k )$ ，超时！

实际上我们只需要找到第一个不能被杀死的怪兽，即第一个血量 $\gt k$ 的怪兽。

我们可以先按照血量从小到大排序，我们记找到第一个血量 $\gt k$ 怪兽的下标为 $i$ ，那么 $\lt i$ 的怪兽都视为死亡， $\ge i$ 的怪兽都为存活。由于血量是有序的了，满足单调性，我们可以使用二分。由于怪兽的血量是会变化的，在二分的时候要将怪兽的血量减去超能战士累积攻击的伤害。

我们还有个问题没有解决，如何在存活的怪兽中，找到最弱的，即攻击力最小的。存活的下标区间为 $[i,n)$ ，我们可以贪心最小值，倒着遍历不断看右边的最小值与当前值哪一个更小，来维护一个最小值数组。

时间复杂度解析

维护小最值数组，需要遍历所有怪物，复杂度为 $O(n)$

查找第一个不能杀死的怪物，用到了二分，直到 $k \le 0$ 时，结束模拟过程。复杂度为 $O(n \cdot \log_{2} n)$

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int t,n,k;
int s = 0;
struct w{
    int h,p;
}arr[N];
int zx[N];
bool cmp(const w &a,const w &b) {
    return a.h < b.h;
}
int fd(int l,int r,int target) {
    while(l <= r) {
        int mid = (l + r) >> 1;
        if (arr[mid].h - s > target)r = mid - 1;
        else l = mid + 1;
    }
    return l >= n ? -1 : l;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while(t--) {
        s = 0;
        cin >> n >> k;
        memset(zx,0,sizeof zx);
        for(int i=0;i<n;i++) cin >> arr[i].h;
        for(int i=0;i<n;i++) cin >> arr[i].p;
        sort(arr,arr+n,cmp);
        int l = 0,r = n - 1;
        zx[r] = arr[r].p;
        for(int i=r-1;i>=0;i--) {
            zx[i] = min(zx[i+1],arr[i].p);
        }
        while(k > 0) {
            int idx = fd(l,r,k);
            if (idx != -1) {
                l = idx;
            }
            int p = zx[idx];
            s += k;
            if (s >= arr[r].h)break;
            k -= p;
        }
        if (s >= arr[r].h) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

T5 - 迷宫L

题目大意

有一个 $0$ 和 $1$ 组成的矩阵，有一个操作，选择一个 $2\times2$ 的子矩阵，在这个子矩阵中选择一个 $L$ ，把这个 $L$ 中的三个数全部变成 $0$ ，如果选择的这个 $L$ 中至少包含一个 $1$ 的话，则可以操作。

题意分析

问最多可以操作多少次

解题思路

如果要让次数最多，那我们要尽可能用上每一个 $1$ ，换句话说最好一次只消除一个 $1$ 。我们可以发现当一个 $2\times2$ 的子矩阵中，存在两个 $0$ 的情况下，可以一次只消除一个 $1$

那么如果没有出现以上这种情况，我们可以先进行一次操作，这样必定能构造出来在 $2\times2$ 中出现两个 $0$ 的情况。这个时候分类讨论一下，我们记 $1$ 出现的次数为 $on$

如果子矩阵中出现了一个 $0$ 则答案为 $on - 1$
如果一个 $0$ 都没有的情况，答案为 $on - 2$

时间复杂度解析

我们需要遍历一次矩阵，复杂度为： $O(n \times m)$

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int t,n,m;
char x;
int on,zn;
int mp[N][N];
int main() {
    cin >> t;
    while(t--) {
        on = zn = 0;
        cin >> n >> m;
        memset(mp,0,sizeof mp);
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                cin >> x;
                mp[i][j] = x - '0';
            }
        }
        int flag = 0;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                if (mp[i][j])on++;
                else zn++;
                if (i+1 <= n && j+1 <=m) {
                    int cnt = 4 - (mp[i][j] + mp[i+1][j] + mp[i][j+1] + mp[i+1][j+1]);
                    if (cnt >= 2) {
                        flag = 1;
                    }
                }
            }
        }
        if (flag) {
            cout << on << endl;
        } else {
            if (zn) {
                cout << on - 1 << endl;
            } else {
                cout << on - 2 << endl;
            }
        }
    }
    return 0;
}

T6 - 质数花瓣

题目大意

在一个长度为 $n$ 的数字区间内，寻找符合要求的质数。

题意分析

如果每次去掉数字的最后一位，仍是质数，则满足要求

解题思路

素数筛模板题，可以套用埃氏筛或欧拉筛

如果你的埃氏筛超时了，请将标记数组换成bitset容器

如果你的欧拉筛超内存了，请将数据类型换成short

当然此题不止这一种解法，你还可以按数字位搜索，找到符合条件的数。

时间复杂度

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

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 10;
bitset<N> st;
void get(int r) {
    st[1] = 1;
    for(int i=2;i<=r/i;i++) {
        if (st[i])continue;
        for(int j=i*i;j<=r;j+=i) {
            st[j] = 1;
        }
    }
}
int main() {
    int n;
    cin >> n;
    int l = pow(10,n-1),r = pow(10,n);
    get(r);
    for(int i=l;i<r;i++) {
       int f = 1;
       int x = i;
       while(x) {
           if (st[x]) {
               f = 0;
               break;
           }
           x /= 10;
       }
       if (f)cout << i << endl;
    }
    return 0;
}