算法笔记

常用STL库

我的算法笔记，首先记录了STL中一些常用的库函数以及STL中实现的各种数据结构的基本用法，其次是动态规划、贪心算法等若干个专题的算法题目链接及相应题解。

知识点总结

1.vector

//变长数组
#include <vector>   
vector<int> v, b;//定义vector类型
vector<int> vec(100);//定义时指定长度100, 默认值为0, 这个长度可以是变量
int num = 12;
v.push_back(num);//推入一个新的值到数组最后,这个值可以为任何类型
v.pop_back();//删除数组最后的那个值
v.front();//数组开头的值
v.back();//数组结尾的值
v = b;//数组拷贝
v == b;//数组是否相同
v[i];//数组中第i个值, 范围：0 到 v.size()-1
v.size();//容器内的元素个数
v.empty();//容器是否为空
// 除了queue和stack外通用的方法
v.clear();//清空容器内的所有元素
v.begin();//容器的一个元素的迭代器
v.end();//容器尾后迭代器

vector<int>::iterator it;//定义迭代器
iter = v.begin();//数组头“指针”
iter = v.end();//数组尾“指针”

vector<int>::iterator it = v.begin()+10; 
v.erase(it);//删除指定位置的元素

v.erase(iterator first,iterator last);//删除向量中 [first,last) 中元素
v.erase( remove(v.begin(), v.end(),x), v.end());//删除v中所有值为x的元素 对于string类型也适用

//v的开始指针指向的是第一个元素，所以指针移动两位，指向第三个元素（下标为2）
//然后在这个元素的前面，注意是前面,插入一个元素。
v.insert(v.begin()+2, 30);

2.list

//双链表
#include <list>
list<int> l;
l.push_front(1);//插入元素到开头
l.pop_front();//从开头删掉元素
l.erase(l.begin());//删除指定迭代器处的元素
l.insert(l.begin(), 1);//在指定迭代器前插入元素
l.reverse();//反转整个链表

3.string

//字符串类
#include <string>
string s1,s2;
s1 += s2;
s1.append(s2);//拼接
char c = 'm';
s1.push_back(c);
s1 > s2;
s1 == s2;
s1 < s2;//按字典序比较字符串
s1.size();//字符串长度
string s3 = s2;//字符串赋值

4.queue

//队列
#include <queue>
queue<int> q;
q.push(1);//将1推入队列
q.pop();//推出队列开头的元素
q.front();//队列的第一个元素
q.clear();//清空队列   
q.empty();//队列判空
q.size();//队列长度

5.stack

//栈
#include <stack>
stack<int> s;
s.push(1);//将1推入堆栈
s.pop();//推出堆栈最后的元素
s.top();//堆栈的最后的元素
s.size();//栈的当前长度
s.empty();//判断栈空

6.pair

#include <map>
pair<int, string> p;
p.first = 1;
p.second = "abc";
p = make_pair(1, "abc");
p = {1, "abc"};

pair<int, string> p[100];
sort(p, p + 100);
// 默认优先first从小到大
// 如果first相同则second从小到大

//pair和其他容器嵌套
vector<pair<int, string> > vp;
queue<pair<float, int> > qp;
queue<pair<pair<int, int>, int> > qpp;

7.set

//set保存了不可重复的元素–二叉搜索树-红黑树
//可以用来去重
#include <set>
set<int> s;
s.insert(1);//插入到集合中,重复的话就会插入失败
s.erase(1);//从集合中删除
s.erase(s.begin());//从集合中删除
s.count(1);//返回某个元素的个数
s.find(1);//返回一个指向被查找到元素的迭代器
s.empty();//集合判空
s.size();//集合的元素个数

set<int>::iterator it;//定义前向迭代器  
//中序遍历集合中的所有元素  
for(it = s.begin(); it != s.end(); it++)  
{  
	cout << *it << " ";  
}  

//由于set是红黑树，所以满足以下内容
//1 内部有序(默认从小到大)
//2 没有重复值，如果出现重复值会不断被覆盖
//3 几乎所有操作复杂度均为 O(logN)
//4 不可以修改节点上的值
//5 修改操作只能进行插入和删除两个操作

8.map

//map字典（键对集合）——二叉搜索树——红黑树
#include <map>
map<char, int> m;
m.insert(make_pair('a', 1));//加入字典
m.insert({'a', 1});//加入字典
m.erase('a');//从字典中删除
m.count('a');//字典中是否存在
m.find('a');//返回对应值的迭代器（若无则返回尾后迭代器）

//通常称map的first元素为key，second元素为value
//由于map是键对红黑树，所以满足以下内容
//1 set的大部分性质；
//2 key不能重复，不能修改，只能删除和添加；
//3 允许value重复，可以对value进行修改；
//4 map是按照key进行排序的；
//5 key和value一定是成对出现的；
//6 map的迭代器指向的内容是一个pair；

9.priority_queue

//优先队列——堆
#include <queue>
priority_queue<int> prq;
prq.top();//堆顶上的元素
prq.pop();//弹出堆顶上的元素
prq.push(1);//推入堆

//priority_queue默认为最大堆，即堆顶的元素最大
//和queue一样，priority_queue不允许访问除了堆顶元素以外的任何一个元素。
//priority_queue的插入和弹出操作的复杂度均为O(logN)
//priority_queue的复杂度为最差情况下的复杂度，而set和map的复杂度均为稳定复杂度的极限值

小根堆排序：

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n;
int main()
{
	scanf("%d",&n);
	for(int i = 0;i < n; ++i) scanf("%d",&a[i]);
	priority_queue<int,vector<int>,greater<int> > pql(a, a + n);
	while(!pql.empty())
	{
		printf("%d ",pql.top());
		pql.pop();
	}
	return 0;
}

10.algorithm

//STL里的算法库
#include <algorithm>
//1 排序函数
sort(a, a + n);
sort(v.begin(),v.end());//默认从小到大排序
sort(a, a + n, less<T>());//从小到大排序
sort(a, a + n, greater<T>());//从大到小排序
bool compare(T& t1, T& t2)
{
	if (t1.a != t2.a)
		return t1.a > t2.a;
	else if (t1.b != t2.b)
		return t1.b > t2.b;
	else
		return t1.c < t2.c;
}
sort(a, a + n, compare);//自定义排序规则
//先按a值降序排列；
//如果a值相同，再按b值降序排列；
//如果a和b都相同，就按c值升序排列；

//对向量ret进行去重，需要先排序
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());//unique函数是algorithm里面的

//二分 lower_bound和upper_bound
int l = lower_bound(v.begin(), v.end(), k) - v.begin();
int r = upper_bound(v.begin(), v.end(), k) - v.begin();
//返回第一个大于等于x的地址，减去数组q就得到索引,没有的话就返回q + R + 1
int pos_1 = lower_bound(q + L, q + R + 1, x) - q;
//返回第一个大于x的地址，减去数组q就得到索引,没有的话就返回q + R + 1
int pos_2 = upper_bound(q + L, q + R + 1, x) - q;  

11.unordered_map

#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
	unordered_map<string, int> umap;//创建一个key为string类型，value为int类型的unordered_map
	string key = "one";
	int value = 1;
	umap.emplace(key, value);//使用变量方式，插入一个元素
	umap.emplace("two", 2);  //也可以直接写上key和value的值
	umap.insert({"three", 3});
	cout << "If key is one, then value is " << umap["one"] << endl << endl; //通过key值来访问value
	for(auto x : umap)//遍历整个map，输出key及其对应的value值
	{
		cout << x.first << "  " << x.second << endl;
	}
	cout << endl;
	for(unordered_map<string, int>::iterator it = umap.begin(); it != umap.end(); ++it)
	{
		cout << it->first << " " << it->second << endl;
	}
	cout << endl;
	for(auto x : umap)//遍历整个map，并根据其key值，查看对应的value值
	{
		cout << umap[x.first] << endl;
	}
	cout << endl;
	auto n = umap.erase("one");//删除
	if(n != 0) cout << "delete one successfully!" << endl;
	else cout << "failure" << endl;
	auto it = umap.find("two");//修改
	if(it != umap.end()) it->second = 222;
	string tmp = "two";
	if(umap.find(tmp) != umap.end()) cout << "find " << tmp << " successfully!" << endl;
    umap.clear();
    cout << "After clear umap, the size of umap is " << umap.size() << endl;
    if(umap.empty()) cout << "It's empty!" << endl;
	return 0;
}

map: map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了map的效率。
unordered_map: unordered_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的

12.cstring库

#include <cstring>
strlen();//字符串长度
strcmp(s1,s2);//值为0，则s1==s2  小于0则s1<s2  大于0则s1>s2
strcpy(s1,s2);//把s2的内容复制到s1
memset(str,0,sizeof(str));//暴力清空任意类型数组（清空为0）  
memcpy();//暴力拷贝

#include <cstdlib>
qsort();//C语言快排
rand();//随机数
malloc();//C语言动态分配内存  
free();
    
#include <ctime>
time(0);//从1970年到现在的秒数（配合随机数）
clock();//程序启动到目前为止的毫秒数

#include <ctype>
isdigit();//判断字符是否为数字
isalpha();//判断字符是否为大小写字母

14.类型转换

//数字 转 字符串类型
//1 利用to_string函数
string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val);

//2 利用stringstream 头文件
#include <stringstream>
stringstream tool;
string s;
int a = 123554;
tool << a;
tool >> s;
cout << s << endl;//转换完就可以用了 

//字符串类型转数字
#include <cstdlib>
string str='111';
int number = atoi(str.c_str());

算法基础课题解

第一讲 基础算法

1.快速排序

原题链接：https://www.acwing.com/problem/content/787/

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1000010;
int q[N];
void quick_sort(int* q, int l, int r)
{
	if (l >= r) return;
	int x = q[l + (r - l) / 2], i = l - 1, j = r + 1;
	while (i < j)
	{
		while (q[++i] < x); //do i++; while (q[i] < x);
		while (q[--j] > x); //do j--; while (q[j] > x);
		if (i < j) swap(q[i], q[j]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}

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

2.第k个数

原题链接：https://www.acwing.com/problem/content/788/

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1000010;
int q[N];
int n,k;
int quick_sort(int* q,int l,int r,int k)
{
	if(l >= r) return q[l];
	int x = q[l + (r - l) / 2], i = l - 1,j = 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]);
	}
	int sl = j - l + 1;
	if(k <= sl) return quick_sort(q, l, j, k);
	else return quick_sort(q,j + 1, r, k - sl);
}
int main()
{
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; ++i) scanf("%d", &q[i]);
	cout<<quick_sort(q, 0, n - 1, k);
	return 0;
}

3.归并排序

原题链接：https://www.acwing.com/problem/content/789/

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6+10;
int q[N],temp[N];
int n;
void merge_sort(int* q, int l, int r)
{
	if(l >= r) return;
	int mid = l + (r - l) / 2;
	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);
	int k = 0,i = l,j = mid + 1;
	while(i <= mid && j <= r)
	{
		if(q[i] <= q[j]) temp[k++] = q[i++];
		else temp[k++] = q[j++];
	}
	while(i <= mid) temp[k++] = q[i++];
	while(j <= r) temp[k++] = q[j++];
	for(i = l,j = 0; i <= r; i++,j++) q[i] = temp[j];
}
int main()
{
	scanf("%d",&n);
	for(int i = 0; i < n; i++) scanf("%d", &q[i]);
	merge_sort(q, 0, n - 1);
	for(int i = 0; i < n; i++) printf("%d ", q[i]);
	return 0;
}

4.逆序对的数量

原题链接：https://www.acwing.com/problem/content/790/

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 100010;
int q[N], temp[N];
int n;
long long merge_sort(int l,int r)
{
	if(l >= r) return 0;
	int mid = l + (r - l) / 2; //int mid = l + r >> 1;
	LL res = merge_sort(l,mid) + merge_sort(mid+1,r);
	int k = 0,i = l,j = mid + 1;
	while(i <= mid && j <= r)
	{
		if(q[i] <= q[j]) temp[k++] = q[i++];
		else
		{
			temp[k++] = q[j++];
			res += (mid - i + 1);
		}
	}
	while(i <= mid) temp[k++] = q[i++];
	while(j <= r) temp[k++] = q[j++];
	for(i = l,j = 0; i <= r; i++,j++) q[i] = temp[j];
	return res;

}
int main()
{
	cin>>n;
	for(int i = 0; i < n; i++) cin>>q[i];
	cout<<merge_sort(0,n-1)<<endl;
	return 0;
}

5.数的范围

原题链接：https://www.acwing.com/problem/content/791/

#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int q[N];
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0;i < n; i++) scanf("%d", &q[i]);
    while(m--)
    {
        int x;
        scanf("%d", &x);
        int l = 0,r = n - 1;
        while(l < r)
        {
            int mid = (l + r) / 2;
            if(q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if(q[l] != x) cout << "-1 -1" << endl;
        else
        {
            cout << l << " ";
            int l = 0,r = n - 1;
            while(l < r)
            {
                int mid = (l + r + 1) / 2;
                if(q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
}

6.数的三次方根

原题链接：https://www.acwing.com/problem/content/792/

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    double x = 0;
    scanf("%lf", &x);
    double l = -10000,r = 10000;
    while(r-l > 1e-8)
    {
        double mid = (l + r) / 2;
        if(mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf\n", l);
    return 0;
}

7.高精度加法

原题链接：https://www.acwing.com/problem/content/793/

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;
vector<int> Add(vector<int>& A, vector<int>& B)
{
	vector<int> C;
	int t = 0;
	for (int i = 0; i < A.size() || i < B.size(); i++)
	{
		if (i < A.size()) t += A[i];
		if (i < B.size()) t += B[i];
		C.push_back(t % 10);
		t /= 10;
	}
	if (t) C.push_back(1);
	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 i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
	vector<int> C = Add(A, B);
	for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
	return 0;
}

8.高精度减法

原题链接：https://www.acwing.com/activity/content/problem/content/826/

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
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;
		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 i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
	if (cmp(A, B))
	{
		vector<int> C = Sub(A, B);
		for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
	}
	else
	{
		printf("-");
		vector<int> C = Sub(B, A);
		for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
	}
	return 0;
}

9.高精度乘法

原题链接：https://www.acwing.com/problem/content/795/

#include <iostream>
#include <vector>
using namespace std;
vector<int> Mul(vector<int>& A, vector<int>& B)
{
	vector<int> C(A.size() + B.size(), 0); // 初始化为0,且999*99最多5位
	for (int i = 0; i < A.size(); i++)
	{
		for (int j = 0; j < B.size(); j++)
		{
			C[i + j] += A[i] * B[j];
		}
	}
	int t = 0;
	for (int i = 0; i < C.size(); i++)   // i = C.size() - 1时 t 一定小于 10
	{
		t += C[i];
		C[i] = t % 10;
		t /= 10;
	}
	while (C.size() > 1 && C.back() == 0) C.pop_back(); // 必须要去前导 0，因为最高位很可能是 0
	return C;
}
int main()
{
	string a, b;
	cin >> a >> b;
	vector<int> A, B;
	for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
	for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
	vector<int> C = Mul(A, B);
	for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
	return 0;
}

10.高精度除法

原题链接：https://www.acwing.com/problem/content/796/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//int r = 0;
vector<int> Div(vector<int>& A, int B, int& r) //r传入r的地址，便于直接对余数r进行修改
{
	vector<int> C;
	for (int i = 0; i < A.size(); i++) //对A从最高位开始处理
	{
		r = r * 10 + A[i]; //将上次的余数*10在加上当前位的数字，便是该位需要除的被除数
		C.push_back(r / B); //所得即为商在这一位的数字
		r = r % B;
	}
	//由于在除法运算中，高位到低位运算，因此C的前导零都在vector的前面而不是尾部，
    //vector只有删除最后一个数字pop_back是常数复杂度，
    //而对于删除第一位没有相应的库函数可以使用，而且删除第一位，其余位也要前移，
	//因此我们将C翻转，这样0就位于数组尾部，可以使用pop函数删除前导0
	reverse(C.begin(), C.end());
	while (C.size() > 1 && C.back() == 0) C.pop_back();
	return C;
}
int main()
{
	string a;
	int B, r = 0; //代表余数
	cin >> a >> B;
	vector<int> A;
	for (int i = 0; i < a.size(); i++) A.push_back(a[i] - '0'); 
    //注意这次的A是由高为传输至低位，由于在除法的手算过程中，发现从高位进行处理
	auto C = Div(A, B, r);
	for (int i = C.size() - 1; i >= 0; i--) cout << C[i]; //将C从最高位传给最低位
	cout << endl << r << endl; //输出余数
	return 0;
}

11.前缀和

原题链接：https://www.acwing.com/problem/content/797/

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
int a[N], s[N];
int n, m;
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
	while (m--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d\n", s[r] - s[l - 1]);
	}
	return 0;
}

12.子矩阵的和

原题链接：https://www.acwing.com/problem/content/798/

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1010;
int a[N][N], s[N][N];
int n, m, q;
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    //初始化前缀和数组
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }

    while (q--)
    {
        int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}

13.差分

原题链接：https://www.acwing.com/problem/content/799/

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N];
int n, m;
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];
        b[i] = a[i] - a[i - 1];  //构建差分数组 等价于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++) a[i] = a[i - 1] + b[i]; //求前缀和
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    return 0;
}

14.差分矩阵

原题链接：https://www.acwing.com/problem/content/800/

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1010;
int a[N][N], b[N][N];
int n, m, q;
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()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &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, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &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++)
        {
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j]; //求二维前缀和
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

15.最长连续不重复子序列

原题链接：https://www.acwing.com/problem/content/801/

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
int a[N], s[N];
int main()
{
    int n = 0;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int res = 0;
    for (int i = 0, j = 0; i < n; i++)
    {
        s[a[i]]++;
        while (s[a[i]] > 1)
        {
            s[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}

16.数组元素的目标和

原题链接：https://www.acwing.com/problem/content/802/

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int main()
{
    int n = 0, m = 0, x = 0;
    scanf("%d%d%d", &n, &m, &x);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);
    for (int i = 0, j = m - 1; i < n; i++)
    {
        while (j >= 0 && a[i] + b[j] > x) j--;
        if (a[i] + b[j] == x)
        {
            printf("%d %d\n", i, j);
            break;
        }

    }
    return 0;
}

17.判断子序列

原题链接：https://www.acwing.com/problem/content/2818/

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int a[N], b[N];
int main()
{
    int n = 0, m = 0;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);
    int i = 0;
    for (int j = 0; j < m; j++)
    {
        if (i < n && a[i] == b[j]) i++;
    }
    if (i == n) printf("Yes\n");
    else printf("No\n");
    return 0;
}

18.二进制中1的个数

原题链接：https://www.acwing.com/problem/content/803/

#include <iostream>
#include <cmath>
using namespace std;
int lowbit(int x)
{
	return x & -x;
}
int main()
{
	int n = 0;
	cin >> n;
	while (n--)
	{
		int x = 0;
		cin >> x;
		int res = 0;
		while (x)
		{
			x -= lowbit(x);
			res++;
		}
		cout << res << " ";
	}
	return 0;
}

19.区间和

原题链接：https://www.acwing.com/problem/content/804/

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 300010;
typedef pair<int, int> PII;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;
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 l + 1;     //前缀和从1开始，因此这里返回下标也从1开始吧
}
int main()
{
	int n, m;
	cin >> n >> m;
	while (n--)
	{
		int b, c;
		scanf("%d%d", &b, &c);
		add.push_back({ b, c });
		alls.push_back(b);
	}
	while (m--)
	{
		int l, r;
		scanf("%d%d", &l, &r);

		query.push_back({ l, r });

		alls.push_back(l);
		alls.push_back(r);
	}

	sort(alls.begin(), alls.end());  //排序
	alls.erase(unique(alls.begin(), alls.end()), alls.end());  //去重
	//处理插入
	for (auto item : add)
	{
		int i = find(item.first);
		a[i] += item.second;
	}
	//预处理前缀和
	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);
		printf("%d\n", s[r] - s[l - 1]);
	}
	return 0;
}

20.区间合并

原题链接：https://www.acwing.com/problem/content/805/

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> merge(vector<pair<int, int>>& vec)
{
	if (vec.size() == 0) return {};
	vector<pair<int, int>> ans;
	sort(vec.begin(), vec.end());
	pair<int, int> temp = vec[0];
	for (int i = 1; i < vec.size(); i++)
	{
		if (temp.second < vec[i].first)
		{
			ans.push_back(temp);
			temp = vec[i];
		}
		else if (temp.second < vec[i].second)
		{
			temp.second = vec[i].second;
		}
	}
	ans.push_back(temp);
	return ans;
}
int main()
{
	int n = 0, l = 0, r = 0;
	cin >> n;
	vector<pair<int, int>> vec;
	for (int i = 0; i < n; i++)
	{
		cin >> l >> r;
		vec.push_back({ l,r });
	}
	vector<pair<int, int>> ans = merge(vec);
	cout << ans.size() << endl;
	return 0;
}

第二讲 数据结构

1.单链表

原题链接：https://www.acwing.com/problem/content/828/

#include <iostream>
using namespace std;
const int N = 100010;
int head, e[N], ne[N], idx;
void init()
{
	head = -1;
	idx = 0;
}
//将x插到头节点
void add_to_head(int x)
{
	e[idx] = x;
	ne[idx] = head;
	head = idx++;
}
//将x插到下标是k的点后面
void add(int k, int x)
{
	e[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx++;
}
//将下标是k的点的后面的点删掉
void remove(int k)
{
	ne[k] = ne[ne[k]];
}
int main()
{
	int m = 0;
	cin >> m;
	init();
	while (m--)
	{
		int k, x;
		char op;
		cin >> op;
		if (op == 'H')
		{
			cin >> x;
			add_to_head(x);
		}
		else if (op == 'D')
		{
			cin >> k;
			if (!k) head = ne[head];
			remove(k - 1);
		}
		else
		{
			cin >> k >> x;
			add(k - 1, x);
		}
	}

	for (int i = head; i != -1; i = ne[i])
	{
		cout << e[i] << " ";
	}
	cout << endl;
	return 0;
}

2.双链表

原题链接：https://www.acwing.com/problem/content/829/

#include <iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idx;

//初始化
void init()
{
    //0表示左端点，1表示右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}
//在下标是k的点的右边，插入x
void add(int k, int x)
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}
//删除第k个点
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}
int main()
{
    cin >> m;
    init();
    while (m--)
    {
        string op;
        int k, x;
        cin >> op;
        if (op == "L")
        {
            cin >> x;
            add(0, x);
        }
        else if (op == "R")
        {
            cin >> x;
            add(l[1], x);
        }
        else if (op == "D")
        {
            cin >> k;
            remove(k + 1);
        }
        else if (op == "IL")
        {
            cin >> k >> x;
            add(l[k + 1], x);
        }
        else
        {
            cin >> k >> x;
            add(k + 1, x);
        }
    }
    for (int i = r[0]; i != 1; i = r[i])
    {
        cout << e[i] << " ";
    }
    cout << endl;
    return 0;
}

3.模拟栈

原题链接：https://www.acwing.com/problem/content/830/

#include <iostream>
using namespace std;
const int N = 100010;
int st[N];
int top = -1;
int n;
int main()
{
    cin >> n;
    while(n--)
    {
        string s;
        cin >> s;
        //栈顶所在索引往后移动一格，然后放入x。
        if(s == "push")
        {
            int a;
            cin >> a;
            st[++top] = a;
        }

        //往前移动一格
        if(s == "pop")
        {
            top --;
        }
        //返回栈顶元素
        if(s == "query")
        {
            cout << st[top] << endl;
        }
        //大于等于 0 栈非空，小于 0 栈空
        if(s == "empty")
        {
            cout << (top == -1 ? "YES" : "NO") << endl;
        }
    }
}

4.表达式求值

原题链接：https://www.acwing.com/problem/content/3305/

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
//优先级表
unordered_map<char, int> h{ {'+', 1}, {'-', 1}, {'*',2}, {'/', 2} };

void eval()//求值
{
	int a = num.top();//第二个操作数
	num.pop();
	int b = num.top();//第一个操作数
	num.pop();
	char p = op.top();//运算符
	op.pop();
	int r = 0;//结果
	//计算结果
	if (p == '+') r = b + a;
	if (p == '-') r = b - a;
	if (p == '*') r = b * a;
	if (p == '/') r = b / a;

	num.push(r);//结果入栈
}

int main()
{
	string s;//读入表达式
	cin >> s;

	for (int i = 0; i < s.size(); i++)
	{
		if (isdigit(s[i]))//数字入栈
		{
			int x = 0, j = i;//计算数字
			while (j < s.size() && isdigit(s[j]))
			{
				x = x * 10 + s[j] - '0';
				j++;
			}
			num.push(x);//数字入栈
			i = j - 1;
		}
		//左括号无优先级，直接入栈
		else if (s[i] == '(')//左括号入栈
		{
			op.push(s[i]);
		}
		//括号特殊，遇到左括号直接入栈，遇到右括号计算括号里面的
		else if (s[i] == ')')//右括号
		{
			while (op.top() != '(')//一直计算到左括号
				eval();
			op.pop();//左括号出栈
		}
		else
		{
			while (op.size() && h[op.top()] >= h[s[i]])//待入栈运算符优先级低，则先计算
				eval();
			op.push(s[i]);//操作符入栈
		}
	}
	while (op.size()) eval();//剩余的进行计算
	cout << num.top() << endl;//输出结果
	return 0;
}

5.模拟队列

原题链接：https://www.acwing.com/problem/content/831/

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int main()
{
	int n;
	cin >> n;
	int hh = 0, tt = 0;
	while (n--)
	{
		string op;
		int x;
		cin >> op;
		if (op == "push")
		{
			cin >> x;
			q[tt++] = x;
		}
		else if (op == "pop")
		{
			hh++;
		}
		else if (op == "empty")
		{
			if (hh < tt) puts("NO");
			else puts("YES");
		}
		else
		{
			cout << q[hh] << endl;
		}
	}
}

6.单调栈

原题链接：https://www.acwing.com/problem/content/832/

#include <iostream>
using namespace std;
const int N = 100010;
int n, stk[N], tt;
int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		int x;
		cin >> x;
		while (tt && stk[tt] >= x) tt--;
		if (tt) cout << stk[tt] << " ";
		else cout << -1 << " ";
		stk[++tt] = x;
	}
	return 0;
}

7.滑动窗口

原题链接：https://www.acwing.com/problem/content/156/

#include <iostream>
#include <cstdio>
using namespace std;
int n, k;
const int N = 1000010;
int a[N], q[N];
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
	int hh = 0, tt = -1;
	for (int i = 0; i < n; ++i)
	{
		// 判断队头是否已经滑出窗口
		if (hh <= tt && i - k + 1 > q[hh]) hh++;
		while (hh <= tt && a[q[tt]] >= a[i]) tt--;
		q[++tt] = i;
		if (i >= k - 1) printf("%d ", a[q[hh]]);
	}
	printf("\n");
	hh = 0, tt = -1;
	for (int i = 0; i < n; ++i)
	{
		// 判断队头是否已经滑出窗口
		if (hh <= tt && i - k + 1 > q[hh]) hh++;
		while (hh <= tt && a[q[tt]] <= a[i]) tt--;
		q[++tt] = i;
		if (i >= k - 1) printf("%d ", a[q[hh]]);
	}
	printf("\n");
	return 0;
}

8.KMP字符串

原题链接：https://www.acwing.com/problem/content/833/

#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
char q[N], s[M];
int ne[N];//保存next数组
int main()
{
	int n, m;
	cin >> n >> q + 1 >> m >> s + 1;//下标均从1开始
	for (int i = 2, j = 0; i <= n; i++)
	{   //j表示匹配成功的长度,i表示q数组中的下标,因为q数组的下标是从1开始的,只有1个时,一定为0,所以i从2开始
		while (j && q[i] != q[j + 1]) j = ne[j];
		//如果不行可以换到next数组
		if (q[i] == q[j + 1]) j++;
		//成功了就加1
		ne[i] = j;
		//对应其下标
	}
	//j表示匹配成功的长度,因为刚开始还未开始匹配,所以长度为0
	for (int i = 1, j = 0; i <= m; i++)
	{
		while (j && s[i] != q[j + 1]) j = ne[j];
		//如果匹配不成功,则换到j对应的next数组中的值
		if (s[i] == q[j + 1]) j++;
		//匹配成功了,那么j就加1,继续后面的匹配
		if (j == n)//如果长度等于n了,说明已经完全匹配上去了
		{
			printf("%d ", i - j);
			//因为题目中的下标从0开始,所以i-j不用+1;
			j = ne[j];
			//为了观察其后续是否还能跟S数组后面的数配对成功
		}
	}
	return 0;
}

9.Trie字符串统计

原题链接：https://www.acwing.com/problem/content/837/

#include <iostream>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];
void insert(char str[])
{
	int p = 0;
	for (int i = 0; str[i]; i++)
	{
		int u = str[i] - 'a';
		if (!son[p][u]) son[p][u] = ++idx;
		p = son[p][u];
	}
	cnt[p]++;
}
int query(char str[])
{
	int p = 0;
	for (int i = 0; str[i]; i++)
	{
		int u = str[i] - 'a';
		if (!son[p][u]) return 0;
		p = son[p][u];
	}
	return cnt[p];
}

int main()
{
	int n;
	scanf("%d", &n);
	while (n--)
	{
		char op[2];
		scanf("%s%s", op, str);
		if (op[0] == 'I') insert(str);
		else printf("%d\n", query(str));
	}
	return 0;
}

10.最大异或对

原题链接：https://www.acwing.com/problem/content/145/

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 3000000;
int n;
int son[M][2], idx;
int a[N];

void insert(int x)
{
	int p = 0;
	for (int i = 30; i >= 0; i--)
	{
		int& s = son[p][x >> i & 1];
		if (!s) s = ++idx;  //创建新节点
		p = s;
	}
}

int query(int x)
{
	int res = 0, p = 0;
	for (int i = 30; i >= 0; i--)
	{
		int s = x >> i & 1;
		if (son[p][!s])
		{
			res += 1 << i;
			p = son[p][!s];
		}
		else p = son[p][s];
	}
	return res;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
		insert(a[i]);
	}
	int res = 0;
	for (int i = 0; i < n; ++i) res = max(res, query(a[i]));
	cout << res << endl;
	return 0;
}

11.合并集合

原题链接：https://www.acwing.com/problem/content/838/

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int n, m;
int p[N];
int find(int x) //返回x的祖宗节点 + 路径压缩
{
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)  p[i] = i;
	while (m--)
	{
		char op[2];
		int a, b;
		scanf("%s%d%d", op, &a, &b);
		if (op[0] == 'M') p[find(a)] = find(b);
		else
		{
			if (find(a) == find(b)) puts("Yes");
			else puts("No");
		}
	}
	return 0;
}

12.连通块中点的数量

原题链接：https://www.acwing.com/problem/content/839/

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int n, m;
int p[N], t_size[N];
int find(int x) //返回x的祖宗节点 + 路径压缩
{
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		p[i] = i;
		t_size[i] = 1;
	}
	while (m--)
	{
		char op[5];
		int a, b;
		scanf("%s", op);
		if (op[0] == 'C')
		{
			scanf("%d%d", &a, &b);
			if (find(a) == find(b)) continue;
			t_size[find(b)] += t_size[find(a)];
			p[find(a)] = find(b);
		}
		else if (op[1] == '1')
		{
			scanf("%d%d", &a, &b);
			if (find(a) == find(b)) puts("Yes");
			else puts("No");
		}
		else
		{
			scanf("%d", &a);
			printf("%d\n", t_size[find(a)]);
		}
	}
	return 0;
}

13.食物链

原题链接：https://www.acwing.com/problem/content/242/

#include <iostream>
using namespace std;
const int N = 50010;
int n, m;
int p[N], d[N];
int find(int x)
{
	if (p[x] != x)
	{
		int t = find(p[x]);
		d[x] += d[p[x]];
		p[x] = t;
	}
	return p[x];
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) p[i] = i;
	int res = 0;
	while (m--)
	{
		int t, x, y;
		scanf("%d%d%d", &t, &x, &y);
		if (x > n || y > n) res++;
		else
		{
			int px = find(x), py = find(y);
			if (t == 1)
			{
				if (px == py && (d[x] - d[y]) % 3) res++;
				else if (px != py)
				{
					p[px] = py;
					d[px] = d[y] - d[x];
				}
			}
			else
			{
				if (px == py && (d[x] - d[y] - 1) % 3) res++;
				else if (px != py)
				{
					p[px] = py;
					d[px] = d[y] + 1 - d[x];
				}
			}
		}
	}
	printf("%d\n", res);
	return 0;
}

14.堆排序

原题链接：https://www.acwing.com/problem/content/840/

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt;

void down(int u)
{
	int t = u;
	if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
	if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
	if (u != t)
	{
		swap(h[u], h[t]);
		down(t);
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
	cnt = n;
	for (int i = n / 2; i; i--) down(i);
	while (m--)
	{
		printf("%d ", h[1]);
		h[1] = h[cnt];
		cnt--;
		down(1);
	}
	return 0;
}

15.模拟堆

原题链接：https://www.acwing.com/problem/content/841/

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int h[N];   //堆
int ph[N];  //存放第k个插入点的下标
int hp[N];  //存放堆中点的插入次序
int cur_size;   //size 记录的是堆当前的数据多少

//这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
//从而我们需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换
//h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void heap_swap(int u, int v)
{
	swap(h[u], h[v]);
	swap(hp[u], hp[v]);
	swap(ph[hp[u]], ph[hp[v]]);
}

void down(int u)
{
	int t = u;
	if (u * 2 <= cur_size && h[t] > h[u * 2]) t = u * 2;
	if (u * 2 + 1 <= cur_size && h[t] > h[u * 2 + 1])  t = u * 2 + 1;
	if (u != t)
	{
		heap_swap(u, t);
		down(t);
	}
}
void up(int u)
{
	if (u / 2 > 0 && h[u] < h[u / 2])
	{
		heap_swap(u, u / 2);
		up(u >> 1);
	}
}

int main()
{
	int n;
	cin >> n;
	int m = 0;      //m用来记录插入的数的个数
	//注意m的意义与cur_size是不同的 cur_size是记录堆中当前数据的多少
	//对应上文 m即是hp中应该存的值
	while (n--)
	{
		string op;
		int k, x;
		cin >> op;
		if (op == "I")
		{
			cin >> x;
			m++;
			h[++cur_size] = x;
			ph[m] = cur_size;
			hp[cur_size] = m;
			//down(size);
			up(cur_size);
		}
		else if (op == "PM")    cout << h[1] << endl;
		else if (op == "DM")
		{
			heap_swap(1, cur_size);
			cur_size--;
			down(1);
		}
		else if (op == "D")
		{
			cin >> k;
			int u = ph[k];            //这里一定要用u=ph[k]保存第k个插入点的下标
			heap_swap(u, cur_size);   //因为在此处heap_swap操作后ph[k]的值已经发生
			cur_size--;               //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
			up(u);
			down(u);
		}
		else if (op == "C")
		{
			cin >> k >> x;
			h[ph[k]] = x;     //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以
			down(ph[k]);      //所以可直接传入ph[k]作为参数
			up(ph[k]);
		}
	}
	return 0;
}

16.模拟散列表

原题链接：https://www.acwing.com/problem/content/842/

#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f;
int h[N];
int find(int x)
{
	int k = (x % N + N) % N;
	while (h[k] != null && h[k] != x)
	{
		k++;
		if (k == N) k = 0;
	}
	return k;
}

int main()
{
	int n;
	scanf("%d", &n);
	memset(h, 0x3f, sizeof(h));
	while (n--)
	{
		char op[2];
		int x;
		scanf("%s%d", op, &x);
		int k = find(x);
		if (*op == 'I') h[k] = x;
		else
		{
			if (h[k] != null) puts("Yes");
			else puts("No");
		}
	}
	return 0;
}

17.字符串哈希

原题链接：https://www.acwing.com/problem/content/843/

#include <iostream>
#include <string>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r)
{
	return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
	scanf("%d%d%s", &n, &m, str + 1);
	p[0] = 1;
	for (int i = 1; i <= n; ++i)
	{
		p[i] = p[i - 1] * P;
		h[i] = h[i - 1] * P + str[i];
	}
	while (m--)
	{
		int l1, r1, l2, r2;
		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
		if (get(l1, r1) == get(l2, r2)) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

第三讲 搜索与图论

1.排列数字

原题链接：https://www.acwing.com/problem/content/844/

#include <iostream>
using namespace std;
const int N = 10010;
int path[N];
bool st[N];
int n;
void dfs(int u)
{
	if (u == n)
	{
		for (int i = 0; i < n; ++i)
		{
			printf("%d ", path[i]);
		}
		printf("\n");
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (!st[i])
		{
			path[u] = i;
			st[i] = true;
			dfs(u + 1);
			st[i] = false;
		}
	}
}

int main()
{
	cin >> n;
	dfs(0);
	return 0;
}

2.n-皇后问题

原题链接：https://www.acwing.com/problem/content/845/

#include <iostream>
using namespace std;
const int N = 10;
int n;
bool col[N], dg[N * 2], udg[N * 2];
char g[N][N];

void dfs(int u)
{
	if (u == n)
	{
		for (int i = 0; i < n; i++)
		{
			puts(g[i]);
		}
		puts("");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		//只要保证不同对角线会对应到不同数组下标即可
		if (!col[i] && !dg[n - u + i] && !udg[u + i])
		{
			g[u][i] = 'Q';
			col[i] = dg[n - u + i] = udg[u + i] = true;
			dfs(u + 1);
			col[i] = dg[n - u + i] = udg[u + i] = false;
			g[u][i] = '.';
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			g[i][j] = '.';
		}
	}
	dfs(0);
	return 0;
}

3.走迷宫

原题链接：https://www.acwing.com/problem/content/846/

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;

int n, m;
int g[N][N];
int d[N][N];
PII q[N * N];

int bfs()
{
	int hh = 0, tt = 0;
	q[0] = { 0, 0 };
	memset(d, -1, sizeof(d));
	d[0][0] = 0;
	int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };

	while (hh <= tt)
	{
		PII t = q[hh++];
		for (int i = 0; i < 4; ++i)
		{
			int x = t.first + dx[i], y = t.second + dy[i];
			if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
			{
				d[x][y] = d[t.first][t.second] + 1;
				q[++tt] = { x, y };
			}
		}
	}
	return d[n - 1][m - 1];
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> g[i][j];
		}
	}
	cout << bfs() << endl;
	return 0;
}

4.八数码

原题链接：https://www.acwing.com/problem/content/847/

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;

int bfs(string start)
{
	string end = "12345678x";
	queue<string> q;
	unordered_map<string, int> d;
	q.push(start);
	d[start] = 0;
	int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
	while (q.size())
	{
		string t = q.front();
		q.pop();
		int distance = d[t];
		if (t == end) return distance;
		//状态转移
		int k = t.find('x');
		int x = k / 3, y = k % 3;

		for (int i = 0; i < 4; i++)
		{
			int a = x + dx[i], b = y + dy[i];
			if (a >= 0 && a < 3 && b >= 0 && b < 3)
			{
				swap(t[k], t[a * 3 + b]);
				if (!d.count(t))
				{
					d[t] = distance + 1;
					q.push(t);
				}
				swap(t[k], t[a * 3 + b]);
			}
		}
	}
	return -1;
}

int main()
{
	string start;
	for (int i = 0; i < 9; ++i)
	{
		char c;
		cin >> c;
		start.push_back(c);
		//start += c;
	}
	cout << bfs(start) << endl;
	return 0;
}

5.树的重心

原题链接：https://www.acwing.com/problem/content/848/

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图，所以每个节点至多对应2n-2条边

int h[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入，n个节点
int ans = N; //表示重心的所有的子树中，最大的子树的结点数目

bool st[N]; //记录节点是否被访问过，访问过则标记为true

//a所对应的单链表中插入b  a作为根
void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// dfs 框架
/*
void dfs(int u)
{
	st[u]=true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(!st[j]) 
		{
			dfs(j);
		}
	}
}
*/
//返回以u为根的子树中节点的个数，包括u节点
int dfs(int u)
{
	int res = 0; //存储 删掉某个节点之后，最大的连通子图节点数
	st[u] = true; //标记访问过u节点
	int sum = 1; //存储 以u为根的树 的节点数, 包括u，如图中的4号节点

	//访问u的每个子节点
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		//因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
		if (!st[j])
		{
			int s = dfs(j);  // u节点的单棵子树节点数 如图中的size值
			res = max(res, s); // 记录最大联通子图的节点数
			sum += s; //以j为根的树 的节点数
		}
	}

	//n-sum 如图中的n-size值，不包括根节点4；
	res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数
	ans = min(res, ans); //遍历过的假设重心中，最小的最大联通子图的 节点数
	return sum;
}

int main()
{
	memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
	cin >> n; //表示树的结点数

	// 题目接下来会输入，n-1行数据，
	// 树中是不存在环的，对于有n个节点的树，必定是n-1条边
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b), add(b, a); //无向图
	}
	dfs(1); //可以任意选定一个节点开始 u<=n
	cout << ans << endl;
	return 0;
}

6.图中点的层次

原题链接：https://www.acwing.com/problem/content/849/

#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], idx, ne[N];
int d[N]; //存储每个节点离起点的距离  d[1]=0
int n, m; //n个节点m条边
int q[N]; //存储层次遍历序列 0号节点是编号为1的节点
void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs()
{
	int hh = 0, tt = 0;
	q[0] = 1; //0号节点是编号为1的节点
	memset(d, -1, sizeof d);
	d[1] = 0; //存储每个节点离起点的距离
	//当我们的队列不为空时
	while (hh <= tt)
	{
		//取出队列头部节点
		int t = q[hh++];
		//遍历t节点的每一个邻边
		for (int i = h[t]; i != -1; i = ne[i])
		{
			int j = e[i];
			//如果j没有被扩展过
			if (d[j] == -1)
			{
				d[j] = d[t] + 1; //d[j]存储j节点离起点的距离，并标记为访问过
				q[++tt] = j; //把j结点 压入队列
			}
		}
	}
	return d[n];
}

int main()
{
	cin >> n >> m;
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
	}
	cout << bfs() << endl;
}

7.有向图的拓扑序列

原题链接：https://www.acwing.com/problem/content/850/

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N], e[N], ne[N], idx;
int n, m;
int q[N], d[N];//q表示队列,d表示点的入度

void add(int a, int b)
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}

bool topsort()
{
	int hh = 0, tt = -1;
	for (int i = 1; i <= n; i++)
		if (!d[i])
			q[++tt] = i;//将入度为零的点入队
	while (hh <= tt)
	{
		int t = q[hh++];
		for (int i = h[t]; i != -1; i = ne[i])
		{
			int j = e[i];
			d[j]--;//删除点t指向点j的边
			if (d[j] == 0)//如果点j的入度为零了,就将点j入队
				q[++tt] = j;
		}
	}
	return tt == n - 1;
	//表示如果n个点都入队了话,那么该图为拓扑图,返回true,否则返回false
}

int main()
{
	cin >> n >> m;
	memset(h, -1, sizeof(h));//如果程序时间溢出，就是没有加上这一句
	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);//因为是a指向b,所以b点的入度要加1
		d[b]++;
	}
	if (topsort())
	{
		for (int i = 0; i < n; i++)
			printf("%d ", q[i]);
		//经上方循环可以发现队列中的点的次序就是拓扑序列
		//注:拓扑序列的答案并不唯一,可以从解析中找到解释
		puts("");
	}
	else puts("-1");
	return 0;
}

8.Dijkstra求最短路 I

原题链接：https://www.acwing.com/problem/content/851/

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510;
int g[N][N];    //为稠密阵所以用邻接矩阵存储
int dist[N];    //用于记录每一个点距离第一个点的距离
bool st[N];     //用于记录该点的最短距离是否已经确定
int n, m;

int Dijkstra()
{
	memset(dist, 0x3f, sizeof dist);     //初始化距离  0x3f代表无限大
	dist[1] = 0;  //第一个点到自身的距离为0
	for (int i = 0; i < n; i++)      //有n个点所以要进行n次 迭代
	{
		int t = -1;       //t存储当前访问的点
		for (int j = 1; j <= n; j++)   //这里的j代表的是从1号点开始
			if (!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;
		st[t] = true;
		for (int j = 1; j <= n; j++)           //依次更新每个点所到相邻的点路径值
			dist[j] = min(dist[j], dist[t] + g[t][j]);
	}

	if (dist[n] == 0x3f3f3f3f) return -1;  //如果第n个点路径为无穷大即不存在最低路径
	return dist[n];
}
int main()
{
	cin >> n >> m;
	memset(g, 0x3f, sizeof g);    //初始化图 因为是求最短路径
								//所以每个点初始为无限大
	while (m--)
	{
		int x, y, z;
		cin >> x >> y >> z;
		g[x][y] = min(g[x][y], z);     //如果发生重边的情况则保留最短的一条边
	}
	cout << Dijkstra() << endl;
	return 0;
}

9.Dijkstra求最短路 II

原题链接：https://www.acwing.com/problem/content/852/

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
vector<vector<pair<int, int>>> gra;
int dist[N];
int st[N];
int n, m;
int solve()
{
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	//这里是距离在前 节点号在后
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	heap.push({ 0, 1 });      // first存储距离，second存储节点编号
	while (heap.size())
	{
		auto t = heap.top();
		heap.pop();
		int node = t.second; int distance = t.first;
		if (st[node]) continue;
		st[node] = true;
		//查看每个出边
		for (int i = 0; i < gra[node].size(); i++) {
			int newnode = gra[node][i].first;
			int len = gra[node][i].second;
			if (dist[newnode] > dist[node] + len) {
				dist[newnode] = dist[node] + len;
				heap.push({ dist[newnode],newnode });
			}
		}
	}
	if (dist[n] == 0x3f3f3f3f) return -1;
	return dist[n];
}

int main()
{
	//cin >> n >> m;
	scanf("%d %d", &n, &m);
	gra.resize(n + 1);

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		//cin >> a >> b >> c;
		scanf("%d %d %d", &a, &b, &c);
		//这里是 目的节点号在前 边长在后
		gra[a].push_back({ b,c });
	}
	printf("%d\n", solve());
	return 0;
}

10.有边数限制的最短路

原题链接：https://www.acwing.com/problem/content/855/

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int dist[N], backup[N];
int k, n, m;
struct edge
{
	int a; int b; int w;
}edge[N];
int bellman_ford()
{
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	for (int i = 1; i <= k; i++)
	{
		memcpy(backup, dist, sizeof dist);
		for (int j = 1; j <= m; j++)
		{
			int a = edge[j].a, b = edge[j].b, w = edge[j].w;
			dist[b] = min(dist[b], backup[a] + w);
		}
	}
	return dist[n];
}
int main()
{
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edge[i].a = a, edge[i].b = b, edge[i].w = c;
	}
	int t = bellman_ford();
	if (t >= 0x3f3f3f3f / 2)puts("impossible");
	else cout << t << endl;
}

11.spfa求最短路

原题链接：https://www.acwing.com/problem/content/853/

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N]; //储存当前点到起点的距离
bool st[N];  //当前点是否在队列当中，防止存重复的点

void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int spfa()
{
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0; //起点距自己的距离为 0
	queue<int> q;
	q.push(1); //起点加入队列
	st[1] = true; //起点在队列里了
	while (q.size()) //如果队列不空
	{
		int t = q.front(); //取出队头
		q.pop(); //删掉队头
		st[t] = false;//这个点已经不在队列里边了
		for (int i = h[t]; i != -1; i = ne[i]) //更新 t 的所有邻边
		{
			int j = e[i]; //取出当前邻边的节点
			if (dist[j] > dist[t] + w[i])
			{
				dist[j] = dist[t] + w[i];
				if (!st[j]) //如果 j 不在队列里边
				{
					q.push(j); //加入队列
					st[j] = true; //在队列里了
				}
			}
		}
	}
	return dist[n];
}

int main()
{
	scanf("%d%d", &n, &m);
	memset(h, -1, sizeof h);
	while (m--)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
	int t = spfa();
	if (t == 0x3f3f3f3f) puts("impossible");
	else printf("%d\n", t);
	return 0;
}

12.spfa判断负环

原题链接：https://www.acwing.com/problem/content/854/

#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], w[N], idx;
int n, m;
int dis[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool spfa()
{
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	queue<int> q;
	for (int i = 1; i <= n; i++)
	{
		st[i] = true;
		q.push(i);
	}

	while (q.size())
	{
		int t = q.front();
		q.pop();
		st[t] = false;
		for (int i = h[t]; i != -1; i = ne[i])
		{
			int j = e[i];
			if (dis[j] > dis[t] + w[i])
			{
				dis[j] = dis[t] + w[i];
				cnt[j] = cnt[t] + 1;

				if (cnt[j] >= n)return true;
				if (!st[j])
				{
					q.push(j);
					st[j] = true;
				}
			}
		}
	}
	return false;
}

int main()
{
	memset(h, -1, sizeof(h));
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
	}
	if (spfa())puts("Yes");
	else puts("No");
	return 0;
}

13.Floyd求最短路

原题链接：https://www.acwing.com/problem/content/856/

#include <iostream>
using namespace std;
const int N = 210, M = 2e+10, INF = 1e9;
int n, m, k, x, y, z;
int d[N][N];

void floyd()
{
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i == j) d[i][j] = 0;
			else d[i][j] = INF;
	while (m--)
	{
		cin >> x >> y >> z;
		d[x][y] = min(d[x][y], z);
		//注意保存最小的边
	}
	floyd();
	while (k--)
	{
		cin >> x >> y;
		if (d[x][y] > INF / 2) puts("impossible");
		//由于有负权边存在所以约大过INF/2也很合理
		else cout << d[x][y] << endl;
	}
	return 0;
}

14.Prim算法求最小生成树

原题链接：https://www.acwing.com/problem/content/860/

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 510, MAXM = 2 * 1e5 + 10, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
int h[MAXM], e[MAXM], w[MAXM], ne[MAXM], idx;
bool vis[MAXN];
int n, m;

void add(int a, int b, int c) 
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int Prim()
{
	memset(vis, false, sizeof vis);
	int sum = 0, cnt = 0;
	priority_queue<PII, vector<PII>, greater<PII>> q;
	q.push({ 0, 1 });

	while (!q.empty())
	{
		auto t = q.top();
		q.pop();
		int ver = t.second, dst = t.first;
		if (vis[ver]) continue;
		vis[ver] = true, sum += dst, ++cnt;

		for (int i = h[ver]; i != -1; i = ne[i])
		{
			int j = e[i];
			if (!vis[j]) {
				q.push({ w[i], j });
			}
		}
	}
	if (cnt != n) return INF;
	return sum;
}

int main()
{
	cin >> n >> m;
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; ++i)
	{
		int a, b, w;
		cin >> a >> b >> w;
		add(a, b, w);
		add(b, a, w);
	}
	int t = Prim();
	if (t == INF) cout << "impossible" << endl;
	else cout << t << endl;
}

15.Kruskal算法求最小生成树

原题链接：https://www.acwing.com/problem/content/861/

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 200010, M = 100010;
int p[M];
int n, m;

struct Edge
{
	int a, b, w;
	bool operator< (const Edge& W)const
	{
		return w < W.w;
	}
}edges[N];

int find(int x)
{
	if (p[x] != x) p[x] = find(p[x]);
	else return x;
}

int Kruskal()
{
	int res = 0, cnt = 0;//res记录最小生成树的树边权重之和,cnt记录的是全部加入到树的集合中边的数量(可能有多个集合)
	for (int i = 0; i < m; i++)
	{
		int a = edges[i].a, b = edges[i].b, w = edges[i].w;
		if (find(a) != find(b))
			/*
			具体可以参考连通块中点的数量,如果a和b已经在一个集合当中了,说明这两个点已经被一种方式连接起来了,
			如果加入a-b这条边,会导致集合中有环的生成,而树中不允许有环生成,所以一个连通块中的点的数量假设
			为x,那么里面x个节点应该是被串联起来的,有x-1条边,所以只有当a,b所属的集合不同时,才能将a-b这条
			边加入到总集合当中去
			*/
		{
			p[find(a)] = p[find(b)];//将a,b所在的两个集合连接起来
			cnt++;//因为加入的是a-b的这一条边,将a,b所在的两个集合连接之后,全部集合中的边数加1
			res += w;//加入到集合中的边的权重之和
		}
	}
	if (cnt == n - 1) return res;//可以生成最小生成树
	else return 0x3f3f3f3f;//树中有n个节点便有n-1条边,如果cnt不等于n-1的话,说明无法生成有n个节点的树
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++) p[i] = i;//初始化并查集

	for (int i = 0; i < m; i++)
	{
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		edges[i] = { a,b,w };
	}
	sort(edges, edges + m);//将边的权重按照大小一一排序
	int t = Kruskal();
	if (t == 0x3f3f3f3f) printf("impossible\n");
	else printf("%d\n", t);

	return 0;
}

16.染色法判定二分图

原题链接：https://www.acwing.com/problem/content/862/

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;//由于是无向图, 顶点数最大是N，那么边数M最大是顶点数的2倍
int e[M], ne[M], h[N], idx;
int st[N];

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool dfs(int u, int color) 
{
	st[u] = color;
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		if (!st[j])
		{
			if (!dfs(j, 3 - color)) return false;
		}
		else if (st[j] == color) return false;
	}
	return true;
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);

	memset(h, -1, sizeof h);
	while (m--) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a);//无向图，a->b, b->a
	}

	bool flag = true;
	for (int i = 1; i <= n; i++) 
	{
		if (!st[i]) 
		{
			if (!dfs(i, 1))
			{
				flag = false;
				break;
			}
		}
	}

	if (flag) puts("Yes");
	else puts("No");
	return 0;
}

17.二分图的最大匹配

原题链接：https://www.acwing.com/problem/content/863/

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 100010;
int n1, n2, m;
int h[N], ne[M], e[M], idx;
bool st[N];
int match[N];

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void init()
{
	memset(h, -1, sizeof h);
}

int find(int x)
{
	//遍历自己喜欢的女孩
	for (int i = h[x]; i != -1; i = ne[i])
	{
		int j = e[i];
		if (!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定
		{
			st[j] = true;//那x就预定这个女孩了
			//如果女孩j没有男朋友，或者她原来的男朋友能够预定其它喜欢的女孩。配对成功
			if (!match[j] || find(match[j]))
			{
				match[j] = x;
				return true;
			}
		}
	}
	//自己中意的全部都被预定了。配对失败。
	return false;
}
int main()
{
	init();
	cin >> n1 >> n2 >> m;
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
	}
	int res = 0;
	for (int i = 1; i <= n1; i++)
	{
		//因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
		memset(st, false, sizeof st);
		if (find(i))
			res++;
	}
	cout << res << endl;
}

第四讲 数学知识

1.试除法判定质数

原题链接：https://www.acwing.com/problem/content/868/

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1010;
int a[N];
int n;
bool isPrime(int n)
{
	if (n < 2) return false;
	for (int i = 2; i <= n / i; i++)
	{
		if (n % i == 0) return false;
	}
	return true;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		if (isPrime(a[i])) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

2.分解质因数

原题链接：https://www.acwing.com/problem/content/869/

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
void divide(int n)
{
	for (int i = 2; i <= n / i; i++)
	{
		if (n % i == 0) //i一定是质数
		{
			int s = 0;
			while (n % i == 0)
			{
				n /= i;
				s++;
			}
			printf("%d %d\n", i, s);
		}
	}
	if (n > 1) printf("%d %d\n", n, 1);
	printf("\n");
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	while (n--)
	{
		int x = 0;
		scanf("%d", &x);
		divide(x);
	}
	return 0;
}

3.筛质数

原题链接：https://www.acwing.com/problem/content/870/

#include <iostream>
using namespace std;
const int N = 1000010;
bool isprime[N];
void get_primes(int n)
{
	for (int i = 2; i <= n; i++)
	{
		isprime[i] = true;
	}
	for (int i = 2; i <= n / i; i++)
	{
		if (isprime[i])
		{
			for (int j = i * i; j <= n; j += i)
			{
				isprime[j] = false;
			}
		}
	}
}
int main()
{
	int n = 0, cnt = 0;
	cin >> n;
	get_primes(n);
	for (int i = 0; i <= n; i++)
	{
		if (isprime[i]) cnt++;
	}
	cout << cnt << endl;
	return 0;
}

或者：

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1000010;
//primes数组用来存放质数
int primes[N], cnt;
//st[i], i为质数则为false否则为true
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) primes[cnt++] = i;
        //假设primes[0]为n最小的质因子,i为最大的因数，
        //易知若primes[i]中i>0,则会进入循环后产生多余的标记。
        for (int j = 0; primes[j] <= n / i; j++)
        {
            //标记;primes[j]一定是primes[j]*i的最小质因子
            st[primes[j] * i] = true;
            //表明primes[j]一定是i的最小质因子,没有必要再遍历,primes要小于等于i的最小质因子
            //这样能保证每个数遍历一遍,而没有重复
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

4.试除法求约数

原题链接：https://www.acwing.com/problem/content/871/

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n;
vector<int> get_divisors(int n)
{
	vector<int> ans;
	for (int i = 1; i <= n / i; ++i)
	{
		if (n % i == 0)
		{
			ans.push_back(i);
			if (i != n / i) ans.push_back(n / i);
		}
	}
	sort(ans.begin(), ans.end());
	return ans;
}

int main()
{
	cin >> n;
	while (n--)
	{
		int x = 0;
		cin >> x;
		vector<int> ans = get_divisors(x);
		for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
		cout << endl;
	}
	return 0;
}

5.约数个数

原题链接：https://www.acwing.com/problem/content/872/

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
	int n = 0;
	cin >> n;
	unordered_map<int, int> primes;
	while (n--)
	{
		int x = 0;
		cin >> x;
		for (int i = 2; i <= x / i; ++i)
		{
			while (x % i == 0)
			{
				x /= i;
				primes[i]++;
			}
		}
		if (x > 1) primes[x]++;
	}

	LL res = 1;
	for (auto prime : primes)
	{
		res = res * (prime.second + 1) % mod;
	}
	cout << res << endl;
	return 0;
}

6.约数之和

原题链接：https://www.acwing.com/problem/content/873/

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
    int n = 0;
    cin >> n;
    unordered_map<int, int> primes;
    while (n--)
    {
        int x = 0;
        cin >> x;
        for (int i = 2; i <= x / i; ++i)
        {
            while (x % i == 0)
            {
                x /= i;
                primes[i]++;

            }
        }
        if (x > 1) primes[x]++;
    }

    LL res = 1;
    for (auto prime : primes)
    {
        int p = prime.first, a = prime.second;
        LL t = 1;
        while (a--)
        {
            t = (t * p + 1) % mod;
        }
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
}

7.最大公约数

原题链接：https://www.acwing.com/problem/content/874/

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int n, a, b;
int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a % b);
}
int main()
{
	scanf("%d", &n);
	while (n--)
	{
		scanf("%d%d", &a, &b);
		printf("%d\n", gcd(a, b));
	}
	return 0;
}

8.欧拉函数

原题链接：https://www.acwing.com/problem/content/875/

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n;

int main()
{
    scanf("%d",&n);
    while(n--)
    {
        int a = 0;
        scanf("%d",&a);
        int res = a;
        for(int i = 2;i <= a/i; ++i)
        {
            if(a % i == 0)
            {
                res = res / i * (i - 1);
                while(a % i == 0) a /= i;
            }
        }
        if(a > 1) res = res / a * (a - 1);
        cout<<res<<endl;
    }
    return 0;
}

9.筛法求欧拉函数

原题链接：https://www.acwing.com/problem/content/876/

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010;
int primes[N], cnt;
int phi[N];
bool st[N];

void get_eulers(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
            phi[i] = i - 1; 
        }
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j]; 
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_eulers(n);
    LL res = 0;
    for (int i = 1; i <= n; i++) res += phi[i];
    printf("%lld\n", res);
    return 0;
}

10.快速幂

原题链接：https://www.acwing.com/problem/content/877/

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
int qmi(int a, int k, int p)
{
	int res = 1;
	while (k)
	{
		if (k & 1) res = (LL)res * a % p;
		k >>= 1;
		a = (LL)a * a % p;
	}
	return res;
}
int main()
{
	scanf("%d", &n);
	while (n--)
	{
		int a, k, p;
		scanf("%d%d%d", &a, &k, &p);
		printf("%d\n", qmi(a, k, p));
	}
	return 0;
}

11.快速幂求逆元

原题链接：https://www.acwing.com/problem/content/878/

#include <iostream>
using namespace std;
typedef long long LL;

LL qmi(int a, int b, int p)
{
    LL res = 1;
    while (b) 
    {
        if (b & 1) res = res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    int n; cin >> n;
    while (n--) 
    {
        int a, p;
        cin >> a >> p;
        if (a % p == 0) puts("impossible");
        else cout << qmi(a, p - 2, p) << endl;
    }
    return 0;
}

12.扩展欧几里得算法

原题链接：https://www.acwing.com/problem/content/879/

#include <iostream>
#include <cstdio>
using namespace std;
int exgcd(int a, int b, int& x, int& y)
{
	if (!b)
	{
		x = 1, y = 0;
		return a;
	}
	else
	{
		int d = exgcd(b, a % b, y, x);
		y -= a / b * x;
		return d;
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	while (n--)
	{
		int a, b, x, y;
		scanf("%d%d", &a, &b);
		exgcd(a, b, x, y);
		printf("%d %d\n", x, y);
	}
	return 0;
}

13.线性同余方程

原题链接：https://www.acwing.com/problem/content/880/

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
int exgcd(int a, int b, int& x, int& y)
{
	if (!b)
	{
		x = 1, y = 0;
		return a;
	}
	else
	{
		int d = exgcd(b, a % b, y, x);
		y -= a / b * x;
		return d;
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	while (n--)
	{
		int a, b, m;
		scanf("%d%d%d", &a, &b, &m);
		int x, y;
		int d = exgcd(a, m, x, y);
		if (b % d) puts("impossible");
		else printf("%d\n", (LL)x * (b / d) % m);
	}
	return 0;
}

14.表达整数的奇怪方式

原题链接：https://www.acwing.com/problem/content/206/

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
int n;
LL exgcd(LL a, LL b, LL& x, LL& y)
{
	if (b == 0)
	{
		x = 1, y = 0;
		return a;
	}

	LL d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
LL inline mod(LL a, LL b)
{
	return ((a % b) + b) % b;
}
int main()
{
	scanf("%d", &n);
	LL a1, m1;
	scanf("%lld%lld", &a1, &m1);
	for (int i = 1; i < n; i++)
	{
		LL a2, m2, k1, k2;
		scanf("%lld%lld", &a2, &m2);
		LL d = exgcd(a1, -a2, k1, k2);
		if ((m2 - m1) % d)
		{
			puts("-1");
			return 0;
		}
		k1 = mod(k1 * (m2 - m1) / d, abs(a2 / d));
		m1 = k1 * a1 + m1;
		a1 = abs(a1 / d * a2);
	}
	printf("%lld\n", m1);
	return 0;
}

15.高斯消元解线性方程组

原题链接：https://www.acwing.com/problem/content/885/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 110;
const double eps = 1e-8;
int n;
double a[N][N];

int gauss()  // 高斯消元，答案存于a[i][n]中，0 <= i < n
{
    int c, r;
    for (c = 0, r = 0; c < n; c++)
    {
        int t = r;
        for (int i = r; i < n; i++) //找绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;
        if (fabs(a[t][c]) < eps) continue;
        for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);//将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i--) a[r][i] /= a[r][c];//将当前行的首位变成1
        for (int i = r + 1; i < n; i++) //用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j--)
                    a[i][j] -= a[r][j] * a[i][c];
        r++;
    }
    if (r < n)
    {
        for (int i = r; i < n; i++)
            if (fabs(a[i][n]) > eps)
                return 2; //无解
        return 1; //有无穷多组解
    }
    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            a[i][n] -= a[i][j] * a[j][n];
    return 0; //有唯一解
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n + 1; j++)
            scanf("%lf", &a[i][j]);
    int t = gauss();
    if (t == 2) puts("No solution");
    else if (t == 1) puts("Infinite group solutions");
    else
    {
        for (int i = 0; i < n; i++)
        {
            if (fabs(a[i][n]) < eps) a[i][n] = 0;  //去掉输出 -0.00 的情况
            printf("%.2lf\n", a[i][n]);
        }
    }
    return 0;
}

16.高斯消元解异或线性方程组

原题链接：https://www.acwing.com/problem/content/886/

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int a[N][N];
int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c++)
    {
        // 找主元
        int t = -1;
        for (int i = r; i < n; i++)
            if (a[i][c])
            {
                t = i;
                break;
            }
        if (t == -1) continue;
        // 交换主元行
        for (int j = c; j <= n; j++) swap(a[r][j], a[t][j]);
        // 左下角消
        for (int i = r + 1; i < n; i++)
            if (a[i][c])//漏了
                for (int j = n; j >= c; j--)//漏了
                    a[i][j] ^= a[r][j];
        r++;
    }
    // 判断
    if (r < n)
    {
        for (int i = r; i < n; i++)//i=r
            if (a[i][n]) return 2;   
        return 1;
    }
    // 消右上角
    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            //如果是0 就不用下面的a[j][j] 来^a[i][j]了
            //如果不是0 才需要用第j行第j列a[j][j]来^第i行第j列a[i][j] 
            //进而进行整行row[i]^row[j] 间接导致 a[i][n]^a[j][n]
            if (a[i][j]) a[i][n] ^= a[j][n];        
    return 0;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= n; j++)
            cin >> a[i][j];
    int t = gauss();
    if (t == 0)
    {
        for (int i = 0; i < n; i++) cout << a[i][n] << endl;
    }
    else if (t == 1) puts("Multiple sets of solutions");
    else puts("No solution");
    return 0;
}

17.求组合数 I

原题链接：https://www.acwing.com/problem/content/887/

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7, N = 2010;
int c[N][N];
int n;
LL C(int a, int b) //通过递归求解组合C(a,b)的值
{
	if (b == 0 || a == b)
		return 1;
	else
		return C(a - 1, b) + C(a - 1, b - 1);
}
void init()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (!j) c[i][j] = 1;
			else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
		}
	}
}
int main()
{
	scanf("%d", &n);
	init();
	while (n--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", c[a][b]);
	}
	return 0;
}

18.求组合数 II

原题链接：https://www.acwing.com/problem/content/888/

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
int fact[N], infact[N];
int qmi(int a, int k, int p)
{
	int res = 1;
	while (k)
	{
		if (k & 1) res = (LL)res * a % p;
		a = (LL)a * a % p;
		k >>= 1;
	}
	return res;
}

int main()
{
	fact[0] = infact[0] = 1;
	for (int i = 1; i < N; i++)
	{
		fact[i] = (LL)fact[i - 1] * i % mod;
		infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
	}
	int n;
	scanf("%d", &n);
	while (n--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
	}
	return 0;
}

19.求组合数 III

原题链接：https://www.acwing.com/problem/content/889/

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;

int qmi(int a, int k, int p)
{
	int res = 1;
	while (k)
	{
		if (k & 1)res = (LL)res * a % p;
		a = (LL)a * a % p;
		k >>= 1;
	}
	return res;
}

int C(int a, int b, int p)//自变量类型int
{
	if (b > a)return 0;//漏了边界条件
	int res = 1;
	// a!/(b!(a-b)!) = (a-b+1)*...*a / b! 分子有b项
	for (int i = 1, j = a; i <= b; i++, j--)//i<=b而不是<
	{
		res = (LL)res * j % p;
		res = (LL)res * qmi(i, p - 2, p) % p;
	}
	return res;
}
//对公式敲
int lucas(LL a, LL b, int p)
{
	if (a < p && b < p)return C(a, b, p);//lucas递归终点是C_{bk}^{ak}
	return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
    //a%p后肯定是<p的,所以可以用C(),但a/p后不一定<p 所以用lucas继续递归
}

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		LL a, b;
		int p;
		cin >> a >> b >> p;
		cout << lucas(a, b, p) << endl;
	}
	return 0;
}

20.求组合数 IV

原题链接：https://www.acwing.com/problem/content/890/

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 5010;
int primes[N], cnt;
int sum[N];
bool st[N];

void get_primes(int n)
{
	for (int i = 2; i <= n; i++)
	{
		if (!st[i])primes[cnt++] = i;
		for (int j = 0; primes[j] * i <= n; j++)
		{
			st[primes[j] * i] = true;
			if (i % primes[j] == 0)break;//==0每次漏
		}
	}
}
// 对p的各个<=a的次数算整除下取整倍数
int get(int n, int p)
{
	int res = 0;
	while (n)
	{
		res += n / p;
		n /= p;
	}
	return res;
}
//高精度乘
vector<int> mul(vector<int> a, int b)
{
	vector<int> c;
	int t = 0;
	for (int i = 0; i < a.size(); i++)
	{
		t += a[i] * b;
		c.push_back(t % 10);
		t /= 10;
	}
	while (t)
	{
		c.push_back(t % 10);
		t /= 10;
	}
	// while(C.size()>1 && C.back()==0) C.pop_back();//考虑b==0时才有pop多余的0 b!=0不需要这行
	return c;
}

int main()
{
	int a, b;
	cin >> a >> b;
	get_primes(a);

	for (int i = 0; i < cnt; i++)
	{
		int p = primes[i];
		sum[i] = get(a, p) - get(a - b, p) - get(b, p);//是a-b不是b-a
	}
	vector<int> res;
	res.push_back(1);
	for (int i = 0; i < cnt; i++)
		for (int j = 0; j < sum[i]; j++)//primes[i]的次数
			res = mul(res, primes[i]);

	for (int i = res.size() - 1; i >= 0; i--) printf("%d", res[i]);
	puts("");

	return 0;
}

21.满足条件的01序列

原题链接：https://www.acwing.com/problem/content/891/

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int qmi(int a, int k, int p)
{
	int res = 1;
	while (k)
	{
		if (k & 1) res = (LL)res * a % p;
		a = (LL)a * a % p;
		k >>= 1;
	}
	return res;
}
int main()
{
	int n;
	cin >> n;
	int a = 2 * n, b = n;
	int res = 1;
	for (int i = a; i > a - b; i--) res = (LL)res * i % mod;
	for (int i = 1; i <= b; i++) res = (LL)res * qmi(i, mod - 2, mod) % mod;
	res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;
	cout << res << endl;
	return 0;
}

22.能被整除的数

原题链接：https://www.acwing.com/problem/content/892/

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 20;
int p[N], n, m;
int main() 
{
	cin >> n >> m;
	for (int i = 0; i < m; i++) cin >> p[i];
	int res = 0;
	//枚举从1 到 1111...(m个1)的每一个集合状态, (至少选中一个集合)
	for (int i = 1; i < 1 << m; i++) 
    {
		int t = 1;//选中集合对应质数的乘积
		int s = 0;//选中的集合数量
		//枚举当前状态的每一位
		for (int j = 0; j < m; j++) 
        {
			//选中一个集合
			if (i >> j & 1) 
            {
				//乘积大于n, 则n/t = 0, 跳出这轮循环
				if ((LL)t * p[j] > n) 
                {
					t = -1;
					break;
				}
				s++;                  //有一个1，集合数量+1
				t *= p[j];
			}
		}
		if (t == -1) continue;
		if (s & 1) res += n / t;              //选中奇数个集合, 则系数应该是1, n/t为当前这种状态的集合数量
		else res -= n / t;                      //反之则为 -1
	}
	cout << res << endl;
	return 0;
}

23.Nim游戏

原题链接：https://www.acwing.com/problem/content/893/

#include <iostream>
#include <cstdio>
using namespace std;
/*
先手必胜状态：先手操作完，可以走到某一个必败状态
先手必败状态：先手操作完，走不到任何一个必败状态
先手必败状态：a1 ^ a2 ^ a3 ^ ... ^an = 0
先手必胜状态：a1 ^ a2 ^ a3 ^ ... ^an ≠ 0
*/
int main()
{
	int n;
	scanf("%d", &n);
	int res = 0;
	for (int i = 0; i < n; i++)
	{
		int x;
		scanf("%d", &x);
		res ^= x;
	}
	if (res == 0) puts("No");
	else puts("Yes");
    return 0;
}

24.台阶-Nim游戏

原题链接：https://www.acwing.com/problem/content/894/

#include <iostream>
using namespace std;
int main()
{
	int res = 0;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		if (i % 2) res ^= x;
	}
	if (res) puts("Yes");
	else puts("No");
	return 0;
}

25.集合-Nim游戏

原题链接：https://www.acwing.com/problem/content/895/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int N = 110, M = 10010;
int n, m;
int f[M], s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值

int sg(int x)
{
	if (f[x] != -1) return f[x];
	//因为取石子数目的集合是已经确定了的,所以每个数的sg值也都是确定的,如果存储过了,直接返回即可
	set<int> S;
	//set代表的是有序集合(注:因为在函数内部定义,所以下一次递归中的S不与本次相同)
	for (int i = 0; i < m; i++)
	{
		int sum = s[i];
		if (x >= sum) S.insert(sg(x - sum));
		//先延伸到终点的sg值后,再从后往前排查出所有数的sg值
	}
	for (int i = 0;; i++)
		//循环完之后可以进行选出最小的没有出现的自然数的操作
		if (!S.count(i))
			return f[x] = i;
}

int main()
{
	cin >> m;
	for (int i = 0; i < m; i++)
		cin >> s[i];
	cin >> n;
	memset(f, -1, sizeof(f));//初始化f均为-1,方便在sg函数中查看x是否被记录过
	int res = 0;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		res ^= sg(x);
		//观察异或值的变化,基本原理与Nim游戏相同
	}
	if (res) printf("Yes");
	else printf("No");
	return 0;
}

26.拆分-Nim游戏

原题链接：https://www.acwing.com/problem/content/896/

#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
const int N = 110;
int n;
int f[N];
unordered_set<int> S;
int sg(int x)
{
	if (f[x] != -1) return f[x];

	for (int i = 0; i < x; i++)
		for (int j = 0; j <= i; j++)//规定j不大于i，避免重复
			S.insert(sg(i) ^ sg(j));//相当于一个局面拆分成了两个局面，由SG函数理论，多个独立局面的SG值，
								    //等于这些局面SG值的异或和
	for (int i = 0; ; i++)
		if (!S.count(i))
			return f[x] = i;
}
int main()
{
	memset(f, -1, sizeof f);
	cin >> n;
	int res = 0;
	while (n--)
	{
		int x;
		cin >> x;
		res ^= sg(x);
	}
	if (res) puts("Yes");
	else puts("No");
	return 0;
}

第五讲 动态规划

1.01背包问题

原题链接：https://www.acwing.com/problem/content/2/

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1010;
int n, V;
int v[N], w[N];
int f[N][N];
int main()
{
	cin >> n >> V;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= V; j++)
		{
			f[i][j] = f[i - 1][j];
			if (v[i] <= j) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
			//如果v[i] > j，就不用选了
		}
	}
	cout << f[n][V] << endl;
	return 0;
}

优化成一维：

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1010;
int n, V;
int v[N], w[N];
int f[N];
int main()
{
	cin >> n >> V;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	for (int i = 1; i <= n; i++)
	{
		for (int j = V; j >= v[i]; j--)
		{
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}
	cout << f[V] << endl;
	return 0;
}

2.完全背包问题

原题链接：https://www.acwing.com/problem/content/3/

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	for (int i = 1; i <= n; i++)
	{
		for (int j = v[i]; j <= m; j++)
		{
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}
	cout << f[m] << endl;
	return 0;
}

3.多重背包问题 I

原题链接：https://www.acwing.com/problem/content/4/

//多重背包问题暴力写法
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
			{
				f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
			}
		}
	}
	cout << f[n][m] << endl;
	return 0;
}

4.多重背包问题 II

原题链接：https://www.acwing.com/problem/content/5/

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
const int N = 25000;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
	cin >> n >> m;
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		int a, b, s;
		cin >> a >> b >> s;
		int k = 1;
		while (k <= s)
		{
			cnt++;
			v[cnt] = a * k;
			w[cnt] = b * k;
			s -= k;
			k *= 2;
		}
		if (s > 0)
		{
			cnt++;
			v[cnt] = a * s;
			w[cnt] = b * s;
		}
	}
	n = cnt;
	for (int i = 1; i <= n; i++)
	{
		for (int j = m; j >= v[i]; j--)
		{
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}
	cout << f[m] << endl;
	return 0;
}

5.分组背包问题

原题链接：https://www.acwing.com/problem/content/9/

#include <iostream>
using namespace std;
const int N = 110;
int f[N];
int v[N][N], w[N][N], s[N];
int n, m, k;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
		for (int j = 0; j < s[i]; j++)
		{
			cin >> v[i][j] >> w[i][j];
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = m; j >= 0; j--)
		{
			for (int k = 0; k < s[i]; k++)
			{    //for(int k=s[i];k>=1;k--)也可以
				if (j >= v[i][k])
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
			}
		}
	}
	cout << f[m] << endl;
}

6.数字三角形

原题链接：https://www.acwing.com/problem/content/900/

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 510;
int n;
int f[N][N], w[N][N];
int main()
{
    cin>>n;
    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= i; j++)
        {
            cin>>w[i][j];
        }
    }
    for(int i = 1;i <= n; i++) f[n][i] = w[n][i];
    for(int i = n - 1;i ;i--)
    {
        for(int j = 1;j <= i; j++)
        {
            f[i][j] = max(f[i+1][j] + w[i][j], f[i+1][j+1] + w[i][j]);
        }
    }
    cout << f[1][1] << endl;
    return 0;
}

7.最长上升子序列

原题链接：https://www.acwing.com/problem/content/897/

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N], dp[N];
int n;
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n; i++) scanf("%d",&a[i]);
    for(int i = 1;i <= n; i++)
    {
        dp[i] = 1;
        for(int j = 1;j < i; j++)
        {
            if(a[j] < a[i])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int res = 0;
    for(int i = 1;i <= n; i++) res = max(res, dp[i]);
    printf("%d\n",res);
    return 0;
}

8.最长上升子序列 II

原题链接：https://www.acwing.com/problem/content/898/

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 100010;
int a[N],q[N];
int n;
int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n; ++i) scanf("%d",&a[i]);
    int len = 0;
    q[0] = -2e9;
    for(int i = 0;i < n; ++i)
    {
        int l = 0,r = len;
        while(l < r)
        {
            int mid = l + r + 1>> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    printf("%d\n",len);
    return 0;
}

9.最长公共子序列

原题链接：https://www.acwing.com/problem/content/899/

#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main()
{
    cin>>n>>m>>a+1>>b+1;
    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j],f[i][j - 1]);
            if(a[i] == b[j]) f[i][j] = max(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

10.最短编辑距离

原题链接：https://www.acwing.com/problem/content/904/

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main()
{
    cin>>n>>a+1>>m>>b+1;
    for(int i = 0;i <= m; i++) f[0][i] = i;
    for(int i = 0;i <= n; i++) f[i][0] = i;
    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= m; j++)
        {
            f[i][j] = min(f[i-1][j] + 1, f[i][j-1] + 1);
            if(a[i] == b[j]) f[i][j] = min(f[i][j],f[i-1][j-1]);
            else f[i][j] = min(f[i][j],f[i-1][j-1] + 1);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

11.编辑距离

原题链接：https://www.acwing.com/problem/content/901/

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 15,M = 1010;
int n,m;
int f[N][N];
char str[M][N];
int edit_distance(char a[],char b[])
{
    int la = strlen(a+1),lb = strlen(b+1);
    for(int i = 0;i <= lb; i++) f[0][i] = i;
    for(int i = 0;i <= la; i++) f[i][0] = i;
    for(int i = 1;i <= la; i++)
    {
        for(int j = 1;j <= lb; j++)
        {
            f[i][j] = min(f[i-1][j]+1, f[i][j-1]+1);
            f[i][j] = min(f[i][j], f[i-1][j-1]+(a[i] != b[j]));
        }
    }
    return f[la][lb];
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0;i < n; i++) scanf("%s", str[i]+1);
    while(m--)
    {
        char s[N];
        int limit;
        scanf("%s%d", s+1, &limit);
        int res = 0;
        for(int i = 0;i < n; i++) 
        {
            if(edit_distance(str[i],s) <= limit) res++;
        }
        printf("%d\n",res);
    }
    return 0;
}

12.石子合并

原题链接：https://www.acwing.com/problem/content/284/

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 310;
int n;
int s[N];
int f[N][N];
int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    for(int len = 2; len <= n; len++)
    {
        for(int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            f[i][j] = 1e8;
            for(int k = i; k < j; k++)
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i - 1]);
            }
        }
    }
    cout << f[1][n] << endl;
    return 0;
}

13.整数划分

原题链接：https://www.acwing.com/problem/content/902/

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010,mod = 1e9 + 7;
int n;
int f[N];
int main()
{
    cin>>n;
    f[0] = 1;
    for(int i = 1;i <= n; i++)
    {
        for(int j = i;j <= n; j++)
        {
            f[j] = (f[j] + f[j - i]) % mod;
        }
    }
    cout<<f[n]<<endl;
    return 0;
}

14.计数问题

原题链接：https://www.acwing.com/problem/content/340/

#include <iostream>
#include <vector>
using namespace std;
int base[10];
int f[10][10];
int g[10][10];

void init()
{
	base[0] = 1;
	for(int i = 1 ; i <= 9 ; i++) base[i] = base[i-1]*10;
	//从00……0 - 99……9 的各位数字有多少个，其中i为数字个数（包含前导零）
	for(int i = 0 ; i <= 9 ; i++) f[1][i] = 1;
	for(int i = 2 ; i <= 9 ; i++)
		for(int j = 0 ; j <= 9 ; j++)
			f[i][j] = f[i-1][j]*10 + base[i-1];
	//从1 - 99……9 的各位数字有多少个，其中i为数字个数（不包含前导零）
	for(int i = 1 ; i <= 9 ; i++) g[1][i] = 1;//循环从1开始
	for(int i = 2 ; i <= 9 ; i++)
	{
		g[i][0] = g[i-1][0] + f[i-1][0]*9;
		for(int j = 1 ; j <= 9 ; j++)
			g[i][j] = g[i-1][j] + f[i-1][j]*9 + base[i-1];
	}
}

vector<int> dp(int n)
{
	vector<int> ans(10,0); //记录答案
	if(n<=0) return ans; //边界条件
	vector<int> nums;
	while(n) nums.push_back(n%10), n/=10;
	vector<int> last(10,0); //记录前缀中各个数字个数
	//统计1 - 99……9(n-1个9)里面各个数字有多少个
	for(int i = 0 ; i <= 9 ; i++) ans[i] = g[nums.size()-1][i];
	//统计大于10……0(n-1个0) 的树里各个数字有多少个
	for(int i = nums.size()-1 ; i >=0 ; i--)
	{
		//循环变量i可以表示剩下的数字有多少个
		int x = nums[i];
		for(int j = i==nums.size()-1 ; j < x ; j++)   //第一次循环不能有0
		{
			//前缀部分
			for(int k = 0 ; k <= 9 ; k++)
				ans[k] += last[k] * base[i];
			//当前位置部分
			ans[j] += base[i];
			//后缀部分
			for(int k = 0 ; k <= 9 ; k++)
				ans[k] += f[i][k];
		}
		//更新前缀计数器
		last[x] ++;

		//统计叶子节点（这个数本身）
		if(!i) for(int k = 0 ; k <= 9 ; k++) ans[k] += last[k];
	}
	return ans;
}

vector<int> ask(int a, int b)
{
	auto x = dp(b);
	auto y = dp(a-1);
	vector<int> ans;
	for(int i = 0 ; i <= 9 ; i++) ans.push_back(x[i]-y[i]);
	return ans;
}

void print(vector<int> ans)
{
	for(auto x:ans) printf("%d ",x);
	puts("");
}

bool check(int x)
{
	auto t = ask(x,x);
	vector<int> cnt(10,0);
	while(x) cnt[x%10]++,x/=10;
	for(int i = 0 ; i <= 9 ; i++)
		if(cnt[i] != t[i])
			return false;
	return true;
}

int main()
{
	init();
	//这里是一个DEBUG函数
	// for(int i = 1 ; i <= 1000000 ; i*=10) {
	//     if(!check(i))
	//         printf("ERROR:%d\n",i);
	// }
	int a,b;
	while(cin >> a >> b, a||b)
	{
		if(a>b) swap(a,b);
		auto t = ask(a,b);
		print(t);
	}
	return 0;
}

15.蒙德里安的梦想

原题链接：https://www.acwing.com/problem/content/293/

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N=12, M = 1 << N;
long long f[N][M] ;// 第一维表示列， 第二维表示所有可能的状态
bool st[M];  //存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true。
//vector<int > state[M];  //二维数组记录合法的状态
vector<vector<int>> state(M);  //两种写法等价:二维数组
int m,n;
int main()
{
	while(cin>>n>>m, n||m)  //读入n和m，并且不是两个0即合法输入就继续读入
	{
		//第一部分：预处理1
		//对于每种状态，先预处理每列不能有奇数个连续的0
		for(int i = 0; i < 1<<n; i++)
		{
			int cnt = 0 ;//记录连续的0的个数
			bool isValid = true; //某种状态没有奇数个连续的0则标记为true
			for(int j=0; j<n; j++) //遍历这一列，从上到下
			{
                //i>>j位运算，表示i（i在此处是一种状态）的二进制数的第j位； &1为判断该位是否为1，如果为1进入if
				if( i>>j & 1) 
				{
                    //这一位为1，看前面连续的0的个数，如果是奇数（cnt &1为真）则该状态不合法
					if(cnt & 1)   
					{
						isValid = false;
						break;
					}
					cnt = 0;//既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清零。//其实清不清零没有影响
				}
				else cnt++;//否则的话该位还是0，则统计连续0的计数器++。
			}
			if(cnt & 1)  isValid =false; //最下面的那一段判断一下连续的0的个数
			st[i]  = isValid; //状态i是否有奇数个连续的0的情况,输入到数组st中
		}
		//第二部分：预处理2
		// 经过上面每种状态 连续0的判断，已经筛掉一些状态。
		//下面来看进一步的判断：看第i-2列伸出来的和第i-1列伸出去的是否冲突
		for(int j = 0; j < 1<<n; j++) //对于第i列的所有状态
		{
			state[j].clear(); //清空上次操作遗留的状态，防止影响本次状态。
			for(int k = 0; k < 1<<n; k++) //对于第i-1列所有状态
			{
				if((j & k) == 0 && st[ j | k]) // 第i-2列伸出来的 和第i-1列伸出来的不冲突(不在同一行)
				//解释一下st[j | k]
				//已经知道st[]数组表示的是这一列没有连续奇数个0的情况，
				//我们要考虑是第i-1列（第i-1列是这里的主体）中从第i-2列横插过来的，还要考虑自己这一列（i-1列）横插到第i列的
				//比如 第i-2列插过来的是k=10101，第i-1列插出去到第i列的是 j =01000，
				//那么合在第i-1列，到底有多少个1呢？
                //自然想到的就是这两个操作共同的结果：两个状态或。 j | k = 01000 | 10101 = 11101
				//这个 j|k 就是当前 第i-1列的到底有几个1，即哪几行是横着放格子的
					state[j].push_back(k); //二维数组state[j]表示第j行，
				//j表示 第i列“真正”可行的状态，如果第i-1列的状态k和j不冲突则压入state数组中的第j行。
				//“真正”可行是指：既没有前后两列伸进伸出的冲突；又没有连续奇数个0。
			}
		}
		//第三部分：dp开始
		memset(f,0,sizeof f);//全部初始化为0，因为是连续读入，这里是一个清空操作。类似上面的state[j].clear()
		f[0][0]=1 ;// 这里需要回忆状态表示的定义，按定义这里是：前第-1列都摆好，且从-1列到第0列伸出来的状态为0的方案数。
		//首先，这里没有-1列，最少也是0列。其次，没有伸出来，即没有横着摆的。即这里第0列只有竖着摆这1种状态。
		for(int i = 1; i <= m; i++) //遍历每一列:第i列合法范围是(0~m-1列)
		{
			for(int j = 0; j< 1<<n; j++)//遍历当前列（第i列）所有状态j
			{
				for(auto k : state[j])//遍历第i-1列的状态k，如果“真正”可行，就转移
					f[i][j] += f[i-1][k];//当前列的方案数就等于之前的第i-1列所有状态k的累加。
			}
		}
		//最后答案是什么呢？
		//f[m][0]表示 前m-1列都处理完，并且第m-1列没有伸出来的所有方案数。
		//即整个棋盘处理完的方案数
		cout<< f[m][0] << endl;
	}
	return 0;
}

16.最短Hamilton路径

原题链接：https://www.acwing.com/problem/content/93/

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20,M = 1<<N;
int f[M][N],w[N][N];//w表示的是无权图
int main()
{
	int n;
	cin>>n;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cin>>w[i][j];

	memset(f,0x3f,sizeof(f));//因为要求最小值，所以初始化为无穷大
	f[1][0] = 0;//因为零是起点,所以f[1][0]=0;

	for(int i = 0; i < 1<<n; i++) //i表示所有的情况
		for(int j = 0; j < n; j++) //j表示走到哪一个点
			if(i>>j&1)
				for(int k = 0; k < n; k++) //k表示走到j这个点之前,以k为终点的最短距离
					if(i>>k&1)
						f[i][j] = min(f[i][j], f[i-(1<<j)][k] + w[k][j]);//更新最短距离

	cout << f[(1<<n)-1][n-1] <<endl;//表示所有点都走过了,且终点是n-1的最短距离
	//位运算的优先级低于'+'-'所以有必要的情况下要打括号
	return 0;
}

17.没有上司的舞会

原题链接：https://www.acwing.com/problem/content/287/

#include <iostream>
#include <cstdio>
using namespace std;
int dp[2][6010];//dp解释见上
int f[2][6010];//f[0]为父亲，f[1]为高兴值
int ind[6010];//入度
int vis[6010];//访问标记
int root;//树的根
void dfs(int u) //递归从后往前更新
{
	if(!u) return;
	vis[u] = 1;//已访问
	root = u;//最后一个访问到的一定是根，所以一直更新根就行了
	dp[0][f[0][u]] += max(dp[1][u] + f[1][u], dp[0][u]);//给父亲更新
	dp[1][f[0][u]] += dp[0][u];
	ind[f[0][u]]--;//更新完一个子节点
	if(!ind[f[0][u]]) dfs(f[0][u]);//在所有子节点更新后再更新（入度为0）
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &f[1][i]);
	int a,b;
	for(int i = 1; i < n; i++)
	{
		scanf("%d%d", &a, &b);
		f[0][a] = b;//保存节点信息
		ind[b]++;
	}
	for(int i = 1; i <= n; i++)
		if(!vis[i] && !ind[i])//没有被访问过，没有入度，说明是叶子节点
			dfs(i);
	printf("%d\n", max(dp[0][root],dp[1][root]+f[1][root]));//取根节点两种方案的最大值
	return 0;
}

18.滑雪

原题链接：https://www.acwing.com/problem/content/903/

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int R, C;
int arr[N][N];
int dp[N][N];
int maxlen = -1;
int addx[] = { 1,-1,0,0 };
int addy[] = { 0,0,1,-1 };
int  Dfs(int x, int y)
{
	if (dp[x][y] != 0) return dp[x][y];
	for (int i = 0; i < 4; i++)
	{
		int newx = x + addx[i];
		int newy = y + addy[i];
		if (newx >= 0 && newx < R && newy >= 0 && newy < C && arr[newx][newy] < arr[x][y])
		{
			dp[x][y] = max(dp[x][y], Dfs(newx, newy) + 1);
		}
	}
	return dp[x][y];
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> R >> C;
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> arr[i][j];
		}
	}

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			int len = Dfs(i, j);
			maxlen = max(maxlen, len);
		}
	}
	cout << maxlen + 1 << endl;
	return 0;
}

第六讲 贪心

1.区间选点

原题链接：https://www.acwing.com/problem/content/907/

//1 将每个区间按右端点从小到大排序
//2 从前往后依次枚举每个区间，如果当前区间已经包含点，则直接pass，否则，选择当前区间的右端点
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range
{
    int l,r;
    bool operator< (const Range& w) const
    {
        return r < w.r;
    }
}range[N];
int main()
{
    scanf("%d", &n);
    for(int i = 0;i < n; i++)
    {
        scanf("%d%d", &range[i].l, &range[i].r);
        //int l,r;
        //scanf("%d%d",&l,&r);
        //range[i] = {l,r};
    }
    sort(range, range + n);
    int res = 0,ed = -2e9;
    for(int i = 0;i < n; i++)
    {
        if(range[i].l > ed)
        {
            res++;
            ed = range[i].r;
        }
    }
    printf("%d\n", res);
    return 0;
}

2.最大不相交区间数量

原题链接：https://www.acwing.com/problem/content/910/

//1 将每个区间按右端点从小到大排序
//2 从前往后依次枚举每个区间，如果当前区间已经包含点，则直接pass，否则，选择当前区间的右端点
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range
{
    int l,r;
    bool operator< (const Range& w) const
    {
        return r < w.r;
    }
}range[N];
int main()
{
    scanf("%d", &n);
    for(int i = 0;i < n; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    sort(range, range + n);
    int res = 0,ed = -2e9;
    for(int i = 0;i < n; i++)
    {
        if(range[i].l > ed)
        {
            res++;
            ed = range[i].r;
        }
    }
    printf("%d\n", res);
    return 0;
}

3.区间分组

原题链接：https://www.acwing.com/activity/content/problem/content/1113/

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
using namespace std;
const int N = 100010;
int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    sort(range, range + n);

    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < n; i ++ )
    {

        if (heap.empty() || heap.top() >= range[i].l){
            heap.push(range[i].r);
        }
        else {
            heap.pop();
            heap.push(range[i].r);
        }
    }
    printf("%d\n", heap.size());
    return 0;
}

4.区间覆盖

原题链接：https://www.acwing.com/problem/content/909/

//1 将所有区间按左端点从小到大排序
//2 从前往后依次枚举每个区间，在所有能覆盖start的区间中选择右端点最大的区间
//3 选完之后将start更新成右端点的最大值
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;
const int N = 100010;
int n;
struct Range
{
    int l, r;
    bool operator<(const Range& w)
    {
        return l < w.l;
    }
}range[N];
int main()
{
    int st, ed;
    scanf("%d%d",&st, &ed);
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d%d", &range[i].l, &range[i].r);
    sort(range, range+n);
    int res = 0;
    bool success = false;
    for(int i = 0;i < n; ++i)
    {
        int j = i,r = -2e9;
        while(j < n && range[j].l <= st)
        {
            r = max(r, range[j].r);
            j++;
        }
        if(r < st)
        {
            res = -1;
            break;
        }
        res++;
        if(r >= ed) 
        {
            success = true;
            break;
        }
        st = r;
        i = j - 1;
    }
    if(!success) res = -1;
    printf("%d\n", res);
    return 0;
}

5.合并果子

原题链接：https://www.acwing.com/problem/content/150/

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    priority_queue<int, vector<int>, greater<int>> heap;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }
    int res = 0;
    while (heap.size() > 1)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
    }
    printf("%d\n", res);
    return 0;
}

6.排队打水

原题链接：https://www.acwing.com/problem/content/description/915/

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;
const int N = 100010;
int n;
int a[N];
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
    sort(a, a + n);
    long long ans = 0;
    for(int i = 0;i < n ; ++i)
    {
        ans += a[i]*(n - i - 1);
    }
    printf("%lld\n", ans);
    return 0;
}

7.货仓选址

原题链接：https://www.acwing.com/problem/content/106/

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int q[N];
int main()
{
    int n = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    sort(q, q + n);
    int i = 0,j = n - 1, sum = 0;
    while(i < j)
    {
        sum += (q[j] - q[i]);
        i++;
        j--;
    }
    printf("%d\n", sum);
    return 0;
}

8.耍杂技的牛

原题链接：https://www.acwing.com/problem/content/127/

#include <iostream>
#include <limits.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
const int N = 50010;
typedef pair<int,int> PII;
PII cows[N];
int n;
int main()
{
    scanf("%d", &n);
    for(int i = 0;i < n; ++i) 
    {
        int w,s;
        scanf("%d%d",&w, &s);
        cows[i] = {w + s, w};
    }
    sort(cows, cows+n);
    int sum = 0,res = INT_MIN;
    for(int i = 0;i < n; ++i)
    {
        int w = cows[i].second,s = cows[i].first - w;
        res = max(res, sum - s);
        sum += w;
    }
    printf("%d\n", res);
    return 0;
}