上海网站建设推荐案例,怎么自己开公司,wordpress 菜单 间距,出售已备案的域名合法吗前缀和差分1.前缀和(1)3956. 截断数组(2)795. 前缀和(3)796. 子矩阵的和(4)1230. K倍区间(5)99. 激光炸弹2.差分(1)797. 差分(2)差分矩阵(3)3729. 改变数组元素(4)100. 增减序列1.前缀和
(1)3956. 截断数组 方法1#xff1a;暴力 先用两个数组分别保存前缀和#xff0c;后缀…
前缀和差分1.前缀和(1)3956. 截断数组(2)795. 前缀和(3)796. 子矩阵的和(4)1230. K倍区间(5)99. 激光炸弹2.差分(1)797. 差分(2)差分矩阵(3)3729. 改变数组元素(4)100. 增减序列1.前缀和
(1)3956. 截断数组 方法1暴力 先用两个数组分别保存前缀和后缀和。然后使用贪心思想来枚举后缀和的下标。 只有后缀和满足1/3的下标大于前缀和的下标就加具体看代码过19/22数据
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N 1e5 10;int n;
int a[N];
int pre[N];
int npre[N];
int h1[N], h2[N];
int cnt1, cnt2;
int sum 0;
int main()
{cin n;for (int i 1; i n; i){cin a[i];sum a[i];}int part sum / 3;pre[0] 0; //pre[i]表示前i个数的总和这里下标从1开始有意义for (int i 1; i n; i) //前缀和{pre[i] pre[i - 1] a[i];if (pre[i] part)h1[cnt1] i;}npre[n] a[n];if (npre[n] part)h2[cnt2] n;for (int i n - 1; i 1; i--) //后缀和{npre[i] npre[i 1] a[i];if (npre[i] part)h2[cnt2] i;}//如此一来存储了第一部分的part值的下标从小到大//又存储了第二部分的part值的下标从大到小//固定第二部分的下标然后找第一部分的下标由于从小到大如果第二部分的下标大于第一部分下标的,则第一部分剩下的下标个数等于//当前答案个数。//然后枚举第二部分的下标反复即可int ans 0; //记录答案while (cnt2){int r h2[cnt2];int temp cnt1; //第一部分的下标while (temp){if (r h1[temp]1) //可以分成三个部分{ans ans temp;break;}temp--;}cnt2--;}cout ans endl;return 0;}
方法2动态规划 枚举第二部分的位置然后找第一部分有多少分割方案。使用动态规划的技巧来减少计算
#includeiostream
#includecstring
using namespace std;
const int N100010;int n;
int cnt;
long long int ans0;int pre[N];int main()
{cinn;int x;for(int i1;in;i){cinx;pre[i]pre[i-1]x;}if(pre[n]%3){cout0;return 0;}else{for(int i2;in-1;i){if(pre[i-1]pre[n]/3)cnt;if(pre[i]pre[n]/3*2)anscnt;}}coutans;return 0;
}
(2)795. 前缀和 前缀和最简单的题目模板题 用一个数组来记录前i个元素的和.
#includeiostream
#includecstring
using namespace std;const int N100010;int n,m;
int a[N];
int pre[N];int main()
{cinnm;for(int i1;in;i) //下标从1开始{cina[i];pre[i]pre[i-1]a[i];}while(m--){int l,r;cinlr;coutpre[r]-pre[l-1]endl; //注意是pre[l-1],要包括a[l]那个数}return 0;
}(3)796. 子矩阵的和 二维前缀和, 模拟过程然后优化反复几次即可掌握
#includeiostream
using namespace std;const int N1010;int g[N][N]; //矩阵
int pre[N][N]; //左上角为11右下角是ij)的矩阵的和int n,m,q;int main()
{cinnmq;for(int i1;in;i)for(int j1;jm;j){cing[i][j];pre[i][j]pre[i][j-1]pre[i-1][j]-pre[i-1][j-1]g[i][j];}while(q--){int x1,x2,y1,y2;cinx1y1x2y2;coutpre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]pre[x1-1][y1-1]endl;}return 0;
}
(4)1230. K倍区间 这个题目看的第一感觉应该是个简单题没想到是个中等题暴力只能过一半数据。 暴力
#includeiostream
#includecstring
using namespace std;const int N1e510;int n,k;int a[N];
int pre[N];
int ans0;int main()
{cinnk;for(int i1;in;i){cina[i];a[i]%k;pre[i]pre[i-1]a[i];}for(int i1;in;i){int temp0;for(int ji;jn;j){tempa[j];if(temp%k0)ans;}}coutans;return 0;
}想到 pre[r]-pre[l-1]k pre[r[pre[l-1]k 用pre[r]作为keyr作为key存储到哈希表没想到也只多过一个数据
#includeiostream
#includecstring
#includeunordered_map
#includevector
using namespace std;const int N1e510;int n,k;int a[N];
int pre[N];
int ans0;int main()
{cinnk;unordered_mapint,vectorintHash;for(int i1;in;i){cina[i];pre[i](pre[i-1]a[i])%k;Hash[pre[i]].push_back(i);}//利用前缀和for(int i1;in;i){if(Hash.count((pre[i-1]k)%k)!0) //找到区间{vectorinttHash[(pre[i-1]k)%k];for(int j0;jt.size();j){if(it[j]){anst.size()-j;break;}}}}coutans;return 0;
}看了题解发现距离答案一步之遥。在于 pre[r]-pre[l-1]k等价于 pre[r]%kpre[l-1]%k 所以找到两个前缀和相同的就好了再利用一点动态规划的技巧.
#includeiostream
using namespace std;
const int N100010;int a[N];
int pre[N];
int Hash[N];int n,k;int main()
{cinnk;for(int i1;in;i){cina[i];pre[i](pre[i-1]a[i])%k;}long long ans0;Hash[0]1; //由于对k取余所以第一个元素可能就是kfor(int i1;in;i) //从前往后遍历到当前遍历到的点前面有多少和他一样的值{ansHash[pre[i]];Hash[pre[i]];}coutans;return 0;}(5)99. 激光炸弹 暴力
#includeiostream
#includecstring
#includealgorithm
using namespace std;const int N5010;int n,r;
int pre[N][N];int main()
{cinnr; //n表示目标点个数r表示炸弹的范围r min(r, 5001);while(n--){int x,y,v;cinxyv;pre[x1][y1]v;}//前缀和for(int i1;i5001;i)for(int j1;j5001;j)pre[i][j]pre[i-1][j]pre[i][j-1]-pre[i-1][j-1]pre[i][j];int ans0;//枚举右下角for(int ir;i5001;i){for(int jr;j5001;j)ansmax(ans,pre[i][j]-pre[i-r][j]-pre[i][j-r]pre[i-r][j-r]);}coutans;return 0;
}2.差分
(1)797. 差分 什么是差分。 一句话就是前缀和运输的逆运算.
#includeiostream
#includealgorithm
using namespace std;const int N1e510;
int a[N];
int b[N];int n;
int T;int main()
{cinnT;for(int i1;in;i) //相当于b是原数组a是b的前缀和{cina[i];b[i]a[i]-a[i-1];}while(T--){int l,r,c;cinlrc;b[l]c;b[r1]-c;}int sum0;for(int i1;in;i){sumb[i];coutsum ;}return 0;
}(2)差分矩阵 同二维前缀和一样就是扩展一个维度(但是很难哦
#includeiostream
#includecstring
#includealgorithm
using namespace std;const int N1010;int pre[N][N];
int a[N][N];int n,m,q;int main()
{cinnmq;for(int i1;in;i)for(int j1;jm;j){cinpre[i][j];a[i][j]pre[i][j]-pre[i-1][j]-pre[i][j-1]pre[i-1][j-1];}while(q--){int x1,x2,y1,y2,c;cinx1y1x2y2c;a[x1][y1]c;a[x1][y21]-c;a[x21][y1]-c;a[x21][y21]c;}int sum0;for(int i1;in;i)for(int j1;jm;j){pre[i][j]pre[i-1][j]pre[i][j-1]-pre[i-1][j-1]a[i][j];coutpre[i][j] ;if(jm)coutendl;}return 0;
}(3)3729. 改变数组元素 说实话这个题目放在差分下面完全不知道和差分有什么关系。 就从后往前读一遍看看哪些位置可以为1就可以了应该是个简单到不能再简单的题
#includeiostream
#includealgorithm
#includecstring
using namespace std;const int N2*(1e510);
int a[N]; //操作数组
int b[N]; //答案数组
int T,n;//假设两个数组aba是原数组b是a的前缀和数组。
//那么a是b的差分b是a的原数组int main()
{cinT;while(T--){memset(b,0,sizeof b);cinn;for(int i1;in;i)cina[i];int cnta[n];for(int in;i1;i--){cntmax(cnt,a[i]);if(cnt1){b[i]1;cnt--;}}for(int i1;in;i)coutb[i] ;coutendl;}return 0;
}(4)100. 增减序列 这个题目难啊由于所有的数都要一样所有差分数组必须除了第一个数其余全是0.由于差分数组每次操作都需要b[L]1,b[R1]-1或b[L]-1,b[R1]1.所以将正数和负数相互抵消后剩下的数要么和b[1]抵消要么和b[n1]抵消。
#includeiostream
#includecstring
#includealgorithm
using namespace std;const int N1e510;long long int a[N];
long long int b[N];int n;int main()
{cinn;for(int i1;in;i){cina[i];b[i]a[i]-a[i-1];}long long int c10,c20; //c1记录正数和c2记录负数和for(int i2;in;i){if(b[i]0)c1b[i];else c2b[i];}long long int ansmin(abs(c1),abs(c2))abs(abs(c1)-abs(c2)); //操作个数long long int countabs(abs(c1)-abs(c2))1;coutansendlcountendl;return 0;
}
