acwing算法基础第一章

知识点概要：

快排，归并，二分，高精度，前缀和与差分，双指针，位运算，离散化，区间合并

模版总结

快速排序

快排模版：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int q[N];

void quicksort(int q[], int l, int r) {
	if (l >= r) return;
	int i = l - 1, j = r + 1;//注意i和j初始化有偏移量
	int x = q[(l + r) >> 1];
/*分区*/
	while (i < j) {
		do i++; while (q[i] < x);
		do j--; while (q[j] > x);
		if (i < j) swap(q[i], q[j]);//不要忘记i<j的限制条件
	}
/*递归*/
	quicksort(q, l, j);
	quicksort(q, j + 1, r);
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> q[i];

	quicksort(q, 0, n - 1);

	for (int i = 0; i < n; i++) cout << q[i] << " ";
	cout << endl;

	return 0;
}

第k个数
思路：先取中点作为分区标准，然后比较k与j-l+1
-if k < j - i + 1 则return quicksort(q, l, j, k);
-else return quicksort(q, j + 1, r, k - j + l - 1);

归并排序

归并排序模板

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N], tmp[N];

void merge_sort(int q[], int l, int r) {
if (l >= r) return;

int mid = l + r >> 1;
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
    if (q[i] <= q[j]) tmp[k++] = q[i++];
    else tmp[k++] = q[j++];
}

while (i <= mid) tmp[k++] = q[i++];
while (j <= r) tmp[k++] = q[j++];

for (int i = l, j = 0; i <= r; i++, j++) {
    q[i] = tmp[j];
}
}

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
scanf(“%d”, &a[i]);
}

merge_sort(a, 0, n - 1);

for (int i = 0; i < n; i++) {
    printf("%d ", a[i]);
}
return 0;
}

*逆序对的数量
思路：
-res = mergesort(q, l, mid) + mergesort(q, mid + 1, r);

• 合并 if q[i] <= q[j] 正常放入tmp数组
else res += mid - i + 1, 并放入tmp数组

二分

整数二分模板

#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> q[i];

	while (m--) {
		int k;
		cin >> k;
		int l = 0, r = n - 1;
        /*
        若l = mid 则 mid = l + r + 1 >> 1;
        若r = mid 则 mid = l + r >> 1;
        */
		while (l < r) {
			int mid = l + r >> 1;
			if (q[mid] >= k) r = mid;
			else l = mid + 1;
		}
        //左边界为>=k 的下界(即 <k 和 >= k 的分界线)
		if (q[l] != k) cout << "-1 -1" << endl;
		else {
			cout << l << " ";
			l = 0, r = n - 1;
			while (l < r) {
				int mid = l + r + 1 >> 1;
				if (q[mid] <= k) l = mid;
				else r = mid - 1;
			}
        //右边界为>=k 的上界(即 >= k 和 > k 的分界线)
			cout << l << endl;
		}
	}

	return 0;
}

实数/小数二分
思路：不需要区分是否加一，但注意当结果有正有负是，上下界分别为+-limit

高精度

加法模板

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> add(vector<int>a, vector<int> b) {
	int la = a.size(), lb = b.size();
	vector<int> res;
	int t = 0;//用t来储存进位
	for (int i = 0; i < max(la, lb); i++) {
		if (i < la) t += a[i];
		if (i < lb) t += b[i];
		res.push_back(t % 10);
		t /= 10;
	}
	if (t) res.push_back(t);//注意检查最后一位

	return res;
}

int main() {
	string A, B;
	vector<int>a, b;
	cin >> A >> B;
	for (int i = A.size() - 1; i >= 0; i--) a.push_back(A[i] - '0');
	for (int j = B.size() - 1; j >= 0; j--) b.push_back(B[j] - '0');

	vector<int> res = add(a, b);
	for (int i = res.size() - 1; i >= 0; i--) cout << res[i];
	cout << endl;

	return 0;
}

减法

#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool cmp(vector<int>& a, vector<int>& b) {
	if (a.size() != b.size()) return a.size() > b.size();
	for (int i = a.size() - 1; i >= 0; i--) {
		if (a[i] != b[i]) return a[i] > b[i];
	}
	return true;
}

vector<int> sub(vector<int> a, vector<int> b) {
	vector<int> c;
	for (int i = 0, t = 0; i < a.size(); i++) {
		t = a[i] - t; //用t为1还是0表示是否借位(背熟这句话)
		if (i < b.size()) t -= b[i];
		c.push_back((t + 10) % 10);
		if (t < 0) t = 1;
		else t = 0;
	}

	while (c.size() > 1 && c.back() == 0) c.pop_back(); //去除前导零
	return c;
}

int main() {
	string A, B;
	vector<int> a, b;
	cin >> A >> B;
	for (int i = A.size() - 1; i >= 0; i--) a.push_back(A[i] - '0');
	for (int j = B.size() - 1; j >= 0; j--) b.push_back(B[j] - '0');

	vector<int> c;
	if (cmp(a, b)) c = sub(a, b);
	else c = sub(b, a), cout << "-";
	for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
	cout << endl;

	return 0;
}

乘法

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> mul(vector<int> a, int b) {
	vector<int> c;
    //用t表示进位， || t 起到最终进位的作用，但要判断a是否越界
	for (int i = 0, t = 0; i < a.size() || t; i++) {
		if (i < a.size()) t += a[i] * b;
		c.push_back(t % 10);
		t /= 10;
	}
	while (c.size() > 1 && c.back() == 0) c.pop_back();
	return c;
}

int main() {
	string A;
	int b;
	vector<int> a, c;

	cin >> A >> b;
	for (int i = A.size() - 1; i >= 0; i--) a.push_back(A[i] - '0');

	c = mul(a, b);

	for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
	cout << endl;

	return 0;
}

除法

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

vector<int> div(vector<int> a, int b, int& v) {
    // v储存余数(一定要记得传引用，否则无法修改v值)
	vector<int> c;
	v = 0;
	for (int i = a.size() - 1; i >= 0; i--) {
		v = v * 10 + a[i];
		c.push_back(v / b);
		v %= b;
	}
	reverse(c.begin(), c.end()); // 不要忘了倒序
	while (c.size() > 1 && c.back() == 0) c.pop_back(); // 去除前导零
	return c;
}

int main() {
	string A;
	int b, v;
	vector<int> a, c;

	cin >> A >> b;
	for (int i = A.size() - 1; i >= 0; i--) a.push_back(A[i] - '0');

	c = div(a, b, v);
	for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
	cout << endl;
	cout << v << endl;

	return 0;
}

小贴士 输出都是倒序输出，除法在函数内部倒序过一次，但打印时仍要倒序输出

前缀和

前缀和与查分的区别：

• 前缀和： s = a[r] - a[l - 1];
• 差分： b[l] += c, b[r + 1] -= c;

1. 前缀和
   一维模版

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int a[N];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 2; i <= n; i++) a[i] += a[i - 1];

	while (m--) {
		int l, r;
		cin >> l >> r;
		cout << a[r] - a[l - 1] << endl;
	}

	return 0;
}

矩阵模版（二维）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m, q;
int s[N][N];

int main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> s[i][j];
		}
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; //类似容斥原理

	while (q--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << s[x2][y2] - s[x2][y1 - 1] - 
			s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl;
		//注意中间两部分各是一个大坐标，一个“小坐标减一”
	}

	return 0;
}

2. 差分
   一维差分

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];

//插入函数，为原数列差分后的结果，直接求和为原数列，可通过 "b[l] += c, b[r + 1] -= c" 的方式快速修改一段元素的值
void insert(int l, int r, int c) {
	b[l] += c, b[r + 1] -= c;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	// 初始化差分数组
	for (int i = 1; i <= n; i++) insert(i, i, a[i]);

	while (m--) {
		int l, r, c;
		cin >> l >> r >> c;
		// 修改差分数组
		insert(l, r, c);
	}
    
	// 通过求和复原
	for (int i = 1; i <= n; i++) b[i] += b[i - 1];

	for (int i = 1; i <= n; i++) cout << b[i] << " ";
	cout << endl;

	return 0;
}

二维差分

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

///插入函数，记住这个修改方式(加减减加)
void insert(int x1, int y1, int x2, int y2, int c) {
	b[x1][y1] += c, b[x1][y2 + 1] -= c,
		b[x2 + 1][y1] -= c, b[x2 + 1][y2 + 1] += c;
}

int main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			insert(i, j, i, j, a[i][j]);
		}
	}

	while (q--) {
		int x1, x2, y1, y2, c;
		cin >> x1 >> y1 >> x2 >> y2 >> c;
		insert(x1, y1, x2, y2, c);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			// 复原过程与插入（差分）相反，也是类似于容斥原理
			b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << b[i][j] << " ";
		}
		cout << endl;
	}

	return 0;
}

双指针

1. 指向两个序列
   基本格式

for(int i = 0, j = 0; i < n; i ++){
    while(j < i && check(i , j)) j ++;
}

最长连续不重复子序列

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int s[N], q[N];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> q[i];

	int res = 0;
	for (int i = 0, j = 0; i < n; i++) {
		s[q[i]]++;
		while (j < i && s[q[i]]>1) s[q[j++]]--;
		res = max(res, i - j + 1);
	}

	cout << res << endl;

	return 0;
}

判断子序列
思路： 用while循环，当a与b匹配时，i++；不论该轮结果如何，j ++。
若i == n (注意，是次数n,不是下标 n - 1) 则说明a为b子串，匹配成功

2.两头夹逼
数组元素的目标和
思路： a数组从头开始，b数组从尾开始。 若和大于x, 则 j --，若j < 0，说明x过小，无解；否则输出答案。

位运算

思路： x -= x & (~x + 1); 用来返回最后一位1
e.g. 1010 -> 10 .

离散化

注意这里用的是 1 ~ n 作为新坐标系，故find 返回的是 r + 1而非 r。
区间和

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;
int a[N], s[N];
// alls储存所有位置下标，包括add中的x 和 query 中的 l, r
vector<int> alls;
// add 的 PII 分别存 位置 和 值， query 的 PII 分别存左右界(注意这种用vector<pair>存数据的方法)
vector<PII> add, query;

// 返回 1-indexed 的 原位置映射到 1 ~ n 的新坐标(利用二分查找)  
int find(int x) {
	int l = 0, r = alls.size() - 1;
	while (l < r) {
		int mid = l + r >> 1;
		if (alls[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return r + 1;
}

int main() {
	cin >> n >> m;
	while (n--) {
		int x, c;
		cin >> x >> c;
		alls.push_back(x);
		add.push_back({ x,c });
	}

	while (m--) {
		int l, r;
		cin >> l >> r;
		alls.push_back(l), alls.push_back(r);
		query.push_back({ l,r });
	}
    
	// 通过sort和去重建立新坐标系，为映射和二分查找做预备
	sort(alls.begin(), alls.end());
	alls.erase(unique(alls.begin(), alls.end()), alls.end());

	for (auto item : add) {
		int x = find(item.first), c = item.second;
		a[x] += c;
	}

	for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];

	for (auto item : query) {
		int l = find(item.first), r = find(item.second);
		cout << s[r] - s[l - 1] << endl;
	}

	return 0;
}

区间合并

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

int n;
// 用vector<PII> 储存区间
vector<PII> regs;

// merge函数
void merge(vector<PII> &regs) {
	vector<PII> res;
	int st = -2e9, ed = -2e9;
	for (auto reg : regs) {
		// 发现新区间(与原区间无交集)
		if (ed < reg.first) {
			//用 st 判断上一个区间是否存在
			if (st != -2e9) res.push_back({ st,ed });
			st = reg.first, ed = reg.second;
		}
		// 有交集，更新ed
		else ed = max(ed, reg.second);
	}
	//将最后一个区间(如果有的话，这个用st判断)放入区间数组
	if (st != -2e9) res.push_back({ st,ed });

	regs = res;
}

int main() {
	cin >> n;
	while (n--) {
		int l, r;
		cin >> l >> r;
		regs.push_back({ l,r });
	}

	sort(regs.begin(), regs.end());

	merge(regs);

	cout << regs.size() << endl;

	return 0;
}