ACGO欢乐赛#48+题解+非正式
2025-06-01 22:07:40
发布于：北京
55阅读
0回复
0点赞
我第一次写比赛题解，做的不好勿喷
AC君！我求您让我被抽中一次吧，我打了十几场可能被抽中的比赛了！
好了，言归正传，接下来是我写的比赛题解
T1
- 题目名称：闪电（我不玩三国杀！）
- 题目所用算法：输入输出、分支结构、变量
- 题目背景
《三国杀》游戏
现给定判定牌的花色已确认为黑桃，且点数为整数 a。请判断该判定牌是否会触发闪电效果。
「闪电」：判定阶段，若判定牌为黑桃2到9 - 数据规模与约定
……懒的写了……
……总之就是你只要别用太刁钻的方法，绝对不会TLE…… - 题目代码与注释
#include <bits/stdc++.h>
using namespace std;
// 这么打会方便很多诶！
int main(){
int n;
cin >> n;
// 输入
if (n >= 2 && n <= 9){
cout << "YES";
} else {
cout << "NO";
}
// 判断（处理）+输出
return 0;
}
T2
- 题目名称：复杂的构造题（一点都不复杂）
- 题目所用算法：输入输出、一维数组、简单模拟、循环结构、变量
- 题目背景
通过a和b数组构造c数组
构造规则：
c 的第 1 个元素是 a 的第 1 个元素加上 b 的最后 1 个元素；
c 的第 2 个元素是 a 的第 2 个元素加上 b 的倒数第 2 个元素；
以此类推，c 的第 i 个元素是 a 的第 i 个元素加上 b 的倒数第 i 个元素。 - 思路及推导
也就是：(len是数组长度）
c[0] = a[0] + b[len - 1 - 0]
c[1] = a[1] + b[len - 1 - 1]
c[2] = a[2] + b[len - 1 - 2]
（之所以这里要先-1再-n，是因为索引从0开始，所以应该先-1，这样才是最后一个元素的索引）
……
推导之后，可以总结出：c[n] = a[n] + b[len - 1 - n] - 数据规模与约定
数组长度不会超过，那么我们最多开1重循环（虽然也不需要开双重及更多）
c数组完全可以存的下所有可能出现在数组的数据 - 题目代码与注释
#include <bits/stdc++.h>
using namespace std;
// 这么打会方便很多诶！
int a[2000005];
int b[2000005];
// 定义两个长度>n的数组
int main(){
int n;
cin >> n;
for (int i = 0;i < n;i++){
cin >> a[i];
}
for (int i = 0;i < n;i++){
cin >> b[i];
}
// 输入
for (int i = 0;i < n;i++){
cout << a[i] + b[n - i - 1] << " ";
}
// 通过刚刚的推导直接计算结果（这里没有再定义一个c数组是因为会让空间时间复杂度变高）+输出
return 0;
}
T3
- 题目名称：神吕蒙------狩猎（我不玩三国杀！）
- 题目所用算法：输入输出、字符串、循环结构、分支结构、变量
- 题目背景
《三国杀》游戏
先用字母表示花色
- a = 梅花
- b = 方块
- c = 黑桃
- d = 红桃
（虽然这步没什么用，因为最后是统计abcd）
这道题非常的善良因为不用我们输出每种选择方案
-
思路及推导
那么我们只需要统计abcd出现与否即可，出现 就可以选择这个，最后统计可以选择几个 -
数据规模与约定
-
题目代码与注释
#include <bits/stdc++.h>
#include <string>
using namespace std;
// 这样写会方便很多欸！
string s;
// 定义字符串s（用于存储那五张牌）
int main(){
int a = 0, b = 0, c = 0, d = 0;
// 用于记录abcd分别出现的次数
cin >> s;
int len = s.size();
for (int i = 0;i < len;i++){
if (s[i] == 'a'){
a++;
} else if (s[i] == 'b'){
b++;
} else if (s[i] == 'c'){
c++;
} else {
d++;
}
}
// 输入+计算abcd分别出现的次数
int cnt = 0;
if (a != 0){
cnt++;
}
if (b != 0){
cnt++;
}
if (c != 0){
cnt++;
}
if (d != 0){
cnt++;
}
cout << cnt;
// 输出
/*
如果这个（abcd中的一个）可以被摸到
cnt++
否则不变
abcd中可能有几个字母会出现很多次，但只计算1次
因为它说“然后获得其中不同花色的牌各一张”，所以最多只能取1张
*/
return 0;
}
T4
- 题目名称：质因子个数
- 题目所用算法：输入输出、（动态）数组（函数）、数学函数、循环结构、分支结构、变量
- 题目背景
统计一个数字 不同 质 因子 的个数
1，不同质因子要求不相同（就是相同的质因子只计算一次）
2，质因子要求是质数（就是形如因子4不算在总数内）
3，因子计算进不同质因子总数的数字一定是给定数字的因数（就是如果给定数字是10,3虽然是质数，但不是10的因子）
4，个数统计的是“个数”而非“具体数字”等
写完才发现我写的都是废话，但不想删了 - 思路及推导
所以我们就可以先把所有质数筛出来，再用这每个质数去和n判断，看看这个质数是不是n的因数 - 数据规模与约定
（如果将n的每一个因子都遍历并判断是否是质数一定会TLE！）
- 题目代码与注释
#include <bits/stdc++.h>
using namespace std;
// 这样打会方便很多诶！
int n;
const int N = 1e7 + 10;
bool prime[N];
vector<int> v;
/*
定义需要的变量
n是输入的n（也就是给定数字）
N是我接下来创建数组的长度
prime数组是用来存储1~10^7中有哪些是质数，0是质数，1不是质数
vector，v数组是用来把所有质数都放进去的
*/
int main(){
cin >> n;
// 输入
prime[1] = 1;
for (int i = 2;i <= sqrt(n);i++){
if (prime[i] == 0){
for (int j = 2 * i;j <= n;j += i){
prime[j] = 1;
}
}
}
// 用埃氏筛将1 ~ n的所有质数“筛”出来
for (int i = 2;i <= n;i++){
if (prime[i] == 0){
v.push_back(i);
}
}
// 将所有质数存到v动态数组中（动态数组更省空间）
int len = v.size();
int cnt = 0;
for (int i = 0;i < len;i++){
if (n % v[i] == 0){
cnt++;
}
}
// 用v数组中（筛出的每个质数）的每个数去除n，如果余数是0，说明这个质数是n的因数
// 不需要担心会出现相同质数，因为我们只是用每个质数去除
cout << cnt;
return 0;
}
T5
- 题目名称：多重背包二进制优化问题（这题分明是找规律）
- 题目所用算法：输入输出、变量、循环结构、数学函数
- 题目背景
1，给定一个正整数n
2，选择一个集合S
3，S中的元素可以通过相应组合成为不大于n的任何数
4，注意：对于组合每个数，S集合中任何数都只能用一次
5，求集合S最小可能大小 - 思路及推导
1,先从小数开始找规律
要是n是1，那么S中只需要1个数——1
要是n是2，S中光1就不够了，一定要再加一个2（因为无法重复使用1）
要是n是3，S中光1和2就可以了，因为1=1,2=2,3=1+2，都满足要求
要是n是4，S中光1和2就不够了，需要在前面推导的结果下再加一个4，这样才能满足要求
……（可以自行按照上面的东西）
2，那么就可以推导规律了
S中的数发现都是2的幂次结果
那我们就从1开始，每次找2的幂次，直到这些数超过n，就是S的最小可能大小
那我们就可以把上面那句话改成数学函数：也就是ceil(log2(n+1)); - 数据规模与约定
第一行T，代表测试样例的数目（）
接下来T行，每行一个整数n() - 题目代码与注释
#include <bits/stdc++.h>
using namespace std;
// 这样写会方便很多
int t;
int main(){
cin >> t;
while(t--){
int n;
cin >> n;
int a = ceil(log2(n + 1));
cout << a << endl;
}
// 三步走——输入+按照推导计算+输出
return 0;
}
T6
- 题目名称：平衡矩阵计数问题
- 题目所用算法：输入输出、变量、二维数组、多重循环、分支结构
- 题目背景
找大矩阵中任意n*m（n和m都不会大于大矩阵边长）小矩阵1和0数量相等的个数 - 思路与推导
枚举+遍历任何一个矩阵，只需要枚举出它左上角和右下角的点就可以 - 数据规模与约定
就是大矩阵只会包括1&0 - 题目代码与注释
#include <bits/stdc++.h>
using namespace std;
// 这样打……
int n;
const int N = 15;
int a[N][N];
/*
n是输入进的大矩阵边长
N是大矩阵的大小
a数组相当于大矩阵（matrix）
*/
int main() {
cin >> n;
int cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
// 输入
for (int x1 = 1; x1 <= n; x1++) {
for (int y1 = 1; y1 <= n; y1++) {
for (int x2 = x1; x2 <= n; x2++) {
for (int y2 = y1; y2 <= n; y2++) {
int zero = 0, one = 0;
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
if (a[i][j] == 0) zero++;
else one++;
}
}
if (zero == one) cnt++;
}
}
}
}
// 枚举左上角、右下角点的坐标并看看是否是1&0个数相等
cout << cnt;
// 输出结果
return 0;
}
那么本次题解就写到这里了，如果哪位大佬有好的建议，欢迎反馈
附：你们可以用自己的想法破解一下文字（看看到底是什么）
aHR0cHM6Ly93d3cuYWNnby5jbi9jb250ZXN0L3JhbmtpbmcvNzc4ND9tYXRjaFJvdW5kSWQ9Nzc4NCZleGFtSWQ9NTkzOTE&vcmlwdE9wZW5MZXZlbD0w
有帮助，赞一个