欢乐赛#34题解（新手向详解）
2024-11-18 20:49:09
发布于：浙江
这是本人第一次写题解，请多多谅解，谢啦！（我是蒟蒻一枚）奖品冲冲冲！我爱ACGO！
步入正文（此篇题解篇幅较长，请耐心看完，最重要的是代码注释）
.
.
.
.
.
.
.
T1.
.
题目
.
.
题意：
十分简单的题，就是去重嘛！去重后输出数据
.
.
数据范围：
- 1 ≤ n ≤ 10⁵
- 1 ≤ A ᵢ ≤ 10⁵
.
.
方法：
定义新的数组，然后将元素组与新数组内的元素对比，若不同则存放在新数组中。方法详见代码注释
.
.
.
// AC代码
#include <iostream>
using namespace std;
int main() {
int tmp[100005] /* 定义一个和a相同大小的数组，存放去重后的数 */, a[100005];
int m = 0 /* 记录存了多少 */, n /* 数据数量 */;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i]; // 输入
for (int i = 0; i < n; i++) {
int j = 0;
for (; j < m; j++) {
/* 拿a[i]依次与tmp里的元素对比 */
if (a[i] == tmp[j]) {
break; // 找到相同的了
}
}
if (j == m) {
// 没有找到相同的，把a中此元素放入tmp里
tmp[m] = a[i];
m++;
}
}
cout << m; // 输出
return 0;
}
// 其实排序后再去重也行，用STL容器也可以
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
T2.
.
题目
.
.
题意
还是十分简单的题，输入字符串后输出执行命令后的坐标，初始位置x和y都为0
.
.
数据范围
- 1 ≤ n ≤ 10⁵
- 字符串只包含 D,U,R,L
.
.
方法
定义变量x和y存储坐标，根据字符串改就行了。方法详见代码注释
.
.
.
// AC代码
#include <iostream>
using namespace std;
int main() {
int n; // 长度
int x = 0, y = 0; // 存储坐标
string s; // 用来存储指令
cin >> n >> s; // 输入
for (int i = 0; i < n; i++) { // 遍历字符串
if (s[i] == 'D') y -= 1; // 向下
else if (s[i] == 'U') y += 1; // 向上
else if (s[i] == 'L') x -= 1; // 向左
else x += 1; // 向右
}
cout << "(" << x << "," << y << ")"; // 输出
return 0;
}
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
T3
.
题目
.
.
题意
需要理解，注意啦！规定不能连续两天休假（真缺德，还良心），且最后一天放假，说明假期一定不可能安排在第1天和第n - 1天
d1：为上月最后1天假期到这月第1个假期的间隔天数，也就是 0 到 i ，间隔天数：i - 1
d2：为第1个假期到第2个假期的间隔天数，为 i 到 j ，间隔天数：j - i - 1
d3：为第2个假期到第3个假期（最后一天）的间隔天数，为 j 到 n ，间隔天数：n - j - 1
求min( |d₁ − d₂| , |d₂ − d₃| , |d₃ − d₁| )的最大值。
.
.
数据范围
- 1 ≤ n ≤ 10⁹
.
.
方法
枚举每一种可能，然后与变量max比较，选出最大的数据，然后输出，方法详见代码注释
.
.
.
// TLE代码
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, /* 天数 */ max = -1 /* 比较值，因绝对值最小为0，所以定义为-1 */;
cin >> n; // 输入
for (int i = 2; i < n - 3; i++) { // 枚举，i 为第1个假期，从第2天算起，原因见题意
for (int j = i + 2; j < n - 1; j++) { // 枚举，j 为第2个假期，从第 i + 2 天算起，原因见题意
int d1 = i - 1, d2 = j - i - 1, d3 = n - j - 1; // 计算间隔天数
int m = min({abs(d1 - d2), abs(d2 - d3), abs(d3 - d1)});
if (m > max) max = m; // 比较
}
}
cout << max; // 输出
return 0;
}
这是根据题意理解敲出来的，但我在比赛时却忘记了数据范围，于是TLE……
但我把 n 为1 到 50 的全试一遍后得到了这些数据：
（5 及以内数据因无法做到不能有连续两天同时休假所以为 -1）
可以看到值为 3 个一组，并且逐渐增加，且符合一个规律：值 = n / 3 - 2，按照此规律写出代码提交后，你就会发现……你竟然成功的过了全部的样例！在此贴上AC代码，此题应该是这次比赛最难的了
.
.
.
// AC代码
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
cout << n / 3 - 2;
return 0;
}
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
T4.
.
题目
.
.
题意
水题啊！直接敲一遍不就行了，就是求质数个数而已
.
.
数据范围
- 1 ≤ n ≤ 10⁹
.
.
方法
应该都学过的，不用讲了吧……
.
.
.
// 代码
#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(const int n) { // 判断是否为质数
if (n < 2) return false;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int n, count = 0; // 定义
cin >> n; // 输入
for (int i = 2; i <= n; i++) {
if (isPrime(i)) count++; //加
}
cout << count; // 输出
return 0;
}
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
T5.
.
题目
.
.
题意
比较字符出现个数是否相同
.
.
数据范围
- 1≤T≤100
- 1≤n≤10⁴
- 字符的ASCII满足：33 ≤ ASCII ≤ 126
.
.
方法
统计每个字符数并存储到数组中后进行比较，详见代码注释
.
.
.
// 代码
#include <iostream>
using namespace std;
int main() {
int t, n; // 定义
cin >> t; // 输入数据
while (t--) {
int a[96] = {0}, b[96] = {0}; // 126-33，在加了两位
string s1, s2;
cin >> n; // 输入数据
cin >> s1 >> s2;
for (int i = 0; i < n; i++) { // 存储到对应的位置
a[s1[i] - 33]++; // 因为字符从33开始，所以-33
b[s2[i] - 33]++;
}
for (int i = 0; i < 94; i++) {
if (a[i] != b[i]) { // 对应字符数量不相等
cout << "NO\n";
break; // 跳出循环
}
if (i == 93) cout << "YES\n"; // 循环结束，结果相等
}
}
return 0;
}
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
T6
.
题目
.
.
题意
输出一句话（超级水沝淼㵘题，为什么这题拿来作为T6？）
.
.
数据范围
- 无
.
.
方法
直接输出
.
.
.
// 代码
#include <iostream>
using namespace std;
int main() {
cout << "Good Luck!";
return 0;
}
// 虽然我已经期中考过了，但还是谢谢好吧！考废了……
.
.
.
.
.
.
.
.
.
END
.
有帮助，赞一个