蓝桥杯训练题目网站(蓝桥杯训练营)

AcWing-蓝桥杯训练日常问题

文章目录

1.AcWing3956.截断数组1.实现思路2.实现代码2.AcWing3729.更改数组元素1.实现思路2.实现代码3，AcWing1460.我在哪里？1.实现思路2.实现代码4.AcWing3768.字符串删除1.实现思路2.实现代码5.AcWing3777.Bricks1.实现思路2.实现代码问题描述

给定长度

n

n

n的数组

A

1

,

A

2

,

……

,

A

n

a_{1},a_{2},…,a_{n}

a1，a2，an。

现在，我们想要在中间截断这个数组以获得三个非空子数组。

要求三个子数组中每个元素之和相等。

有多少种不同的截断方法？

输入格式

第一行包含整数

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

5

,

-

10000

≤

A

我

≤

10000

1≤n≤10^{5}，-10000≤a_{i}≤10000

1≤n≤105，?10000≤ai≤10000。

输入样本1

4

1233

输出样本1

1

输入样本2

5

12345

输出样本2

0

输入样本3

2

00

输出样本3

0

执行

一、AcWing3956.截断数组

我们有一个长度为n的数组。将其分成三段，使三段中的元素相等。求有多少种截断方法。首先，我们可以先解决一些sum。如果3不能整除总和s，则必定无解。如果想要解，s必须是3的倍数。因此，我们可以先计算每个段的总和s以及总和s/3。问题是有多少种选择使得每段的总和为s/3。我们可以先确定后面的点，使得前面的和为2s/3，然后选择前面的点，使得第一段为s/3。在枚举过程中，我们可以利用前缀和来计算从起点到各段的前缀和。我们可以判断第一段的前缀和为s/3，第二段的前缀和为2s/3。

1.实现思路

#include位/stdc++.husing命名空间std;intn;inta[100005];longlongres=0,cnt=0;intmain(){cinn;for(inti=1;i=n;i++){intx=0;cinx;a[i]=a[i-1]+x;//前缀和数组}if(a[n]%3!=0||n3){cout'0'endl;}else{for(intj=2;jn;j++){if(a[j-1]==a[n]/3){cnt++;}if(a[j]==a[n]/3*2){res+=cnt;}}coutres;}返回0;}

2.实现代码

标题说明

给定一个空数组

V

V

V和一个整数数组

A

1

,

A

2

,

……

,

A

n

a_{1},a_{2},…,a_{n}

a1，a2，an。

现在我们需要比较数组

V

V

继续进行

n

n

n操作。

不。

我

我

i操作的具体过程如下：

来自数组

V

V

在V的末尾插入一个整数0。将位于数组中

V

V

V的末尾

A

我

人工智能}

ai元素变成

1

1

1。注意：

A

我

人工智能}

ai可能为0，即不进行任何更改。

A

我

人工智能}

ai可能大于数组V中当前包含的元素数量。在这种情况下，数组中的所有元素都被视为

1

1

1.

请在所有操作完成后输出数组

V

V

五、输入格式

第一行包含整数

时间

时间

T表示共享

时间

时间

T组测试数据。

每组数据的第一行包含整数

n

n

名词

第二行包含

n

n

n个整数

A

1

,

A

2

,

……

,

A

n

a_{1},a_{2},…,a_{n}

a1，a2，an。

输出格式

每组数据输出一行结果，表示所有操作完成后的数组。

V

V

V、数组中的元素之间用空格分隔。

数据范围

1

≤

时间

≤

20000

1≤T≤20000

1≤T≤20000

1

≤

n

≤

2

×

1

5

1≤n≤2×10^{5}

1≤n≤2×105

≤

A

我

≤

n

0≤a_{i}≤n

0≤ai≤n

确保全部在一个测试点内

n

n

n的总和不超过

2

×

1

5

2×10^{5}

2×105。

输入样本

3

6

030013

10

0001050002

3

000

输出样本

110111

0111110011

000

执行

二、AcWing3729.改变数组元素

由于我们每次操作都会添加一个数字，所以操作i次后，新数组的长度为i，然后当前数组的最后一个ai数字变为1。由于里面有第i个数组总的，把最后一个ai数字改为1，意味着我们将i-ai+1到i这个区间内的所有ai数字都改为1，也就是这个区间的数据。操作一次。因此，我们可以开一个与原数组长度相同的新数组来记录该区间内数据操作的次数。因为V数组中的1不会改变，所以多次操作和操作一次的效果是一样的。最后，如果新数组中的元素大于0，则V数组中对应的元素为1。如果新数组中的元素等于0，则V数组中对应的元素为0。010-1010#include位/stdc++.husing命名空间std;constintN=200010;intn;intb[N];intmain(){intT;cinT;while(T--){cinn;memset(b,0,(n+1)*4);for(inti=1;i=n;i++){intx;cinx;x=min(x,i);//如果x大于i，则更新为i，因为此时数组中所有元素都变为1intl=i-x+1,r=i;b[l]++;b[r+1]--;}for(inti=1;i=n;i++){b[i]+=b[i-1];}for(inti=1;i=n;i++){cout!b[i]'';}coutendl;}返回0；}

1.实现思路

标题说明

农夫约翰出去沿路散步，但现在他意识到自己可能迷路了！

路边有一排人

氮

氮

N个农场。

不幸的是，农场没有编号，约翰很难知道他在小路上的位置。

然而，每个农场沿路都有一个彩色邮箱，因此约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。

每个邮箱的颜色是

A。

Z

A.Z

由A.Z之间的字母指定，因此沿着道路

氮

氮

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个字符组成的字符串，每个字符在

A。

Z

A.Z

在A.Z内

输出格式

输出一行，其中包含一个整数，该整数是可以解决FarmerJohn问题的最小数字。

K

K

K值。

数据范围

1

≤

氮

≤

100

1≤N≤100

1≤N≤100

输入样本

7

ABCDABC

输出样本

4

执行

2.实现代码

我们需要找到一个最小的K，使得不存在被K分隔的两个相同的字符串。我们可以使用强力解决方案，即四个for循环。第一个循环枚举每个K，第二个循环枚举第一个子字符串，第三个循环枚举第二个子字符串，第四个循环枚举判断两个字符串是否相同。三、AcWing1460.我在哪？

#include位/stdc++.husing命名空间std;intn;stringstr;intmain(){cinnstr;for(intk=1;k=n;k++){boolflag=false;for(inti=0;i+k-1n;i++){for(intj=i+1;j+k-1n;j++){boolsame=true;}for(intu=0;uk;u++)if(str[i+u]!=str[j+u]){相同=false;休息;}if(相同){flag=true;休息;如果中断；}if(!flag){coutkendl;休息;返回0;}

1.实现思路

标题说明

给定一个

n

n

n个小写字母组成的字符串。

现在，您需要删除一些字母，以便字符串中不再有三个或更多连续字符。

X

X

X。

需要删除的最少字母数是多少？

如果字符串不包含三个或更多连续的

X

X

x，不需要删除任何字母。

输入格式

第一行包含整数

n

n

名词

第二行包含一个长度为的字符串

n

n

n的小写字母字符串。

输出格式

输出需要删除的最少字母数。

数据范围

3

≤

n

≤

100

3≤n≤100

3≤n≤100

输入样本1

6

xxxiii

输出样本1

1

输入样本2

5

xxxx

输出样本2

0

输入样本3

10xxxxx