13. 分治

分治，字⾯上的解释是「分⽽治之」，就是把⼀个复杂的问题分成两个或更多的相同的⼦问题，直到 最后⼦问题可以简单的直接求解，原问题的解即⼦问题的解的合并。

1.P1908 逆序对 - 洛谷

 

#include<iostream>using namespace std;typedef long long LL;
LL ret;const int N = 5e5 + 10;
int n;
int a[N];
int tmp[N];LL merge(int left, int right)
{//分到最后不能再继续分了if (left >= right)return 0;LL ret = 0;int mid = (left + right) / 2;ret += merge(left, mid);ret += merge(mid + 1, right);int cur1 = left, cur2 = mid + 1, i = left;while (cur1 <= mid && cur2 <= right){if (a[cur1] <= a[cur2]){tmp[i++] = a[cur1++];}else{tmp[i++] = a[cur2++];ret += mid - cur1 + 1;}}while (cur1 <= mid)tmp[i++] = a[cur1++];while (cur2 <= right)tmp[i++] = a[cur2++];for (int i = left; i <= right; i++){a[i] = tmp[i];}return ret;
}int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}ret = merge(1, n);cout << ret << endl;
}

2.P1923 【深基9.例4】求第 k 小的数 - 洛谷

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<ctime>
using namespace std;int n,k;
const int N = 5e6 + 10;
int a[N];int get_random(int l, int r)
{return a[rand() % (r - l + 1) + l];
}int quick_sort(int left, int right, int k)
{//if (left == right)return a[left];int p = get_random(left,right);int l = left - 1, r = right + 1, i = left;while (i < r){if (a[i] < p){swap(a[++l], a[i++]);}else if (a[i] == p){i++;}else{swap(a[--r], a[i]);}}//这个时候就区分成3个区域//l - left + 1,r - l - 1;right - r +1int a1 = l - left + 1, b1 = r - l - 1, c1 = right - r + 1;if (k <= a1)return quick_sort(left, l, k);//记得写上返回else if (k <= a1 + b1){return  p;}else{return	quick_sort(r, right, k - a1 - b1);//记得写上返回}
}int main()
{srand(time(0));scanf("%d", &n);scanf("%d", &k);k++;//由于题意，这里的k要++for (int i = 1; i <= n; i++){scanf("%d", &a[i]);}printf("%d", quick_sort(1, n, k));
}

 3.P1115 最大子段和 - 洛谷

 

#include<iostream>using namespace std;typedef long long LL;
int n;
const int N = 2e5 + 10;
int a[N];LL dfs(int left,int right)
{if (left == right)return a[left];LL ret;int mid = (left + right) / 2;ret = max(dfs(left, mid), dfs(mid + 1, right));LL lmax = a[mid], lsum = a[mid];for (int i = mid - 1; i >= left; i--){lsum += a[i];lmax = max(lmax, lsum);}LL rmax = a[mid + 1], rsum = a[mid + 1];for (int i = mid + 2; i <= right; i++){rsum += a[i];rmax = max(rsum, rmax);}return max(lmax + rmax, ret);
}int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}cout<<dfs(1,n);return 0;
}

4.P1228 地毯填补问题 - 洛谷

 

 

#include<iostream>using namespace std;int k,x,y;void dfs(int a, int b, int len, int x, int y)
{if (len == 1)return;//除去的条件len = len / 2;//左上角if (x < a + len && y < b + len){//出对角，cout << a + len << " " << b + len << " " << 1 << endl;dfs(a, b, len, x, y);//光处理其他三个角了，忘记处理所属区域的角了dfs(a, b + len, len, a + len - 1, b + len);dfs(a + len, b, len, a + len, b + len - 1);dfs(a + len, b + len, len, a + len, b + len);}else if (x >= a + len && y >= b + len){cout << a + len - 1 << " " << b + len - 1 << " " << 4 << endl;dfs(a + len, b + len, len, x, y);dfs(a, b, len, a + len - 1, b + len - 1);dfs(a, b + len, len, a + len - 1, b + len);dfs(a + len, b, len, a + len, b + len - 1);}else if (x >= a + len){cout << a + len - 1 << " " << b + len << " " << 3 << endl;dfs(a + len, b, len, x, y);dfs(a, b, len, a + len - 1, b + len - 1);dfs(a, b + len, len, a + len - 1, b + len);dfs(a + len, b + len, len, a + len, b + len);}else{cout << a + len << " " << b + len - 1 << " " << 2 << endl;dfs(a, b + len, len, x, y);dfs(a, b, len, a + len - 1, b + len - 1);dfs(a + len, b, len,a + len, b + len - 1);dfs(a + len, b + len, len, a + len, b + len);}
}int main()
{cin >> k >> x >> y;k = (1 << k);dfs(1, 1, k, x, y);
}