第十四届蓝桥杯省赛C++ C组所有题目以及题解（C++）【编程题均通过100%测试数据】

第一题《求和》【简单模拟】

【问题描述】

求1（含）至20230408（含）中每个数的和。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【代码】

#include <iostream>
using namespace std;
int main()
{long long res = 0;for(int i = 1;i<=20230408;i++) res += i;printf("%lld",res);// 请在此输入您的代码return 0;
}

【答案】

204634714038436

第二题《工作时长》【模拟】

【问题描述】

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【代码】

#include <bits/stdc++.h>
using namespace std;//2022是平年
int Month[13] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};int sum[520];
int month, day, h, mi, s; //月,日,时,分,秒int main() {int ans = 0;for (int i = 0; i < 520; i++) {string str;getline(cin, str);month = (str[6] - '0') + (str[5] - '0') * 10;day = (str[9] - '0') + (str[8] - '0') * 10;h = (str[12] - '0') + (str[11] - '0') * 10;mi = (str[15] - '0') + (str[14] - '0') * 10;s = (str[18] - '0') + (str[17] - '0') * 10;sum[i] = (Month[month - 1] + day) * 86400 + h * 3600 + mi * 60 + s;}sort(sum, sum + 520);for (int i = 0; i < 520; i += 2) {ans += sum[i + 1] - sum[i];}cout << ans << endl;return 0;
}

【答案】

5101913

第三题《三国游戏》【贪心】

本题题解参考这篇博客：【贪心】第十四届蓝桥杯省赛C++ / Java / Python C组《三国游戏》（C++）

第四题《填充》【贪心】

本题题解参考这篇博客：【贪心】第十四届蓝桥杯省赛C++ / Java / Python C组《填充》（C++）

第五题《翻转》【思维】

本题题解参考这篇博客：【思维】第十四届蓝桥杯省赛C++ C组/研究生组 Python A组/C组《翻转》（C++）

第六题《子矩阵》【单调队列】

本题题解参考这篇博客：【单调队列】第十四届蓝桥杯省赛C++ C组 Java C组/研究生组 Python A组《子矩阵》（C++）

第七题《互质数的个数》【欧拉函数+快速幂】

本题题解参考这篇博客：【欧拉函数+快速幂】第十四届蓝桥杯省赛C++ C组 Java A组/研究生组 Python 研究生组《互质数的个数》（C++）

第八题《异或和之差》【trie树】

【题目描述】

给定一个含有 n 个元素的数组 $A_{i}$ ，你可以选择两个不相交的子段。

求出这两个子段内的数的异或和的差值的最大值。

【输入格式】

输入的第一行包含一个整数 n。

第二行包含 n 个整数 $A_{i}$ ，相邻整数之间使用一个空格分隔。

【输出格式】

输出一行包含一个整数表示答案。

【数据范围】

对于 40% 的评测用例，n ≤ 5000；
对于所有评测用例，2 ≤ n ≤ 2× $10^{5}$ ，0 ≤ $A_{i}$ ≤ $2^{20}$ 。

【输入样例】

6
1 2 4 9 2 7

【输出样例】

14

【样例解释】

两个子段可以分别选 1 和 4，9，2，差值为 15−1=14。

【思路】

求异或最值，一般用trie树做。

trie树可以在len(num)的时间内求出与num异或最大/最小的值
题目求的是区间，我们可以维护一个前缀异或和sum[i],那么我们求一段异或和最大，也就是求前缀和中的与sum[i]异或最大的值，最小同理，

题目求的是两段区间的差值最大，因为两段区间不相交，我们可以先求出前缀的最大/最小值，后缀在求一遍，答案就是前缀最大值-后缀最小值 or 后缀最大值-前缀最小值

【代码】

#include <bits/stdc++.h>using namespace std ;
typedef long long LL ;
typedef pair<LL,int> PLI ; 
const int N = 1e6 + 10 ; int  n , a[N] ; 
int son[2][N] , idx ; 
int mx[N] , mi[N] ;void insert(int x)
{int p = 0 ; for(int i = 20 ; i >= 0 ; i --){int u = (x >> i) & 1 ; if(!son[u][p]) son[u][p] = ++ idx ; p = son[u][p] ; }
}int query_mi(int x)
{int p = 0 , res = 0;for(int i = 20 ; i >= 0 ; i --){int u = (x >> i) & 1 ; if(!son[u][p]){u = !u ; res |= (1 << i) ; }p = son[u][p] ;}return res ; 
}
int query_mx(int x)
{int p = 0 , res = 0;for(int i = 20 ; i >= 0 ; i --){int u = (x >> i) & 1 ; if(son[!u][p]) res |= (1 << i) ;else u = !u ;  p = son[!u][p] ; }return res ; 
}int main()
{cin >> n ;for(int i = 1 ; i <= n; i ++) cin >> a[i] ; mx[0] = 0 , mi[0] = 2e9 ;int sum = 0 ;insert(sum) ; for(int i = 1 ; i <= n ; i ++){sum ^= a[i] ; mx[i] = max(mx[i - 1] , query_mx(sum)) ;mi[i] = min(mi[i - 1] , query_mi(sum)) ; insert(sum) ; }memset(son , 0 , sizeof son) ; idx = 0 ; sum = 0 ;int ans = 0 , mx2 = 0 , mi2 = 2e9; insert(sum) ; for(int i = n ; i ; i --){sum ^= a[i] ; mx2 = max(mx2 , query_mx(sum)) ; mi2 = min(mi2 , query_mi(sum)) ; ans = max({ans , mx[i - 1] - mi2 , mx2 - mi[i - 1]}) ; insert(sum) ; }cout << ans << endl ;return 0 ;
}

第九题《公因数匹配》【质因数分解】

【题目描述】

给定 n 个正整数 $A_{i}$ ，请找出两个数 i,j 使得 i<j 且 $A_{i}$ 和 $A_{j}$ 存在大于 1 的公因数。

如果存在多组 i,j，请输出 i 最小的那组。

如果仍然存在多组 i,j，请输出 i 最小的所有方案中 j 最小的那组。

【输入格式】

输入的第一行包含一个整数 n。

第二行包含 n 个整数分别表示 $A_{1}$ , $A_{2}$ ,⋅⋅⋅, $A_{n}$ ，相邻整数之间使用一个空格分隔。

【输出格式】

输出一行包含两个整数分别表示题目要求的 i,j，用一个空格分隔。

由于官方没有提及无解时如何进行输出，所以本题目前保证有解。

【数据范围】

对于 40% 的评测用例，n≤5000；
对于所有评测用例，1≤n≤ $10^{5}$ ，1≤Ai≤ $10^{6}$ 。

【输入样例】

5
5 3 2 6 9

【输出样例】

2 4

【代码】

#include <iostream>
#include <algorithm>
#include <vector>
#define x first // 宏定义，方便使用pair中的两个元素
#define y second
using namespace std;
typedef pair<int, int> PII; // 定义pair类型，用于存放下标
const int N = 1e6 + 10;
int n;
int a[N]; // a数组用于存放每个质因子在数列中最后一次出现的位置
vector<PII> v; // 存放有重叠的两个数的下标
int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++){int x;scanf("%d", &x);// 对x进行质因数分解for (int j = 2; j <= x / j; j ++){if (x % j == 0){// 如果j已经在数列中出现过了，说明有至少一个数和当前数在j这个质因子上有重叠if (a[j])   v.push_back({a[j], i}); else    a[j] = i; // 否则将j在a数组中标记为当前数在数列中的下标while (x % j == 0)  x /= j; // 将j从x中除掉，以便下一个质因子的分解}}if (x > 1)  {// 如果x剩下了一个大于1的质因子，同上处理if (a[x])   v.push_back({a[x], i});else    a[x] = i;}}sort(v.begin(), v.end()); // 按照第一个元素（之前标记的下标）排序printf("%d %d", v[0].x, v[0].y); // 输出第一个元素即可return 0;
}

第十题《子树的大小》【模拟】

【题目描述】

【输入格式】

输入包含多组询问。

输入的第一行包含一个整数 T，表示询问次数。

接下来 T 行，每行包含三个整数 n,m,k 表示一组询问。

【输出格式】

输出 T 行，每行包含一个整数表示对应询问的答案。

【数据范围】

对于 40% 的评测用例，T≤50，n≤ $10^{6}$ ，m≤16；
对于所有评测用例，1≤T≤ $10^{5}$ ，1≤k≤n≤ $10^{9}$ ，2≤m≤ $10^{9}$ 。

【输入样例】

3
1 2 1
11 3 4
74 5 3

【输出样例】

1

2

24

【思路】

题解来源：AcWing 4971. 子树的大小 - AcWing

【代码】

#include<iostream>
#include<cstring>
#include<algorithm>#define int long long 
using namespace std;typedef long long ll;int n, m;
int k;
int sum;
signed main()
{int T;cin >> T;while(T --){cin >> n >> m >> k;int t = 1;sum = 1;while(sum < k){t *= m;sum += t;}int ans  = 0, p = 1;int l = k - (sum - t) - 1;while(sum < n){ans += p;l = l * m;t *= m;p *= m;sum += t;}n -= sum - t;ans += min(p, max(0ll, n - l));cout << ans << endl;}return 0;
}