差分（蓝桥备赛）

本文主要是介绍差分（蓝桥备赛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目都在蓝桥云课

1.字符迁移

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
int n,q;
string s;
int a[200010];
int main()
{cin>>n>>q;cin>>s;memset(a,0,sizeof(a));while(q--){ll l,r,k;cin>>l>>r>>k;k%=26;a[l-1]+=k;a[r]-=k;}for(int i=1; i<n; i++){a[i]+=a[i-1];}for(int i=0; i<n; i++){s[i]='a'+(s[i]-'a'+a[i])%26;}cout<<s<<endl;return 0;
}

2.线段覆盖

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1000010];
int main()
{int n,m;cin>>n>>m;while(m--){int l,r;cin>>l>>r;a[l]++;a[r+1]--;}for(int i=1; i<=n; i++){a[i]+=a[i-1];}int max1=0;for(int i=1;i<=n;i++){max1=max(max1,a[i]);}int sign=0;for(int i=1;i<=n;i++){if(max1==a[i]){sign++;}}cout<<max1<<" "<<sign<<endl;return 0;
}

3.重新排序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll a[100010],a1[100010];//必须long long 
int main()
{cin>>n;for(int i=0; i<n; i++){cin>>a[i];}cin>>m;while(m--){int l,r;cin>>l>>r;a1[l-1]++;a1[r]--;}for(int i=1; i<n; i++){a1[i]+=a1[i-1];//必须long long的原因，数据量太大了会爆 }ll sum=0,sum1=0;for(int i=0; i<n; i++){sum+=a[i]*a1[i];}sort(a,a+n,greater<int>());sort(a1,a1+n,greater<int>());for(int i=0; i<n; i++){sum1+=a[i]*a1[i];}cout<<sum1-sum<<endl;return 0;
}

 

 

这篇关于差分（蓝桥备赛）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---