欢乐赛#33题解

2024-11-22 13:30:57

发布于：江苏

19阅读

0回复

3点赞

第一题题解

A33695.换行

解题思路
第一题比较简单，单纯的考察C++的基础知识转义字符的使用，注意一下换行符的使用即可。

#include <bits/stdc++.h>

#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
using namespace std;

int main(){
    cout<<"\\n";
    return 0;
}

第二题题解

A33696.求和

解题思路
第二题主要考察了一下时间复杂度的计算，如果简单的使用 $for$ 循环， $n$ 的范围是 $1≤n≤2147483647$ ，时间复杂度是 $O(n)$ ，会超时，所以需要使用数学方法，高斯求和(等差求和公式)，时间复杂度是 $O(1)$ 。

#include <bits/stdc++.h>

#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
using namespace std;

int T, n;

int main()
{
    cin >> T;
    while (T--)
    {
        scanf("%d", &n);
        printf("%lld\n", n * (n + 1ll) / 2);
    }
    return 0;
}

第三题题解

A33697.权重

解题思路：
本题的重点还是考察了数据范围，把数据开成long long，基本上就没啥问题了。
首先读取字符串，统计一下每个字符出现的次数，然后给的公式计算权重进行累加即可。

#include <bits/stdc++.h>

#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
using namespace std;

string s;
long long bucket[6], w[6], sum;

int main()
{
    cin >> s;
    for (int i = 1; i <= 5; i++)
        cin >> w[i];
    int len = s.size();
    for (int i = 0; i < len; i++)
    {
        if (s[i] == 'a')
            bucket[1]++;
        else if (s[i] == 'e')
            bucket[2]++;
        else if (s[i] == 'i')
            bucket[3]++;
        else if (s[i] == 'o')
            bucket[4]++;
        else if (s[i] == 'u')
            bucket[5]++;
    }
    for (int i = 1; i <= 5; i++)
        sum += bucket[i] * w[i];
    cout << sum;
    return 0;
}

第四题题解

A33698.最大公约数

计算因子个数：
- 定义函数 countFactors，用于计算一个整数的因子个数。通过从 1 到该整数的平方根进行遍历，因为如果 i 是 num 的因子，那么 num / i 也是 num 的因子（除了 i 和 num / i 相等的情况，此时只算一个）。
- 对于每个能整除 num 的 i，先将因子个数加 2（表示 i 和 num / i 两个因子），如果 i 和 num / i 相等，就需要把多算的一次减掉，从而准确得到 num 的因子个数。
处理输入并计算因子个数序列：
- 在 main 函数中，先读取输入的 n（整数个数）和 m（目标累加和）。
- 然后通过循环依次读取 n 个整数，对于每个读取到的整数 tmp，调用 countFactors 函数计算其因子个数，并将结果添加到向量 v 中，这样就得到了所有整数的因子个数构成的向量。
排序与累加查找：
- 使用 sort 函数对向量 v 中的因子个数进行排序，排序方式是从大到小（通过 greater<int> 指定）。
- 接着通过循环依次累加排序后的因子个数，用变量 sum 记录累加和。在每次累加后，判断 sum 是否大于等于 m，如果满足这个条件，就输出当前的累加次数 i + 1（因为索引是从 0 开始的，所以要加 1 才是从 1 开始计数的正确索引），然后程序结束。

复杂度分析

时间复杂度：
- 计算因子个数部分：对于每个整数计算因子个数时，需要从 1 到该整数的平方根进行遍历，假设输入的整数最大值为 N，那么计算一个整数因子个数的时间复杂度大约为 $O(\sqrt{N})$ 。总共要计算 n 个整数的因子个数，所以这部分的时间复杂度大约为 $O(n\sqrt{N})$ 。
- 排序部分：使用 sort 函数对向量 v 进行排序，一般 sort 函数的时间复杂度为 $O(nlogn)$ ，这里 n 是向量 v 的长度，也就是输入的整数个数。
- 累加查找部分：通过循环依次累加向量 v 中的元素，时间复杂度为 $O(n)$ 。
- 综合起来，整个程序的时间复杂度大约为 $O(n\sqrt{N} + nlogn + n)$ ，简化后约为 $O(n\sqrt{N} + nlogn)$ 。
空间复杂度：
- 主要的空间消耗在于存储每个整数的因子个数的向量 v，向量 v 的长度最大为 n，所以空间复杂度为 $O(n)$ 。

#include <bits/stdc++.h>

#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
using namespace std;

vector<int> v;
int n, m, tmp;

// 计算因子个数
int countFactors(int num)
{
    int count = 0;
    for (int i = 1; i <= sqrt(num); ++i)
    {
        if (num % i == 0)
        {
            count += 2; // i 和 num/i 都是因子
            if (i == num / i)
                count--; // 如果 i 和 num/i 相等，则只算一个
        }
    }
    return count;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &tmp);
        v.push_back(countFactors(tmp));
    }
    sort(v.begin(), v.end(), greater<int>()); // 对因子个数进行排序
    int sum = 0;
    for (int i = 0; i < v.size(); i++)
    {
        sum += v[i];
        if (sum >= m)
        {
            cout << i + 1 << endl;
            return 0;
        }
    }
    return 0;
}

第五题题解

A33699.美丽数组

判断回文

// 判断是否是回文数组
bool isPalindrome()
{
    for (int i = 1; i <= n / 2; i++)
    {
        if (a[i] != a[n - i + 1])
            return false;
    }
    return true;
}

判断奇数项之和与偶数项之和是否相等

// 判断数组奇数项之和是否等于偶数项之和
bool isSumEqual()
{
    long long sum1 = 0, sum2 = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i % 2 == 1)
            sum1 += a[i];
        else
            sum2 += a[i];
    }
    return sum1 == sum2;
}

时间复杂度分析

对于每个测试用例：
- 判断回文数组的操作：在 isPalindrome 函数中，需要遍历数组的前半部分元素，时间复杂度为 $O(n)$ ，其中 n 为数组的长度。
- 判断奇数项之和与偶数项之和是否相等的操作：在 isSumEqual 个函数中，需要遍历数组的每一个元素，时间复杂度也为 $O(n)$ 。
总共存在 T 个测试用例，所以整个程序的时间复杂度为 $O(Tn)$ 。

空间复杂度分析

主要的空间消耗在于存储数组元素的数组 a，其大小为 100005，但实际上对于每个测试用例，只使用了其中的 n 个位置来存储数组元素。所以空间复杂度为 $O(n)$ ，这里的 n 是指每个测试用例中数组的长度。

#include <bits/stdc++.h>

#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
using namespace std;

int T, n, a[100005];

// 判断是否是回文数组
bool isPalindrome()
{
    for (int i = 1; i <= n / 2; i++)
    {
        if (a[i] != a[n - i + 1])
            return false;
    }
    return true;
}

// 判断数组奇数项之和是否等于偶数项之和
bool isSumEqual()
{
    long long sum1 = 0, sum2 = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i % 2 == 1)
            sum1 += a[i];
        else
            sum2 += a[i];
    }
    return sum1 == sum2;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        if (isPalindrome())
        {
            printf("No\n");
            continue;
        }
        if (isSumEqual())
        {
            printf("Yes\n");
            continue;
        }
        printf("No\n");
    }
    return 0;
}

第六题题解

A33700.字典序问题

整体思路
- 我们要想办法构造出一个可能的字典序最大的字符串。考虑到数字越大在字典序中越靠后，所以要尽量让高位数字尽可能大。
- 因为 n 的取值范围可能很大（从代码中看，是用字符串来接收 n 的，这也暗示了 n 可能是非常大的数），所以我们通过对 n 的字符串表示进行分析和操作来找到答案。
具体步骤
- 首先，判断 n 是否全部由数字 9 组成。如果是，那字典序最大的字符串就是 n 本身啦，不过代码里没有显式地处理这种全 9 的情况，我们先接着往下看一般情况的处理。
- 然后，我们先构造一个临时字符串 tmp，它的长度是 n 的长度减1，并且每个字符都是 9。为什么要这样做呢？因为我们要让高位尽可能大，所以先假设高位都是 9，然后再根据实际情况进行调整。假设现在有一个5位数，那么9999算是最大的数字，除非这个5位数是9999?,所以需要对最后一位数字进行判断。
- 最后，我们再看 n 的最后一位数字。如果 n 的最后一位不是 0，并且 n 的前 len - 1 位（也就是去掉最后一位的部分）组成的字符串大于等于我们刚才构造的 tmp，那就把 n 的最后一位数字加到 tmp 后面。这样得到的 tmp 就是我们要找的字典序最大的字符串啦。

#include <bits/stdc++.h>

#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
using namespace std;

string n, tmp;
int len;

int main()
{
    cin >> n;
    len = n.size();
    for (int i = 0; i < len - 1; i++)
        tmp += '9';
    if (n[len - 1] != '0' && n.substr(0, len - 1) >= tmp)
        tmp += n[len - 1];
    cout << tmp;
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

第一题题解

第二题题解

第三题题解

第四题题解

复杂度分析

第五题题解

第六题题解

热门讨论