A. 求和：
问题描述
求 11 （含）至 2023040820230408 （含）中每个数的和。
思路：等差数列，d位1，Sn = （a1+an）*n/2;
参考代码：
#include <iostream>
using namespace std;
typedef long long LL;
int main()
{
LL n = 20230408;
LL res = n*(n+1)/2;
cout<<res;
return 0;
}B.工作时长：
问题描述：
小蓝手里有一份 20222022 年度自己的上班打卡记录文件，文件包含若干条打卡记录，每条记录的格式均为“yyyy-MM-dd HH:mm:ssyyyy-MM-dd HH:mm:ss”，即按照年-月-日 时:分:秒的形式记录着一个时间点（采用 2424 小时进制）。由于某些原因，这份文件中的时间记录并不是按照打卡的时间顺序记录的，而是被打乱了。但我们保证小蓝每次上班和下班时都会正常打卡，而且正好打卡一次，其它时候不会打卡。每一对相邻的上-下班打卡之间的时间就是小蓝本次的工作时长，例如文件内容如下的话：
2022-01-01 12:00:05
2022-01-02 00:20:05
2022-01-01 07:58:02
2022-01-01 16:01:35
表示文件中共包含了两段上下班记录，1）20222022-0101-0101 0707:5858:02∼202202∼2022-0101-0101 1212:0000:0505，工作时长为 1452314523 秒；2）20222022-0101-0101 1616:0101:35∼202235∼2022-0101-0202 0000:2020:0505，工作时长为 2991029910 秒；工作时长一共是 14523+29910=4443314523+29910=44433 秒。现在小蓝想知道在 20222022 年度自己的工作时长一共是多少秒？
思路：
直接将文件里的时间点复制到excel表转换成时间，然后后排第二个减去第一个求和。
C.三国游戏
问题描述：
小蓝正在玩一款游戏。
游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z（一开始可以认为都为 00）。
游戏有 n个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i� 个事件发生时会分别让 X,Y,Z 增加 Ai,Bi,Ci。
当游戏结束时 (所有事件的发生与否已经确定)，如果 X,Y,Z 的其中一个大于另外两个之和，我们认为其获胜。
例如，当 X>Y+Z 时，我们认为魏国获胜。
小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?
如果不存在任何能让某国获胜的情况，请输出 −1。
输入格式
输入的第一行包含一个整数 n。
第二行包含 n个整数表示 Ai，相邻整数之间使用一个空格分隔。
第三行包含 n个整数表示 Bi，相邻整数之间使用一个空格分隔。
第四行包含 n个整数表示 Ci，相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 40%40% 的评测用例，n≤500；
对于 70%70% 的评测用例，n≤5000；
对于所有评测用例，1≤n≤10^5，0≤Ai,Bi,Ci≤10^9。
注意，蓝桥杯官方给出的关于 Ai,Bi,Ci的数据范围是 1≤Ai,Bi,Ci≤10^9，但是这与给出的输入样例相矛盾，因此予以纠正。
输入样例：
3
1 2 2
2 3 2
1 0 7
输出样例：
2
样例解释
发生两个事件时，有两种不同的情况会出现获胜方。
发生 1,21,2 事件时蜀国获胜。
发生 1,31,3 事件时吴国获胜。
题解思路：
w1 = a1- b1 - c1;
w2 = a2-b2-c2;
........
可以转换最多选取多少个w，使其和>0；
可以直接求出每个w，从大到小排序，再相加不断更新次数，当出现<=0时返回答案，再用max求出每个w的最大值；
题解：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int a[N],b[N],c[N];
int w[N];
int n;
int get(int x[],int y[],int z[])
{
for(int i=0;i<n;i++) w[i] = x[i] - y[i] - z[i];
LL ans = 0;
int s = -1;
sort(w,w+n,greater<int>());
for(int i=0;i<n;i++)
{
ans += w[i];
if(ans>0) s = i+1;
else break;
}
return s;
}
int main()
{
scanf("%d", &n);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
for(int i=0;i<n;i++) cin>>c[i];
int res = max(get(a,b,c),max(get(b,a,c),get(c,a,b)));
cout<<res<<endl;
return 0;
}D. 填充
题目描述：
有一个长度为 n 的 0101 串，其中有一些位置标记为 ?，这些位置上可以任意填充 0 或者 1，请问如何填充这些位置使得这个 0101 串中出现互不重叠的 00 和 11 子串最多，输出子串个数。
输入格式
输入一行包含一个字符串。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于所有评测用例，1≤n≤10^6。
输入样例：
1110?0
输出样例：
2
样例解释
如果在问号处填 0，则最多出现一个 00 和一个 11：111000。
解题思路：
一次遍历，每次遍历检查1.当前点与下一点是否相等；2.当前是？；3.当前点的下一点是？
则cnt++,且跳过下一个点。
相当于消消乐游戏，而?则可以当作万能牌来使用。
参考代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
char s[N];
int main()
{
scanf("%s", s);
int len = strlen(s);
int cnt = 0;
for(int i=0;i<len-1;i++)//范围要到len-1.
if(s[i]==s[i+1] || s[i]=='?' || s[i+1]=='?')
{
cnt++;
i++;
}
cout<<cnt<<endl;
return 0;
}E.翻转
题目描述：
小蓝用黑白棋的 n 个棋子排成了一行，他在脑海里想象出了一个长度为 n的 0101 串 T，他发现如果把黑棋当做 11，白棋当做 00，这一行棋子也是一个长度为 n 的 0101 串 S。
小蓝决定，如果在 S 中发现一个棋子和它两边的棋子都不一样，就可以将其翻转变成另一个颜色。
也就是说，如果 S 中存在子串 101101 或者 010010，就可以选择将其分别变为 111111 和 000000，这样的操作可以无限重复。
小蓝想知道最少翻转多少次可以把 S 变成和 T 一模一样。
输入格式
输入包含多组数据。
输入的第一行包含一个正整数 D 表示数据组数。
后面 2D行每行包含一个 0101 串，每两行为一组数据，第 2i−1行为第 i 组数据的 Ti，第 2i行为第 i 组数据的 Si，Si 和 Ti 长度均为 ni。
输出格式
对于每组数据，输出一行包含一个整数，表示答案，如果答案不存在请输出 −1。
数据范围
对于 20%20% 的评测用例，1≤∑1Dni≤10；
对于所有评测用例，保证 1≤∑1Dni≤10^6，ni>0。
输入样例：
2
1000111
1010101
01000
11000
输出样例：
2
-1解题思路：
由于一定有答案，所有将目标串ed与待翻转串st一一对比，发现不同则进行交换，最后一定能的得到答案否则输出-1。
参考代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n;
char a[N],b[N];
int main()
{
scanf("%d",&n);
while (n -- )
{
scanf("%s%s", a, b);
int len = strlen(b);
int ans = 0;
for(int i=0;i<len;i++)
if(a[i]!=b[i])
{
if(!i || i==len-1 || b[i-1]==b[i] ||b[i+1]==b[i])
{
ans = -1;
break;
}
ans++;
b[i]=a[i];
}
cout<<ans<<endl;
}
return 0;
}F.子矩阵
题目描述：
给定一个 n×m （n 行 m 列）的矩阵。
设一个矩阵的价值为其所有数中的最大值和最小值的乘积。
求给定矩阵的所有大小为 a×b （a行 b列）的子矩阵的价值的和。
答案可能很大，你只需要输出答案对 998244353998244353 取模后的结果。
输入格式
输入的第一行包含四个整数分别表示 n,m,a,b，相邻整数之间使用一个空格分隔。
接下来 n行每行包含 m个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 Ai,j。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 40%40% 的评测用例，1≤n,m≤100；
对于 70%70% 的评测用例，1≤n,m≤500；
对于所有评测用例，1≤a≤n≤1000，1≤b≤m≤1000，1≤Ai,j≤10^9。
输入样例：
2 3 1 2
1 2 3
4 5 6
输出样例：
58
样例解释
1×2+2×3+4×5+5×6=581×2+2×3+4×5+5×6=58。
解题思路：
（图片来源与acwing y总的题解视频）
由图可以看到可以通过单调队列来求取每行一个区间的最大值与最小值，
再基于每行最值求每列的最值，最终结果相乘就是答案；
考点：单调队列，在一个长位n的区间滑动着求取每k个区间的最值（k<n）.
参考代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1010,MOD = 998244353;
int w[N][N],rmax[N][N],rmin[N][N];
int n,m,A,B;
int q[N];
void get_max(int a[],int b[],int tot,int k)
{
int hh = 0,tt = -1;
for(int i=0;i<tot;i++)
{
if(hh<=tt && q[hh]<=i-k) hh++;
while(hh<=tt && a[q[tt]]<=a[i]) tt--;
q[++tt] = i;
if(i>=k-1) b[i] = a[q[hh]];
}
}
void get_min(int a[],int b[],int tot,int k)
{
int hh = 0,tt = -1;
for(int i=0;i<tot;i++)
{
if(hh<=tt && q[hh]<=i-k) hh++;
while(hh<=tt && a[q[tt]]>=a[i]) tt--;
q[++tt] = i;
if(i>=k-1) b[i] = a[q[hh]];
}
}
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",&w[i][j]);
for(int i=0;i<n;i++)
{
get_max(w[i],rmax[i],m,B);
get_min(w[i],rmin[i],m,B);
}
int a[N],b[N],c[N];
LL ans = 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);
for(int j=A-1;j<n;j++)
ans = (ans + (LL)b[j] * c[j]) % MOD;
}
cout<<ans % MOD<<endl;
return 0;
}
G.互质个数
题目描述：
给定 a,b，求 1≤x<a^b 中有多少个 x 与 a^b 互质。
由于答案可能很大，你只需要输出答案对 998244353998244353 取模的结果。
输入格式
输入一行包含两个整数分别表示 a,b，用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 30%30% 的评测用例，ab≤10^6；
对于 70%70% 的评测用例，a≤10^6，b≤10^9；
对于所有评测用例，1≤a≤10^9，1≤b≤10^18。
输入样例1：
2 5
输出样例1：
16
输入样例2：
12 7
输出样例2：
11943936解题思路：
求一个数的质数我们可以利用欧拉函数：
本题是求a^b的欧拉函数可以转换为：
而a^b-1则可以用快速幂来求取。
参考代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MOD = 998244353;
LL a,b;
LL qmi(LL a,LL k)
{
LL res = 1 % MOD;
while(k)
{
if(k & 1) res = res * a % MOD;
k >>= 1;
a = a * a % MOD;
}
return res;
}
int main()
{
scanf("%lld%lld", &a, &b);
if(a==1)
{
cout << "0"<<endl;
return 0;
}
int res = a,x = a;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
res = res/i*(i-1);
while(x%i==0) x/=i;
}
}
if(x>1) res = res / x * (x-1);
cout<<(res * qmi(a,b-1))%MOD<<endl;
return 0;
}H.异或和之差
题目描述：
给定一个含有 n 个元素的数组 Ai，你可以选择两个不相交的子段。
求出这两个子段内的数的异或和的差值的最大值。
输入格式
输入的第一行包含一个整数 n。
第二行包含 n 个整数 Ai，相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 40% 的评测用例，n≤5000；
对于所有评测用例，2≤n≤2×10^5，0≤Ai≤2200。
输入样例：
6
1 2 4 9 2 7
输出样例：
14
样例解释
两个子段可以分别选 11 和 4，9，24，9，2，差值为 15−1=14。
解题思路及参考代码：
1.暴力枚举每次对比求取最大和最小的异或值，最后相减（蓝桥杯官网能过60%）
#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef long long LL;
const int N = 1000010;
LL a[N];
int n;
int main()
{
LL emax = -INT_MIN, emin = INT_MAX;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%lld", &a[i]);
for (int i = 0; i < n; i ++ )
{
for (int j = i+1; j < n; j ++ )
{
emax = max(emax,a[i]^a[j]);
emin = min(emin,a[i]^a[j]);
}
}
cout<<emax-emin<<endl;
return 0;
}
2.求异或最值，一般用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 ;
}
作者：乀
链接：https://www.acwing.com/solution/content/186318/
来源：AcWingI.公因数匹配
题目描述：
给定 n 个正整数 Ai，请找出两个数 i,j 使得 i<j 且 Ai和 Aj 存在大于 11 的公因数。
如果存在多组 i,j，请输出 i最小的那组。
如果仍然存在多组 i,j，请输出 i 最小的所有方案中 j 最小的那组。
输入格式
输入的第一行包含一个整数 n。
第二行包含 n个整数分别表示 A1,A2,⋅⋅⋅,An1,2,···，相邻整数之间使用一个空格分隔。
输出格式
输出一行包含两个整数分别表示题目要求的 i,j，用一个空格分隔。
由于官方没有提及无解时如何进行输出，所以本题目前保证有解。
数据范围
对于 40% 的评测用例，n≤5000；
对于所有评测用例，1≤n≤10^5，1≤Ai≤10^6。
输入样例：
5
5 3 2 6 9
输出样例：
2 4解题思路：
求取每次输入值 i 的质因数（和因数已经被质因数分解了不影响），并且将其质因数当作数组下标，且该位置存储读入的数i，后续再有新的数读入先判断其质因数是否已背标记，如果有则说明有公因数了。将新读入的数与之前存储的数一并读入到pair中。最后再通过排序求得最小的一对。
参考代码：
#include<iostream>
#include<algorithm>
#include<vector>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 1e6 + 10;
vector<PII> p;
int n,x;
int a[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
for(int j = 2;j <= x/j; j++)
{
if(x % j == 0)
{
if(a[j]) p.push_back({a[j],i});
else a[j] = i;
while(x % j == 0) x /= j;
}
}
if(x>1)
{
if(a[x]) p.push_back({a[x],i});
else a[x] = i;
}
}
sort(p.begin(),p.end());
printf("%d %d\n",p[0].x,p[0].y);
return 0;
}J.子树的大小
题目描述：
给定一棵包含 n 个结点的完全 m 叉树，结点按从根到叶、从左到右的顺序依次编号。
例如下图是一个拥有 11 个结点的完全 3 叉树。
你需要求出第 k 个结点对应的子树拥有的结点数量。
输入格式
输入包含多组询问。
输入的第一行包含一个整数 T，表示询问次数。
接下来 T行，每行包含三个整数 n,m,k, 表示一组询问。
输出格式
输出 T 行，每行包含一个整数表示对应询问的答案。
数据范围
对于 40%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解题思路：
题目要求：
对于每一行的数据表示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;
}
作者：layfolk
链接：https://www.acwing.com/solution/content/227484/
来源：AcWing
