视频题解

---

A

解题思路

为了最小化总成本，我们需要尽可能多地购买最便宜的水果，但必须确保至少有两种不同的水果。因此，最优策略是：

• 购买 $X-1$ 个最便宜的水果。
• 购买 $1$ 个第二便宜的水果。

这样，总成本为 $\text{min} \times (X-1) + \text{mid}$，其中 $\text{min}$ 是三种价格中的最小值，$\text{mid}$ 是中间值。

参考代码

代码首先读取测试用例数量 $T$，然后对于每个测试用例，读取 $X$、$A$、$B$、$C$。接着对三个价格进行排序，找到最小值、中间值和最大值。最后输出计算结果 $\text{min} \times (X-1) + \text{mid}$。

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

void solve() {
    int x, a, b, c;
    cin >> x >> a >> b >> c;
    int mx = max({a, b, c});
    int mi = min({a, b, c});
    int mid = a + b + c - mi - mx;
    cout << mi * (x - 1) + mid << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

解题思路

要解决这个问题，我们需要考虑所有可能的正方形子矩阵，并计算每个子矩阵的迹，然后找出其中的最大值。由于 $N \leq 100$，我们可以使用一个直接的方法来遍历所有可能的子矩阵。

关键观察

• 一个正方形子矩阵由其左上角坐标 $(i, j)$ 和边长 $l$ 确定。
• 子矩阵的迹就是从 $(i, j)$ 开始，沿着主对角线方向连续 $l$ 个元素的和，所以我们只需要确定左上角后，不断往右下角走即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N][N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x = i, y = j;
            int sum = 0;
            while (x <= n && y <= n) {
                sum += a[x][y];
                ans = max(ans, sum);
                x++;
                y++;
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

C

解题思路

我们可以将问题分解为三种情况：

1. 两个字符串在同一位置都是1：无论选择A还是B，都会得到1分
2. 两个字符串在同一位置只有一个1：可以选择得到1分或0分
3. 两个字符串在同一位置都是0：无论选择哪个，都只能得到0分

算法实现

1. 统计两个字符串中同一位置都是1的个数（记为ans）
2. 统计两个字符串中只有一个1的个数（记为c）
3. 判断逻辑：
   • 如果ans是奇数，那么已经有一个奇数基础，直接输出"YES"
   • 如果ans是偶数，但c至少为1，我们可以通过调整情况2的选择来使总分变为奇数
   • 否则，无法使分数为奇数，输出"NO"

参考代码

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

int main(){
	int T;
	cin >> T;
	while (T--){
		int n;
		cin >> n;
		string a, b;
		cin >> a >> b;
		int ans = 0, c = 0;
		for (int i = 0; i < n; i++){
			if (a[i] == '1' && b[i] == '1') ans += 1;
			else if (a[i] == '1' || b[i] == '1') c++;
		}
		if (ans % 2 == 1) cout << "YES" << endl;
		else{
			if (c >= 1) cout << "YES" << endl;
			else cout << "NO" << endl;
		}
	}
}

D

解题思路

对于两个数字 $a$ 和 $b$，我们需要逐位相加但不进位：

1. 从最低位（个位）开始处理
2. 对每一位，计算 $(a_i + b_i) \mod 10$，其中 $a_i$ 和 $b_i$ 分别是 $a$ 和 $b$ 在第 $i$ 位的数字
3. 将结果按位组合成最终数字

例如：

• $12 + 9$：个位 $(2+9) \mod 10 = 1$，十位 $(1+0) \mod 10 = 1$，结果是 $11$
• $25 + 25$：个位 $(5+5) \mod 10 = 0$，十位 $(2+2) \mod 10 = 4$，结果是 $40$

算法实现

使用循环逐位处理两个数字：

1. 初始化结果为 $0$，基数 $base = 1$（表示当前处理的是个位）
2. 当 $a > 0$ 或 $b > 0$ 时，循环：
   • 取出 $a$ 和 $b$ 的当前最低位（通过取模 $10$）
   • 计算当前位的和：$cur = (a \mod 10 + b \mod 10) \mod 10$
   • 将当前位的结果加到最终结果中：$ans = ans + cur \times base$
   • 更新 $a$ 和 $b$：$a = \lfloor a/10 \rfloor$，$b = \lfloor b/10 \rfloor$（去掉已处理的位）
   • 更新 $base$：$base = base \times 10$（准备处理下一位）
3. 输出最终结果

参考代码

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

int main() {
    int T;
    cin >> T;
    while (T--) {
        ll a, b;
        cin >> a >> b;
        ll ans = 0, base = 1;
        
        // 逐位处理，直到a和b都变为0
        while (a > 0 || b > 0) {
            // 取出当前最低位并相加（模10，不进位）
            ll cur = ((a % 10) + (b % 10)) % 10;
            // 将当前位的结果加到最终答案中
            ans = ans + cur * base;
            // 去掉已处理的最低位
            a /= 10;
            b /= 10;
            // 准备处理下一位（十位、百位等）
            base *= 10;
        }
        cout << ans << endl;
    }
    return 0;
}

E

解题思路

将序列中的数字分为四类：

• bob数字：只能被 a 整除的数字（小B专属）。
• alice数字：只能被 b 整除的数字（小A专属）。
• 公共数字：同时被 a 和 b 整除的数字（双方都可移除）。
• 无关数字：既不能被 a 也不能被 b 整除的数字（不影响游戏）。

游戏结果取决于前三类数字的数量：

1. 如果没有公共数字（albob == 0）：

   • 游戏仅在 bob 数字和 alice 数字之间进行。
   • 小B先手，只能移除 bob 数字；小A后手，只能移除 alice 数字。
   • 如果 bob 数字数量大于 alice 数字数量，小B赢；否则小A赢。
   • 理由：小B可以先移除 bob 数字，双方轮流移除。如果 bob 数字更多，小B最后剩余数字可移除，小A无法行动；否则小A剩余数字可移除，小B无法行动。

2. 如果有公共数字（albob != 0）：

   • 公共数字可以被双方移除。
   • 最优策略下，小B会先手移除所有公共数字，阻止小A使用它们。
   • 移除后，游戏进入小A先手的状态，只剩下 bob 和 alice 数字。
   • 如果 alice 数字数量大于 bob 数字数量，小A赢；否则小B赢。
   • 理由：移除公共数字后，小A先手面对 bob 和 alice 数字。如果 alice 数字更多，小A能赢；否则小B赢。

3. 特殊情况：

   • 如果没有数字可移除（所有数字都是无关数字），小B无法行动，小A赢。
   • 如果只有公共数字，小B可以移除所有公共数字，小A无法行动，小B赢。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int arr[N];

void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    int alice = 0, bob = 0, albob = 0;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
        if(arr[i] % a == 0 && arr[i] % b == 0) {
            albob++;
        }
        else if(arr[i] % a == 0) {
            bob++;
        }
        else if(arr[i] % b == 0) {
            alice++;
        }
    }
    if(alice == 0 && bob == 0 && albob != 0) {
        cout << "BOB" << endl;
    }
    else if(alice == 0 && bob == 0 && albob == 0) {
        cout << "ALICE" << endl;
    }
    else if(albob == 0) {
        if(alice >= bob) {
            cout << "ALICE" << endl;
        }
        else {
            cout << "BOB" << endl;
        }
    }
    else {
        if(alice > bob) {
            cout << "ALICE" << endl;
        }
        else {
            cout << "BOB" << endl;
        }
    }
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
	return 0;
}

F

解题思路

1. 检查总和：计算数组所有元素的总和 $sum$。如果 $sum \bmod 3 \neq 0$，则输出 $-1$。
2. 统计余数：统计数组中元素模 3 余数为 1 的个数（记为 $cnt1$）和余数为 2 的个数（记为 $cnt2$）。余数为 0 的元素已经是 3 的倍数，无需处理。
3. 配对操作：每次操作可以同时处理一个余数为 1 和一个余数为 2 的元素，使它们变成余数为 0。因此，如果 $cnt1 = cnt2$，所需操作次数即为 $cnt1$。
4. 处理多余元素：如果 $cnt1$ 和 $cnt2$ 不相等，则先进行 $\min(cnt1, cnt2)$ 次配对操作。剩余的多余元素（均为余数 1 或余数 2）每 3 个可以通过 2 次操作变为余数为 0。因此，总操作次数为 $\min(cnt1, cnt2) + \frac{|cnt1 - cnt2|}{3} \times 2$。

注意：由于总和能被 3 整除，必有 $|cnt1 - cnt2|$ 是 3 的倍数，因此计算中无需担心整除问题。

代码实现

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

void solve() {
    int n;
    cin >> n;
    int cnt1 = 0, cnt2 = 0;
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
        if (x % 3 == 1) cnt1++;
        if (x % 3 == 2) cnt2++;
    }
    if (sum % 3 != 0) {
        cout << -1 << endl;
        return;
    }
    if (cnt1 == cnt2) {
        cout << cnt1 << endl;
        return;
    }
    int ans = min(cnt1, cnt2);
    int rem = max(cnt1, cnt2) - min(cnt1, cnt2);
    ans += rem / 3 * 2;
    cout << ans << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}