官方题解｜挑战赛#2

AC君

2024-03-25 10:34:06

发布于：浙江

100阅读

0回复

0点赞

直播预告

直播时间：3月23日（周六）下午4点半开始
直播地址： B站ACGO官方账号
直播内容：赛事复盘（欢迎观看大型翻车现场）
主讲人：小鱼老师

官方题解｜挑战赛#2

T1 - 不能整除

题目解析

我们可以拿题面中 $n = 3$ 且 $k = 5$ 去思考，这里的答案是 $7$ 。

让我们展开这个序列 $1,2,\underline{3},4,5,\underline{6},7,8,\underline{9},10,11,\underline{12} ...$ ，其中标下划线的数，为 $3$ 的倍数。

我们在算个数的时候，是要忽略 $3$ 的倍数的。

那么我们发现每次经过 $n - 1$ 个数，才会出现一个 $n$ 的倍数。

那么我们看一下要经过几次 $n - 1$ 会数到我们想到的数，还是以上面的数举例子。

第1轮： $1，2，\underline{3}$
第2轮： $4，5，\underline{6}$
第3轮： $7，8，\underline{9}$

我们观察，想要数到第 $5$ 个，要数 $3$ 轮， $7$ 在第三轮出现，这个轮次可以直接求得为： $\lceil \frac{k}{n-1} \rceil$ ，那么前两轮中每次我们都会少数 $1$ 个。

最终的答案为 k + 轮次 - 1。

AC代码

#include <bits/stdc++.h>
using namespace std;
int ceil(int a,int b) {
    return a / b + (a % b > 0);
}
int main() {
    int t,n,k;
    cin >> t;
    while(t--) {
        cin >> n >> k;
        cout << k + ceil(k,n-1) - 1 << endl;
    }
    return 0;
}

也可以写成下面这种形式

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t,n,k;
    cin >> t;
    while(t--) {
        cin >> n >> k;
        cout << k + (k - 1) / (n - 1) << endl;
    }
    return 0;
}

复杂度

由于我们已经推算出，计算的公式了，所以对于任何情况都是 $O(1)$ 。

T2 - 来自领导的烦恼

特邀出题人Macw题解：原链接

题目解析

本题可以使用动态规划或递归的方式来实现，本质上是一道01背包的变型题。假设一共有 $n$ 名员工，每一位员工的技能水平用 $a[i]$ 表示。要使得两个部门的员工技能总和之差最小，意思就是尽可能地将一个部门的技能之和”凑“到 $\sum\limits_{i=1}^{n}a[i] \times \frac{1}{2}$ ，也就是所有员工技能总和的一半。套用背包问题的模板，每一位员工就是每一件“物品”，背包的容量就是“所有员工技能总和的二分之一”。

AC代码

参考代码在01背包的基础上进行了内存优化，将二维dp数组转换成了一维dp数组。其中：

arr[i] 表示第i个员工的技能水平。
sum 表示所有员工技能水平之和。

#include <iostream>
#include <cmath>
using namespace std;

int n, sum;
int arr[5005], dp[100005];

int main(){
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> arr[i];
        sum += arr[i];
    }
    int half = sum / 2;
    for (int i=1; i<=n; i++){
        for (int j=half; j>=0; j--){
            if (j - arr[i] >= 0){
                dp[j] = max(dp[j], dp[j-arr[i]] + arr[i]);
            }   
        }
    }
    cout << sum - 2*dp[half] << endl;
    return 0;
}

时间复杂度分析

本题通过两个for循环来填写dp表格，外层循环遍历每一个员工，内层循环遍历所有员工的技能水平之和。外层循环执行 $n$ 次，内层循环执行 $\sum\limits_{i=1}^{n}a[i]$ 次。因此，本道题目的时间复杂度为 $\Theta(n\times \sum\limits_{i=1}^{n}a[i])$ ，为 $O(n^2)$ 。

T3 - 星光交错的律动

特邀出题人Macw题解：原链接

题目解析

这道题可能跟博弈论有一点关系，没有学习过博弈论做起来应该问题也不大。思考一个问题，先手必胜的前提是什么？

先手必胜的前提是，在任何一种局面下，先手都有至少一种操作可以使后手处于必败的局面。
若先手进行任何操作后，后手都可以选择必胜的操作，则先手无法必胜。
如果当前玩家无法进行任何操作，那么对手获胜。

整体的思路就是通过递归不断搜索每一种决策情况，判断是否存在必胜的策略。

具体的实现方法：

创建两个函数，名为first和second。

first(x, y)函数返回当两位玩家分别选择数字x和y时，先手是否必胜。
second(x, y)函数返回当两位玩家分别选择数字x和y时，后手是否必胜。

两个函数来回交替调用对方，即在first(x, y)函数中调用second(x, y)函数，在second(x, y)中调用first(x, y)。如果存在必胜的策略，返回true，否则返回false。若先手玩家无法再进行操作时，也返回false。

AC代码

参考代码一：

#include <iostream>
#include <cstring>
using namespace std;

int vis[1005];
bool last(int x, int y);

bool first(int x, int y){
    bool isEnd, p1, p2;
    isEnd = p1 = p2 = true;
    if (x * 2 <= 1000 && !vis[x * 2]){
        isEnd = false;
        vis[x * 2] = 1;
        p1 = last(x*2, y);
        vis[x * 2] = 0;
    }
    if (x % 3 == 0 && !vis[x / 3]){
        isEnd = false;
        vis[x / 3] = 1;
        p2 = last(x / 3, y);
        vis[x / 3] = 0;
    }
    if (isEnd) return false;
    // 如果后手有一条方案会必死，那么先手就一定赢。
    return !(p1 && p2);  
}

bool last(int x, int y){
    bool isEnd, p1, p2;
    isEnd = p1 = p2 = true;
    if (y * 2 <= 1000 && !vis[y * 2]){
        isEnd = false;
        vis[y * 2] = 1;
        p1 = first(x, y * 2);
        vis[y * 2] = 0;
    }
    if (y % 3 == 0 && !vis[y / 3]){
        isEnd = false;
        vis[y / 3] = 1;
        p2 = first(x, y / 3);
        vis[y / 3] = 0;
    }
    if (isEnd) return false;
    return !(p1 && p2);  
}

int main(){
    int t, x, y;
    cin >> t;
    while(t--){
        memset(vis, 0, sizeof vis);
        cin >> x >> y;
        if (first(x, y)) cout << "Macw07" << endl;
        else cout << "Penelope_77" << endl;
    }
    return 0;
}

参考代码二：

decision(r)函数返回当两位玩家分别选择数字val[0]和val[1]时，r选手（先手为0，后手为1）是否必胜。

#include <iostream>
#include <cstring>
using namespace std;

int vis[1005];
int val[5];

bool decision(int r){
    bool isEnd, p1, p2;
    isEnd = p1 = p2 = true;
    if (val[r] * 2 <= 1000 && !vis[val[r] * 2]){
        isEnd = false;
        val[r] *= 2;
        vis[val[r]] = 1;
        p1 = decision(!r);
        vis[val[r]] = 0;
        val[r] /= 2;
    }
    if (val[r] % 3 == 0 && !vis[val[r] / 3]){
        isEnd = false;
        val[r] /= 3;
        vis[val[r]] = 1;
        p2 = decision(!r);
        vis[val[r]] = 0;
        val[r] *= 3;
    }
    if (isEnd) return false;
    return !(p1 && p2);  
}

int main(){
    int t, x, y;
    cin >> t;
    while(t--){
        memset(vis, 0, sizeof vis);
        cin >> x >> y;
        val[0] = x;
        val[1] = y;
        if (decision(0)) cout << "Macw07" << endl;
        else cout << "Penelope_77" << endl;
    }
    return 0;
}

复杂度分析

本道题目将通过深度优先搜索DFS的方式来实现，每一层递归模拟某一位玩家的两个决策（将数字乘二或将数字除以三）。因此本道题目的时间复杂度大致为 $O(2^d)$ ，其中 $d$ 表示递归的深度。考虑题目数据范围 $1 <= x, y <= 1000$ ，递归深度约为 $\log2(\frac{x+y}{2})$ ，完全可以在限定时间内通过所有的测试点。

T4 - 我心中珍藏的游戏

特邀出题人Macw题解：原链接

题目解析

题目问最多可以获得的额外伤害，其实就是询问在这些技能中，如何怎样选取一个最优的发动技能顺序使得攻击加成最大。我们可以把每一个技能看作成一个图的顶点，把每一个攻击加成看作图的边，权制为 $Ei,j$ 。由于 $Ei,j$ 与 $Ej,i$ 相等，则可以将这个图视为无向图。可以样样例抽象成下图：

考虑使用贪心的思想来解决本题，每次在图中找到权值最大的一条边选择即可，但图中不能出现环。因为是无向图，在考虑的时候可以忽略技能使用的顺序。接下来就是找一个最大生成树即可。

AC代码

#include <iostream>
#include <algorithm>
using namespace std;

int n, cnt, ans;
int f[805];
struct edge{
    int x, y, z;
} edges[700005];

bool cmp(edge a, edge b){
    return a.z > b.z;
}

int getf(int x){
    if (f[x] == x) return x;
    return f[x] = getf(f[x]);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i=1; i<=n; i++){
        f[i] = i;
        for (int j=1; j<=n; j++){
            int t; cin >> t;
            if (i == j || t == 0) continue;
            edges[++cnt] = (edge){i, j, t};
        }
    }
    sort(edges+1, edges+1+cnt, cmp);
    for (int i=1; i<=cnt; i++){
        int u = edges[i].x;
        int v = edges[i].y;
        int U = getf(u), V = getf(v);
        if (U != V){
            f[U] = V;
            ans += edges[i].z;
        }
    }
    cout << ans << endl;
    return 0;
}

时间复杂度分析

本道题可以使用最小生成树Kruskal算法来实现，将题目的模型抽象化后可以被看作为一个最多有 $\frac{(1+n)*n}{2} - n$ 条边的无向图（化简后可得 $\frac{n^2 - n}{2}$ )。注意一开始需要对每一条边进行排序。本道题的时间复杂度约为 $O(2\times n^2 \log_2{n})$ 。

T5 - 拳击教练

题目解析

对于每一个选手，我们需要找到能力值比他小的选手的数量，并且要排除死对头的情况。

我们可以先把所有选手的能力值，从小到大排序。

如原序列为：10 4 10 15，排序后 4 10 10 15。

那么如果我们想找到所有能力值低于10的选手数量，那么只需要找到大于等于10在序列中出现的第一个位置。这里大于等于10能力值的位置为 $2$ ，则有 $2 - 1$ 个人的能力值小于10，那这里就可以用二分去做了。

那么如处理，死对头呢？因为现在的答案是包含有死对头的情况的。

对于每个选手，我们只需要记录，所有能力值比这个选手小的，并且还是死对头的数量，这个可以在建立死对头关系的时候就处理。

AC代码

#include <bits/stdc++.h>
using namespace std;
int n,k;
int x,y;
int a[200010];
int b[200010];
int c[200010];
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        b[i] = a[i];
        c[i] = 0;
    }
    sort(a+1,a+n+1);
    while(k--) {
        cin >> x >> y;
        if (b[y] < b[x]) {
            c[x]++;
        } else if (b[y] > b[x]) {
            c[y]++;
        }
    }
    for(int i=1;i<=n;i++) {
        int idx = lower_bound(a+1,a+n+1, b[i]) - a;
        int ans = idx - c[i] - 1;
        cout << max(0,ans) << " ";
    }
    cout << endl;
    return 0;
}

复杂度

对于每个选手都要进行一次二分查找，则复杂度为 $O(n \cdot log_{2} n)$ 。

T6 - 一对好数

题目解析

这题最重要就是要往 $\&$ 运算突破。
如果能找到 $x，y$ ，那么他们必然包含 $a$ 。

例如： $a = 1，b = 8$ ，找到的 $x = 3，y = 5$ 。

$x = 3$ 转二进制：0011
$y = 5$ 转二进制: 0101

为了让 $x \ \& \ y = a，3 \ \& \ 5 = 1$ 。那么他们在二进制中必须要包含 $a$ 这里为 0001。

如果我把他们两个的0001都去了， $x$ 就变为 0010，我们记作 $x_1$ 。

$y$ 就变成 0100，我们记作 $y_1$ 既然 $x + y = b$ 。

那么我们推算 $(x_1 + a) + (y_1 + a) = b$ ，可以转为 $b - (a + a) = x_1 + y_1$ 。

并且 $x_1 + y_1$ 一定不包含 $a$ ，所以 $(b - a - a) \ \& \ a = 0$ 时就能找到 $x_1，y_1$ 。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll t,a,b;
    cin >> t;
    while(t--) {
        cin >> a >> b;;
        if (b  >= a * 2 && (((b - a * 2) & a) == 0)) {
            cout << "Yes" << endl;
        }else {
            cout << "No" << endl;
        }
    }
    return 0;
}