1.4 习题思路简述本节将给出以下题的题解P4552 IncDec SequenceP2004 领地选择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_11d1​1将d i − 1 d_i-1di​−1或者将d i − 1 d_i-1di​−1将不存在的末尾元素 1 11这样一来就会产生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#includebits/stdc.husingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti0;in;i)#define_rep(i,a,b)for(intia;ib;i)#defineendl\nconstintmaxn1e510;ll a[maxn],diff[maxn];// 别忘了long longintmain(){ios::sync_with_stdio(0);cin.tie(0);intn;cinn;_for(i,n){cina[i];}// 初始化差分diff[0]a[0];_rep(i,1,n){diff[i]a[i]-a[i-1];}ll x0,y0;// 正数和、负数和_rep(i,1,n){if(diff[i]0)xdiff[i];elsey-diff[i];}coutmax(x,y)\nllabs(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#includebits/stdc.husingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti0;in;i)#define_rep(i,a,b)for(intia;ib;i)#defineendl\nconstintmaxn1e310;inta[maxn][maxn],pre[maxn][maxn];intmain(){ios::sync_with_stdio(0);cin.tie(0);intn,m,c;cinnmc;_for(i,n){_for(j,m){cina[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];}}intmaxxINT_MIN;intmaxi0,maxj0;_for(i,n-c1){_for(j,m-c1){intval;if(i){if(j)valpre[ic-1][jc-1]-pre[i-1][jc-1]-pre[ic-1][j-1]pre[i-1][j-1];elsevalpre[ic-1][jc-1]-pre[i-1][jc-1];}else{if(j)valpre[ic-1][jc-1]-pre[ic-1][j-1];elsevalpre[ic-1][jc-1];}if(valmaxx){maxxval;maxii;maxjj;}}}coutmaxi1 maxj1endl;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#includebits/stdc.husingnamespacestd;typedeflonglongll;constintmaxn2e55;ll cnt_left[maxn*2],cnt_right[maxn*2];#define_for(i,n)for(inti0;in;i)#define_rep(i,a,b)for(intia;ib;i)#defineendl\nintmain(){ios::sync_with_stdio(0);cin.tie(0);intn;ll b;cinnb;vectorllarr(n);intpos-1;// 记录第一个b出现的下标_for(i,n){cinarr[i];if(pos-1arr[i]b)posi;}intoffsetn;// 第一步统计b左侧所有前缀和0 ~ pos-1intsumoffset;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 ans0;_rep(i,0,2*n1){anscnt_left[i]*cnt_right[i];}coutansendl;return0;}1.4.12P1496 火烧赤壁题意简述赤壁之战中曹操战船起火给定任意个区间[ l , r ) [l,r)[l,r)表示这些区间里有战船起火计算起火的战船总数算法分析用差分离散化即可主要是离散化算法要好好想想还有区间是左闭右开非常容易理解出错。代码位置1\problems\P1496.cpp#includebits/stdc.husingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti0;in;i)#define_rep(i,a,b)for(intia;ib;i)#defineendl\nconstintmaxn4e510;ll diff[maxn];// 记得开long longll nums[maxn];struct{ll s,t;}s[maxn];intmain(){ios::sync_with_stdio(0);cin.tie(0);intn;cinn;ll len0;_for(i,n){cins[i].ss[i].t;nums[len]s[i].s;nums[len]s[i].t;}sort(nums,numslen);inttotunique(nums,numslen)-nums;// 去重_for(i,n){intllower_bound(nums,numstot,s[i].s)-nums;intrlower_bound(nums,numstot,s[i].t)-nums;diff[l];diff[r]--;}ll ans0;intcover0;_for(i,tot-1){coverdiff[i];if(cover0){ansnums[i1]-nums[i];}}coutansendl;return0;}