洛谷综合题单

试机题

三道试机题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
int main(){
 	cout<<"                ********\n";
 	cout<<"               ************\n";
	cout<<"               ####....#.\n";
 	cout<<"             #..###.....##....\n";
 	cout<<"             ###.......######              ###            ###\n";
 	cout<<"                ...........               #...#          #...#\n";
 	cout<<"               ##*#######                 #.#.#          #.#.#\n";
 	cout<<"            ####*******######             #.#.#          #.#.#\n";
 	cout<<"           ...#***.****.*###....          #...#          #...#\n";
 	cout<<"           ....**********##.....           ###            ###\n";
 	cout<<"           ....****    *****....\n";
 	cout<<"             ####        ####\n";
 	cout<<"           ######        ######\n";
 	cout<<"##############################################################\n";
 	cout<<"#...#......#.##...#......#.##...#......#.##------------------#\n";
 	cout<<"###########################################------------------#\n";
 	cout<<"#..#....#....##..#....#....##..#....#....#####################\n";
 	cout<<"##########################################    #----------#\n";
 	cout<<"#.....#......##.....#......##.....#......#    #----------#\n";
 	cout<<"##########################################    #----------#\n";
 	cout<<"#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#\n";
 	cout<<"##########################################    ############\n";
 	return 0;
}
1
2
3
4
5
6
7
8
#include <iostream>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>
using namespace std;
bool st[10];
string str;
void dfs(int x) {
	if (x == 9) {
		int a = stoi(str.substr(0, 3));
		int b = stoi(str.substr(3, 3));
		int c = stoi(str.substr(6, 3));
		if (a * 2 == b && a * 3 == c) {
			cout << a << " " << b << " " << c << endl;
		}
	}
	for (int i = 1; i < 10; i++) {
		if (!st[i]) {
			st[i] = true;
			str.push_back(i + '0');
			dfs(x + 1);
			st[i] = false;
			str.pop_back();
		}
	}
}
int main(){
	dfs(0);
	return 0;
}

入门阶段

本部分内容针对入门 OIer ，主要是语言基础内容。

从零开始

语言基础题。

1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;
int main() {
    int a, b;
	cin >> a >> b;
	int c = a * 10 + b;
	cout << c / 19; 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int main() {
    int n, a1, a2, b1, b2, c1, c2, res1, res2, res3, res;
	cin >> n >> a1 >> a2 >> b1 >> b2 >> c1 >> c2;
	if (n % a1 == 0) res1 = n / a1 * a2;
	else res1 = (n / a1 + 1) * a2;
	if (n % b1 == 0) res2 = n / b1 * b2;
	else res2 = (n / b1 + 1) * b2;
	if (n % c1 == 0) res3 = n / c1 * c2;
	else res3 = (n / c1 + 1) * c2;
	res = min(res1, min(res2, res3));
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int main() {
	int x, rem = 0;
    double res;
    for (int i = 1; i <= 12; i++) {
    	cin >> x;
    	rem = rem + 300 - x;
    	if (rem < 0) {
    		cout << -i;
    		return 0;
		} else if (rem >= 100) {
			res += (rem / 100) * 100;
			rem %= 100;
		}
	}
	cout << res * 1.2 + rem;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int main() {
	int a, b;
	int res = 0, mind = 0;
	for (int i = 1; i <= 7; i++) {
		cin >> a >> b;
		int t = min(0, 8 - a - b);
		if (mind > t) {
			res = i;
			mind = t;
		}
	}
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int main() {
	int k;
	cin >> k;
	double t;
	for (int i = 1; i < 10000000; i++) {
		t += 1.0 / i;
		if (t > k) {
			cout << i;
			break;
		}
	}
    return 0;
}

  • P1980 计数问题

  • #include <iostream>
using namespace std;
int main() {
    int n, x, res = 0;
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        int t = i;
        while (t > 0) {
            if (t % 10 == x) res++;
            t /= 10;
        }
    }
    cout << res;
    return 0;
}

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    - [P1014 Cantor表](https://www.luogu.com.cn/problem/P1014)

    ```c++
    #include <iostream>
    #include <string>
    using namespace std;
    const int N = 1000;
    string g[N][N];
    int main() {
    	int n, i = 1, j = 1, t = 1, flag = 1;
    	cin >> n;
    	while (t < n) {
    		if (flag == 1) {
    			j++;
    			flag = 2;
    		} else if (flag == 2) {
    			i++;
    			j--;
    			if(j == 1) flag = 3;
    		} else if (flag == 3) {
    			i++;
    			flag = 4;
    		} else if (flag == 4) {
    			i--;
    			j++;
    			if (i == 1) flag = 1;
    		}
    		t++;
    	}
    	cout << i << "/" << j;
        return 0;
    }

  • P1307 数字反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
	string n;
	cin >> n;
	if (n[0] == '-') {
		cout << '-';
		n = n.substr(1);
	} else if (n == "0") {
		cout << 0;
		return 0;
	}
	reverse(n.begin(), n.end());
	while (n[0] == '0') {
	    n.erase(0, 1);
	}
	cout << n;
    return 0;
}

优化

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main() {
	int n, m = 0;
	cin >> n;
	while (n) {
		m = m * 10 + n % 10;
		n /= 10;
	}
	cout << m;
    return 0;
}

数组基础

数组可以用于存储大量的信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int nums[11], n, res;
int main() {
    for (int i = 0; i < 10; i++) {
    	cin >> nums[i];
	}
	cin >> n;
	for (int i = 0; i < 10; i++) {
		if (n + 30 >= nums[i]) res++;
	}
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
bool nums[10001];
int main() {
    int n, m, l, r;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
    	cin >> l >> r;
    	for (int j = l; j <= r; j++)
    		nums[j] = true;
	}
	int res = 0;
	for (int i = 0; i <= n; i++)
		if (!nums[i]) res++;
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector<int> nums;
    int x;
    while (true) {
    	cin >> x;
    	if (x == 0) break;
    	nums.push_back(x);
	}
	reverse(nums.begin(), nums.end());
	for (auto it: nums) cout << it << " ";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <set>
using namespace std;
int nums[101];
bool st[20001];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
    	cin >> nums[i];
    	st[nums[i]] = true;
	}
	set<int> res;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (nums[i] == nums[j]) continue;
			if (st[nums[i] + nums[j]]) res.insert(nums[i] + nums[j]); 
		}
	}
	cout << res.size();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <set> 
using namespace std;
set<int> nums[1001];
int main() {
    int n, m, k, x;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
    	for (int j = 0; j < m; j++) {
    		cin >> x;
    		nums[x].insert(j);
		}
	}
	for (int i = 1; i <= k; i++) {
		cout << nums[i].size() << " ";
	}
    return 0;
}

字符串基础

字符串是特殊的数组，但它也有很多自身的特点。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <string>
using namespace std;
int main() {
	string s;
    getline(cin, s);
    int res = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != ' ' && s[i] != '\n') res++;
	} 
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main() {
	int a, b, c;
	char d, e;
	scanf("%d-%d-%d-%c", &a, &b, &c, &d);
	int t = (a + (b / 100) * 2 + (b % 100 / 10) * 3 + (b % 10) * 4 + (c / 10000) * 5 + (c % 10000 / 1000) * 6 + (c % 1000 / 100) * 7 + (c % 100 / 10) * 8 + (c % 10) * 9 ) % 11;
	if (t == 10) e = 'X';
	else e = '0' + t;
	if (d == e) cout << "Right";
	else cout << a << "-" << b << "-" << c << "-" << e;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>
using namespace std;
int main() {
	string p, s;
	cin >> p;
	getchar();
	for (int i = 0; i < p.size(); i++)
		p[i] = tolower(p[i]);
	int id = -1, cnt = 0, j = 0;
	getline(cin, s);
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == ' ') continue;
		int j = i;
		for (;j < s.size(); j++) {
			if (s[j] == ' ') break;
			s[j] = tolower(s[j]);
		}
		if (p == s.substr(i, j - i)) {
			if (id == -1) id = i;
			cnt++;
		}
		i = j;
	}
	if (id == -1) cout << id;
	else cout << cnt << " " << id;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int days[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main() {
	int date1, date2, res = 0;
	cin >> date1 >> date2;
	for (int i = 1; i <=12; i++) {
		for (int j = 1; j <= days[i]; j++) {
			int t = j % 10 * 1000 + j / 10 * 100 + i % 10 * 10 + i / 10;
			t = t * 10000 + i * 100 + j;
			if (t >= date1 && t <= date2) res++;
		}
	}
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string nums[21];
bool cmp(string a, string b) {
	return a + b > b + a;
}
int main() {
	int n;
	cin >> n;
	string a;
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	sort(nums, nums + n, cmp);
	for (int i = 0; i < n; i++) {
		cout << nums[i];
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> s, t;
int main() {
	string str;
	while(getline(cin, str)) {
		if (str == "EOF") break;
		string a;
		for (int i = 0; i < str.size(); i++) {
			if (str[i] == '<') {
				if (!a.empty()) a.pop_back();
			} else a.push_back(str[i]);
		}
		s.push_back(a);
	}
	while(getline(cin, str)) {
		if (str == "EOF") break;
		string a;
		for (int i = 0; i < str.size(); i++) {
			if (str[i] == '<') {
				if (!a.empty()) a.pop_back();
			} else a.push_back(str[i]);
		}
		t.push_back(a);
	}
	int time, cnt = 0;
	cin >> time;
	for (int i = 0; i < t.size(); i++) {
		for (int j = 0; j < min(s[i].size(), t[i].size()); j++) {
			if (s[i][j] == t[i][j]) cnt++;
		}
	}
	cout << cnt * 60 / time;
    return 0;
}

函数，递归及递推

这是初学者最难理解的部分，建议画出递归图来理解递归的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int nums[1001];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i / 2; j++) {
			nums[i] += nums[j];
		}
		nums[i]++;
	}
	cout << nums[n];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
using namespace std;
int nums[21], n, k, res;
bool st[10000001];
void dfs(int a, int start, int t) {
	if (a == k) {
		if (!st[t]) res++;
		return;
	}
	for (int i = start; i < n; i++) {
		dfs(a + 1, i + 1, t + nums[i]);
	}
}
int main() {
	cin >> n >> k;
	st[0] = st[1] = true;
	for (int i = 2; i < 10000001; i++) {
		if (!st[i]) {
			for (int j = i + i; j < 10000001; j += i)
				st[j] = true;
		}
	}
	for (int i = 0; i < n; i++)
		cin >> nums[i];
	dfs(0, 0, 0);
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
typedef long long LL;
LL dp[21][21][21];

int main() {
	for (int i = 0; i < 21; i++) {
		for (int j = 0; j < 21; j++) {
			dp[0][i][j] = dp[i][0][j] = dp[i][j][0] = 1;
		}
	}
	for (int i = 1; i < 21; i++) {
		for (int j = 1; j < 21; j++) {
			for (int k = 1; k < 21; k++) {
				if (i < j && j < k) {
					dp[i][j][k] = dp[i][j][k-1] + dp[i][j-1][k-1] - dp[i][j-1][k];
				} else {
					dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k] + dp[i-1][j][k-1] - dp[i-1][j-1][k-1];
				}
			}
		}
	}
	LL a, b, c;
	while (cin >> a >> b >> c) {
		if (a == -1 && b == -1 && c == -1) break;
		if (a <= 0 || b <= 0 || c <= 0) printf("w(%lld, %lld, %lld) = 1\n", a, b, c);
		else if (a > 20 || b > 20 || c > 20) printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, dp[20][20][20]);
		else printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, dp[a][b][c]);
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;
int main() {
	long long a, b, c;
	cin >> a >> b >> c;
	long long res = c * a + c * (c - 1) * (b - a) / 2;
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
const int MOD = 100003;
int dp[100001];
int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= k; i++) dp[i] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = i - 1; j > max(i - k - 1, 0); j--) {
			dp[i] = (dp[i] + dp[j]) % MOD;
		}
	}
	cout << dp[n];
    return 0;
}

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int n, k, res;
void dfs(int cnt, int s, int t) {
	if (cnt == k && t == n) res++;
	if (cnt == k) return;
	for (int i = s; t + i*(k - cnt) <= n; i++) {
		dfs(cnt + 1, i, t + i);
	}
}
int main() {
	cin >> n >> k;
	dfs(0, 1, 0);
	cout << res;
    return 0;
}

dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int dp[201][7];
int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		dp[i][1] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 2; j <= k; j++) {
			dp[i][j] += dp[i - 1][j - 1];
			if (i > j)
				dp[i][j] += dp[i - j][j];				
		}
	}
	cout << dp[n][k];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;
int fib[10000001];
int main() {
	int m;
	cin >> m;
	fib[0] = 0;
	fib[1] = 1;
	for (int i = 2; i < 10000001; i++) {
		fib[i] = (fib[i - 1] + fib[i - 2]) % m;
	}
	int res = 0;
	for (int i = 1; i < 10000000; i++) {
		if (fib[i] == 0 && fib[i + 1] == 1) {
			res = i;
			break;
		}
	}
	cout << res;
    return 0;
}

基础算法

这一部分的内容包含了 OI 中的基础算法，供各位巩固基础。

当然，这里面也有一些难度比较高的题目。

模拟

模拟，顾名思义就是题目要求你做什么你就做什么，这样的题目很考验选手的代码组织能力。

这里不仅仅有非常基础的模拟，也有一些非常复杂的题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int gg[100001][4];
int main() {
	int n, a, b, g, k, x, y, res = -1;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a >> b >> g >> k;
		gg[i][0] = a;
		gg[i][1] = a + g;
		gg[i][2] = b;
		gg[i][3] = b + k;
	}
	cin >> x >> y;
	for (int i = n; i > 0; i--) {
		if (x >= gg[i][0] && x <= gg[i][1] && y >= gg[i][2] && y <= gg[i][3]) {
			res = i;
			break;
		}
	}
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;
int main() {
	int n, x;
	cin >> n >> x;
	if (n == 0) {
		cout << x;
		return 0;
	}
	if (x > 1) cout << x << "x^" << n;
	else if (x == 1) cout << "x^" << n;
	else if (x == -1) cout << "-x^" << n;
	else if (x < -1) cout << x << "x^" << n;
	for (int i = n - 1; i > 1; i--) {
		cin >> x;
		if (x > 1) cout << "+" << x << "x^" << i;
		else if (x == 1) cout << "+x^" << i;
		else if (x == -1) cout << "-x^" << i;
		else if (x < -1) cout << x << "x^" << i;
	}
	cin >> x;
	if (x > 1) cout << "+" << x << "x";
	else if (x == 1) cout << "+x";
	else if (x == -1) cout << "-x";
	else if (x < -1) cout << x << "x";
	cin >> x;
	if (x > 0) cout << "+" << x;
	else if (x < 0) cout << x;
    return 0;
}

优化版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int main() {
    int n, x;
    cin >> n;
    for (int i = n; i >= 0; i--) {
        cin >> x;
        if (x) {
        	if (x > 0 && i != n) cout << "+";
	        if (abs(x) > 1 || i == 0) cout << x;
	        if (x == -1 && i) cout << "-";
	        if (i > 1) cout << "x^" << i;
	        if (i == 1) cout << "x";
		}
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;
int a[401], b[401];
int main() {
    int n, na, nb;
    cin >> n >> na >> nb;
    for (int i = 0; i < na; i++) 
    	cin >> a[i];
	for (int i = 0; i < nb; i++) 
		cin >> b[i];
	for (int i = na; i < n + na; i += na) {
		for (int j = 0; j < na; j++) 
			a[i + j] = a[j];
	}
	for (int i = nb; i < n + nb; i += nb) {
		for (int j = 0; j < nb; j++) 
			b[i + j] = b[j];
	}
	int resa = 0, resb = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] == b[i]) continue;
		if (a[i] == 0 && b[i] == 2 || a[i] == 0 && b[i] == 3 || a[i] == 1 && b[i] == 0 || a[i] == 1 && b[i] == 3 || a[i] == 2 && b[i] == 1 || a[i] == 2 && b[i] == 4 || a[i] == 3 && b[i] == 2 || a[i] == 3 && b[i] == 4 || a[i] == 4 && b[i] == 0 || a[i] == 4 && b[i] == 1)
			resa++;
		else
			resb++;
	}
	cout << resa << " " << resb << endl;
    return 0;
}

优化版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int v[5][5] = {{0, 0, 1, 1, 0}, {1, 0, 0, 1, 0}, {0, 1, 0, 0, 1}, {0, 0, 1, 0, 1}, {1, 1, 0, 0, 0}};
int a[201], b[201];
int main() {
    int n, na, nb, resa = 0, resb = 0;
    cin >> n >> na >> nb;
    for (int i = 0; i < na; i++)
    	cin >> a[i];
    for (int i = 0; i < nb; i++)
    	cin >> b[i];
    for (int i = 0; i < n; i++) {
    	resa += v[a[i % na]][b[i % nb]];
    	resb += v[b[i % nb]][a[i % na]];
	}
	cout << resa << " " << resb << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <string>
using namespace std;
struct node{
	bool flag;
	string name;
} nums[100001];
int main() {
    int n, m, a, s;
    cin >> n >> m;
    for (int i = 0; i < n; i++) 
    	cin >> nums[i].flag >> nums[i].name;
	int start = 0;
	for (int i = 0; i < m; i++) {
		cin >> a >> s;
		if (nums[start].flag ^ a) 
			start = (start + s) % n;
		else 
			start = (start - s + n) % n;
	}
	cout << nums[start].name;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
vector<pair<int, int> > res1, res2;
int main() {
	string str;
	int a = 0, b = 0, c = 0, d = 0;
	bool flag = true;
    while (flag && getline(cin, str)) {
    	for (auto ch: str) {
    		if (ch == 'W') {
    			a++;
    			c++;
    			if (a >= 11 && a - b >= 2) {
    				res1.push_back({a, b});
    				a = 0;
    				b = 0;
				}
				if (c >= 21 && c - d >= 2) {
					res2.push_back({c, d});
					c = 0;
					d = 0;
				}
			} else if (ch == 'L') {
				b++;
				d++;
				if (b >= 11 && b - a >= 2) {
					res1.push_back({a, b});
					a = 0;
					b = 0;
				}
				if (d >= 21 && d - c >= 2) {
					res2.push_back({c, d});
					c = 0;
					d = 0;
				}
			} else if (ch == 'E') {
				flag = false;
				break;
			}
		}
	}
	if (a || b) res1.push_back({a, b});
	else res1.push_back({0, 0});
	if (c || d) res2.push_back({c, d});
	else res2.push_back({0, 0});
	for (auto it: res1) 
		cout << it.first << ":" << it.second << endl;
	cout << endl;
	for (auto it: res2) 
		cout << it.first << ":" << it.second << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int main() {
	int l, r, res = 0;
	cin >> l >> r;
	for (int i = l; i <= r; i++) {
		int t = i;
		while (t > 1) {
			if (t % 10 == 2) res++;
			t /= 10;
		}
	} 
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;
int nums[40][40];
int main() {
	int n;
	cin >> n;
	nums[0][n/2] = 1;
	for (int i = 2; i <= n * n; i++) {
		bool flag = false;
		int j = 0, k = 0;
		for (j = 0; j < n; j++) {
			for (k = 0; k < n; k++) {
				if (nums[j][k] == i - 1) {
					flag = true;
					break;
				}
			}
			if (flag) break;
		}
		if (j == 0 && k != n-1) nums[n-1][k+1] = i;
		if (j != 0 && k == n-1) nums[j-1][0] = i;
		if (j == 0 && k == n-1) nums[1][k] = i;
		if (j != 0 && k != n-1) {
			if (nums[j-1][k+1]) nums[j+1][k] = i;
			else nums[j-1][k+1] = i;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << nums[i][j];
			if (j != n - 1) cout << " ";
			else cout << endl;
		}
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <string>
using namespace std;
bool st[101][256], isin[101];
int main() {
	int t, n, com;
	string O, x, y;
	char op, val;
	cin >> t;
	for (int i = 0; i < t; i++) {
		fill(st[0], st[0] + 101 * 256, false);
		fill(isin, isin + 101, false);
		bool flag = true, flag2 = true;
		cin >> n >> O;
		if (O[2] == '1') com = 0;
		else com = stoi(O.substr(4));
		int cnt = 0, maxn = 0, cur = 0;
		for (int i = 0; i < n; i++) {
			cin >> op;
			if (op == 'F') {
				cnt++;
				cin >> val >> x >> y;
				for (int j = 0; j < cnt; j++) {
					if (st[j][val]) {
						flag = false;
						break;
					}
				}
				st[cnt][val] = true;
				if (x != "n" && y == "n" ) {
					bool flag3 = true;
					cur++;
					for (int j = 0; j < cnt; j++) {
						if (isin[j]) {
							flag3 = false;
							break;
						}
					}
					if (flag3) maxn = max(maxn, cur);
				} else if (x == "n" && y != "n" || x != "n" && y != "n" && stoi(x) > stoi(y)) {
					isin[cnt] = true;
				} 
			} else if (op == 'E') {
				isin[cnt] = false;
				for (int i = 0; i < 256; i++)
					st[cnt][i] = false;
				cnt--;
				if (cnt < 0) {
					flag = false;
					cnt = 0;
				}
				cur--;
				if (cur < 0) cur = 0;
			}
		}
		if (!flag || cnt != 0) cout << "ERR" << endl;
		else if (maxn == com) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
    return 0;
}

排序算法

通过排序，我们可以将数据有序化，这让我们对数据的处理方便了很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
using namespace std;
int nums[100001];
void quick_sort(int l, int r) {
	if (l >= r) return;
	int i = l - 1, j = r + 1, t = nums[l + r >> 1];
	while (i < j) {
		do i++; while (nums[i] < t);
		do j--; while (nums[j] > t);
		if (i < j) swap(nums[i], nums[j]);
	}
	quick_sort(l, j);
	quick_sort(j + 1, r);
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) 
		cin >> nums[i];
	quick_sort(0, n - 1);
	for (int i = 0; i < n; i++)
		cout << nums[i] << " ";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <set>
using namespace std;
set<int> nums;
int main() {
	int n, x;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		nums.insert(x);
	}
	cout << nums.size() << endl;
	for (auto it: nums) 
		cout << it << " ";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
	int num, score;
} nums[5001];
bool cmp(node &a, node &b) {
	if (a.score != b.score) return a.score > b.score;
	return a.num < b.num;
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> nums[i].num >> nums[i].score;
	sort(nums, nums + n, cmp);
	int t = m * 1.5;
	while (t < n) {
		if (nums[t].score == nums[t-1].score) t++;
		else break;
	}
	cout << nums[t - 1].score << " " << t << endl;
	for (int i = 0; i < t; i++) {
		cout << nums[i].num << " " << nums[i].score << endl;
	}
	
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
struct node{
	string name;
	int score1, score2, paper, money;
	char ganbu, poor;
} nums[101];
bool cmp(const node &a, const node &b) {
	return a.money > b.money;
}
int main() {
	int n, sum = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int money = 0;
		cin >> nums[i].name >> nums[i].score1 >> nums[i].score2 >> nums[i].ganbu >> nums[i].poor >> nums[i].paper;
		if (nums[i].score1 > 80 && nums[i].paper >= 1) money += 8000;
		if (nums[i].score1 > 85 && nums[i].score2 > 80) money += 4000;
		if (nums[i].score1 > 90) money += 2000;
		if (nums[i].score1 > 85 && nums[i].poor == 'Y') money += 1000;
		if (nums[i].score2 > 80 && nums[i].ganbu == 'Y') money += 850;
		nums[i].money = money;
		sum += money;
	}
	stable_sort(nums, nums + n, cmp);
	cout << nums[0].name << "\n" << nums[0].money << "\n" << sum;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
	int num, v, score;
} nums[200001], a[100001], b[100001];
bool cmp(const node &a, const node &b) {
	if (a.score != b.score) return a.score > b.score;
	else return a.num < b.num;
}
int n;
void merge() {
	int id = 0, i = 0, j = 0;
	while (i < n && j < n) {
		if (a[i].score > b[j].score || a[i].score == b[j].score && a[i].num < b[j].num) nums[id++] = a[i++];
		else nums[id++] = b[j++];
	}
	while (i < n) nums[id++] = a[i++];
	while (j < n) nums[id++] = b[j++];
}
int main() {
	int r, q;
	scanf("%d %d %d", &n, &r, &q);
	for (int i = 0; i < 2 * n; i++) {
		scanf("%d", &nums[i].score);
		nums[i].num = i + 1;
	}
	for (int i = 0; i < 2 * n; i++)
		scanf("%d", &nums[i].v);
	sort(nums, nums + 2 * n, cmp);
	for (int i = 0; i < r; i++) {
		int t = 0;
		for (int j = 0; j < 2 * n; j += 2) {
			if (nums[j].v > nums[j+1].v) {
				nums[j].score++;
				a[t] = nums[j];
				b[t++] = nums[j+1];
			} else {
				nums[j+1].score++;
				a[t] = nums[j+1];
				b[t++] = nums[j];
			}
		}
		merge();
	}
	printf("%d", nums[q - 1].num);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
using namespace std;
int nums[500001];
long long res;
void merge_sort(int l, int r) {
	if (l >= r) return;
	int mid = l + r >> 1;
	merge_sort(l, mid);
	merge_sort(mid + 1, r);
	vector<int> t;
	int i = l, j = mid + 1;
	while (i <= mid && j <= r) {
		if (nums[i] <= nums[j]) t.push_back(nums[i++]);
		else {
			res += mid - i + 1;
			t.push_back(nums[j++]);
		}
	}
	while (i <= mid) t.push_back(nums[i++]);
	while (j <= r) t.push_back(nums[j++]);
	for (int k = l; k <= r; k++) nums[k] = t[k - l];
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	merge_sort(0, n - 1);
	cout << res;
	return 0;
}

二分答案

对一个满足单调性质的问题，我们可以采用二分答案的方法来解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
double a, b, c, d, nums[201];
double f(double x) {
	return a * x * x * x + b * x * x + c * x + d;
}
void check(double l, double r, bool flag) {
	while (r - l > 1e-6) {
		double mid = (l + r) / 2;
		if (flag) {
			if (f(mid) > 0) r = mid;
			else l = mid;
		} else {
			if (f(mid) < 0) r = mid;
			else l = mid;
		}
	}
	printf("%.2f ", l);
}
int main() {
	cin >> a >> b >> c >> d;
	double i = -100;
	bool flag = false, flag2 = true;
	if (f(-100) < 0) flag = true;
	while (i <= 100) {
		if (flag2) {
			if (f(i) * f(-100) < 0) {
				check(i - 0.5, i, flag);
				flag2 = false;
			}
		} else {
			if (f(i) * f(-100) > 0) {
				check(i - 0.5, i, !flag);
				flag2 = true;
			}
		}
		i += 0.5;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
int l, n, m, nums[50005], res;
bool check(int x) {
	int cnt = 0, now = 0;
	for (int i = 1; i <= n+1; i++) {
		if (nums[i] - nums[now] < x) cnt++;
		else now = i;
	}
	if (cnt > m) return false;
	return true;
}
int main() {
	cin >> l >> n >> m;
	for (int i = 1; i <= n; i++) cin >> nums[i];
	nums[n+1] = l;
	int i = 1, j = l;
	while (i < j) {
		int mid = i + j + 1 >> 1;
		if (check(mid)) i = mid;
		else j = mid - 1;
	}
	cout << i;
	return 0;
}

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstring>
using namespace std;
int g[1005][1005], n, m, mid, x, y;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
bool visit[1005][1005], flag;
void dfs(int a, int b) {
	if (a == n - 1) {
		flag = true;
		return;
	}
	for (int i = 0; i < 4; i++) {
		x = a + dx[i], y = b + dy[i];
		if (x >= 0 && x < n && y >= 0 && y < m && !visit[x][y] && g[x][y] <= mid) {
			visit[x][y] = true;
			dfs(x, y);
			visit[x][y] = false;
			if (flag) return;
		}
	}
}
bool check() {
	flag = false;
	memset(visit, false, sizeof(visit));
	dfs(0, 0);
	return flag;
}
int main() {
	cin >> n >> m;
	int l = 1000, r = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &g[i][j]);
			l = min(l, g[i][j]);
			r = max(r, g[i][j]);
		}
	}
	while (l < r) {
		mid = l + r >> 1;
		if (check()) r = mid;
		else l = mid + 1;
	}
	cout << r;
	return 0;
}

bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int g[1005][1005], n, m, mid, x, y;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
bool visit[1005][1005];
bool bfs() {
	memset(visit, false, sizeof(visit));
	queue<pair<int, int> > q;
	q.push({0, 0});
	while (!q.empty()) {
		int a = q.front().first, b = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			x = a + dx[i], y = b + dy[i];
			if (x >= 0 && x < n && y >= 0 && y < m && !visit[x][y] && g[x][y] <= mid) {
				q.push({x, y});
				visit[x][y] = true;
				if (x == n - 1) return true;
			}
		}
	}
	return false;
}
int main() {
	cin >> n >> m;
	int l = 1000, r = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &g[i][j]);
			l = min(l, g[i][j]);
			r = max(r, g[i][j]);
		}
	}
	while (l < r) {
		mid = l + r >> 1;
		if (bfs()) r = mid;
		else l = mid + 1;
	}
	cout << r;
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
typedef long long LL;
LL s, res = 1e12, t;
int n, m, w[200005], v[200005], sums[200005], cnts[200005], q[200005][2], mid;
bool check() {
	t = 0;
	for (int i = 1; i <= n; i++) {
		if (w[i-1] >= mid) {
			sums[i] = sums[i-1] + v[i-1];
			cnts[i] = cnts[i-1] + 1;
		} else {
			sums[i] = sums[i-1];
			cnts[i] = cnts[i-1];
		}
	}
	for (int k = 0; k < m; k++) {
		int l = q[k][0], r = q[k][1];
		t += (cnts[r] - cnts[l-1]) * (sums[r] - sums[l-1]);
	}
	res = min(res, abs(t-s));
	if (t > s) return true;
	return false;
}
int main() {
	cin >> n >> m >> s;
	for (int i = 0; i < n; i++) 
		cin >> w[i] >> v[i];
	for (int i = 0; i < m; i++) 
		cin >> q[i][0] >> q[i][1];
	int l = 1, r = 1e6;
	while (l < r) {
		mid = l + r >> 1;
		if (check()) l = mid + 1;
		else r = mid; 
	}
	cout << res << endl;
	return 0;
} 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
long long n, m, w[1000005], d[1000005], s[1000006], t[1000005], diff[1000005], nums[1000005], mid;
bool check() {
	fill(diff, diff + 1000005, 0);
	for (int i = 1; i <= mid; i++) {
		diff[s[i]] += d[i];
		diff[t[i] + 1] -= d[i];
	}
	for (int i = 1; i <= n; i++) {
		nums[i] = nums[i - 1] + diff[i];
		if (nums[i] > w[i]) return false;
	}	
	return true;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) 
		cin >> w[i];
	for (int i = 1; i <= m; i++) 
		cin >> d[i] >> s[i] >> t[i];
	int l = 1, r = n + 1;
	while (l < r) {
		mid = l + r >> 1;
		if (check()) l = mid + 1;
		else r = mid; 
	}
	if (r > n) cout << 0;
	else cout << "-1\n" << l << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
using namespace std;
typedef long long LL;
LL n, m, mid, nums[100005];
LL check() {
	LL cnt = 0, t = 0;
	for (int i = 0; i < n; i++) {
		t += nums[i];
		t = max<LL>(0, t);
		if (t >= mid) {
			t = 0;
			cnt++;
		}
	}
	return cnt;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) 
		cin >> nums[i];
	LL l = 1, r = 1e18;
	while (l < r) {
		mid = l + r >> 1;
		if (check() > m) l = mid + 1;
		else r = mid; 
	}
	mid = l;
	if (check() != m) {
		cout << -1;
		return 0;
	}
	cout << l << " ";
	r = 1e18;
	while (l < r) {
		mid = l + r + 1>> 1;
		if (check() < m) r = mid - 1;
		else l = mid; 
	}
	cout << r;
	return 0;
}

分治

分治，即分而治之，将大问题分解为小问题，分别求解，最后合并结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p) {
	LL res = 1, t = a;
	while (b) {
		if (b & 1) res = (res * t) % p;
		t = (t * t) % p;
		b >>= 1;
	}
	res %= p;
	return res;
}
int main() {
    LL a, b, p;
    cin >> a >> b >> p;
    printf("%d^%d mod %d=%d", a, b, p, qmi(a, b, p));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
void fun(int x) {
	while (x >= 1) {
    	int t = 1, cnt = 0;
    	do {
    		t *= 2;
    		cnt++;
		} while (x >= t);
		int a = cnt - 1;
		if (a == 0) cout << "2(0)";
		else if (a == 1) cout << "2";
		else {
			cout << "2(";
			fun(a);
			cout << ")";			
		}
		x -= t / 2;
		if (x != 0) cout << "+";
	}
}
int main() {
    int n;
    cin >> n;
    fun(n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
vector<vector<LL>> nums;
bool cmp(vector<LL> &a, vector<LL> &b) {
	return a[2] < b[2];
}
int main() {
    int n, a, b;
    cin >> n;
    for (int i = 0; i < n; i++) {
    	cin >> a >> b;
    	nums.push_back({a, b, a + b});
	}
	sort(nums.begin(), nums.end(), cmp);
	LL res = 1e12;
	for (int i = 1; i < n; i++) {
		for (int k = 1; k < 5; k++) {
			int j = i - k;
			if (j < 0) break;
			res = min((nums[i][0] - nums[j][0]) * (nums[i][0] - nums[j][0]) + (nums[i][1] - nums[j][1]) * (nums[i][1] - nums[j][1]), res);
		}
	}
	printf("%.4f", sqrt(res));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <string>
using namespace std;
typedef long long LL;
int main() {
    string str;
    LL n, i;
    cin >> str >> n;
    while (n > str.size()) {
    	i = str.size();
    	while (n > i) i *= 2;
    	i /= 2;
    	n -= (i + 1);
    	if (n == 0) n = i;
    	cout << n << endl;
	}
	cout << str[n - 1];
    return 0;
}

贪心

贪心，指的是决策时都采取当前最优解的算法。有的时候，这样做确实可以获得最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int, int> PII;
PII nums[5005];
int main() {
    int n, m, price, cnt;
    cin >> n >> m;
    for (int i = 0; i < m; i++) 
    	cin >> nums[i].first >> nums[i].second;
	sort(nums, nums + m);
	int res = 0, id = 0;
	while (n > 0) {
		if (n >= nums[id].second) {
			res += nums[id].first * nums[id].second;
			n -= nums[id].second;
		} else {
			res += n * nums[id].first;
			n = 0;
		}
		id++;
	}
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int nums[305];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    	cin >> nums[i];
	sort(nums, nums + n);
	LL res = 0;
	int l = 0, r = n - 1, cur = 0;
	while (l < r) {
		res += (nums[r] - cur) * (nums[r] - cur);
		cur = nums[r--];
		if (l == r) {
			res += (nums[r] - cur) * (nums[r] - cur);;
			break;
		}
		res += (nums[l] - cur) * (nums[l] - cur);
		cur = nums[l++];
		if (l == r) {
			res += (nums[l] - cur) * (nums[l] - cur);;
			break;
		}
	}
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
int nums[30005];
int main() {
    int w, n;
    cin >> w >> n;
    for (int i = 0; i < n; i++)
    	cin >> nums[i];
	sort(nums, nums + n);
	int res = 0, l = 0, r = n - 1;
	while (l <= r) {
		if (nums[r] + nums[l] > w) {
			res++;
			r--;
		} else {
			res++;
			r--;
			l++;
		}
	}
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
	int val, row, col;
} nums[250005];
bool st[505], you[505];
int res;
bool cmp(node &a, node &b) {
	return a.val < b.val;
}
void dfs(int x) {
	if (nums[x].val < res) return;
	if (you[nums[x].row] && !st[nums[x].col] || you[nums[x].col] && !st[nums[x].row]) {
		res = max(res, nums[x].val);
		return;
	}
	if (!st[nums[x].row]) {
		st[nums[x].col] = true;
		st[nums[x].row] = true;
		you[nums[x].row] = true;
		dfs(x - 1);
		st[nums[x].col] = false;
		st[nums[x].row] = false;
		you[nums[x].row] = false;
	}
	if (!st[nums[x].col]) {
		st[nums[x].row] = true;
		st[nums[x].col] = true;
		you[nums[x].col] = true;
		dfs(x - 1);
		st[nums[x].row] = false;
		st[nums[x].col] = false;
		you[nums[x].col] = false;
	}
}
int main() {
    int n, id = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	for (int j = i + 1; j <= n; j++) {
    		cin >> nums[id].val;
    		nums[id].row = i;
    		nums[id++].col = j;
		}	
	}
    sort(nums, nums + id, cmp);
    dfs(id - 1);
    cout << "1\n" << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>
using namespace std;
int n, sum[100005], q[100005], h[100005];
struct node {
	int dist, fatigue;
} v[100005];
bool cmp(node &a, node &b) {
	return a.fatigue > b.fatigue;
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) 
    	cin >> v[i].dist;	
    for (int i = 1; i <= n; i++) 
    	cin >> v[i].fatigue;
    sort(v + 1, v + 1 + n, cmp);
    for (int i = 1; i <= n; i++) 
    	sum[i] = sum[i - 1] + v[i].fatigue;
    for (int i = 1; i <= n; i++) 
    	q[i] = max(q[i - 1], 2 * v[i].dist);
    for (int i = n; i >= 1; i--)
    	h[i] = max(h[i + 1], 2 * v[i].dist + v[i].fatigue);
    for (int i = 1; i <= n; i++) 
    	cout << max(sum[i] + q[i], sum[i - 1] + h[i]) << endl;
    return 0;
}

没有用高精度（60分）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
struct node {
	int l, r;
	double t;
} v[10005];
bool cmp(node &a, node &b) {
	return a.l * a.r < b.l * b.r;
}
int main() {
    LL n, a, b;
    cin >> n >> a >> b;
    for (int i = 0; i < n; i++) {
    	cin >> v[i].l >> v[i].r;
    	v[i].t = (double)v[i].l / v[i].r;
	}
    sort(v, v + n, cmp);
    LL res = 0, cur = a;
    for (int i = 0; i < n; i++) {
    	res = max(res, (LL)a / v[i].r);
    	a *= v[i].l;
	}
	cout << res;
    return 0;
}

构造

构造题是一种形式灵活多样的题型。正是因为这个特点，使得构造题没有一种通用的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string str, res1 = "", res2 = "";
    cin >> str;
    int cnt = 0;
    for (int i = 0; i < str.size(); i++) {
    	if (str[i] == 'Z') {
    		for (int j = i + 1; j < str.size(); j++) {
    			if (str[j] != 'Z') {
    				cout << -1;
    				return 0;
				}
			}
			break;
		}
	}
	for (int i = str.size() - 1; i >= 0; i--) {
		if (str[i] == 'Z') {
			res1 += '0';
			res2 += '0';
		} else if (str[i] == 'Y') {
			res1 += '0';
			res2 += '1';
		} else if (str[i] == 'X') {
			res1 += '1';
			res2 += '0';
		}
	}
	reverse(res1.begin(), res1.end());
	reverse(res2.begin(), res2.end());
	cout << res1 << "\n" << res2;
    return 0;
}

高精度

在 C++ 中，long long 都无法表示我们需要的整数时怎么办？那就用高精度吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string a, b, c;
    cin >> a >> b;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    if (a.size() < b.size()) swap(a, b);
    int t = 0, i = 0;
    for (; i < b.size(); i++) {
    	c += ((a[i] - '0' + b[i] - '0' + t) % 10) + '0';
    	t = (a[i] - '0' + b[i] - '0' + t) / 10;
	}
	for (; i < a.size(); i++) {
		c += ((a[i] - '0' + t) % 10) + '0';
    	t = (a[i] - '0' + t) / 10;
	}
	if (t) c += '1';
	reverse(c.begin(), c.end());
	cout << c;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string a, b, c;
    cin >> a >> b;
    if (a == b) {
		cout << "0";
		return 0;
	}
    if (a.size() < b.size()) {
    	int e = b.size() - a.size();
    	for (int i = 0; i < e; i++) 
    		a = '0' + a;
	} else if (a.size() > b.size()) {
		int e = a.size() - b.size();
		for (int i = 0; i < e; i++)
			b = '0' + b;
	}
    for (int i = 0; i < a.size(); i++) {
    	if (a[i] + '0' < b[i] + '0') {
    		swap(a, b);
    		cout << "-";
    		break;
		} else if (a[i] + '0' > b[i] + '0') {
			break;
		}
	}
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());    
    int t = 0;
    for (int i = 0; i < a.size(); i++) {
    	int d = a[i] - b[i] - t;
    	if (d < 0) {
    		c += ((d + 10) % 10) + '0';
    		t = 1;
		} else {
			c += (d % 10) + '0';
			t = 0;
		}
	}
	reverse(c.begin(), c.end());
	while (c[0] == '0') c.erase(c.begin());
	cout << c;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int c[40005];
int main() {
    string a, b;
    cin >> a >> b;
    if (a[0] == '0' || b[0] == '0') {
    	cout << 0;
    	return 0;
	}
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
    int t = 0;
    for (int i = 0; i < b.size(); i++) {
    	for (int j = 0; j < a.size(); j++) {
    		c[i+j] += (a[j] - '0') * (b[i] - '0');
		}
	}
    for (int i = 0; i < a.size() + b.size() - 1; i++) {
    	c[i] += t;
    	if (c[i] >= 10) {
    		t = c[i] / 10;
    		c[i] %= 10;
		} else t = 0;
	}
	if (t) {
		c[a.size() + b.size() - 1] = t;
		for (int i = a.size() + b.size() - 1; i >= 0; i--)
			cout << c[i];
	} else {
		for (int i = a.size() + b.size() - 2; i >= 0; i--) 
			cout << c[i];
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string a, c;
    int b;
    cin >> a >> b;
    long long t = 0;
    for (int i = 0; i < a.size(); i++) {
    	t = t * 10 + a[i] - '0';
    	c += (t / b) + '0';
    	t -= t / b * b;
	}
    while (c[0] == '0') c.erase(c.begin());
    if (c.size()) cout << c;
    else cout << "0";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s[51], fac[51];
string mul(string a, int b) {
	string c;
	int t = 0;
	reverse(a.begin(), a.end());
	for (int i = 0; i < a.size(); i++) {
		int d = (a[i] - '0') * b + t;
		c += (d % 10) + '0';
		if (d >= 10) t = d / 10;
		else t = 0;
	}
	if (t) {
		string e = to_string(t);
		reverse(e.begin(), e.end());
		c += e;
	}
	reverse(c.begin(), c.end());
	return c;
}
string add(string a, string b) {
	string c;
	int t = 0, i = 0;
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	for (; i < a.size(); i++) {
		int d = a[i] - '0' + b[i] - '0' + t;
		c += (d % 10) + '0';
		if (d >= 10) t = 1;
		else t = 0;
	}
	for (; i < b.size(); i++) {
		int d = b[i] - '0' + t;
		c += (d % 10) + '0';
		if (d >= 10) t = 1;
		else t = 0;
	}
	if (t) c += '1';
	reverse(c.begin(), c.end());
	return c;
}
int main() {
    int n;
    cin >> n;
    s[1] = fac[1] = "1";
    for (int i = 2; i <= n; i++) {
    	fac[i] = mul(fac[i - 1], i);
    	s[i] = add(s[i - 1], fac[i]);
	}
	cout << s[n];
    return 0;
}

前缀和 & 差分

前缀和是一种重要的预处理，能大大降低查询的时间复杂度，而差分则是一种和前缀和相对的策略。

暴力（96分）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
typedef long long LL;
LL sums[50005];
int main() {
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	cin >> x;
    	sums[i] = sums[i - 1] + x;
	}
	int res = 0;
	for (int i = 1; i <= n - res; i++) {
		for (int j = i + res; j <= n; j++) {
			if ((sums[j] - sums[i - 1]) % 7 == 0)
				res = j - i + 1;
		}
	}
	cout << res;
    return 0;
}

技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int sums[50005], l[7], r[7];
int main() {
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	cin >> x;
    	sums[i] = (sums[i - 1] + x) % 7;
	}
	
	for (int i = n; i >= 1; i--)
		l[sums[i]] = i;
	l[0] = 0;
	for (int i = 1; i <= n; i++) 
		r[sums[i]] = i;
	int res = 0;
	for (int i = 0; i < 7; i++) 
		res = max(res, r[i] - l[i]);
	cout << res;
    return 0;
}

dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int g[105][105], dp[105][105];
int main() {
    int n, m, res = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= m; j++) {
    		cin >> g[i][j];
    		if (g[i][j] != 0) dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
    		res = max(res, dp[i][j]);
		}
	}
	cout << res;
    return 0;
}

前缀和+二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
int g[105][105] = {0}, dp[105][105];
int main() {
    int n, m, x, res = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= m; j++) {
    		cin >> x;
    		g[i][j] = g[i-1][j] + g[i][j-1] - g[i-1][j-1] + x;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int l = 0, r = min(n, m);
			while (l < r) {
				int mid = l + r + 1 >> 1;
				if (i + mid > n || j + mid > m || g[i + mid][j+mid] - g[i+mid][j] - g[i][j+mid] + g[i][j] < mid * mid) r = mid - 1;
				else l = mid;
			}
			if (g[i+r][j+r] - g[i+r][j] - g[i][j+r] + g[i][j] == r*r) res = max(res, r);
		}
	}
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int g[1005][1005], res[1005][1005];
int main() {
    int n, m, x1, y1, x2, y2;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
    	cin >> x1 >> y1 >> x2 >> y2;
    	g[x1][y1] += 1;
    	g[x2+1][y1] -= 1;
    	g[x1][y2+1] -= 1;
    	g[x2+1][y2+1] += 1;
    }
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= n; j++) {
    		g[i][j] += g[i-1][j] + g[i][j-1] - g[i-1][j-1];
    		cout << g[i][j];
    		if (j < n) cout << " ";
    		else cout << endl;
		}
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int g[5005][5005], res;
int main() {
    int n, m, x, y, v;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
    	cin >> x >> y >> v;
    	g[x+1][y+1] += v;
	}
	for (int i = 1; i < 5005; i++) {
		for (int j = 1; j < 5005; j++) 
			g[i][j] += g[i][j - 1] + g[i - 1][j] - g[i - 1][j - 1];
	}
	for (int i = m; i < 5005; i++) {
		for (int j = m; j < 5005; j++) 
			res = max(res, g[i][j] - g[i][j - m] - g[i - m][j] + g[i - m][j - m]);
	}
	cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
typedef long long LL;
int a[100005];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	cin >> a[i];
	}
	LL p = 0,  q = 0;
	for (int i = 2; i <= n; i++) {
		int c = a[i] - a[i - 1];
		if (c > 0) p += c;
		else q -= c;
	}
	LL res1 = max(p, q);
	LL res2 = abs(p - q) + 1;
	cout << res1 << "\n" << res2;
    return 0;
}

搜索

搜索其实就是高级的枚举，很多题目都可以用搜索完成。就算不能，搜索也是骗分神器。

深度优先搜索

深度优先搜索（DFS），即按照深度优先的顺序搜索的算法。

深度优先搜索一般使用栈来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
using namespace std;
bool col[14], dg[28], udg[28];
int n, cnt = 0;
vector<int> res;
void dfs(int u) {
	if (u == n) {
		if (cnt < 3) {
			for (int i = 0; i < n; i++) cout << res[i] << " ";
			cout << endl;
		}
		cnt++;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
			col[i] = dg[u + i] = udg[n - u + i] = true;
			if (cnt < 3) res.push_back(i + 1);
			dfs(u + 1);
			col[i] = dg[u + i] = udg[n - u + i] = false;
			if (cnt < 3) res.pop_back();
		}
	}
}
int main() {
	cin >> n;
	dfs(0);
	cout << cnt;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <string> 
#include <map>
using namespace std;
int n, res;
map<string, int> st;
string strs[21], str;
void dfs(string t) {
	res = max(res, (int)t.size());
	for (int i = 0; i < n; i++) {
		if (st[strs[i]] > 0) {
			int size = min(t.size(), strs[i].size());
			for (int k = 1; k < size; k++) {
				bool flag = true;
				for (int p = 1; p <= k; p++) {
					if (t[t.size() - p] != strs[i][k - p]) {
						flag = false;
						break;
					}
				}
				if (flag) {
					st[strs[i]]--;
					dfs(t + strs[i].substr(k));
					st[strs[i]]++;
					break;
				} 
			}
		}
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str;
		st[str] = 2;
		strs[i] = str;
	}
	cin >> str;
	for (int i = 0; i < n; i++) {
		if (str[0] == strs[i][0]) {
			st[strs[i]]--;
			dfs(strs[i]);
			st[strs[i]]++;
		}
	}
	cout << res;
    return 0;
}

广度优先搜索

广度优先搜索（BFS），即优先扩展浅层节点，逐渐深入的搜索算法。

广度优先搜索一般使用队列来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef pair<int, int> PII;
bool visit[32][32];
int g[32][32], n;
int dx[5] = {0, 0, 1, -1, 0};
int dy[5] = {1, -1, 0, 0, 0};
vector<PII> res;
bool bfs(int x, int y) {
	queue<PII> q;
	q.push({x, y});
	bool flag = true;
	while (!q.empty()) {
		auto u = q.front();
		q.pop();
		x = u.first, y = u.second;
		res.push_back({x, y});
		for (int i = 0; i < 5; i++) {
			int a = x + dx[i], b = y + dy[i];
			if (a >= 1 && a <= n && b >= 1 && b <= n && !visit[a][b] && g[a][b] == 0) {
				if ((a == 1 || a == n || b == 1 || b == n) && g[a][b] == 0) flag = false; 
				visit[a][b] = true;
				q.push({a, b});
			}
		}
	}
	return flag;
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> g[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (!visit[i][j] && g[i][j] == 0) {
				res.clear();
				if (bfs(i, j)) {
					for (int k = 0; k < res.size(); k++) 
						g[res[k].first][res[k].second] = 2;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) 
			cout << g[i][j] << " ";
		cout << endl;
	}
    return 0;
}

记忆化搜索

通过将已经遍历的状态记录下来，从而减少重复的搜索量，这就是记忆化搜索。

动态规划的时候，记忆化搜索也是一种高效简洁的实现方式。

搜索的剪枝

对于一些不必要搜索的部分，我们可以避免访问这些状态，从而提高搜索效率。

动态规划

动态规划是一种重要的思维方法，通过利用已有的子问题信息高效求出当前问题的最优解。

线性动态规划

线性动态规划，即具有线性阶段划分的动态规划。

背包动态规划

背包动态规划是线性动态规划中特殊的一类，NOIP中考到的次数也不少。

区间动态规划

区间动态规划一般以区间作为动态规划的阶段。

Part 4.4 树形动态规划

树形动态规划，即在树上进行的动态规划。

因为树的递归性质，树形动态规划一般都是递归求解的。

字符串

字符串问题有很多自己的特点。

字符串哈希

字符串哈希通过牺牲很小的准确率，达到快速进行字符串匹配的效果。

Part 5.2 KMP

KMP 算法可以用来解决模式串匹配问题。

数学

OI 中的数学知识很多，也有些杂乱。

位运算

将十进制整数转换为二进制后，有很多按位运算的运算符。

如果能善于利用位运算的一些性质，往往能达到事半功倍的效果。

整除相关

与整除相关的概念有很多，比较常用的有素数，最大公约数和欧拉函数。

素数

素数，指的是除 1 和它本身之外没有其他约数的数。

最大公约数

如果两个数有一个共同的约数，那么这个约数就被称为公约数。最大公约数就是指这两个数的所有公约数中，最大的一个。

求解两个数的最大公约数，可以采用欧几里得算法解决。

欧拉函数

欧拉函数 表示了小于 的数字中，与 互质的数字个数。

同余方程

求解同余方程往往可以引出不少话题。

线性同余方程&乘法逆元

线性同余方程是同余方程中最基础的内容。

中国剩余定理

中国剩余定理可以快速解一元线性同余方程组。

高次同余方程

BSGS 算法可以高效计算离散对数。

而高次剩余的求解更加复杂，其中二次剩余作为高次剩余中比较特殊的情况，可以使用 Cipolla 法求解。

博弈论

博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。

概率与期望

概率和期望是紧密相连的，OI 中往往会出现和概率期望相关的动态规划问题。

数据结构

灵活地运用数据结构可以高效地查询并处理需要的信息。

链表

在一个数列中高效插入一个元素，链表毫无疑问是最好的选择。

栈

栈，是一种后进先出（FILO）的数据结构。

队列

队列，是一种先进先出（FIFO）的数据结构。

并查集

并查集常用于处理一些不相交集合的合并和查询问题。

Part 7.5 二叉堆

二叉堆是一棵完全二叉树，堆中某个节点的值总是不大于或不小于其父节点的值。

Part 7.6 ST表

ST表可以离线查询区间最值。

Part 7.7 树状数组

树状数组是一种简洁高效的树形数据结构。

线段树

线段树的通用性比树状数组更强，可以处理更多涉及区间操作的题目。

图论

图论是数学的一个分支，它以图为研究的对象。

图的存储与遍历

这里的图论内容都比较简单，涉及图的存储以及遍历图的方式。

最短路问题

很多题目都可以转化为最短路的模型。因此，掌握最短路算法非常重要。

树上问题

作为一种特殊的图，树上的问题具有很多鲜明的特点。

二叉树

二叉树是一种特殊的树，它有很多特殊的性质。

Part 8.3.2 树的直径

树的直径被定义为树上最远的两点间的距离。

计算树的直径，可以通过两遍 DFS 解决。

公共祖先

两个点的最近公共祖先，即两个点的所有公共祖先中，离根节点最远的一个节点。

求解最近公共祖先，常用的方法是树上倍增或者树链剖分。

生成树

用 条边将图上的 个点连接起来，形成的树就被称为生成树。

拓扑排序

将一个有向无环图排序，使得所有排在前面的节点不能依赖于排在后面的节点，这就是拓扑排序。

差分约束

差分约束要解决的问题是：求出一组 元不等式的一组解，使得所有约束关系都能得到满足。

图的连通性相关

利用 Tarjan 算法，我们可以解决很多与图的连通性相关的问题。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~