贵州省建设职业技术学院网站,网站建设合同范本-经过律师审核,平面设计培训机构排行,网站网页设计怎样文章目录一、AcWing 3956. 截断数组#xff08;中等#xff09;1. 实现思路2. 实现代码二、AcWing 3729. 改变数组元素#xff08;中等#xff09;1. 实现思路2. 实现代码三、AcWing 1460. 我在哪#xff1f;#xff08;简单#xff09;1. 实现思路2. 实现代码四、AcWin…
文章目录一、AcWing 3956. 截断数组中等1. 实现思路2. 实现代码二、AcWing 3729. 改变数组元素中等1. 实现思路2. 实现代码三、AcWing 1460. 我在哪简单1. 实现思路2. 实现代码四、AcWing 3768. 字符串删减简单1. 实现思路2. 实现代码五、AcWing 3777. 砖块简单1. 实现思路2. 实现代码一、AcWing 3956. 截断数组中等 题目描述
给定一个长度为 nnn 的数组 a1,a2,…,ana_{1},a_{2},…,a_{n}a1,a2,…,an。 现在要将该数组从中间截断得到三个非空子数组。 要求三个子数组内各元素之和都相等。 请问共有多少种不同的截断方法 输入格式
第一行包含整数 nnn。 第二行包含 nnn 个整数 a1,a2,…,ana_{1},a_{2},…,a_{n}a1,a2,…,an。 输出格式
输出一个整数表示截断方法数量。 数据范围
前六个测试点满足 1≤n≤101≤n≤101≤n≤10。 所有测试点满足 1≤n≤105−10000≤ai≤100001≤n≤10^{5}−10000≤a_{i}≤100001≤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 res0,cnt0;
int main()
{cinn;for(int i1;in;i){int x0;cinx;a[i]a[i-1]x; //前缀和数组}if(a[n]%3!0 || n3){cout0endl;}else{for(int j2;jn;j){if(a[j-1]a[n]/3){cnt;}if(a[j]a[n]/3*2){rescnt;}}coutres;}return 0;
}二、AcWing 3729. 改变数组元素中等 题目描述
给定一个空数组 VVV 和一个整数数组 a1,a2,…,ana_{1},a_{2},…,a_{n}a1,a2,…,an。 现在要对数组 VVV 进行 nnn 次操作。 第 iii 次操作的具体流程如下
从数组 VVV 尾部插入整数 000。将位于数组 VVV 末尾的 aia_{i}ai 个元素都变为 111已经是 111 的不予理会。
注意
aia_{i}ai 可能为 0即不做任何改变。aia_{i}ai 可能大于目前数组 V 所包含的元素个数此时视为将数组内所有元素变为 111。 请你输出所有操作完成后的数组 VVV。 输入格式
第一行包含整数 TTT表示共有 TTT 组测试数据。 每组数据第一行包含整数 nnn。 第二行包含 nnn 个整数 a1,a2,…,ana_{1},a_{2},…,a_{n}a1,a2,…,an。 输出格式
每组数据输出一行结果表示所有操作完成后的数组 VVV数组内元素之间用空格隔开。 数据范围
1≤T≤200001≤T≤200001≤T≤20000 1≤n≤2×1051≤n≤2×10^{5}1≤n≤2×105 0≤ai≤n0≤a_{i}≤n0≤ai≤n 保证一个测试点内所有 nnn 的和不超过 2×1052×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-ai1 到 i 的区间内的 ai 个数全部变成 1也就是这个区间内的数据操作一次。因此我们可以开一个新数组与原数组长度相等用以记录区间内数据操作的个数因为 V 数组当中的 1 不会发生改变所以操作多次和操作一次的效果是相同的。最后如果新数组当中的元素大于 0那么 V 数组中对应的元素就是 1如果新数组中的元素等于 0那么 V 数组中对应的元素就是 0。
2. 实现代码
#include bits/stdc.h
using namespace std;
const int N200010;
int n;
int b[N];
int main()
{int T;cinT;while(T--){cinn;memset(b,0,(n1)*4);for(int i1;in;i){int x;cinx;xmin(x,i); //如果x大于i的话就更新成i因为此时是将数组内的所有元素变为1 int li-x1,ri; b[l];b[r1]--;}for(int i1;in;i){b[i]b[i-1];}for(int i1;in;i){cout!!b[i] ;}coutendl;}return 0;
}三、AcWing 1460. 我在哪简单 题目描述
农夫约翰出门沿着马路散步但是他现在发现自己可能迷路了 沿路有一排共 NNN 个农场。 不幸的是农场并没有编号这使得约翰难以分辨他在这条路上所处的位置。 然而每个农场都沿路设有一个彩色的邮箱所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。 每个邮箱的颜色用 A..ZA..ZA..Z 之间的一个字母来指定所以沿着道路的 NNN 个邮箱的序列可以用一个长为 NNN 的由字母 A..ZA..ZA..Z 组成的字符串来表示。 某些邮箱可能会有相同的颜色。 约翰想要知道最小的 KKK 的值使得他查看任意连续 KKK 个邮箱序列他都可以唯一确定这一序列在道路上的位置。 例如假设沿路的邮箱序列为 ABCDABC 。 约翰不能令 K3K3K3因为如果他看到了 ABC则沿路有两个这一连续颜色序列可能所在的位置。 最小可行的 KKK 的值为 K4K4K4因为如果他查看任意连续 444 个邮箱那么可得到的连续颜色序列可以唯一确定他在道路上的位置。 输入格式
输入的第一行包含 NNN第二行包含一个由 NNN 个字符组成的字符串每个字符均在 A..ZA..ZA..Z 之内。 输出格式
输出一行包含一个整数为可以解决农夫约翰的问题的最小 KKK 值。 数据范围
1≤N≤1001≤N≤1001≤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. 字符串删减简单 题目描述
给定一个由 nnn 个小写字母构成的字符串。 现在需要删掉其中的一些字母使得字符串中不存在连续三个或三个以上的 xxx。 请问最少需要删掉多少个字母 如果字符串本来就不存在连续的三个或三个以上 xxx则无需删掉任何字母。 输入格式
第一行包含整数 nnn。 第二行包含一个长度为 nnn 的由小写字母构成的字符串。 输出格式
输出最少需要删掉的字母个数。 数据范围
3≤n≤1003≤n≤1003≤n≤100 输入样例 1 6 xxxiii 输出样例 1 1 输入样例 2 5 xxoxx 输出样例 2 0 输入样例 3 10 xxxxxxxxxx 输出样例 3 8 具体实现
1. 实现思路
我们利用 cnt 存储当前连续出现字符 x 的个数。若出现了一个字符 x则 cnt 加一。若出现了一个其它字符则 cnt 清零。若当前 cnt3说明遇到了连续三个 x此时需要删除一次。特别地此时删除最后一个字符 x 后可能补位的字符仍为 x如输入样例 3 所示。此时不能将 cnt 清零而应该减一然后继续遍历。
2. 实现代码
#include bits/stdc.h
using namespace std;int main()
{int n;string s;cinns;int res0,cnt0;for(int i0;in;i){if(s[i]x){cnt;if(cnt3){cnt--;res;}}else{cnt0;}}coutresendl;return 0;
}
五、AcWing 3777. 砖块简单 题目描述
nnn 个砖块排成一排从左到右编号依次为 1∼n1∼n1∼n。 每个砖块要么是黑色的要么是白色的。 现在你可以进行以下操作若干次可以是 000 次 选择两个相邻的砖块反转它们的颜色。黑变白白变黑 你的目标是通过不超过 3n3n3n 次操作将所有砖块的颜色变得一致。 输入格式
第一行包含整数 TTT表示共有 TTT 组测试数据。 每组数据第一行包含一个整数 nnn。 第二行包含一个长度为 nnn 的字符串 sss。其中的每个字符都是 W 或 B如果第 iii 个字符是 W则表示第 iii 号砖块是白色的如果第 iii 个字符是 B则表示第 iii 个砖块是黑色的。 输出格式
每组数据如果无解则输出一行 −1−1−1。 否则首先输出一行 kkk表示需要的操作次数。 如果 k0k0k0则还需再输出一行 kkk 个整数p1,p2,…,pkp_{1},p_{2},…,p_{k}p1,p2,…,pk。其中 pip_{i}pi 表示第 iii 次操作选中的砖块为 pip_{i}pi 和 pi1p_{i1}pi1 号砖块。 如果方案不唯一则输出任意合理方案即可。 数据范围
1≤T≤101≤T≤101≤T≤10 2≤n≤2002≤n≤2002≤n≤200 输入样例 4 8 BWWWWWWB 4 BWBB 5 WWWWW 3 BWB 输出样例 3 6 2 4 -1 0 2 2 1 具体实现
1. 实现思路
并没有要求操作次数最少因此只需输出任意一组可成功操作的次数即可。最终的结果只有两种要么全黑要么全白 两种情况可以依次枚举任一情况都可。同一个位置我们最多操作 1 次因为操作两次的话就变回原样。并且操作的顺序不影响最后的结果。其中第一个砖块只能操作一次所以如果第一个砖块跟我们目标颜色相同的话就不需要进行操作如果不同的话就一定会进行操作。第一个砖块是否操作是已经确定的了第二个砖块也是同样的道理后续皆同。因此在最后如果最后一个砖块和目标颜色相同的话就一定有解如果不同的话就一定无解这中间我们只需要操作 n-1 次。
2. 实现代码
#include bits/stdc.h
using namespace std;
int n;
string str;
void update(char c)
{if(cW){cB;}else{cW;}
}
bool check(char c)
{vectorintres;string sstr;for(int i0;in-1;i){if(s[i]!c){update(s[i]);update(s[i1]);res.push_back(i1); //字符串从0开始题目中从1开始}}if(s.back()!c){return false;}coutres.size()endl;for(int x0;xres.size();x){coutres[x] ;}if(res.size()!0){coutendl;}return true;
}
int main()
{int T;cinT;while(T--){cinnstr;if(!check(B)!check(W)){cout-1endl;}}return 0;
}
