《上海市计算机学会竞赛平台2024年8月月赛丙组题目T1 统计得分 T2 等差数列的素性 T3 互质序列》 题解

T1 统计得分

内存限制: 256 Mb时间限制: 1000 ms

题目描述

在一场知识竞赛中，选手答对一题得 11 分，答错不得分且要倒扣 11 分，但扣分不能让分数小于 00。

给定一个由 Y 及 N 构成的字符序列，答对记为 Y，答错记为 N。

选手一开始从 00 分开始，请输出选手最后的得分。

输入格式

• 单个字符序列：保证仅由字母 Y 及 N 组成。

输出格式

• 单个整数，表示最终得分。

数据范围

设 �n 表示字符序列的长度，1≤n≤100,000。

样例数据

输入:

YNNYYY

输出:

3

解析

这个问题相对简单，只需要遍历输入的字符序列，并根据字符是 'Y' 还是 'N' 来更新得分。每次答对（'Y'）得 1 分，答错（'N'）扣 1 分，但得分不能小于 0。

以下是使用 C++ 实现的代码：

#include <iostream>
#include <string>

int main() {
    std::string sequence;
    std::cin >> sequence;

    int score = 0;

    for (char c : sequence) {
        if (c == 'Y') {
            ++score;
        } else if (c == 'N') {
            --score;
            if (score < 0) {
                score = 0; // 防止得分小于0
            }
        }
    }

    std::cout << score << std::endl;

    return 0;
}

以下是对提供的 C++ 代码逻辑的详细解释：

该代码的主要目的是计算一个由 'Y' 和 'N' 组成的字符序列所代表的得分。在这个场景中，'Y' 表示答对一题，得 1 分；'N' 表示答错一题，扣 1 分，但得分不能小于 0。

代码逻辑如下：

1. ‌输入读取‌：

   • 使用 std::cin >> sequence; 从标准输入读取一个字符串 sequence。这个字符串仅由 'Y' 和 'N' 组成，代表选手的答题情况。

2. ‌初始化得分‌：

   • 声明一个整数变量 score 并初始化为 0。这个变量将用于跟踪选手的当前得分。

3. ‌遍历字符序列‌：

   • 使用范围 for 循环 for (char c : sequence) 遍历字符串 sequence 中的每个字符 c。
   • 在循环体内，根据字符 c 的值更新得分：
     • 如果c是 'Y'，表示答对一题，因此使用 ++score;将得分增加 1。
     • 如果 c 是 'N'，表示答错一题，因此使用 --score; 将得分减少 1。
     • 紧接着，检查得分是否小于 0。如果是，则使用 score = 0; 将得分重置为 0，以确保得分不会变成负数。

4. ‌输出最终得分‌：

   • 使用 std::cout << score << std::endl; 将最终得分输出到标准输出。

重要的是要注意，得分在任何时候都不会小于 0，因为代码中有明确的检查来防止这种情况发生。每次答错后，都会检查得分，并在必要时将其重置为 0。

这个逻辑非常直接，它按照题目要求计算了选手的最终得分，并考虑了得分不能小于 0 的限制。

 T2 等差数列的素性

内存限制: 256 Mb时间限制: 1000 ms

题目描述

给定三个整数 n，a 与 d，表示一个项数为 n 的等差数列，首项为 a，公差为 d。

请统计，从这个等差数列中有多少数字是素数。

输入格式

• 三个整数： n，a 与 d

输出格式

• 单个整数：表示素数数量

数据范围

• 50%50% 的数据，1≤n≤1000
• 100%100% 的数据，1≤n≤10000
• 1≤d≤1000
• 1≤a≤1000

样例数据

输入:

5 1 2

输出:

3

说明:

3,5,7

解析

要解决这个问题，我们需要编写一个 C++ 程序，该程序将生成一个等差数列，并统计该数列中有多少个素数。以下是解决方案的步骤：

1. ‌读取输入‌：从标准输入读取三个整数 n（项数）、a（首项）和 d（公差）。

2. ‌生成等差数列‌：使用循环生成等差数列的每一项。等差数列的通项公式是 a_i = a + (i - 1) * d，其中 i 是项数索引，从 1 到 n。

3. ‌检查素数‌：对于等差数列中的每一项，检查它是否是素数。素数是大于 1 的自然数，除了 1 和它本身外，不能被其他自然数整除。

4. ‌统计素数‌：维护一个计数器，记录等差数列中素数的数量。

5. ‌输出结果‌：将素数的数量输出到标准输出。

以下是实现这个解决方案的 C++ 代码：

#include <iostream>
#include <cmath>

// 函数：检查一个数是否是素数
bool isPrime(int num) {
    if (num <= 1) return false; // 1 和负数不是素数
    if (num == 2) return true;  // 2 是素数
    if (num % 2 == 0) return false; // 偶数不是素数

    // 检查从 3 到 sqrt(num) 的奇数是否能整除 num
    for (int i = 3; i <= std::sqrt(num); i += 2) {
        if (num % i == 0) return false;
    }
    return true;
}

int main() {
    int n, a, d;
    std::cin >> n >> a >> d;

    int primeCount = 0;

    for (int i = 0; i < n; ++i) {
        int term = a + i * d;
        if (isPrime(term)) {
            ++primeCount;
        }
    }

    std::cout << primeCount << std::endl;

    return 0;
}

代码解释

• ‌isPrime 函数‌：这个函数接受一个整数作为参数，并返回一个布尔值，表示该整数是否是素数。它首先检查特殊情况（小于等于 1 的数、2 和偶数）。然后，它使用从 3 到 sqrt(num) 的奇数来检查是否存在能整除 num 的数。

• ‌main 函数‌：

  • 读取输入：使用 std::cin 读取 n、a 和 d。
  • 初始化素数计数器 primeCount 为 0。
  • 使用 for 循环生成等差数列的每一项，并调用 isPrime 函数检查该项是否是素数。如果是，则增加 primeCount。
  • 输出素数数量：使用 std::cout 输出 primeCount。

复杂度分析

• ‌时间复杂度‌：O(n * sqrt(m))，其中 n 是等差数列的项数，m 是等差数列中最大的数。对于每个数，我们都需要检查从 2 到 sqrt(m) 的数是否能整除它。
• ‌空间复杂度‌：O(1)，因为我们只需要存储几个整数变量和计数器。

这个代码应该在给定的时间限制和内存限制内运行良好，即使对于最大的输入规模（n = 10000）也是如此。

 T3 互质序列

内存限制: 256 Mb时间限制: 1000 ms

题目描述

给定一个长度为 �n 的序列 �1,�2,...,��a1​,a2​,...,an​，你可以在任意位置（即任意数字前后）插入一个你指定的数字。请问最少添加多少次，才能使整个序列中，相邻两个元素均互质？

输入格式

输入共两行：
第一行，一个正整数 �n ，
第二行，�n 个正整数，表示给定序列�1,�2,...,��a1​,a2​,...,an​。

输出格式

输出共一行：一个整数，表示答案。

数据范围

• 对于 30%30% 的数据，1≤n≤10
• 对于 60%60% 的数据，1≤n≤103，1≤ai​≤103
• 对于 100%100% 的数据，1≤n≤105，1≤ai​≤109

样例数据

输入:

4
6 3 2 8

输出:

2

说明:

最少添加两次，例如：在6和3之间插入一个5，在2和8之间插入一个3。

解析 

要解决这个问题，我们需要找到一种方法，通过插入最少的数字，使得给定序列中的相邻元素都互质（即最大公约数为1）。以下是一个基于贪心策略和动态规划的解决方案。

思路

1. ‌贪心策略‌：

   • 对于序列中的每对相邻元素 ai​ 和 ai+1​，如果它们不互质（即 gcd(ai​,ai+1​)>1），我们需要在这两个元素之间插入一个与它们都互质的数字。
   • 一个简单而有效的方法是插入数字1，因为1与任何数字都互质。但是，为了可能减少插入次数，我们可以尝试找到一个小于等于某个合理上限（如1000，因为大于1000的素数较少且不一定更有效）的最小素数来插入，该素数需要与相邻两数都互质。

2. ‌动态规划‌：

   • 我们可以使用动态规划来优化插入过程，但直接应用动态规划可能由于数据范围较大而不现实。
   • 不过，我们可以利用“贪心”地选择每个插入点最小化的思想，逐个处理相邻元素。

3. ‌实现细节‌：

   • 遍历给定序列，检查每对相邻元素是否互质。
   • 如果不互质，则尝试插入一个最小的素数（从2开始检测，逐步增大，直到找到一个与两相邻元素都互质的数）。
   • 统计插入次数。

代码实现

以下是基于上述思路的代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // For std::gcd in C++17, otherwise you may need to implement it

// Function to find the smallest number that is coprime with both a and b
int findSmallestCoprime(int a, int b) {
    // Start checking from 2 upwards for the smallest coprime number
    for (int i = 2; i <= 1000; ++i) { // Limit to a reasonable number like 1000
        if (std::gcd(i, a) == 1 && std::gcd(i, b) == 1) {
            return i;
        }
    }
    // If no such number found in the range (although theoretically there should be), return 1
    // 1 is always coprime with any number but might not be the most optimal in all cases
    return 1;
}

int main() {
    int n;
    std::cin >> n;
    
    std::vector<int> sequence(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> sequence[i];
    }
    
    int insertCount = 0;
    
    for (int i = 0; i < n - 1; ++i) {
        if (std::gcd(sequence[i], sequence[i + 1]) > 1) {
            // Adjacent elements are not coprime, we need to insert a number
            ++insertCount;
            // Optionally, we could insert the smallest coprime number found (here we just insert 1 for simplicity)
            // int coprime = findSmallestCoprime(sequence[i], sequence[i + 1]);
            // Insert coprime number logically here if needed (not changing sequence, just for understanding)
        }
    }
    
    std::cout << insertCount << std::endl;
    
    return 0;
}

说明

1. ‌输入处理‌：
   • 读取输入的长度 n 和序列。
2. ‌遍历序列‌：
   • 对每对相邻元素，检查它们是否互质。
   • 如果不互质，增加插入计数器。
3. ‌输出结果‌：
   • 输出插入次数。

优化

• 上述代码在实际情况下已经足够高效，因为它避免了不必要的复杂计算，并采用了简单的贪心策略。
• 如果需要进一步优化，可以预处理一些小的素数集合，或者对特定情况采用更高级的算法，但在大多数情况下，上述方法已经足够。

希望这个解决方案能够帮助你解决这个问题。

结束了！

对了，忘说了一句话：

要想c++成绩好，就来jiabei小课堂。

还有，点我主页，看我简介，别给那三个人点赞就完了