C/C++蓝桥杯算法真题打卡（Day5）

一、P8772 [蓝桥杯 2022 省 A] 求和 - 洛谷

算法代码：

#include<bits/stdc++.h>  // 包含标准库中的所有头文件，方便编程
using namespace std;     // 使用标准命名空间，避免每次调用标准库函数时都要加 std::int main() {int n;               // 声明一个整数变量 n，用于存储输入的整数个数cin >> n;            // 从标准输入读取 n 的值vector<int> a(n);    // 声明一个大小为 n 的整数向量 a，用于存储输入的 n 个整数for(int i = 0; i < n; i++) {  // 循环 n 次，读取每个整数cin >> a[i];     // 将输入的整数存储到向量 a 的第 i 个位置}vector<long long> sum(n + 1, 0);  // 声明一个大小为 n+1 的长整型向量 sum，用于存储前缀和，初始化为 0for(int i = 0; i < n; i++) {      // 循环 n 次，计算前缀和sum[i + 1] = sum[i] + a[i];   // 计算前缀和：sum[i+1] = sum[i] + a[i]}long long s = 0;     // 声明一个长整型变量 s，用于存储最终的两两相乘再相加的和，初始化为 0for(int i = 0; i < n; i++) {      // 循环 n 次，计算两两相乘再相加的和s += a[i] * (sum[n] - sum[i + 1]);  // 累加 a[i] 与后面所有元素的乘积}cout << s;           // 输出最终的结果 sreturn 0;            // 返回 0，表示程序正常结束
}

关键点解释：

前缀和数组 sum：
- sum[i] 表示数组 a 的前 i 个元素的和。
- sum[i + 1] = sum[i] + a[i] 用于计算前缀和。
两两相乘再相加的和 s：
- sum[n] - sum[i + 1] 表示从 a[i+1] 到 a[n-1] 的和。
- a[i] * (sum[n] - sum[i + 1]) 表示 a[i] 与后面所有元素的乘积之和。
- 通过累加这些乘积，得到最终的结果 s。
时间复杂度：
- 该算法的时间复杂度为 O(n)，因为只需要遍历数组两次（一次读取输入，一次计算前缀和和最终结果）。
空间复杂度：
- 使用了额外的 sum 数组，空间复杂度为 O(n)。

二、 P8716 [蓝桥杯 2020 省 AB2] 回文日期 - 洛谷

算法代码：

#include<bits/stdc++.h>  // 包含标准库中的所有头文件，方便编程
using namespace std;     // 使用标准命名空间，避免每次调用标准库函数时都要加 std::int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};  // 打个月份表，存储每个月的天数// 判断日期是否合法
bool check_valid(int date) {int year = date / 10000;  // 提取年份int month = date % 10000 / 100;  // 提取月份int day = date % 100;  // 提取日if (day == 0 || month <= 0 || month > 12) return false;  // 显然的不合法情况if (month != 2 && day > months[month]) return false;  // 月份不是2，day不合法就不合法if (month == 2) {  // 月份是2if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {  // 判断闰年if (day > 29) return false;  // 是闰月，day必须<=29} else if (day > 28) return false;  // 是平月，day必须<=28}return true;  // 日期合法
}// 判断字符串是否是回文
bool check_huiwen(string s) {int len = s.size();  // 获取字符串长度for (int i = 0, j = len - 1; i < j; i++, j--)  // i从前往后，j从后往前扫一遍if (s[i] != s[j]) return false;  // 不对称，就不回文return true;  // 字符串是回文
}// 判断字符串是否是ABABBABA型回文
bool check_ABAB(string s) {if (check_huiwen(s)) {  // 首先它得是个回文数// 接下来只需判断前4位是否合法if (s[0] != s[2] || s[1] != s[3] || s[0] == s[1]) return false;  // 结合ABABBABA思考return true;  // 是ABABBABA型回文}return false;  // 不是ABABBABA型回文
}int main() {int n; cin >> n;  // 读取输入的整数nbool flag = 0;  // 标记是否已经找到第一个回文数for (int i = n + 1; ; i++) {  // 从n+1开始枚举回文数if (check_valid(i)) {  // 判断日期是否合法string s = to_string(i);  // 将整数转换为字符串if (check_huiwen(s) && !flag) {  // 输出第一个回文数cout << i << endl;flag = 1;  // 标记已经找到第一个回文数}if (check_ABAB(s)) {  // 输出第一个特殊回文数cout << i;return 0;  // 找到特殊回文数后结束程序}}}return 0;  // 程序正常结束
}

代码思路

这段代码的主要目标是找到从给定日期 n 开始的第一个回文日期和第一个符合特定格式（ABABBABA）的回文日期。以下是代码的思路和实现步骤：

1. 准备工作

包含头文件和命名空间：
- #include<bits/stdc++.h>：包含所有标准库头文件，方便使用各种数据结构和函数。
- using namespace std;：使用标准命名空间，避免每次调用标准库函数时都要加 std::。
月份表：
- int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  - 用一个数组存储每个月的天数，方便后续判断日期的合法性。
  - 注意：2月的天数需要根据闰年动态调整。

2. 判断日期是否合法

函数 check_valid(int date)：
- 输入：一个整数 date，表示日期，格式为 YYYYMMDD。
- 功能：
  1. 提取年、月、日：
    - year = date / 10000：提取年份。
    - month = date % 10000 / 100：提取月份。
    - day = date % 100：提取日。
  2. 检查日期的合法性：
    - 如果 day == 0 或 month <= 0 或 month > 12，日期不合法。
    - 如果月份不是2月，且 day 超过该月的天数，日期不合法。
    - 如果是2月：
      - 判断是否是闰年：
        
        闰年规则：能被4整除但不能被100整除，或者能被400整除。
      - 如果是闰年，2月最多29天；否则最多28天。
- 返回值：如果日期合法，返回 true；否则返回 false。

3. 判断字符串是否是回文

函数 check_huiwen(string s)：
- 输入：一个字符串 s，表示日期。
- 功能：
  - 使用双指针法，从字符串的两端向中间扫描，判断字符是否对称。
  - 如果所有字符都对称，则是回文。
- 返回值：如果是回文，返回 true；否则返回 false。

4. 判断字符串是否是ABABBABA型回文

函数 check_ABAB(string s)：
- 输入：一个字符串 s，表示日期。
- 功能：
  1. 首先调用 check_huiwen(s) 判断是否是回文。
  2. 如果是回文，进一步检查是否符合ABABBABA格式：
    - ABABBABA格式要求：
      - 第1位 == 第3位。
      - 第2位 == 第4位。
      - 第1位 != 第2位。
- 返回值：如果符合ABABBABA格式，返回 true；否则返回 false。

5. 主函数逻辑

输入：
- 读取整数 n，表示起始日期。
初始化：
- bool flag = 0;：用于标记是否已经找到第一个回文日期。
枚举日期：
- 从 n + 1 开始，逐个枚举日期 i。
- 对每个日期 i：
  1. 调用 check_valid(i) 判断日期是否合法。
  2. 如果合法：
    - 将日期转换为字符串 s。
    - 调用 check_huiwen(s) 判断是否是回文：
      - 如果是回文且 flag == 0，输出该日期，并设置 flag = 1。
    - 调用 check_ABAB(s) 判断是否是ABABBABA型回文：
      - 如果是，输出该日期并结束程序。
结束条件：
- 找到第一个ABABBABA型回文日期后，程序结束。