关键词：
文章目录
- 一、AcWing 3956. 截断数组（中等）
- 二、AcWing 3729. 改变数组元素（中等）
- 三、AcWing 1460. 我在哪？（简单）
- 四、AcWing 3768. 字符串删减（简单）
- 五、AcWing 3777. 砖块（简单）
一、AcWing 3956. 截断数组（中等）
题目描述
给定一个长度为
n
n
n 的数组
a
1
,
a
2
,
…
,
a
n
a_1,a_2,…,a_n
a1,a2,…,an。
现在，要将该数组从中间截断，得到三个非空子数组。
要求，三个子数组内各元素之和都相等。
请问，共有多少种不同的截断方法？
输入格式
第一行包含整数
n
n
n。
第二行包含
n
n
n 个整数
a
1
,
a
2
,
…
,
a
n
a_1,a_2,…,a_n
a1,a2,…,an。
输出格式
输出一个整数，表示截断方法数量。
数据范围
前六个测试点满足：
1
≤
n
≤
10
1≤n≤10
1≤n≤10。
所有测试点满足：
1
≤
n
≤
1
0
5
，
−
10000
≤
a
i
≤
10000
1≤n≤10^5，−10000≤a_i≤10000
1≤n≤105，−10000≤ai≤10000。
输入样例 1
4
1 2 3 3
输出样例 1
1
输入样例 2
5
1 2 3 4 5
输出样例 2
0
输入样例 3
2
0 0
输出样例 3
0
具体实现
1. 实现思路
- 我们有一个长度为 n 的数组，将其分成三段，使三段内的元素都相等，求有多少种截断方法。
- 首先，我们可以先求解一些总和 s，如果 3 不可以整除总和 s 的话，就一定无解。如果想要有解的话，s 一定是 3 的倍数。因此，我们可以先计算出总和 s 和每一段的总和 s/3。
- 问题就转变为一共有多少种选法，使得每一段的和都是 s/3。
- 我们可以先确定后面的点，让前面的总和是 2s/3，再选择前面的点，满足第一段是 s/3。
- 我们再枚举的过程中，可以使用前缀和，计算出从起始点到每一段的前缀和，判断第一段前缀和是 s/3，第二段前缀和是 2s/3 即可。
2. 实现代码
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005];
long long res=0,cnt=0;
int main()
cin>>n;
for(int i=1;i<=n;i++)
int x=0;
cin>>x;
a[i]=a[i-1]+x; //前缀和数组
if(a[n]%3!=0 || n<3)
cout<<"0"<<endl;
else
for(int j=2;j<n;j++)
if(a[j-1]==a[n]/3)
cnt++;
if(a[j]==a[n]/3*2)
res+=cnt;
cout<<res;
return 0;
二、AcWing 3729. 改变数组元素（中等）
题目描述
给定一个空数组
V
V
V 和一个整数数组
a
1
,
a
2
,
…
,
a
n
a_1,a_2,…,a_n
a1,a2,…,an。
现在要对数组
V
V
V 进行
n
n
n 次操作。
第
i
i
i 次操作的具体流程如下：
- 从数组 V V V 尾部插入整数 0 0 0。
- 将位于数组 V V V 末尾的 a i a_i ai 个元素都变为 1 1 1（已经是 1 1 1 的不予理会）。
注意：
- a i a_i ai 可能为 0，即不做任何改变。
-
a
i
a_i
ai 可能大于目前数组 V 所包含的元素个数，此时视为将数组内所有元素变为
1
1
1。
请你输出所有操作完成后的数组 V V V。
输入格式
第一行包含整数
T
T
T，表示共有
T
T
T 组测试数据。
每组数据第一行包含整数
n
n
n。
第二行包含
n
n
n 个整数
a
1
,
a
2
,
…
,
a
n
a_1,a_2,…,a_n
a1,a2,…,an。
输出格式
每组数据输出一行结果，表示所有操作完成后的数组 V V V，数组内元素之间用空格隔开。
数据范围
1
≤
T
≤
20000
1≤T≤20000
1≤T≤20000
1
≤
n
≤
2
×
1
0
5
1≤n≤2×10^5
1≤n≤2×105
0
≤
a
i
≤
n
0≤a_i≤n
0≤ai≤n
保证一个测试点内所有
n
n
n 的和不超过
2
×
1
0
5
2×10^5
2×105。
输入样例
3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0
输出样例
1 1 0 1 1 1
0 1 1 1 1 1 0 0 1 1
0 0 0
具体实现
1. 实现思路
- 由于我们每次操作都会加入一个数，在操作 i 次之后，新数组的长度就是 i，然后，再将当前数组的最后面的 ai 个数变成 1。
- 由于第 i 次数组一共有 i 个，将后 ai 个数变为 1，也就是我们将是 i-ai+1 到 i 的区间内的 ai 个数全部变成 1，也就是这个区间内的数据操作一次。
- 因此，我们可以开一个新数组与原数组长度相等，用以记录区间内数据操作的个数，因为 V 数组当中的 1 不会发生改变，所以，操作多次和操作一次的效果是相同的。
- 最后，如果新数组当中的元素大于 0，那么 V 数组中对应的元素就是 1，如果新数组中的元素等于 0，那么 V 数组中对应的元素就是 0。
2. 实现代码
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n;
int b[N];
int main()
int T;
cin>>T;
while(T--)
cin>>n;
memset(b,0,(n+1)*4);
for(int i=1;i<=n;i++)
int x;
cin>>x;
x=min(x,i); //如果x大于i的话就更新成i，因为此时是将数组内的所有元素变为1
int l=i-x+1,r=i;
b[l]++;b[r+1]--;
for(int i=1;i<=n;i++)
b[i]+=b[i-1];
for(int i=1;i<=n;i++)
cout<<!!b[i]<<" ";
cout<<endl;
return 0;
三、AcWing 1460. 我在哪？（简单）
题目描述
农夫约翰出门沿着马路散步，但是他现在发现自己可能迷路了！
沿路有一排共
N
N
N 个农场。
不幸的是农场并没有编号，这使得约翰难以分辨他在这条路上所处的位置。
然而，每个农场都沿路设有一个彩色的邮箱，所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用
A
.
.
Z
A..Z
A..Z 之间的一个字母来指定，所以沿着道路的
N
N
N 个邮箱的序列可以用一个长为
N
N
N 的由字母
A
.
.
Z
A..Z
A..Z 组成的字符串来表示。
某些邮箱可能会有相同的颜色。
约翰想要知道最小的
K
K
K 的值，使得他查看任意连续
K
K
K 个邮箱序列，他都可以唯一确定这一序列在道路上的位置。
例如，假设沿路的邮箱序列为 ABCDABC 。
约翰不能令
K
=
3
K=3
K=3，因为如果他看到了 ABC，则沿路有两个这一连续颜色序列可能所在的位置。
最小可行的
K
K
K 的值为
K
=
4
K=4
K=4，因为如果他查看任意连续
4
4
4 个邮箱，那么可得到的连续颜色序列可以唯一确定他在道路上的位置。
输入格式
输入的第一行包含 N N N，第二行包含一个由 N N N 个字符组成的字符串，每个字符均在 A . . Z A..Z A..Z 之内。
输出格式
输出一行，包含一个整数，为可以解决农夫约翰的问题的最小 K K K 值。
数据范围
1 ≤ N ≤ 100 1≤N≤100 1≤N≤100
输入样例
7
ABCDABC
输出样例
4
具体实现
1. 实现思路
- 我们要找到一个最小的 K，使得字符串当中从 K 分开不存在两个相同的字符串。
- 我们可以使用暴力解法，也就是 4 个 for 循环，第一重循环枚举每一个 K，第二重循环枚举第一个子串，第三重循环枚举第二个子串，第四重循环判断两个字串是否相同。
2. 实现代码
#include <bits/stdc++.h>
using namespace std;
int n;
string str;
int main()
cin >> n >> str;
for (int k = 1; k <= n; k ++ )
bool flag = false;
for (int i = 0; i + k - 1 < n; i ++ )
for (int j = i + 1; j + k - 1 < n; j ++ )
bool same = true;
for (int u = 0; u < k; u ++ )
if (str[i + u] != str[j + u])
same = false;
break;
if (same)
flag = true;
break;
if (flag) break;
if (!flag)
cout << k << endl;
break;
return 0;
四、AcWing 3768. 字符串删减（简单）
题目描述
给定一个由
n
n
n 个小写字母构成的字符串。 【备战蓝桥杯】算法·每日一题（详解+多解）--day12✨博主介绍计算器问题的双栈通用解法题目解题思路💫点击直接资料领取💫✨博主介绍🌊作者主页：苏州程序大白🌊作者简介：🏆CSDN人... 查看详情 【迎战蓝桥杯】算法·每日一题（详解+多解）--day7✨博主介绍和大于等于target的最短子数组解题思路💫点击直接资料领取💫✨博主介绍🌊作者主页：苏州程序大白🌊作者简介：🏆CSDN人工... 查看详情 写在前面距离这届蓝桥杯已经过了八个月了，一直没总结算法，实在是太懒了，懒狗一条…考前看知乎上说蓝桥杯一个月准备可以拿省一，当时还真信了，不过也可能是我有点懒，准备也不够一个月，... 查看详情 【C语言蓝桥杯每日一题】——单词分析😎前言🙌单词分析🙌总结撒花💞 😎博客昵称：博客小梦😊最喜欢的座右铭：全神贯注的上吧！！！😊作者简介：一名热爱C/C+... 查看详情 【C语言蓝桥杯每日一题】——既约分数😎前言🙌既约分数🙌递归版解题代码：😍非递归版解题代码：😍总结撒花💞既约分数😎) 😎博客昵称：博客小梦😊最喜欢的座右铭... 查看详情 目录scratch数字计算一、题目要求1、准备工作2、编程实现3、具体要求 查看详情 目录scratch售票找零一、题目要求编程实现二、案例分析1、角色分析 查看详情 目录scratch完美数一、题目要求1、编程实现2、具体要求二、案例分析 查看详情 目录scratch指令移动一、题目要求1、准备工作2、编程实现二、案例分析 查看详情 目录scratch摘苹果一、题目要求1、编程实现2、具体要求二、案例分析 查看详情 目录scratch辨别质数合数一、题目要求1、准备工作2、编程实现3、具体要求 查看详情 目录scratch太极图一、题目要求1、准备工作2、功能实现二、案例分析 查看详情 目录scratch太极图一、题目要求1、准备工作2、功能实现二、案例分析 查看详情 目录scratch从小到大排序一、题目要求1、准备工作2、编程实现 查看详情 目录scratch水仙花数一、题目要求1、编程实现2、具体要求二、案例分析 查看详情 目录scratch汉娜蹦床一、题目要求1、准备工作2、编程实现3、具体要求 查看详情 专栏： 蓝桥杯——每日四道编程题（两道真题+两道模拟）“蓝桥杯就要开始了，这些题刷到就是赚到”₍ᐢ..ᐢ₎♡另一个专栏： 蓝桥杯——每日四道填空题（两道真题+两道模拟题）目录专栏... 查看详情
现在，需要删掉其中的一些字母，使得字符串中不存在连续三个或三个以上的
x
x
x。
请问，最少需要删掉多少个字母？迎战蓝桥杯算法·每日一题（详解+多解）--day7(代码片段)
acwing蓝桥杯(代码片段)
c语言蓝桥杯每日一题——单词分析(代码片段)
c语言蓝桥杯每日一题——既约分数(代码片段)
蓝桥杯集训100题scratch数字计算蓝桥杯scratch比赛专项预测编程题集训模拟练习题第16题
蓝桥杯集训100题scratch售票找零蓝桥杯scratch比赛专项预测编程题集训模拟练习题第23题
蓝桥杯集训100题scratch完美数蓝桥杯scratch比赛专项预测编程题集训模拟练习题第19题
蓝桥杯集训100题scratch指令移动蓝桥杯scratch比赛专项预测编程题集训模拟练习题第14题
蓝桥杯集训100题scratch摘苹果蓝桥杯scratch比赛专项预测编程题集训模拟练习题第21题
蓝桥杯集训100题scratch辨别质数合数蓝桥杯scratch比赛专项预测编程题集训模拟练习题第15题
蓝桥杯集训100题scratch太极图蓝桥杯scratch比赛专项预测编程题集训模拟练习题第22题
蓝桥杯集训100题scratch太极图蓝桥杯scratch比赛专项预测编程题集训模拟练习题第22题
蓝桥杯集训100题scratch从小到大排序蓝桥杯scratch比赛专项预测编程题集训模拟练习题第17题
蓝桥杯集训100题scratch水仙花数蓝桥杯scratch比赛专项预测编程题集训模拟练习题第18题
蓝桥杯集训100题scratch汉娜蹦床蓝桥杯scratch比赛专项预测编程题模拟练习题第08题
蓝桥杯每日四道编程题（两道真题+两道模拟）|第四天(代码片段)
蓝桥杯每日一练之数列排序