文章目录
1. 求和2. 工作时长3. 三国游戏4. 填充5. 翻转6. 子矩阵8. 异或和之差10. 子树的大小第14届蓝桥杯省赛真题，关于数论的题目不是很会，又没理解的很清楚，所以有两道的题解没有发出来。
这两道题：互为 质数的个数和 公因数匹配。
1. 求和
这道题很简单的，直接对其进行求和就好了，可以使用循环求和，也可以利用那个等差数列的公式((s1 + sn) * n) / 2.
最后的答案就是204634714038436，但是如果用编程算的话记得得开long long.
2. 工作时长
这道题是给我们一堆数据，表示一个人这一年中的所有工作时长，并且题目中已经要求其上班下班只打一次卡。
所以这道题的思路是很简单的，只需要对数据进行排序，然后每两个进行一对处理，即可求出这次的共工作时长，然后将所有的求出来就好了。
感觉难点在于读入数据很麻烦，需要注意一些细节。
#include <iostream>#include <algorithm> using namespace std;const int N = 530;struct Data{int month,day;int h,m,s;}d[N];bool cmp(Data a, Data b){if (a.month != b.month)return a.month < b.month;else if (a.day != b.day)return a.day < b.day;else if (a.h != b.h)return a.h < b.h;else if (a.m != b.m)return a.m < b.m;elsereturn a.s < b.s;}int main(){//读入数据 string s;for (int i = 0; i < 520; i++){getline(cin,s);//读入一行//s.c_str(), 将string 形式的s 转化成 c语言中的char* 的形式。 sscanf(s.c_str(),"2022-%d-%d %d:%d:%d",&d[i].month,&d[i].day,&d[i].h,&d[i].m,&d[i].s);}//将其进行排序 sort(d, d + 520, cmp);//计算答案 int ans = 0;for (int i = 0; i < 520 - 1; i += 2){//分别求出开始和结束的秒数，相减即可。int st = d[i].day * 24 * 60 * 60 + d[i].h * 60 * 60 + d[i].m * 60 + d[i].s; int ed = d[i + 1].day * 24 * 60 * 60 + d[i + 1].h * 60 * 60 + d[i + 1].m * 60 + d[i + 1].s;ans += ed - st;}printf("%d\n",ans);return 0;}3. 三国游戏
题目要求：
输入一个整数n表示有n个事件发生，接下来的三行，每一行输入n个数，表示其第i个事件发生的时候当前自己的士兵增加多少，要求我们求出所有事件中，如果有人获胜，然后那个获胜的国家的最多发生的次数是多少。
思路：
i 个事件发生时候,x,y,z,w分别表示魏蜀吴已经第i个事件的价值魏国的价值是w[i] = x[i] - y[i] - z[i]蜀国的价值是w[i] = y[i] - x[i] - z[i]吴国的价值是w[i] = y[i] - x[i] - y[i]既然求出每个国家相对于每个事件的简直之后，对价值数组进行降序的排序，利用sum变量来记录当前的价值，如果价值大于0的话就是使事件加1，否则就直接break掉，至此之后的事件都是递减的了。最后分别比较魏蜀吴三个国家的最大值就好了。 #include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;typedef long long LL;int n; //n 个事件 int X[N],Y[N],Z[N];//对应魏蜀吴三个国家 int w[N];//第i个事件的价值数组 bool cmp(int a, int b){return a > b;}int GetAns(int* a, int* b, int* c){//初始化价值数组 memset(w, 0, sizeof w);for (int i = 1; i <= n; i++)w[i] += a[i] - b[i] - c[i];//将其的价值按照从大到小的顺序排序 sort(w + 1, w + 1 + n, cmp);LL sum = 0;int ans = 0;for (int i = 1; i <= n; i++){//如果其中价值小于了0，就说明它不会胜利，又因为是从大到小排序的，所以之后的一定不会在胜利了。 sum += w[i];if (sum > 0)ans++;elsebreak; }if (ans == 0)return -1;elsereturn ans;}int main(){scanf("%d",&n);//读入数据 for (int i = 1; i <= n; i++)scanf("%d",&X[i]);for (int i = 1; i <= n; i++)scanf("%d",&Y[i]);for (int i = 1; i <= n; i++)scanf("%d",&Z[i]);//分别求出三个国家中，每个国家获胜的最多次数是多少，如果获胜不了，返回-1。 int ans_A = GetAns(X,Y,Z);int ans_B = GetAns(Y,Z,X);int ans_C = GetAns(Z,X,Y);printf("%d\n",max(ans_A,max(ans_B,ans_C)));return 0;}4. 填充
题目要求：
将输入的字符串其中的？换成0或者1，看看最多能组成多少个无重叠的连续00或者11.
思路：
#include <bits/stdc++.h>using namespace std;const int N = 1e6 + 10;char s[N];int main(){scanf("%s",s);int len = strlen(s); int res = 0;for (int i = 0; i < len - 1; i++){if (s[i] == s[i + 1] || s[i] == '?' || s[i + 1] == '?'){res ++;i++;}}printf("%d\n",res);return 0;}5. 翻转
题目要求：
题目要求输入字符串s和t,然后将s转化成t转化的要求满足s[i - 1] == s[i + 1]条件才可以转化s[i]。
思路：
s进行遍历，比较s[i] 和 s[j]如果两者不一致的时候，就去看看是否能替换，如果能替换那么替换次数加1，否则的话，直接返回-1就好了。 #include <bits/stdc++.h>using namespace std;const int N = 1e6 + 10;int n;char s[N],t[N]; //t为主串，a为子串，将s翻转成t. int GetAns(){int len = strlen(s);int res = 0;for (int i = 0; i < len; i++){//如果说当前的字符不相等的情况下才去考虑是否翻转 if (s[i] != t[i]){//首尾不可翻转 if (i == 0 || i == len - 1)return -1; else if (s[i - 1] != s[i + 1]) //前后不相同不可翻转return -1; else //可以翻转 res++;}}return res;}int main(){scanf("%d",&n);while (n--){scanf("%s%s",s,t); if (strcmp(s,t) == 0) printf("0\n"); else { int ans = GetAns(); if (ans == 0) printf("-1\n"); else printf("%d\n",ans); }}return 0;}6. 子矩阵
题目要求：
给我们一个n * m的矩阵，然后对矩阵中所有a * b的子矩阵进行求解最小值和最大值。将每一块矩阵的最小值和最大值的乘积相加在一起。
暴力：
这道题可以直接使用暴力来做，对于矩阵中每一个位置开始，向左，下延申矩阵，然后求出其的最大值和最小值，将其乘积加起来就好了，但是下面的做法只能过6个测试用例，感觉也还行，关键写起来也简单，比赛的时候，先考虑暴力做法吧，先把暴力的分拿了。
#include <bits/stdc++.h>using namespace std;const int N = 1010, MOD = 998244353;typedef long long LL;int n, m, A, B;int g[N][N];int main(){//输入数据 scanf("%d%d%d%d",&n,&m,&A,&B); for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)scanf("%d",&g[i][j]);LL res = 0;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++){int mi,ma;mi = ma = g[i][j];for (int k = i; k < A + i; k++)for (int l = j; l < B + j; l++){mi = min(mi, g[k][l]);ma = max(ma, g[k][l]);}res = (res + (LL)mi * ma) % MOD;}printf("%d\n",res);return 0;} 二维滑动窗口：
这一种方法则可以通过全部的测试用例
b的的最大值和最小值。接着在对每一列进行一个窗口大小为a最大值和最小值。然后就可以使两者相乘的和加起来就好了。 #include <bits/stdc++.h>using namespace std;const int N = 1010, MOD = 998244353;typedef long long LL;int n, m, A, B;int g[N][N], rmax[N][N], rmin[N][N];int que[N];void get_max(int* a, int* b, int size, int k){ int front = 0, rear = 0; for (int i = 0; i < size; i++) { if (front != rear && que[front] <= i - k) front++; while (front != rear && a[que[rear - 1]] <= a[i]) rear--; que[rear++] = i; if (i >= k - 1) b[i] = a[que[front]]; }}void get_min(int* a, int* b, int size, int k){ int front = 0, rear = 0; for (int i = 0; i < size; i++) { if (front != rear && que[front] <= i - k) front++; while (front != rear && a[que[rear - 1]] >= a[i]) rear--; que[rear++] = i; if (i >= k - 1) b[i] = a[que[front]]; }}int main(){ scanf("%d%d%d%d",&n, &m, &A, &B); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d",&g[i][j]); //预处理每一行的最大值和最小值 for (int i = 0; i < n; i++) { get_max(g[i], rmax[i], m, B); get_min(g[i], rmin[i], m, B); } int res = 0; int a[N],b[N],c[N]; //a临时存储A区间内的最大值或者最小值。 b存储矩阵中的最大值， c存储矩阵中的最小值。 //i从0开始的是不会有值的。 for (int i = B - 1; i < m; i++) { for (int j = 0; j < n; j++) a[j] = rmax[j][i]; get_max(a, b, n, A); for (int j = 0; j < n; j++) a[j] = rmin[j][i]; get_min(a, c, n, A); //j与外层循环的i意思一致。 for (int j = A - 1; j < n; j++) res = (res + (LL)b[j] * c[j]) % MOD; } printf("%d\n",res); return 0;}8. 异或和之差
题目要求：
题目要求我们求出给定的一个数组中，两个不相交子数组，的异或和之差，也就是所选的两个子数组相减，使这个差值变得最大，返回这个差值。
思路：
ls[N]和rs[N].想象一下，前缀和的性质，s[l,r] = s[r] - s[l - 1] (l <= r)其实这个性质同样可以运用到异或和数组中去，s[l,r] = s[r] ^ s[l - 1]. 因为a ^ b = c 即可得出 b ^ c = a, a ^ c = b。
所以也就能发现：s [l , r] = s[r] ^ s[l - 1]
s是一个前缀和数组，里面其实存放的是每一个区间的前缀异或和，我们对数组进行字典树的一个很经典的操作，就可以得出s[i] 异或那个数最大。既然可以求出1个i那么就可以求出所有的 i.下面就有点动态规划的意思了.状态表示:集合：rmax[i] 表示前i个异或和区间属性：对于所有的异或和区间取最大值。状态计算：rmax[i] = max(rmax[i - 1], query_max(ls[i], lson)).后面的函数表示从字典树中查找出与ls[i]异或最大的值。因为是前缀和数组，所以求出最大值，也就求出了区间。像这样子的数组一共又4个。而字典树分为左右两边，整体代码如下：
#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10, INF = 0x3f3f3f3f;int n;int a[N], ls[N], rs[N]; //数组与前缀异或和 后缀异或和int lmax[N], lmin[N], rmax[N], rmin[N]; //左右区间的最值int lson[1 << 22][2], rson[1 << 22][2], idx; //左边区间的字典树以及右边区间的字典树。void Insert(int x, int son[][2]){ int r = 0; for (int i = 20; i >= 0; i--) { int u = x >> i & 1; if (!son[r][u]) son[r][u] = ++idx; r = son[r][u]; }}int query_max(int x, int son[][2]){ int r = 0, res = 0; for (int i = 20; i >= 0; i--) { int u = x >> i & 1; if (son[r][!u]) { res += 1 << i; r = son[r][!u]; } else r = son[r][u]; } return res;}int query_min(int x, int son[][2]){ int r = 0, res = 0; for (int i = 20; i >= 0; i--) { int u = x >> i & 1; if (!son[r][u]) { res += 1 << i; r = son[r][!u]; } else r = son[r][u]; } return res;}int main(){ //读入数据 scanf("%d",&n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); //初始化四个数组 for (int i = 0; i <= n + 1; i++) { rmax[i] = lmax[i] = 0; rmin[i] = lmin[i] = INF; } Insert(0, lson); for (int i = 1; i <= n; i++) { ls[i] = ls[i - 1] ^ a[i]; lmax[i] = max(lmax[i - 1], query_max(ls[i], lson)); lmin[i] = min(lmin[i - 1], query_min(ls[i], lson)); Insert(ls[i], lson); } idx = 0; Insert(0, rson); for (int i = n; i >= 1; i--) { rs[i] = rs[i + 1] ^ a[i]; rmax[i] = max(rmax[i + 1], query_max(rs[i], rson)); rmin[i] = min(rmin[i + 1], query_min(rs[i], rson)); Insert(rs[i], rson); } int res = 0; for (int i = 1; i <= n - 1; i++) res = max(res, max(lmax[i] - rmin[i + 1], rmax[i + 1] - lmin[i])); printf("%d\n", res); return 0;}10. 子树的大小
题目要求：
对于每一行的数据表示n个节点，完全m叉树，求节点k的子树有多少个，包括k节点在内。
思路：
其实只要找出k节点的左右孩子lc,rc就好了，感觉这个需要不断的尝试，才能找到规律。lc = (k - 1) * m + 2, rc = k * m + 1.
m叉树,所以只有其左孩子和右孩子都小于等于节点n的话，就能计算出该层的节点个数是多少。当发现左孩子大于n的时候，退出循环即可。当发现右孩子大于等于n的时候，是rc = n, 进行最后一次操作就好了。 #include <bits/stdc++.h>using namespace std;typedef long long LL;int T;int n,m,k;int Helper(){int res = 1;LL lc = k, rc = k;if (k > n)//节点不存在return 0;bool flag = true;while (flag){ //计算左右孩子lc = (lc - 1) * m + 2;rc = rc * m + 1;//左孩子大于总结点个数就说明该层啥也没有，不需要增加了，直接break就好了。if (lc > n)break; //右孩子大于等于n的话，将右孩子变成n 执行最后一次节点增加操作即可。if (rc >= n){rc = n;flag = false;}res += rc - lc + 1;} return res;}int main(){scanf("%d",&T);while (T --){scanf("%d%d%d",&n,&m,&k);printf("%d\n",Helper());}return 0;}