建设主管部门网站,wordpress4.9.2,网络编程技术清华大学出版社答案,wordpress手机号码插件作者#xff1a;指针不指南吗 专栏#xff1a;Acwing 蓝桥集训每日一题 #x1f43e;输出的时候#xff0c;注意数据类型#x1f43e; 文章目录1.截断数组2.前缀和3.子矩阵的和4.k倍区间1.截断数组 给定一个长度为 n 的数组 a1a_1a1,a2a_2a2,…,ana_nan。 现在… 作者指针不指南吗 专栏Acwing 蓝桥集训每日一题 输出的时候注意数据类型 文章目录1.截断数组2.前缀和3.子矩阵的和4.k倍区间1.截断数组 给定一个长度为 n 的数组 a1a_1a1,a2a_2a2,…,ana_nan。 现在要将该数组从中间截断得到三个非空子数组。 要求三个子数组内各元素之和都相等。 请问共有多少种不同的截断方法 输入格式 第一行包含整数 n。 第二行包含 n个整数 a1a_1a1,a2a_2a2,…,ana_nan。 输出格式 输出一个整数表示截断方法数量。 数据范围 前六个测试点满足 1≤n≤10。 所有测试点满足 1≤n≤10510^5105−10000≤aia_iai≤10000。 输入样例1 4
1 2 3 3输出样例1 1输入样例2 5
1 2 3 4 5输出样例2 0输入样例3 2
0 0输出样例3 0思路 分三个非空子数组且和相同即每个子数组的和是s[n]/3 首先呢枚举两个节点肯定不行时间复杂度是 O(n2n^2n2)题里面的数量级太大了 所以只能尝试枚举一个节点再把剩下一个表示出来 做法枚举第二个节点 j 随着 j 的增加第一个节点满足 s[n]/3也会增加用cnt 存储 j 前面满足条件的第一个节点当j 也满足条件时把总的存在 ans 中 注意结果最大是100010的阶乘远超int 类型会爆开long long 考虑特殊请款不够三个元素s[n]%3!0 代码实现 #includebits/stdc.h
using namespace std;int s[100010];
long long ans;int main()
{int n;cinn;for(int i1;in;i){ //计算前缀和scanf(%d,s[i]);s[i]s[i-1];}//考虑特殊情况if(s[n]%3!0||n3){cout0;return 0;}int cnt0;for(int i2;in;i){if(s[i-1]s[n]/3) cnt; //第二个节点之前满足条件可以成为第一个节点的个数if(s[i]s[n]/3*2) anscnt; //满足条件成为第二个节点加上第一个节点类似于加法原理}printf(%lld,ans); //注意数据类型时long longreturn 0;
}2.前缀和 输入一个长度为 n 的整数序列。 接下来再输入 m个询问每个询问输入一对 l,r。 对于每个询问输出原序列中从第 l个数到第 r个数的和。 输入格式 第一行包含两个整数 n 和 m。 第二行包含 n个整数表示整数数列。 接下来 m行每行包含两个整数 l 和 r表示一个询问的区间范围。 输出格式 共 m 行每行输出一个询问的结果。 数据范围 1≤l≤r≤n, 1≤n,m≤100000, −1000≤数列中元素的值≤1000−1000≤数列中元素的值≤1000 输入样例 5 3
2 1 3 6 4
1 2
1 3
2 4输出样例 3
6
10代码实现 #includebits/stdc.h
using namespace std;int s[100010];int main()
{int n,m;cinnm;for(int i1;in;i){cins[i];s[i]s[i-1];}while(m--){int a,b;cinab;couts[b]-s[a-1]endl;}return 0;
}3.子矩阵的和 输入一个 n行 m 列的整数矩阵再输入 q 个询问每个询问包含四个整数 x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 nmq。 接下来 n行每行包含 m 个整数表示整数矩阵。 接下来 q 行每行包含四个整数 x1,y1,x2,y2表示一组询问。 输出格式 共 q行每行输出一个询问的结果。 数据范围 1≤n,m≤1000, 1≤q≤200000, 1≤x1≤x2≤n, 1≤y1≤y2≤m, −1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000 输入样例 3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4输出样例 17
27
21代码实现
#includeiostream
using namespace std;const int N1010;int s[N][N];int n,m,q;int main(){cinnmq;for(int i1;in;i)for(int j1;jm;j){cins[i][j];s[i][j]s[i-1][j]s[i][j-1]s[i-1][j-1];}while(q--){int x1,y1,x2,y2;cinx1y1x2y2;couts[x2][y2]-s[x1-1][y2]-s[x2][y1-1]s[x1-1][y1-1];}return 0;
}4.k倍区间 题目描述 给定一个长度为 N 的数列1,2,⋯A1,A2,⋯A N如果其中一段连续的子序列之和是 K 的倍数我们就称这个区间 是 K 倍区间。 你能求出数列中总共有多少个 K 倍区间吗 输入描述 第一行包含两个整数 N 和 K(1≤N,K≤10510^5105 )。 以下 N 行每行包含一个整数 A i ( 1≤A i≤10510^5105 ). 输出描述 输出一个整数代表 K 倍区间的数目。 示例 输入 5 2
1
2
3
4
5输出 6代码实现
#includebits/stdc.h
using namespace std;typedef long long LL;
const LL N100010;
LL s[N],cnt[N];int main()
{LL n,k,i,r,res0;cinnk;for(i1;in;i) cins[i]; //前缀和for(i1;in;i) s[i]s[i-1];//同余cnt[0]1; //包含它本身,初始化为1for(r1;rn;r) {LL us[r]%k; rescnt[u];cnt[u];}coutresendl;return 0;}
