ACGO 24新春欢乐赛全部题目解析
2024-02-26 15:38:22
发布于：新加坡
ACGO 24新春欢乐赛全部题目解析
在题解开始前，祝大家新春快乐。
PS：有任何异议可以在评论区或ACGO交流群内讨论。
T1. 新年快乐
思路：
思路不难，贪心做法就行。每次取出数列中最小的两个数字并加到相对小的那个数字上面。每次操作完对数列进行排序操作。像这种需要进行多次排序的题目，我个人认为这道题最方便的做法就是使用小根堆优先队列。当然这个数据量用插入排序或其它类型的排序也可以在1s内卡过去。小根堆可以通过优先队列的方式实现，具体操作可以看代码。
代码：
#include <iostream>
#include <queue>
using namespace std;
int n, t, a, ans;
priority_queue<int, vector<int>, greater<int> > que;
int main(){
cin >> n >> t;
for (int i=1; i<=n; i++){
cin >> a;
que.push(a);
}
while(que.size()){
int p = que.top(); que.pop();
int q = que.top(); que.pop();
int sum = p + q;
if (p + q <= t){
que.push(sum);
que.push(min(p, q));
ans += 1;
} else break;
}
cout << ans << endl;
return 0;
}
T2. 新年大扫除
思路：
也是一道基础的贪心题目。一般的思路是从头遍历整一个字符串，遍历到某一个需要打扫的点后就一次性地将后面的k-1个点全都打扫完即可。通过记录一个答案变量ans不断进行累加即可。
*备注：*我看到有些题解直接输出，但思考了一下这样子的解法并不完善。如果在字符串中正好有一段长度大于等于k的位置被打扫完了，那么输出的答案就会比预期的答案更大。这道题应该是数据不严谨导致的这种方法可以通过。
代码：
#include <iostream>
using namespace std;
int n, k, ans;
string str;
int main(){
cin >> n >> k >> str;
for (int i=0; i<n; i++){
if (str[i] == 'O'){
ans += 1;
i += k - 1;
}
}
cout << ans << endl;
return 0;
}
T3. 新年魔法
思路：
这个问题是一个纯粹的模拟算法，根据题目要求反复执行减法运算即可。然而，这种方法只能获得40%的分数。因此，需要在原始算法的基础上进行一定的优化。通过观察代码，可以发现当数字远远大于数字时，如果比大倍，程序就会盲目执行次循环（递归）。因此，可以考虑预处理这两个数字和，即当大于时，计算需要减去多少次才能使小于，并将答案累加；反之亦然。
代码：
#include <iostream>
using namespace std;
int a, b, ans;
void recursion(int a, int b){
if (a <= 0 || b <= 0) return ;
ans ++;
if (a > b) recursion(a - b, b);
else recursion(b - a, a);
}
int main(){
cin >> a >> b;
if (a < b) swap(a, b);
ans += a / b;
a = a - b * (a / b);
recursion(a, b);
cout << ans << endl;
return 0;
}
T4. 新年排列
思路：
相对来说这道题是本次欢乐赛中最难的题目了。但想通之后就会觉得很简单。
首先，根据题意，经过 次操作后，整个序列将变为类似 [1, 2, 3, ..., n-1, n] 的形式。换句话说，整个序列都是严格递增的，每次递增一个单位。我们采用贪心策略，假设序列中存在一个子序列 [1, 2, 3, ..., m-1, m]，那么我们只需每次提取出大于 的最小的 个不同的数字，即提取出 m+1, m+2, ..., m+k，对它们进行排序后放置在序列的末尾。重复这个操作即可。
因此，我们的目标转变为如何找到一个最长的子序列，从1开始严格递增。对于这个问题，我们并不需要知道子序列的具体内容，只需知道其长度即可（实际上，知道长度就等于知道了内容）。我们可以使用一个数组 isExists 来记录某个数字是否已经出现过。当读入数字 num1 时，检查 isExists[num1-1] 是否为真。如果是，表示它可以与前一个数字构成严格递增的子序列；否则，计算就会停止，因为在这之后无论如何也无法构建我们所需的子序列。同时，在初始化阶段将 isExists[0] 设置为1。
代码：
// 代码并不是最优解，空间上还有优化的余地。
// 比赛中因为不考虑空间就没有继续优化了。
// 各位可以酌情自己改一下下面的算法。
#include <iostream>
#include <cmath>
using namespace std;
int n, k, arr[100005], t;
bool isExists[100005];
int main(){
cin >> n >> k;
isExists[0] = 1;
for (int i=1; i<=n; i++){
cin >> arr[i];
if (isExists[arr[i]-1]){
isExists[arr[i]] = 1;
t = max(t, arr[i]);
}
}
int pending = n - t;
cout << ceil(pending*1.0 / k) << endl;
return 0;
}
T5. 新年游戏
思路：
这道题其实不难，没有大家说的那么的困难。这道题可以使用拓展欧几里得的辗转相除法来求解出所有数的共同最大公约数，也可以使用一个贪心的算法来解。相对来说贪心算法更容易被想到，这里提供一个贪心算法的代码：每次取出数列中最大的两个不相同的数字进行减法运算即可。看到有使用优先队列和向量的解法，我个人认为用插入排序的方法最直接也最简单。程序的终止条件一定是当所有的数字相同时结束，如果有人任意两个数字不相同那么就应该继续找出最大的两个不相同的数字相减。
为了使得插入排序的时间消耗尽可能的低，在最开始先使用sort对整个序列进行一次从小到大的排序操作就行了。代码中check函数用于判断是否还可以继续进行减法运算。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
int n, arr[105];
bool check(){
for (int i=2; i<=n; i++){
if (arr[i] != arr[i-1]){
return false;
}
}
return true;
}
int main(){
cin >> n;
for (int i=1; i<=n; i++) cin >> arr[i];
sort(arr+1, arr+n+1);
while (check() == false){
for (int i=n-1; i>=1; i--){
if (arr[i] != arr[n]){
arr[n] -= arr[i];
break;
}
}
int t = arr[n], i=n;
while(t <= arr[i] && i >= 1){
arr[i] = arr[i-1];
i -= 1;
}
arr[i+1] = t;
}
cout << arr[1] * n << endl;
return 0;
}
T6. 新年均馔
思路：
本质上就是找出序列中的最小的那个数。这道题不多说了，可以自己去想一下。有点类似水桶问题 - 一个水桶能装下多少的水取决于最短的其最短的那一根木板。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
int ans, mini = 0x7f7f7f7f;
int n, arr[55];
int main(){
cin >> n;
for (int i=1; i<=n; i++){
cin >> arr[i];
mini = min(mini, arr[i]);
}
for (int i=1; i<=n; i++){
ans += arr[i] - mini;
}
cout << ans << endl;
return 0;
}
T7. 新年花坛守护战
思路：
依然是一道贪心问题，从头遍历每一个花坛，找局部最优解就可以了。每次就只有两种选择，一种选择是使用幸运福花，另一种选择就是使用烟花炮，比较一下使用哪一个比较划算就可以了。程序实现上也没有难度。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
int ans, k;
int n, arr[105];
int main(){
cin >> n >> k;
for (int i=1; i<=n; i++) {
cin >> arr[i];
// 看看哪一个划算。
ans += min(k, arr[i]);
}
cout << ans << endl;
return 0;
}
T8. 新年红包
思路：
看到大家有使用桶排序的，这里给大家提供一个“新船解法”，使用异或位运算来解决。先了解一下异或运算：
异或（XOR）是一种基本的位运算，用符号 '^' 表示，在许多编程语言中也是如此。它的操作数是两个布尔值，若两个操作数的值不同，则结果为真，否则为假。
在位运算中，异或操作的规则如下：
- 如果两个操作数的对应位相同（均为 0 或均为 1），则结果为 0。
- 如果两个操作数的对应位不同（一个为 0，另一个为 1），则结果为 1。
异或位运算的真值表如下：
| 输入 A | 输入 B | 输出 A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
例子：
10011011
XOR 10011110
------------
00000101
下面是异或运算的一些性质：
-
交换律：对于任何两个操作数，异或运算满足交换律，即
-
结合律：对于任何三个操作数，异或运算满足结合律，即 。
-
自反性：一个数与自己进行异或运算，结果为 0，即
-
零与任何数的异或运算结果为该数本身：即 。
-
任何数与 1 的异或运算结果取反：即，其中 表示 的按位取反。
异或运算常常用于以下场景：
-
交换值：使用异或运算可以在不借助额外变量的情况下交换两个变量的值，例如：
a = a ^ b b = a ^ b a = a ^ b -
检测出现奇数次的元素：如果一个数组中除了一个元素之外，其余所有元素都出现偶数次，可以通过对数组中的所有元素进行异或运算，最终剩下的就是出现奇数次的元素。
-
加密：在信息安全领域，异或运算经常用于简单的加密和解密操作。
这里就使用了检测出现奇数次的元素来求解出答案。
代码：
#include <iostream>
using namespace std;
int n, t, m;
int main(){
cin >> n;
for (int i=1; i<=n; i++){
cin >> t;
m ^= t;
}
cout << m << endl;
return 0;
}
T9. 新年糖果
思路：
看到有使用公式的，也有使用贪心算法的。这道题的最优解应该是使用二分答案的算法，尤其是当数据量特别大的时候，否则就容易出现超时的情况。我们来二分糖果快乐值为的数量，让的糖果数量尽可能多就可以了，答案一定是符合单调性的。check函数用于计算当有count颗快乐值为的糖果的时候，是否可以满足题目的要求（即每一个小朋友都至少有一颗糖果可以吃到）。
代码：
#include <iostream>
using namespace std;
long long ans;
long long n, s;
bool check(int count){
int remain = n - count + 1;
return remain + n * count * 2 <= s;
}
int main(){
cin >> n >> s;
int l = 0, r = n+1;
while(l <= r){
int mid = (l + r) >> 1;
if (check(mid)){
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
cout << ans << endl;
return 0;
}
T10. 新年消消乐
思路：
这是一道数学问题，关于奇数和偶数的一些性质：
- 奇数 + 奇数一定是一个偶数
- 偶数 + 偶数一定是一个偶数。
- 奇数 + 偶数一定是一个奇数。
因此只有第三种情况可以拼出奇数，那么如果需要让每一组同学的数值相加为奇数，那么就需要让奇数和偶数的出现次数一样多才可以。判断奇数和偶数数量是否相同，相同输出YES，否则输出NO。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
int n, t;
int odd, even;
int main(){
cin >> n;
for (int i=1; i<=2*n; i++){
cin >> t;
if (t % 2) odd++;
else even++;
}
if (odd == even) cout << "YES" << endl;
else cout << "NO" << endl;
return 0;
}
有帮助，赞一个