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

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

逆序对

题目描述

完整代码

#include
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;
    }
    else
      tmp[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
    cin>>num[i];
  }
  res=0;
  merge_sort(0,n-1);
  cout<
}

代码讲解 

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

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

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

Max Sum

题目描述

完整代码

#include
#include
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 part
  int 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 way
  for(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 number
    return 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;
  else
    return 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
      cin>>num[i];
    }
    node res=maxSubArray(num,0,n-1);
    if(ncase){//equivalent to if(ncace!=0)
      cout<
    }
    cout<<"Case "<<++ncase<<":\n";
    cout<" "<1<<" "<1<
  }
}

代码讲解

用分治法解决的思路是：

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

棋盘覆盖问题

题目描述

完整代码

#include
#include
using namespace std;
 
int tile=1;// index of tile
 
void tileBoard(vectorint> >& 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 placed
 
  if (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 corner
  if (specialX >= x + half && specialY < y + half) { // in the bottom-left corner
    tileBoard(board, x + half, y, specialX, specialY, half); // find the bottom-left corner
  } else { // special block is not in the bottom-left corner
    board[x + half][y + half - 1] = currentTile; // put current tile in BL corner
    tileBoard(board, x + half, y, x + half, y + half - 1, half); // find the bottom-left corner
  }
 
  // bottom-right corner
  if (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<
  vectorint> > 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 offset
  board[x-1][y-1]=0;
  tileBoard(board,0,0,x-1,y-1,size);
 
  for(const auto & row:board){
    for(int i=0;isize();i++){
      cout<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 
#include 
#include 
using namespace std;
string str;
int solve(int left,int right,char c){
  if(left==right){
    if(c==str[left])
      return 0;
    else
      return 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')<
  }
  return 0;
}

代码讲解

先拆分。用个solve函数返回当前字符串变多少个能成为good string。退出条件：如果最后只剩一个了，这个是指定的c，那就不用变，为0；否则，要变一个，为1。

然后尝试字符串前一半为a，根据题意，此时如果前一半中有不是a的，要变的次数+1。然后加上递归后一半中要变的。

同理再尝试字符串的后一半为a，根据题意，此时如果后一半中有不是a的，要变的次数+1。然后加上递归前一半中要变的。

最后，返回前后对比变的次数更少的那一个。