ACGO欢乐赛#55全题解

毛奕程

2025-09-02 19:02:18

发布于：江苏

11阅读

0回复

0点赞

作为我第一次AK的欢乐赛，一定要发个题解庆祝一下。
免责声明： 本作品作者很菜，不喜也别喷。

T1 奇数判断

知识点：分支结构
判断奇偶问题。

#include <cstdio>
using namespace std;

int a, b, c;

int main() {
    scanf("%d%d%d", &a, &b, &c);
    if ((a*b-c)%2) printf("Yes");
    else printf("No");
    return 0;
}

T2 小明的神秘宝箱

知识点：循环结构
循环求和问题，记的开个long long！

#include <cstdio>
using namespace std;

int n;
long long lsum, rsum;

int main() {
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        lsum += l, rsum += r;
    }
    printf("%lld %lld", lsum, rsum);
    return 0;
}

T3 找出卧底

知识点：字符串
字符串统一大小写比较，可以使用<cctype>头文件做。

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

int n, cnt;

int main() {
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        for (char &c:s) {
            if (islower(c)) 
                c = toupper(c);
        }
        if (s == "WOHEYEZHI") cnt++;
    }
    cout << cnt;
    return 0;
}

T4 寻找最小公倍数

知识点：基础数学知识
公倍数问题，可以暴力枚举，更优方法可参考其他题解。

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

int n, a[505], maxlcm;

int main() {
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        scanf("%d", a+i);
    }
    for (int i=1; i<=n; i++) {
        for (int j=i; j<=n; j++) {
            int t = a[i]*a[j]/__gcd(a[i], a[j]);
            if (t > maxlcm) maxlcm = t;
        }
    }
    printf("%d", maxlcm);
    return 0;
}

T5 对称矩阵

知识点：二维数组&循环嵌套
矩阵问题，使用循环嵌套时间复杂度 $O(tn^2)$ ，判断条件复杂建议写check()函数。

#include <cstdio>
using namespace std;

int t, n;
bool g[1005][1005];

bool check() {
    //判断横向对称
    for (int u = n/2, d = n/2+1; u>=1&&d<=n; u--, d++) {
        for (int j=1; j<=n; j++) {
            if (g[u][j] != g[d][j]) return 0;
        }
    }
    //判断纵向对称
    for (int i=1; i<=n; i++) {
        for (int l = n/2, r = n/2+1; l>=1&&r<=n; l--, r++) {
            if (g[i][l] != g[i][r]) return 0;
        }
    }
    return 1;
}

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                scanf("%d", &g[i][j]);
            }
        }
        if (check()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

T6 宝石项链

知识点：STL
位运算+桶思想，但是桶的容量最多 $2×10^5$ 但是要统计 $10^9$ 种元素，map成了开桶的最佳容器，再加上vector长度灵活可变就变成了统计一个颜色对应的不定个数下标的不二之选。记得开个long long。

#include <cstdio>
#include <map>
#include <vector>
using namespace std;

int n;
long long beauty;
//桶<宝石颜色, 宝石颜色对应下标>
map<int, vector<int>> mp;

int main() {
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        int ai; scanf("%d", &ai);
        mp[ai].push_back(i);
    }
    for (auto i:mp) {
        long long sum=0;
        for (int j:i.second) sum ^= j;
        sum *= i.first;
        beauty += sum;
    }
    printf("%lld", beauty);
    return 0;
}