核心思想：

将一个大问题拆成一些子问题，求解完子问题后，进行合并，降低时间复杂度

一、经典例题

1、求序列中最大子串和

对于答案而言，因为连续，我们现在将一个区间分成两个部分，最终答案为

（1）左区间的最大值

（2）右区间的最大值

（3）左区间的最大后缀 + 右区间的最大前缀

三者取最大值，因为每个操作其实本质上都是相同的，直接分治成子问题，最后合并

#include<iostream>
using namespace std;

typedef long long ll;

const int N = 1000005;
int a[N];

ll cdq(int n, int l, int r) {
    if(l == r) return a[l];
    
    int mid = l + r >> 1;
    ll sum = max(cdq(n, l, mid), cdq(n, mid + 1, r));
    
    ll t1 = 0, t2 = 0, t = 0;
    for(int i = mid + 1; i <= r; ++ i)
         t += a[i], t1 = max(t1, t);
    t = 0;
    for(int i = mid; i >= l; -- i)
         t += a[i], t2 = max(t2, t);
    sum = max(sum, t1 + t2);
    return sum;
}

int main() {
    
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i) scanf("%d", &a[i]);
    
    printf("%lld\n", cdq(n, 0, n - 1));
    
    return 0;
}

2、确定二叉树

核心思想：

利用（1）前序遍历：根左右（2）中序遍历：左根右（3）后序遍历：左右根

确定好根节点的位置，分成左子树和右子树两个区间，依次递归处理！！！

（1）根据前序遍历 + 后序遍历确定一颗二叉树

#include<bits/stdc++.h>

using namespace std;

vector<int> ans;

void deal(int l1, int r1, int l2, int r2, const vector<int>& pre, const vector<int>& suf) {
	
	if(l1 > r1) return;
	if(l1 == r1) {
	 ans.push_back(pre[l1]);
	 return ;	
	}
	
	int x = pre[l1 + 1], pos = -1;
	for(int i = l2; i <= r2; ++ i) 
	  if(suf[i] == x) {
	  	pos = i;
	  	break;
	  }
	
	deal(l1 + 1, l1 + 1 + pos - l2, l2, pos, pre, suf);
	ans.push_back(pre[l1]);
	deal(l1 + 1 + pos - l2 + 1, r1, pos + 1, r2 - 1, pre, suf);
	
}

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int n;
	cin >> n;
	vector<int> pre(n), suf(n);
	
	for(int i = 0; i < n; ++ i) cin >> pre[i];
	for(int i = 0; i < n; ++ i) cin >> suf[i];
	
	deal(0, n - 1, 0, n - 1, pre, suf);
	
	for(int x : ans) cout << x << " ";
	cout << "\n";
	
	return 0;
}

（2）中序 + 后序确定二叉树

#include<bits/stdc++.h>

using namespace std;

void deal(int l1, int r1, int l2, int r2, const string &s1, const string &s2) {
	
	if(l2 > r2 || l1 > r1) return;
	if(l1 == r1) {
		cout << s1[l1];
		return;
	}
	
	int pos = -1;
	char c = s2[r2];
	cout << c;
	for(int i = l1; i <= r1; ++ i)
	  if(c == s1[i]) {
	  	pos = i;
	  	break;
	  }
	
	deal(l1, pos - 1, l2, l2 + pos - 1 - l1, s1, s2);
	deal(pos + 1, r1, l2 + pos - 1 - l1 + 1, r2 - 1, s1, s2);
	
}

int main() {
	
	string s1, s2;
	cin >> s1 >> s2;
	
	int n = s1.size();
	
	deal(0, n - 1, 0, n - 1, s1, s2);
	
	return 0;
}

（3）前序 + 中序确定后序

#include<bits/stdc++.h>

using namespace std;

void deal(int l1, int r1, int l2, int r2, const string &s1, const string &s2) {
	
	if(l2 > r2 || l1 > r1) return;
	if(l1 == r1) {
		cout << s1[l1];
		return;
	}
	
	int pos = -1;
	char c = s1[l1];
	for(int i = l2; i <= r2; ++ i)
	  if(c == s2[i]) {
	  	pos = i;
	  	break;
	  }
	
	deal(l1 + 1, l1 + 1 + pos - 1 - l2, l2, pos - 1, s1, s2);
	deal(l1 + 1 + pos - 1 - l2 + 1, r1, pos + 1, r2, s1, s2);
	cout << c;
}

int main() {
	
	string s1, s2;
	cin >> s1 >> s2;
	
	int n = s1.size();
	
	deal(0, n - 1, 0, n - 1, s1, s2);
	
	return 0;
}

!!!宗旨：先找到根节点，分成左右子树，重复递归！！！

3、FBI 树

于给定的长度为 2 𝑛 2 n ，仅由 "0" "0" 和 "1" "1" 组成的字符串 𝑠 s ，请按下方的规则构造出一棵二叉树 𝑇 T ： ∙ ∙记当前子树 𝑇 𝑖 T i 的根节点为 root 𝑖 root i ； ∙ ∙记当前子树分得的字符串 𝑠 𝑖 s i 的长度大于 1 1 ，则将 𝑠 𝑖 s i 从中间分开，分为等长的左右子串 𝑠 𝑖 ′ s i ′ 和 𝑠 𝑖 ′ ′ s i ′′ ； ∙ ∙由 𝑠 𝑖 ′ s i ′ 递归构造 root 𝑖 root i 的左子树 𝑇 𝑖 ′ T i ′ ，由 𝑠 𝑖 ′ ′ s i ′′ 递归构造 root 𝑖 root i 的右子树 𝑇 𝑖 ′ ′ T i ′′ ；

由于难以将整棵树完整的输出，所以我们定义节点的简称： ∙ ∙若当前节点分得字符串仅 "0" "0" 构成，那么该节点简称 B B 节点； ∙ ∙若当前节点分得字符串仅 "1" "1" 构成，那么该节点简称 I I 节点； ∙ ∙若当前节点分得字符串既包含 "0" "0" 又包含 "1" "1" ，那么该节点简称 F F 节点。

你只需要输出所构造二叉树的后序遍历。每一个节点使用简称表示。

#include<bits/stdc++.h>

using namespace std;

char deal(int l, int r, const string &s) {
	
	if(l == r) {
		if(s[l] == '1')  {
		  cout << 'I';
		  return 'I';
	    }
		else {
			cout << 'B';
			return 'B';
		}
	}
	
	char c1 = deal(l, l + r >> 1, s);
	char c2 = deal((l + r) / 2 + 1, r, s);
	
	if(c1 == c2 && c1 == 'B') {
		cout << 'B';
		return 'B';
	}
	if(c1 == c2 && c2 == 'I') {
		cout << 'I';
		return 'I';
	}
	
	cout << 'F';
	return 'F';
	
}

int main() {
	
	int n;
	cin >> n;
	
	string s;
	cin >> s;
	
	deal(0, (int)s.size() - 1, s);
	cout << "\n";
	
	return 0;
}

4、在一堆点中找出距离最近的两个点

思路：分治

将一堆数据分成两部分，距离的最小值为

（1）左堆内的最小值（2）右堆内的最小值（3）两个交界处的最小值

PS 下面的代码是正常代码的变式，比较特殊，而且初始值不可以超过2e5 + 10，否则会超时

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 1;

struct node{
	int x, y;
	bool st;
};

vector<node> a;

double dis(node t1, node t2) {
	if(t1.st == t2.st) return N;
	int dx = t1.x - t2.x, dy = t1.y - t2.y;
	return sqrt(1LL * dx * dx + 1LL * dy * dy); // 转换成long long， 否组会爆 int 
}

double cdq(int l, int r) {
	
	if(l >= r) return N;
	if(l + 1 == r) return dis(a[l], a[r]);
	int mid = l + r >> 1;
	double ans = min(cdq(l, mid), cdq(mid + 1, r));
   // 两堆的最小值
   // 接下来求相邻两堆之间的距离最小值
	vector<node> tmp;
	for(int i = l; i <= r; ++ i)
	  if(fabs(a[i].x - a[mid].x) <= ans) 
	   tmp.push_back(a[i]);
	
	for(int i = 0; i < tmp.size(); ++ i)
	 for(int j = i + 1; j < tmp.size(); ++ j) {
	 	if(tmp[j].y - tmp[i].y > ans) break; // 减少循环次数，防止超时
	 	if(tmp[j].st == tmp[i].st) continue;
	 	ans = min(ans, dis(tmp[i], tmp[j]));
	 }
	
	return ans;
}

void deal() {
	int n;
    cin >> n;
    a.resize(2 * n);
    for(int i = 0; i < n; ++ i) cin >> a[i].x >> a[i].y, a[i].st = 1;
    for(int i = n; i < 2 * n; ++ i) cin >> a[i].x >> a[i].y, a[i].st = 0;
    
    sort(a.begin(), a.end(), [&](node t1, node t2){
    	if(t1.x == t2.y) return t1.y < t2.y;
    	return t1.x < t2.x;
	});
  // 先按照 x 的大小 排序， 之所在这里给 y 排序，是为了方便，因为在接下来的tmp数组需要对y排序
	double ans = cdq(0, 2 * n - 1);
	printf("%.03lf\n", ans);
}

int main() {
	
	ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int t;
    cin >> t;
    while(t --)
    deal();
    
    return 0;
}

分治 + 递归！！！ 理解 + 运用

核心思想：

一、经典例题

分治 + 递归！！！理解 + 运用