分治算法求解：逆序对，Max Sum，棋盘覆盖，a-Good String——中山大学软件工程学院算法第四次实验课必做+选做题

写英文注释不是要“秀英文”，而是因为鄙人正在准备雅思，顺手练习

逆序对

题目描述

完整代码

#include<iostream>
using namespace std;
int num[500010]; // input numbers
int tmp[500010]; // sequence after merging left and right part
long long res;// Count of inversions
void merge(int left,int mid,int right){int i=left,j=mid+1;int idx=0;while(i<=mid&&j<=right){if(num[i]>num[j]){tmp[idx++]=num[j++];res+=mid-i+1;}elsetmp[idx++]=num[i++];}while(i<=mid)tmp[idx++]=num[i++];while(j<=right)tmp[idx++]=num[j++];
}
void merge_sort(int left,int right){if(left>=right){return;}int mid=(left+right)/2;merge_sort(left,mid);merge_sort(mid+1,right);merge(left,mid,right);for(int i=left;i<=right;i++){num[i]=tmp[i-left]; //num数组不是tmp数组翻转过来！//这里是调整索引}
}
int main(){ios::sync_with_stdio(false);int n;cin>>n;for(int i=0;i<n;i++){cin>>num[i];}res=0;merge_sort(0,n-1);cout<<res<<endl;
}

代码讲解

归并排序。在合并的过程发现逆序的时候，后面有多少个就说明有多少个逆序了。

  for(int i=left;i<=right;i++){num[i]=tmp[i-left]; //num数组不是tmp数组翻转过来！//这里是调整索引}

注意这里的索引调整 i-left 是因为 tmp 数组是从 0 开始的，而 num 数组的相应段是从 left 开始的。

Max Sum

题目描述

完整代码

#include<iostream>
#include<cstring>
using namespace std;
int num[100010];
struct node{int l,r,sum;node(int x,int y,int z):l(x),r(y),sum(z){}//constructor initialization
};
node crossingSubArray(int num[],int mid,int low,int high){node s3(0,0,0);int sum=0;int max_left=-10000;// max value for the left partint max_right=-10000;// max value for the right part// A very sophisticated algorithm. Since this array crosses both the left and right arrays, the middle must be crossed!// For the left part, the sequence starts from the middle and goes to the low index. If there is an index that achieves a larger value, update the left index.for(int i=mid;i>=low;i--){sum+=num[i];if(sum>=max_left){max_left=sum;s3.l=i;}}sum=0;// possess the right array in the same wayfor(int i=mid+1;i<=high;i++){sum+=num[i];if(sum>max_right){max_right=sum;s3.r=i;}}s3.sum=max_left+max_right;return s3;
}
node maxSubArray(int num[],int left,int right){if(left==right){//means that there is only one numberreturn node(left,right,num[left]);}int mid=(left+right)/2;node s1= maxSubArray(num,left,mid);node s2= maxSubArray(num,mid+1,right);node s3= crossingSubArray(num,mid,left,right);if(s1.sum>=s2.sum&&s1.sum>=s3.sum)return s1;else if(s2.sum>=s1.sum&&s2.sum>=s3.sum)return s2;elsereturn s3;
}
int main(){int T,n;ios::sync_with_stdio(false);cin>>T;int ncase=0;while(T--){cin>>n;memset(num,0,sizeof(num));for(int i=0;i<n;i++){cin>>num[i];}node res=maxSubArray(num,0,n-1);if(ncase){//equivalent to if(ncace!=0)cout<<endl;}cout<<"Case "<<++ncase<<":\n";cout<<res.sum<<" "<<res.l+1<<" "<<res.r+1<<endl;}
}

代码讲解

用分治法解决的思路是：

把数组对半分，使得和最大的左和右索引，要么包括了左半边，要么包括了右半边，要么一个在左边，一个在右边。所以在这三个中取最大值即可。如果只在某半边，因为最后会把那个块拆成单个，所以是可以直接通过比较比出来。如果是穿过了中间，注意要从中间往两边增（拆成先往左增再往右增）来比较怎么样才是最大的并且记下来此时的下标。

棋盘覆盖问题

题目描述

完整代码

#include<iostream>
#include<vector>
using namespace std;int tile=1;// index of tilevoid tileBoard(vector<vector<int> >& board,int x,int y,int specialX,int specialY,int size){if(size==1) return;int half=size/2;int currentTile=tile++;// top-left corner// if the special block is in the top-left corner, solve the top-left corner first.// if not, the top-left block among the four in the center can be determined as the place where the current tile should be placedif (specialX < x + half && specialY < y + half) {tileBoard(board, x, y, specialX, specialY, half);} else {board[x + half - 1][y + half - 1] = currentTile;tileBoard(board, x, y, x + half - 1, y + half - 1, half);}if (specialX < x + half && specialY >= y + half) {tileBoard(board, x, y + half, specialX, specialY, half);} else {board[x + half - 1][y + half] = currentTile;tileBoard(board, x, y + half, x + half - 1, y + half, half);}// bottom-left cornerif (specialX >= x + half && specialY < y + half) { // in the bottom-left cornertileBoard(board, x + half, y, specialX, specialY, half); // find the bottom-left corner} else { // special block is not in the bottom-left cornerboard[x + half][y + half - 1] = currentTile; // put current tile in BL cornertileBoard(board, x + half, y, x + half, y + half - 1, half); // find the bottom-left corner}// bottom-right cornerif (specialX >= x + half && specialY >= y + half) {tileBoard(board, x + half, y + half, specialX, specialY, half);} else {board[x + half][y + half] = currentTile;tileBoard(board, x + half, y + half, x + half, y + half, half);}
}
int main(){int k,x,y;cin>>k>>x>>y;int size=(1<<k);vector<vector<int> > board(size,vector<int>(size,0));// a quick way to initialize the 2D vector to 0// The number of dimensions in the vector corresponds to the number of levels of nesting//NOTE:the coordinate offsetboard[x-1][y-1]=0;tileBoard(board,0,0,x-1,y-1,size);for(const auto & row:board){for(int i=0;i<row.size();i++){cout<<row[i]<<(i==row.size()-1?'\n':' '); // A simple but useful judgement}}}//the board look like this
/**   y 0 1 2* x 0 TL TR*   1 BL BR*   2**/

代码讲解

这题的思路还有点绕。就是先把棋盘分成4大块。先看特殊方块在不在左上，如果在的话递归进入左上搜索。如果不在，说明左上最靠近中心（也就是左上大块最右下的小块）标记为当前的骨牌。其余几个同理。

a-Good String

题目描述

完整代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string str;
int solve(int left,int right,char c){if(left==right){if(c==str[left])return 0;elsereturn 1;}int mid =(left+right)/2;int res1=0,res2=0;for(int i=left;i<=mid;i++){if(str[i]!=c) {res1++;}}for(int i=mid+1;i<=right;i++){if(str[i]!=c) {res2++;}}return min(res1 + solve(mid + 1, right, c + 1), res2 + solve(left, mid, c + 1));
}
int main(){int T,n;cin>>T;while(T--){cin>>n>>str;cout<<solve(0,n-1,'a')<<endl;}return 0;
}