蓝桥杯训练day1

1.前缀和

(1)3956. 截断数组

方法1：暴力
先用两个数组分别保存前缀和，后缀和。然后使用贪心思想来枚举后缀和的下标。
只有后缀和满足1/3的下标大于前缀和的下标，就加（具体看代码）过（19/22）数据

#include<iostream>
#include<cstring>
#include<algorithm>
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：动态规划
枚举第二部分的位置，然后找第一部分有多少分割方案。使用动态规划的技巧来减少计算

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;int n;
int cnt;
long long int ans=0;int pre[N];int main()
{cin>>n;int x;for(int i=1;i<=n;i++){cin>>x;pre[i]=pre[i-1]+x;}if(pre[n]%3){cout<<"0";return 0;}else{for(int i=2;i<=n-1;i++){if(pre[i-1]==pre[n]/3)cnt++;if(pre[i]==pre[n]/3*2)ans+=cnt;}}cout<<ans;return 0;
}

(2)795. 前缀和

前缀和最简单的题目，模板题
用一个数组来记录前i个元素的和.

#include<iostream>
#include<cstring>
using namespace std;const int N=100010;int n,m;
int a[N];
int pre[N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++)  //下标从1开始{cin>>a[i];pre[i]=pre[i-1]+a[i];}while(m--){int l,r;cin>>l>>r;cout<<pre[r]-pre[l-1]<<endl;    //注意是pre[l-1],要包括a[l]那个数}return 0;
}

(3)796. 子矩阵的和

二维前缀和,
模拟过程，然后优化，反复几次即可掌握

#include<iostream>
using namespace std;const int N=1010;int g[N][N];  //矩阵
int pre[N][N];  //左上角为（1，1），右下角是（i，j)的矩阵的和int n,m,q;int main()
{cin>>n>>m>>q;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>g[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;cin>>x1>>y1>>x2>>y2;cout<<pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1]<<endl;}return 0;
}

(4)1230. K倍区间

这个题目，看的第一感觉应该是个简单题，没想到是个中等题，暴力只能过一半数据。
暴力：

#include<iostream>
#include<cstring>
using namespace std;const int N=1e5+10;int n,k;int a[N];
int pre[N];
int ans=0;int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];a[i]%=k;pre[i]=pre[i-1]+a[i];}for(int i=1;i<=n;i++){int temp=0;for(int j=i;j<=n;j++){temp+=a[j];if(temp%k==0)ans++;}}cout<<ans;return 0;
}

想到
pre[r]-pre[l-1]=k
pre[r[=pre[l-1]+k
用pre[r]作为key，r作为key存储到哈希表，没想到也只多过一个数据

#include<iostream>
#include<cstring>
#include<unordered_map>
#include<vector>
using namespace std;const int N=1e5+10;int n,k;int a[N];
int pre[N];
int ans=0;int main()
{cin>>n>>k;unordered_map<int,vector<int>>Hash;for(int i=1;i<=n;i++){cin>>a[i];pre[i]=(pre[i-1]+a[i])%k;Hash[pre[i]].push_back(i);}//利用前缀和for(int i=1;i<=n;i++){if(Hash.count((pre[i-1]+k)%k)!=0) //找到区间{vector<int>t=Hash[(pre[i-1]+k)%k];for(int j=0;j<t.size();j++){if(i<=t[j]){ans+=t.size()-j;break;}}}}cout<<ans;return 0;
}

看了题解，发现距离答案一步之遥。在于
pre[r]-pre[l-1]=k等价于 pre[r]%k=pre[l-1]%k
所以找到两个前缀和相同的就好了，再利用一点动态规划的技巧.

#include<iostream>
using namespace std;
const int N=100010;int a[N];
int pre[N];
int Hash[N];int n,k;int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];pre[i]=(pre[i-1]+a[i])%k;}long long ans=0;Hash[0]=1;  //由于对k取余，所以第一个元素可能就是kfor(int i=1;i<=n;i++)   //从前往后遍历，到当前遍历到的点，前面有多少和他一样的值{ans+=Hash[pre[i]];Hash[pre[i]]++;}cout<<ans;return 0;}

(5)99. 激光炸弹

暴力

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=5010;int n,r;
int pre[N][N];int main()
{cin>>n>>r;   //n表示目标点个数，r表示炸弹的范围r = min(r, 5001);while(n--){int x,y,v;cin>>x>>y>>v;pre[x+1][y+1]+=v;}//前缀和for(int i=1;i<=5001;i++)for(int j=1;j<=5001;j++)pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+pre[i][j];int ans=0;//枚举右下角for(int i=r;i<=5001;i++){for(int j=r;j<=5001;j++)ans=max(ans,pre[i][j]-pre[i-r][j]-pre[i][j-r]+pre[i-r][j-r]);}cout<<ans;return 0;
}

2.差分

(1)797. 差分

什么是差分。
一句话：就是前缀和运输的逆运算.

#include<iostream>
#include<algorithm>
using namespace std;const int N=1e5+10;
int a[N];
int b[N];int n;
int T;int main()
{cin>>n>>T;for(int i=1;i<=n;i++)  //相当于，b是原数组，a是b的前缀和{cin>>a[i];b[i]=a[i]-a[i-1];}while(T--){int l,r,c;cin>>l>>r>>c;b[l]+=c;b[r+1]-=c;}int sum=0;for(int i=1;i<=n;i++){sum+=b[i];cout<<sum<<" ";}return 0;
}

(2)差分矩阵

同二维前缀和一样，就是扩展一个维度(但是很难哦）

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=1010;int pre[N][N];
int a[N][N];int n,m,q;int  main()
{cin>>n>>m>>q;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>pre[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;cin>>x1>>y1>>x2>>y2>>c;a[x1][y1]+=c;a[x1][y2+1]-=c;a[x2+1][y1]-=c;a[x2+1][y2+1]+=c;}int sum=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];cout<<pre[i][j]<<" ";if(j==m)cout<<endl;}return 0;
}

(3)3729. 改变数组元素

说实话，这个题目放在差分下面，完全不知道和差分有什么关系。
就从后往前读一遍看看哪些位置可以为1就可以了，应该是个简单到不能再简单的题，，，

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N=2*(1e5+10);
int a[N];  //操作数组
int b[N];   //答案数组
int T,n;//假设两个数组a，b，a是原数组，b是a的前缀和数组。
//那么a是b的差分，b是a的原数组int main()
{cin>>T;while(T--){memset(b,0,sizeof b);cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int cnt=a[n];for(int i=n;i>=1;i--){cnt=max(cnt,a[i]);if(cnt>=1){b[i]=1;cnt--;}}for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<endl;}return 0;
}

(4)100. 增减序列

这个题目难啊，由于所有的数都要一样，所有差分数组必须除了第一个数其余全是0.由于差分数组每次操作都需要b[L]+1,b[R+1]-1或b[L]-1,b[R+1]+1.所以将正数和负数相互抵消后，剩下的数要么和b[1]抵消，要么和b[n+1]抵消。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=1e5+10;long long int a[N];
long long int b[N];int n;int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i]-a[i-1];}long long int c1=0,c2=0;  //c1记录正数和，c2记录负数和for(int i=2;i<=n;i++){if(b[i]>=0)c1+=b[i];else    c2+=b[i];}long long int ans=min(abs(c1),abs(c2))+abs(abs(c1)-abs(c2));  //操作个数long long int count=abs(abs(c1)-abs(c2))+1;cout<<ans<<endl<<count<<endl;return 0;
}