前言

大家好！我是 EnigmaCoder。

• 本文是我的蓝桥杯刷题周计划的第一周内容，内含25题。刷题内容主要为C++库函数、STL容器和基础算法，每道题分为题目、代码、题解分析三部分，且附有原题链接。
• 希望能对您有帮助！

题目一

原题链接：lanqiao1389

题目

给定一个数组，其采用如下代码定义：

int data[200];
for(i = 0 ; i < 200 ; i ++）data[i] = 4 * i + 6;

现给定某个数，请你求出它在 data 数组中的位置（下标）。

输入描述
输入一个待查找的整数（该整数一定在数组 data 中）。

输出描述
输出该整数在数组中的指标。

输入输出样例
示例 1
输入

262
输出

64
示例 2
输入

438
输出

108

运行限制

• 最大运行时间：1s

• 最大运行内存: 128M

代码

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{int data[200];for(int i = 0 ; i < 200 ; i ++)data[i] = 4 * i + 6;int n;cin>>n;cout<<lower_bound(data,data+200,n)-data<<endl;return 0;
}

题解分析

本题可以使用整数二分查找解题，这里采用C++的lower_bound库函数，使解题更迅速、简洁。

• lower_bound(st,ed,x)库函数需要输入三个参数，前两个参数是迭代器，最后一个参数为目标元素。其返回第一个大于等于目标元素的迭代器。如果没有，就返回最后一个元素的下一个地址。
• 注意：查找区间[st ,ed)为左闭右开区间，所以题解中是[data,data+200)。
• 该库函数默认在升序序列中使用，如果要在降序序列中使用，则要加上比较函数。lower_bound(st,ed,x,greater<int>())

---

题目二

原题链接：lanqiao1265

题目

题目描述
给定一个长度为 N的数组 A，请你先从小到大输出它的每个元素，再从大到小输出它的每个元素。

输入描述
第一行包含一个整数 N

第二行包含 N 个整数 a1,…,an，表示数组 A 的元素。

1≤N≤5×10^5, −10^9≤ai≤ 10^9

输出描述
输出共两行，每行包含 N 个整数，表示答案。

输入输出样例
示例 1
输入

5
1 3 2 6 5
输出

1 2 3 5 6
6 5 3 2 1
运行限制

• 最大运行时间：3s
• 最大运行内存: 128M

代码

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{vector<int>s;int N;cin>>N;s.resize(N);for(int i=0;i<N;i++){cin>>s[i];}sort(s.begin(),s.end());for(int ele:s){cout<<ele<<" ";}cout<<endl;sort(s.begin(),s.end(),greater<int>());for(int ele:s){cout<<ele<<" ";}cout<<endl;return 0;
}

题解分析

本题可以使用数组解题，这里使用了STL中的vector容器解题，遍历起来更加方便。

• 题目思路是使用sort库函数进行升序排序，再降序排序，各自遍历输出一遍即可。

• sort库函数的参数与lower_bound一样为左闭右开区间，加上greater<int>()进行降序排序。

• 当然，这里的降序排序可以使用reverse进行反转，代码为reverse(s.begin(),s.end());。此时，数据会发生反转，再输出即可。

• 注意：vector容器在输入时要先用resize分配空间。也可以先录入给临时变量，再用push_back()输入到vector容器中。

  for(int i=0;i<N;i++){int t;cin>>t;s.push_back(t);
  }
  

---

题目三

原题链接：lanqiao497

题目

题目描述
小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。

请计算这次考试的最高分、最低分和平均分。

输入描述
输入的第一行包含一个整数 n(1≤n≤10^4)表示考试人数。

接下来 n 行，每行包含一个 0 至 100 的整数，表示一个学生的得分。

输出描述
输出三行。

第一行包含一个整数，表示最高分。

第二行包含一个整数，表示最低分。

第三行包含一个实数，四舍五入保留正好两位小数，表示平均分。

输入输出样例

示例
输入

7
80
92
56
74
88
99
10

输出

99
10
71.29

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{vector<int>s;int n;cin>>n;s.resize(n);for(int i=0;i<n;i++){cin>>s[i];}cout<<*max_element(s.begin(),s.end())<<endl;cout<<*min_element(s.begin(),s.end())<<endl;
long long sum=0;for(int ele:s){sum+=ele;}cout<<fixed<<setprecision(2)<<1.0*sum/n<<endl;return 0;
}

题解分析

本题解使用了万能头文件bits/stdc++.h、max_element/min_element库函数和vector容器。

• 本题思路很简单，使用max_element/min_element找到最大值和最小值。然后，由于数值较大，使用long long类型的变量来记录总值，最后输出平均值即可。

• 注意：max_element/min_element库函数返回的是区间中目标值的迭代器，所以要用*获取迭代器对应的值。

• cout输出使用fixed<<setprecision(x)保留x位小数。

---

题目四

原题链接：lanqiao1113

题目

题目描述
CLZ 银行只有两个接待窗口，VIP 窗口和普通窗口，VIP 用户进入 VIP 窗口排队，剩下的进入普通窗口排队。现有 M 次操作，操作四种类型，如下：

• IN name V：表示一名叫 name 的用户到 VIP 窗口排队
• OUT V：表示 VIP 窗口队头的用户离开排队
• IN name N：表示一名叫 name 的用户到普通窗口排队
• OUT N：表示普通窗口队头的用户离开排队
  求M 次操作结束后 VIP 窗口队列和普通窗口队列中的姓名。

输入描述
第一行是一个整数 M（1≤M≤1000），表示一共有 M 次操作。

第二行到第 M+1 行输入操作，格式如下：

IN name V

OUT V

IN name N

OUT N

输出描述
输出M 次操作后 VIP 窗口队列和普通窗口队列中的姓名（从头到尾），先输出 VIP 窗口队列后输出普通窗口队列。

示例 1

输入

5
IN xiaoming N
IN Adel V
IN laozhao N
OUT N
IN CLZ V

输出

Adel
CLZ
laozhao

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{int m;cin>>m;string a;queue<string> v,n;for(int i=0;i<m;i++){cin>>a;if(a=="IN"){string name,p;cin>>name>>p;if(p=="V")v.push(name);else n.push(name);}else{string p;cin>>p;if(p=="V")v.pop();else n.pop();}}while(v.size()){cout<<v.front()<<endl;v.pop();}while(n.size()){cout<<n.front()<<endl;n.pop();}return 0;
}

题解分析

本题情景是银行窗口排队，可以想到使用queue容器(队列)解决。有两个窗口就使用两个queue容器，然后根据题目分情况解题即可。

• queue容器使用string类型，进行字符串输入。

• q.push()表示添加元素；q.pop()表示移除队头元素；q.front()表示获取队头元素；q.size()表示队列里的元素个数；

• 队列遍历输出：

  while(q.size()){cout<<q.front()<<endl;q.pop();}
  

---

题目五

原题链接：lanqiao2928

题目

问题描述
最近暑期特训算法班的同学们表现出色，他们的老师肖恩决定给他们分发糖果。肖恩购买了 n 个不同种类的糖果，用小写的阿拉伯字母表示。每个糖果必须分发给一个同学，并且每个同学至少要分到一个糖果。同学们的开心程度定义为他们所分到的糖果组成的字符串 s[i] 的字典序。肖恩希望同学们的开心程度相差尽量小，因此他要找到一种方案，使得所有糖果组成的字符串中字典序最大的字符串尽可能小。请输出能够实现字典序最小可能的max(s[1],s[2],s[3],…,s[x]) 。

输入描述
第一行输入两个整数
n 和x ，分别表示有 n 个糖果 x 个同学。

第二行输入一个长度为 n 的字符串S S[i] 表示第 i 个糖果的种类。

数据保证

1≤n≤10 ^6 ,1≤x≤n,S[i]∈[ ′ a ′ , ′ z ′ ] 。

输出描述
输出一个字符串，为所有糖果组成的字符串中字典序最大的字符串最小的可能值。

样例输入
6 2

caabdc
样例输出
abccd
说明
一个最优分配方案是一个同学拿到 abccd ，一个同学拿到 a 。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+9;
char s[N];
int main()
{int n,x;cin>>n>>x;cin>>s+1;sort(s+1,s+n+1);if(s[1]==s[n]){for(int i=1;i<=n/x+(n%x?1:0);i++)cout<<s[1];}else if(s[1]==s[x]){for(int i=x;i<=n;i++)cout<<s[i];}else{cout<<s[x];}return 0;
}

题解分析

找规律的贪心，考验思维，将字符串分类讨论，设计贪心策略。

• 先给字符串排序，然后我们可以分为三类讨论：
  • 1)字符串全相等 （假设全a)，那就是尽量使得每个人分到的字符串的最大长度尽可能小就行。
  • 2)s[x]== s[1]，说明第x个是最小的字符带着后面所有的字符一起输出。
  • 3)s[x]!=s[1]，后面一坨字符可以直接丢到s[1]后面，分给第一个同学。

---

题目六

原题链接：lanqiao741

题目

题目描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n−1 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 3 种果子，数目依次为 1，2，9。可以先将 1、2 堆合并，新堆数目为 3，耗费体力为 3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力 =3+12=15。可以证明 15 为最小的体力耗费值。

输入描述
输入两行。

第一行是一个整数 n(1≤n≤10^4 )，表示果子的种类数。

第二行包含 n 个整数，用空格分隔，第 i 个整数 (1≤a i≤2×10 4 ) 是第 i 种果子的数目。

输出描述
输出一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2^31 。

输入输出样例
示例 1
输入

3
1 2 9
输出

15

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{priority_queue<long long,vector<long long>,greater<long long>>pq; int n;cin>>n;for(int i=0;i<n;i++){long long t;cin>>t;pq.push(t);}long long sum=0;while(pq.size()>1){long long f=pq.top();pq.pop();long long e=pq.top();pq.pop();sum+=f+e;pq.push(f+e);}
cout<<sum;return 0;
}

题解分析

本题需要使用贪心策略和优先队列进行解题。

• 优先队列priority_queue使用堆实现，其默认为=大根堆== ，想要使用小根堆则要使用比较函数。
• 使用贪心策略是因为每次合成最小的两堆果子可以使得耗费的体力最小 ，由局部最优解得到最终最优解。
• 注意：合成后的果子堆必须重新放入优先队列中 ，优先队列会根据其值将其放在合适的地方以确保最后能得到最优解。

---

题目七

原题链接lanqiao549

题目

题目描述
在一个 n 行 m 列的方格图上有一些位置有地雷，另外一些位置为空。请为每个空位置标一个整数，表示周围八个相邻的方格中有多少个地雷。

输入描述
输入的第一行包含两个整数 n,m。第 2 行到第 n+1 行每行包含 m 个整数，相邻整数之间用一个空格分隔。如果对应的整数为 0，表示这一格没有地雷。如果对应的整数为 1，表示这一格有地雷。其中，1≤n,m≤100 分钟后还是在当天。

输出描述
输出 n 行，每行 m 个整数，相邻整数之间用空格分隔。对于没有地雷的方格，输出这格周围的地雷数量。对于有地雷的方格，输出9。

输入输出样例
示例 1
输入

3 4
0 1 0 0
1 0 1 0
0 0 1 0

输出

2 9 2 1
9 4 9 2
1 3 9 2

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码

#include <iostream>
#include <vector>
using namespace std;int main() {int n, m;cin >> n >> m;vector<vector<int>> a(n + 2, vector<int>(m + 2, 0)); // 初始化矩阵 avector<vector<int>> b(n + 2, vector<int>(m + 2, 0)); // 初始化矩阵 b// 输入矩阵 a 的内部元素for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];}}// 计算雷区for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (a[i][j] == 1) {b[i][j] = 9; // 标记雷} else {int count = 0; // 统计周围雷的数量for (int di = -1; di <= 1; di++) {for (int dj = -1; dj <= 1; dj++) {if (di == 0 && dj == 0) continue; // 跳过自身count += a[i + di][j + dj];}}b[i][j] = count;}}}// 输出结果矩阵for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cout << b[i][j] << " ";}cout << endl; // 每行结束后换行}return 0;
}

题解分析

本题是一道模拟题，基于扫雷游戏而来。

• 类似于这种对二维数组中某一位置的周围进行操作的题目，必须考虑边界问题 ，可以在其周围再加一圈的空间以确保不会越界。
• 注意：类似于这种题目，在对原二维数组a进行修改操作前，必须先将其赋值给临时二维数组b，对临时二维数组b进行修改，最后记得赋值回原二维数组a 这样是为了避免数据干扰 如果直接在原数组 a 上进行标记和计算结果的存储，那么在计算后续格子周围雷数时，前面已经被修改的元素值会干扰计算，导致结果出错。而使用临时二维数组 b ，可以在不改变原数组 a 的情况下，独立地计算和存储每个格子周围雷的数量以及雷的标记。

---

题目八

原题链接：lanqiao551

题目

题目描述
小蓝负责花园的灌溉工作。

花园可以看成一个 n 行 m 列的方格图形。中间有一部分位置上安装有出水管。小蓝可以控制一个按钮同时打开所有的出水管，打开时，有出水管的位置可以被认为已经灌溉好。每经过一分钟，水就会向四面扩展一个方格，被扩展到的方格可以被认为已经灌溉好。即如果前一分钟某一个方格被灌溉好，则下一分钟它上下左右的四个方格也被灌溉好。给定花园水管的位置，请问 k 分钟后，有多少个方格被灌溉好？

输入描述
输入的第一行包含两个整数 n,m。

第二行包含一个整数 t，表示出水管的数量。

接下来 t 行描述出水管的位置，其中第 i 行包含两个数r,c 表示第 r 行第 c 列有一个排水管。

接下来一行包含一个整数 k。

其中，1≤n,m≤100,1≤t≤10,1≤k≤100。

输出描述
输出一个整数，表示答案。

输入输出样例
示例 1
输入

3 6
2
2 2
3 4
1

输出

9

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{int n,m;cin>>n>>m;int a[n+2][m+2]={0};int t;cin>>t;for(int i=1;i<=t;i++){int N,M;cin>>N>>M;a[N][M]=1;}int k;cin>>k;while(k--){int t[n+2][m+2];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){t[i][j]=a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]==1){if(a[i-1][j]==0)t[i-1][j]=1;if(a[i][j-1]==0)t[i][j-1]=1;if(a[i][j+1]==0)t[i][j+1]=1;if(a[i+1][j]==0)t[i+1][j]=1;}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]=t[i][j];}}}int sum=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]==1)sum++;}}cout<<sum;return 0;
}

题解分析

本题同样为模拟题，与扫雷题不同之处在于只用对某一位置的上下左右方格进行操作 。

• 与扫雷相同，需考虑边界和临时数组。

---

题目九

原题链接lanqiao2489

题目

问题描述
请问十六进制数 2021ABCD 对应的十进制是多少？

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

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=50;
int a[N];
int main()
{string s="2021ABCD";for(int i=0;i<s.size();i++){if(s[i]>='0'&&s[i]<='9')a[i+1]=s[i]-'0';else a[i+1]=s[i]-'A'+10;}ll x=0;for(int i=1;i<=s.size();i++){x=x*16+a[i];}cout<<x;return 0;
}

题解分析

本题思路简单，十六进制转十进制，套用模板即可。

• 需要注意的是，任意进制转十进制，需要将每一位转换为int类型放入数组中，然后对数组进行操作。

---

题目十

原题链接：lanqiao1230

题目

题目描述
给定一个 N 进制数 S，请你将它转换为 M 进制。

输入描述
第一行为一个整数 T，表示测试数据数量。 (1≤T≤10^5)每个测试用例包含两行，第一行包含两个整数 N,M。

第二行输入一个字符串 S，表示 N 进制数。

数据范围保证：2≤N,M≤16，若 N≥10，则用 A∼F 表示字码 10∼15。保证 S 对应的十进制数的位数不超过 10。

输出描述
输出共 T，每行表示一组数据的答案。

输入样例
2
2 10
10101
11 2
1793A5068

输出样例
21
10101111001010100111010101011

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=50;
int a[N];
char ch[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
int main()
{int t;cin>>t;while(t--){int n,m;cin>>n>>m;string s;cin>>s;int len=s.size();for(int i=0;i<len;i++){if(s[i]>='0'&&s[i]<='9')a[i+1]=s[i]-'0';else a[i+1]=s[i]-'A'+10;}ll x=0;for(int i=1;i<=len;i++){x=x*n+a[i];}string ans;while(x){ans+=ch[x%m];x/=m;}reverse(ans.begin(),ans.end());cout<<ans<<endl;}return 0;
}

题解分析

本题是N进制转为M进制，可以以十进制为桥梁 。先将N进制转换为十进制 ，再将十进制转换为M进制。

• 十进制数转换任意进制数 ，使用string类型的变量承接答案。
• 题中的M不会超过十六进制 ，所以可以定义一个字符数组 ，再取模使用即可。
• 注意：十进制转任意进制是倒序输入字符串的，所以最后必须用reverse反转字符串得正解。

---

题目十一

原题链接：lanqiao2296

题目

问题描述

请找到一个大于 20222022 的最小数，这个数转换成二进制之后，最低的 66 个二进制位全为 00 。

请将这个数的十进制形式作为答案提交。

答案提交

本题为一道结果填空的题，只需要算出结果后，在代码中使用输出语句将结果输出即可。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

代码

#include <bits/stdc++.h>
using namespace std;
const int N=50;
int a[N];
char ch[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
int main()
{int sum=0;for(int i=2023;i<=10000;i++){int t=i;string ans;while(t){ans+=ch[t%2];t/=2;}reverse(ans.begin(),ans.end());int len=ans.size();int w=0;for(int j=len-1;j>len-7;j--){if(ans[j]=='0')w++;}if(w==6){cout<<i;break;}}return 0;
}

题解分析

本题十进制转换为二进制。

• 但要注意的是，二进制位是左高右低，所以从最后进行判断六个0。

---

题目十二

原题链接：lanqiao2406

题目

问题描述
请找到一个大于 2022 的最小数，这个数转换成十六进制之后，所有的数位（不含前导 0）都为字母（A 到 F）。

请将这个数的十进制形式作为答案提交。

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

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

代码

#include <bits/stdc++.h>
using namespace std;
char ch[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
int main() {for (int i = 2023; i <= 1000000000; i++) {int t = i;string ans;while (t) {ans += ch[t % 16];t /= 16;}reverse(ans.begin(), ans.end());int len = ans.size();int w = 0;for (int j = 0; j <len; j++) {if (ans[j] >= 'A' && ans[j] <= 'F') w++;}if (w == len ) {cout << i << endl;  // 直接输出 ibreak;}}return 0;
}

题解分析

本题相较于上一题只是条件改变了而已，套用模板即可。

---

题目十三

原题链接：lanqiao2406

题目

问题描述
随着 2024 年的钟声回荡，传说中的时空之门再次敞开。这扇门是一条神秘的通道，它连接着二进制和四进制两个不同的数码领域，等待着勇者们的探索。

在二进制的领域里，勇者的力量被转换成了力量数值的二进制表示中各数位之和。

在四进制的领域里，力量的转换规则相似，变成了力量数值的四进制表示中各数位之和。

穿越这扇时空之门的条件是严苛的：当且仅当勇者在二进制领域的力量等同于四进制领域的力量时，他才能够成功地穿越。

国王选定了小蓝作为领路人，带领着力量值从 1 到 2024 的勇者们踏上了这段探索未知的旅程。作为小蓝的助手，你的任务是帮助小蓝计算出，在这 2024 位勇者中，有多少人符合穿越时空之门的条件。

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

代码

#include <bits/stdc++.h>
using namespace std;
char ch[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
int fun (int x,int k){string ans;while(x){ans+=ch[x%k];x/=k;}int w=0;for(char ele:ans){w+=ele-'0';}return w;
}
int main()
{int sum=0;for(int i=1;i<=2024;i++){if(fun(i,2)==fun(i,4)){sum++;}}cout<<sum;return 0;
}

题解分析

本题是十进制转换为二进制和四进制。由于转换过程有重复部分，所以使用函数进行包装。

---

题目十四

原题链接：lanqiao2080

题目

问题描述

给定 n个整数 a1,a2,⋅⋅⋅,an ，求它们两两相乘再相加的和，即：

S=a1⋅a2+a1⋅a3+⋯+a1⋅an+a2⋅a3+⋯+an−2⋅an−1+an−2⋅an+an−1⋅an

输入格式

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

第二行包含 n个整数 a1,a2,⋯,an。

输出格式

输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。

样例输入

4
1 3 6 9

样例输出

117

评测用例规模与约定

对于 30%的数据，1≤n≤1000,1≤ai≤100。

对于所有评测用例， 1≤n≤200000,1≤ai≤1000 。

运行限制

• 最大运行时间：1s
• 最大运行内存: 512M

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int main(){long long n;cin>>n;long long a[N];for(int i=1;i<=n;i++){cin>>a[i];}long long prefix[N];prefix[0]=0;for(int i=1;i<=n;i++)prefix[i]=prefix[i-1]+a[i];long long sum=0for(int i=1;i<=n;i++)sum+=a[i]*(prefix[n]-prefix[i]);cout<<sum;return 0;
}

题解分析

本题需要使用前缀和。

• 构建前缀和：for(int i=1;i<=n;i++)prefix[i]=prefix[i-1]+a[i];
• 提出公因子求区间和：for(int i=1;i<=n;i++)sum+=a[i]*(prefix[n]-prefix[i]);

---

题目十五

原题链接：lanqiao3382

题目

问题描述
给定一个长度为 n 的整数数组 a 以及 m 个查询。

每个查询包含三个整数 l,r,k 表示询问 l∼r 之间所有元素的 k 次方和。

请对每个查询输出一个答案，答案对 10⁹+7 取模。

输入格式
第一行输入两个整数n,m 其含义如上所述。

第二行输入 n 个整数 a[1],a[2],…,a[n]。

接下来 m 行，每行输入三个整数 l,r,k 表示一个查询。

输出格式
输出 m 行，每行一个整数，表示查询的答案对 10^9+7 取模的结果。

样例输入
5 3
1 2 3 4 5
1 3 2
2 4 3
3 5 1
样例输出
14
99
12
评测数据规模：
对于 100% 的评测数据：1≤n,m≤10^5 1≤a[i]≤100，
1≤l≤r≤n 1≤k≤5。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long ;
const int N=1e5+9;
const int p=1e9+7;
ll a[6][N],prefix[6][N];int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[1][i];for(int i=2;i<=5;i++){for(int j=1;j<=n;j++){a[i][j]=a[i-1][j]*a[1][j]%p;}}for(int i=1;i<=5;i++){for(int j=1;j<=n;j++){prefix[i][j]=(prefix[i][j-1]+a[i][j])%p;}}while(m--){int l,r,k;cin>>l>>r>>k;cout<<(prefix[k][r]-prefix[k][l-1]+p)%p<<endl;}return 0;
}

题解分析

本题仍然使用前缀和，由于k比较小，所以我们可以处理出五个数组分别表示不同的次方。

• 例如：a3[]中的元素都是数组a中元素的3次方。
• 再对五个数组预处理出前缀和，对于每次询问利用前缀和的性质可O(1)解决。
• 注意：prefix[k][r]-prefix[k][l-1]可能为负数，因此需要加上模数 p 再取模，确保结果为正数。

---

题目十六

原题链接：lanqiao3291

题目

问题描述
给定一个长度为n 的数组 a[1],a[2],…,a[n]。 同时给定 m 个操作，每个操作有三个整形数据 x,y,z。 每个操作的意义就是给数组中下标为 x 与下标为 y 之间（包括 x,y）的元素的值加上 z。

输入格式
输入有多组数据，数据组数不大于 5。 每一组数据第一行有两个整数 n,m(0<n,m<10^5 ) 。 第二行有 n 个整数，分别代表a[1],a[2],…,an 的初始值。 接下来就 m 行，每一行有 3 个整数 x,y,z(0<x≤y≤n,0<z<10)。

输出格式
在一行内输出这个序列的所有元素的值，并且每个值之间应该以空格隔开。

输入样例
10 5
0 0 0 0 0 0 0 0 0 0
1 5 1
2 6 1
3 7 1
4 9 1
5 10 1
1 1
1
1 1 2
输出样例
1 2 3 4 5 4 3 2 2 1
3

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],diff[N];
int main()
{int n,m;while(cin>>n>>m){for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++)diff[i]=a[i]-a[i-1];while(m--){int x,y,z;cin>>x>>y>>z;diff[x]+=z;diff[y+1]-=z;}for(int i=1;i<=n;i++)a[i]=a[i-1]+diff[i];for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
}return 0;
}

题解分析

本题利用差分数组对数组a进行区间修改即可。

• 差分数组的构建：for(int i=1;i<=n;i++)diff[i]=a[i]-a[i-1];
• 区间加z: diff[x]+=z; diff[y+1]-=z;

---

题目十七

原题链接：lanqiao1276

题目

题目描述

小明拥有 N个彩灯，第 ii 个彩灯的初始亮度为 ai。

小明将进行 Q 次操作，每次操作可选择一段区间，并使区间内彩灯的亮度 +x（x 可能为负数）。

求 Q次操作后每个彩灯的亮度（若彩灯亮度为负数则输出 0）。

输入描述

第一行包含两个正整数 N，Q，分别表示彩灯的数量和操作的次数。

第二行包含 N个整数，表示彩灯的初始亮度。

接下来 Q行每行包含一个操作，格式如下：

l r x，表示将区间 l∼r的彩灯的亮度 +x。

1≤N,Q≤5×10⁵，0≤ai≤10 ⁹，1≤l≤r≤N， −10⁹≤x≤10⁹

输出描述

输出共 1 行，包含 N个整数，表示每个彩灯的亮度。

输入输出样例

示例 1

输入

5 3
2 2 2 1 5
1 3 3
4 5 5
1 1 -100

输出

0 5 5 6 10

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码

#include <bits/stdc++.h>
using namespace std;
const int N =5000010;
using ll=long long;
ll a[N],diff[N];
int main()
{a[0]=diff[0]=0;int n,q;cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)diff[i]=a[i]-a[i-1];while(q--){int l,r,x;cin>>l>>r>>x;diff[l]+=x;diff[r+1]-=x;}for(int i=1;i<=n;i++)a[i]=a[i-1]+diff[i];for(int i=1;i<=n;i++){if(a[i]<0)cout<<0ll<<" ";elsecout<<a[i]<<" ";}return 0;
}

题解分析

本题利用差分数组对数组a进行区间修改即可。

• 注意：输出时亮度为负数则输出0，且本题需要用到long long类型。

---

题目十八

原题链接：lanqiao3419

题目

问题描述
平衡串指的是一个字符串，其中包含两种不同字符，并且这两种字符的数量相等。

例如, ababab 和 aababb 都是平衡串，因为每种字符各有三个，而 abaab 和 aaaab 都不是平衡串，因为它们的字符数量不相等。

平衡串在密码学和计算机科学中具有重要应用，比如可以用于构造哈希函数或者解决一些数学问题。

小郑拿到一个只包含 LQ 的字符串，他的任务就是找到最长平衡串，且满足平衡串的要求，即保证子串中 LQ 的数量相等。

输入格式
输入一行字符串，保证字符串中只包含字符 LQ。

输出格式
输出一个整数，为输入字符串中最长平衡串的长度。

样例输入
LQLL

样例输出
2

评测数据规模
对于所有评测数据，输入字符串的长度 len ≤1000。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char s[N];int prefix[N];
int main(){cin>>s+1;int n=strlen(s+1);for(int i=1;i<=n;i++){prefix[i]=prefix[i-1]+(s[i]=='L'?1:-1);}int ans=0;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){if(prefix[j]-prefix[i-1]==0)ans=max(ans,j-i+1);}}cout<<ans<<endl;return 0;
}

题解分析

• 将L看做1，Q看做-1，只有当某个区间的和为0时，字符串是平衡的。
• 我们可以预处理出前缀和，然后枚举所有区间（这一步的时间复杂度是O(n^2)的），得到所有平衡区间的长度最后取大输出即可。

---

题目十九

原题链接：lanqiao3412

题目

问题描述
小蓝是机甲战队的队长，他手下共有 n 名队员，每名队员都有一个战斗力值 w i。现在他需要将这 n 名队友分成两组 a 和 b，分组必须满足以下条件：

每个队友都属于 a 组或 b 组。
a 组和 b 组都不为空。
战斗力差距最小。
战斗力差距的计算公式为 ∣max(a)−min(b)∣，其中
max(a) 表示 a 组中战斗力最大的，
min(b) 表示 b 组中战斗力最小的。

请你计算出可以得到的最小战斗力差距。

输入格式
第一行一个整数 n，表示队员个数。

第二行
n 个整数 w 1,w 2 ,w 3…w n，分别表示每名队友的战斗力值。

数据范围保证：
2≤n≤10 ⁵ 1≤w ≤10 ⁹ 。

输出格式
输出一个整数，表示可以得到的最小战斗力差距。

样例输入
3
1 2 3
样例输出
1
说明
样例中，当 a=[1,3]，b=[2]，此时战斗力差距为 1，无法得到比 1 更小的安排方式。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
using ll=long long;
ll a[N];
int main()
{ll n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);ll m=1e9+10;for(int i=2;i<=n;i++){ll t=a[i]-a[i-1];m=min(m,t);}cout<<m;return 0;
}

题解分析

• 本题是简单排序模型。
• 要将战斗力分为两部分，为了使得差距最小，我们可以将战斗力排序后，找一个位置进行划分，使得左边的都在a，右边的都在b，从而这个差距就是这个位置两边的战斗力差距，说明差距的取值仅有n-1种，枚举即可。
• 当混乱的数据不好处理且排序不影响答案时，尝试先排序再分析。

---

题目二十

原题链接：lanqiao545

题目

题目描述
在很久很久以前，有 n 个部落居住在平原上，依次编号为 1 到 n。第 i 个部落的人数为 t 。

有一年发生了灾荒。年轻的政治家小蓝想要说服所有部落一同应对灾荒，他能通过谈判来说服部落进行联合。

每次谈判，小蓝只能邀请两个部落参加，花费的金币数量为两个部落的人数之和，谈判的效果是两个部落联合成一个部落（人数为原来两个部落的人数之和）。

输入描述
输入的第一行包含一个整数 n，表示部落的数量。

第二行包含 n 个正整数，依次表示每个部落的人数。

其中，1≤n≤1000，1≤t i ≤10⁴。

输出描述
输出一个整数，表示最小花费。

输入输出样例
示例 1
输入

4
9 1 3 5
输出

31
运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
priority_queue<ll,vector<ll>,greater<ll>>pq;
int main()
{ll n;cin>>n;for(int i=1;i<=n;i++){int e;cin>>e;pq.push(e);}ll ans=0;while(pq.size()>1){ll t1=pq.top();pq.pop();ll t2=pq.top();pq.pop();int sum=t1+t2;ans+=sum;pq.push(sum);}cout<<ans;return 0;
}

题解分析

本题是总操作数一定情况下的最小代价模型。

• 我们知道这里一共需要进行的操作次数一定是n-1次，那么贪心地想，如果每次选择代价最小的两个部落合并，不仅可以使得当前代价最小，还可以使得后续合并的代价也尽可能小。
• 部落大小通过优先队列来维护。

---

题目二十一

原题链接：lanqiao532

题目

题目描述
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入描述
第 1 行包括一个整数 w (80≤w≤200)，为每组纪念品价格之和的上限。

第 2 行为一个整数n(1≤n≤30000)，表示购来的纪念品的总件数。

第3 ~ n+2行每行包含一个正整数 pi (5≤p i≤w)，表示所对应纪念品的价格。

输出描述
输出一行，包含一个整数，即最少的分组数目。

输入输出样例
示例 1
输入

100
9
90
20
20
30
50
60
70
80
90
输出

6

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{int w,n;cin>>w>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);int l=1,r=n;int ans=0;while(l<=r){if((a[r]+a[l]>w)||(a[r]>w)){ans++;r--;}else{ans++;l++,r--;}}cout<<ans;return 0;
}

题解分析

本题是最小数目的贪心模型

• 为了使组数最小，我们应该使得每一组内尽可能装两种礼物（最多只能装两件），尽量占满一组的容量。
• 先进行升序排序，然后使用对撞指针，对右指针进行判断，如果其与左指针相加或其本身大于W，就独自为一组，否则，两指针为一组。
• 这里的贪心策略为，每一个贵的礼物带一个便宜的成一组。

---

题目二十二

原题链接：lanqiao1371

题目

题目描述

给定一个长度为 n 的字符串 S。请你判断字符串 S是否回文。

输入描述

输入仅 11 行包含一个字符串 S。

1≤∣S∣≤10⁶，保证 S只包含大小写、字母。

输出描述

若字符串 S为回文串，则输出 Y，否则输出 N。

输入输出样例

示例 1

输入

abcba

输出

Y

示例 2

输入

abcbb

输出

N

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{string s;cin>>s;int l=0,r=s.size()-1;while(l<=r){if(s[l]==s[r]){l++,r--;}else{cout<<'N';return 0;}}cout<<'Y';return 0;
}

题解分析

本题使用对撞指针求解。

• 首先引入了<bits/stdc++.h>头文件，使用了std命名空间。在main函数中，定义了一个字符串s。然后通过cin从标准输入读取一个字符串存入s。接着定义了两个变量l和r，分别初始化为字符串的首字符位置和尾字符位置。
• 之后进入一个循环，当l小于等于r时循环继续。在循环中，如果s[l]和s[r]相等，说明当前首尾字符相同，将l加一，r减一，继续检查下一对字符。如果s[l]和s[r]不相等，说明字符串不是回文串，输出N并返回 0 结束程序。如果循环正常结束，说明字符串是回文串，输出Y并返回 0结束程序。

---

题目二十三

原题链接：lanqiao1372

题目

题目描述

给定一个长度为 n的序列 a1,a2,⋯,an 和一个常数 S。

对于一个连续区间如果它的区间和大于或等于 S，则称它为美丽的区间。

对于一个美丽的区间，如果其区间长度越短，它就越美丽。

请你从序列中找出最美丽的区间。

输入描述

第一行包含两个整数 n,S，其含义如题所述。

接下来一行包含 n个整数，分别表示 a1,a2,⋯,an。

10≤N≤10⁵，1×ai≤10⁴，1≤S≤10⁸。

** 输出描述**

输出共一行，包含一个整数，表示最美丽的区间的长度。

若不存在任何美丽的区间，则输出 0。

输入输出样例

示例 1

输入

5 6
1 2 3 4 5

输出

2

** 运行限制**

• 最大运行时间：1s
• 最大运行内存: 128M

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int a[N],S;int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,s;cin>>n>>s;for(int i=1;i<=n;i++)cin>>a[i];int ans=n+1;for(int i=1,j=0,sum=0;i<=n;i++){while(i>j||(j+1<=n&&sum<s))sum+=a[++j];if(sum>=s)ans=min(ans,j-i+1);sum-=a[i];}
cout<<(ans>n?0:ans)<<endl;return 0;
}

题解分析

本题使用快慢指针求解。

• 在main函数中，首先使用ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)来同步输入输出流，提高输入输出效率。然后读取两个整数n和s。接着通过循环读取n个整数存入数组a。

• 定义变量ans初始值为n + 1。然后通过两个指针i和j以及变量sum来实现一个滑动窗口的功能。内层循环在满足一定条件下增加j，直到窗口内的和大于等于s或者j达到边界。如果窗口内的和大于等于s，则更新ans为最小的窗口长度。然后在每次外层循环中，将sum减去a[i]，移动窗口的左边界。

---

题目二十四

原题链接：lanqiao1331

题目

二进制中 1 的个数

题目描述
给定一个整数 x，输出该数二进制表示中 1 的个数。

例：9 的二进制表示为 1001，有 2 位是 1 ，所以函数返回 2。

输入描述
输入 x （内存空间为 32 位的整数）。

输出描述
第一行输出 x 二进制表示中 1 的个数。

输入输出样例
示例 1
输入

9

输出

2

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{unsigned int x;cin>>x;int ans=0;while(x){if(x&1)ans++;x>>=1;}cout<<ans<<endl;return 0;
}

题解分析

本题需要用到位运算相关知识。

• x&1表示使用按位与操作符 & 检查 x 的最低位是否为 1。如果 x & 1 的结果为 1，说明 x 的最低位是 1，此时将 ans 加 1。

• x >>= 1表示将 x 右移一位，相当于去掉 x 的最低位，继续检查下一个最低位。

---

题目二十五

原题链接：lanqiao3400

题目

问题描述
在一个神秘的世界中，存在着一个称为"异或森林"的地方。异或森林中的每个树木都拥有独特的力量。肖恩进入了这片森林，他得到了一个任务：找出数组中满足条件的连续子数组，使得连续子数组中所有元素异或运算结果的因数个数为偶数。完成任务将揭示宝藏的所在地。现在，你能告诉肖恩有多少个连续子数组满足条件吗？

注意：0 的因数个数视为奇数。

输入描述
第一行输入一个数字 n 表示数组元素个数。

第二行输入 n 个数字，第 i 个数字 a[i] 表示数组的第 i 个元素。

数据保证
1≤n≤10 ⁴ 1≤a[i]≤n 。

输出描述
输出一个数字表示满足条件的连续子数组的数量。

样例输入
5
1 2 3 4 5
样例输出
7

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int a[N],prexor[N],cnt[N];int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)prexor[i]=prexor[i-1]^a[i];cnt[0]=1;int ans=n*(n+1)/2;for(int i=1;i<=n;i++){for(int j=0;j<=200;j++){int sq=j*j;ans-=cnt[prexor[i]^sq];}cnt[prexor[i]]++;}cout<<ans<<'\n';return 0;
}

题解分析

• 首先转化条件：因数个数为偶数个=>不是完全平方数。

• 正难则反：计算有多少个子数组的异或和为完全平方数，用总区间个数减去即可。

• 先求前缀异或和prexor，枚举所有平方数sq（不超过200个)，然后对于prexor[i]，要有prexor[i] ^ prexor[i]= sq，于是就是统计多少个i满足j<i且,prexor[j]=prexor[i] ^ sq。

• 总区间个数为n* (n + 1)/ 2，且元素异或和最大值不超过2e4。