1.4 习题思路简述
本节将给出以下题的题解：
- P4552 IncDec Sequence
- P2004 领地选择
- P1627 中位数
- P1496 火烧赤壁
代码仓库位置：https://github.com/zhenghan123456/algotithm_programming
在这里建议每道题都认真思考，习题题解只是简单表明一下思路，不会和例题一样具体
1.4.9P4552 IncDec Sequence
题意简述
给定一个数组a aa，你可以进行任意次操作，每次操作任选一个a aa中的区间，让这个区间加1 11或减1 11，给出最少能让区间中的数全部相等的操作次数及在最少操作次数前提下能有多少种情况
算法分析
首先读题时看到让区间加1 11或减1 11，这就可以往差分算法方向思考，那么容易想到当差分数组除了第一个数之外的所有元素都是0 00的时候所有数都相等。而对一个区间[ l , r ) [l,r)[l,r)进行操作，则是让d l ± 1 , d r ∓ 1 d_l\pm 1,d_r \mp 1dl±1,dr∓1，为了尽快归零，就要对每一个两端，让负数加1 11，正数减1 11，这么一来，所有负数或者所有正数必然都会归零。
设有正数和为a aa，负数和为− b -b−b，那么需要进行m i n ( a , b ) min(a,b)min(a,b)次操作可以让所有正数或者所有负数都归零，然后要进行的操作次数为m a x ( a , b ) − m i n ( a , b ) max(a,b)-min(a,b)max(a,b)−min(a,b)，最终要进行的最少操作次数为m a x ( a , b ) max(a,b)max(a,b)
第一小问处理完之后看到第二小问。不妨先想一想，什么时候会出现不同结果。
不难想到，因为最终结果都是相等的数字，所以只有d 1 d_1d1会影响得到的结果。而当正数和负数都没有归零的时候，d 1 d_1d1是不会被操作的，而当其中一个归零之后（不妨假设未归零的是正数，负数同理）。
接下来每一步操作都有两种方法：设这个整数在d i d_idi上，则可以将d 1 + 1 d_1+1d1+1，将d i − 1 d_i-1di−1，或者将d i − 1 d_i-1di−1，将不存在的末尾元素+ 1 +1+1，这样一来就会产生m a x ( a , b ) − m i n ( a , b ) = ∣ a − b ∣ max(a,b)-min(a,b)=|a-b|max(a,b)−min(a,b)=∣a−b∣种结果，最后加上默认情况即可。
代码位置：1\problems\P4552.cpp
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'constintmaxn=1e5+10;ll a[maxn],diff[maxn];// 别忘了long longintmain(){ios::sync_with_stdio(0);cin.tie(0);intn;cin>>n;_for(i,n){cin>>a[i];}// 初始化差分diff[0]=a[0];_rep(i,1,n){diff[i]=a[i]-a[i-1];}ll x=0,y=0;// 正数和、负数和_rep(i,1,n){if(diff[i]>0)x+=diff[i];elsey-=diff[i];}cout<<max(x,y)<<'\n'<<llabs(x-y)+1<<'\n';}1.4.10P2004 领地选择
题意简述
给出一个n × m n \times mn×m的加权矩形和一个值c cc，求在这个矩形中权值和最大的c × c c\times cc×c正方形的左上角坐标
算法分析
因为数据范围不大，可以考虑枚举所有可能的左上角坐标，通过二维前缀和算法计算正方形的权值和，最终找到最大值。
代码位置：1\problems\P2004.cpp
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'constintmaxn=1e3+10;inta[maxn][maxn],pre[maxn][maxn];intmain(){ios::sync_with_stdio(0);cin.tie(0);intn,m,c;cin>>n>>m>>c;_for(i,n){_for(j,m){cin>>a[i][j];}}pre[0][0]=a[0][0];_rep(i,1,n){pre[i][0]=a[i][0]+pre[i-1][0];}_rep(i,1,m){pre[0][i]=a[0][i]+pre[0][i-1];}_rep(i,1,n){_rep(j,1,m){pre[i][j]=a[i][j]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];}}intmaxx=INT_MIN;intmaxi=0,maxj=0;_for(i,n-c+1){_for(j,m-c+1){intval;if(i){if(j)val=pre[i+c-1][j+c-1]-pre[i-1][j+c-1]-pre[i+c-1][j-1]+pre[i-1][j-1];elseval=pre[i+c-1][j+c-1]-pre[i-1][j+c-1];}else{if(j)val=pre[i+c-1][j+c-1]-pre[i+c-1][j-1];elseval=pre[i+c-1][j+c-1];}if(val>maxx){maxx=val;maxi=i;maxj=j;}}}cout<<maxi+1<<' '<<maxj+1<<endl;return0;}1.4.11P1627 中位数
题意简述
给定序列a aa，求其中有多少个序列，令其中位数为b bb
中位数定义：将一个序列的元素从小到大排列之后，大小位于中间的数
算法分析
根据题意，一个序列（设长度为n nn）的中位数是b bb，那就必须满足大于b bb的数的数量x xx和小于b bb的数的数量y yy满足0 ≤ x , y ≤ n 2 0 \le x,y \le \frac{n}{2}0≤x,y≤2n（向下取整），统计区间中有多少个大于b bb和小于b bb的数可以使用前缀和算法的变体，参考下面的代码。
代码位置：1\problems\P1627.cpp
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=2e5+5;ll cnt_left[maxn*2],cnt_right[maxn*2];#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'intmain(){ios::sync_with_stdio(0);cin.tie(0);intn;ll b;cin>>n>>b;vector<ll>arr(n);intpos=-1;// 记录第一个b出现的下标_for(i,n){cin>>arr[i];if(pos==-1&&arr[i]==b)pos=i;}intoffset=n;// 第一步：统计b左侧所有前缀和（0 ~ pos-1）intsum=offset;cnt_left[sum]=1;_for(i,pos){if(arr[i]>b)sum++;elseif(arr[i]<b)sum--;cnt_left[sum]++;}// 第二步：统计b及右侧所有前缀和（pos ~ n-1）_rep(i,pos,n){if(arr[i]>b)sum++;elseif(arr[i]<b)sum--;cnt_right[sum]++;}ll ans=0;_rep(i,0,2*n+1){ans+=cnt_left[i]*cnt_right[i];}cout<<ans<<endl;return0;}1.4.12P1496 火烧赤壁
题意简述
赤壁之战中曹操战船起火，给定任意个区间[ l , r ) [l,r)[l,r)，表示这些区间里有战船起火，计算起火的战船总数
算法分析
用差分+离散化即可，主要是离散化算法要好好想想，还有区间是左闭右开非常容易理解出错。
代码位置：1\problems\P1496.cpp
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'constintmaxn=4e5+10;ll diff[maxn];// 记得开long longll nums[maxn];struct{ll s,t;}s[maxn];intmain(){ios::sync_with_stdio(0);cin.tie(0);intn;cin>>n;ll len=0;_for(i,n){cin>>s[i].s>>s[i].t;nums[len++]=s[i].s;nums[len++]=s[i].t;}sort(nums,nums+len);inttot=unique(nums,nums+len)-nums;// 去重_for(i,n){intl=lower_bound(nums,nums+tot,s[i].s)-nums;intr=lower_bound(nums,nums+tot,s[i].t)-nums;diff[l]++;diff[r]--;}ll ans=0;intcover=0;_for(i,tot-1){cover+=diff[i];if(cover>0){ans+=nums[i+1]-nums[i];}}cout<<ans<<endl;return0;}
