Czj's Blog

第一讲-排序与枚举

发表于 更新于 分类于 ，
本文字数： 7.7k 阅读时长 ≈ 7 分钟

作业链接

[蓝桥杯] 第一讲：排序与枚举 - 题单 - 洛谷 | 计算机科学教育新生态

AC 代码

P1177 【模板】排序 - 洛谷

知识点：sort 函数

学习怎么使用 sort 将数组变为升序有序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int n, x;
const int N = 1e5+9;
int a[N];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", a + i);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
n = int(input())  # 读取整数n
a = list(map(int, input().split()))  # 读取n个整数并存储到列表a中

a.sort()  # 对列表a进行排序

# 输出排序后的结果，每个数字后跟一个空格
print(" ".join(map(str, a)))

P1271 【深基 9.例 1】选举学生会 - 洛谷

知识点：桶排序

数组下标本身就是有序的，可以根据值域考虑使用下标来实现有序化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int n, m, x;
const int N = 1e4 + 9;
int p[N];
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d", &x);
		p[x]++;
	}
	for (int i = 1; i <= n; i++) {
		while (p[i]) {
			printf("%d ", i);
			p[i]--;
		}
	}
	return 0;
}

P10901 [蓝桥杯 2024 省 C] 封闭图形个数 - 洛谷

知识点：自定义排序函数

基础的 sort 函数只能升序排列，通过手写 cmp 函数可以实现自定义的排序方法。cmp 是一种 bool 类型的函数，通过比较传入的两个值，保证相邻的 x 和 y 符合我们定义的规则。

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
#include<bits/stdc++.h>
using namespace std;
int mp[] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
int n;
const int N = 2e5+9;
int a[N];

bool cmp(int x, int y) {
	int cnt1 = 0, cnt2 = 0;
	bool flg = 0;
	if (x < y)flg = 1;
	while (x) {
		cnt1 += mp[x % 10];
		x /= 10;
	}
	while (y) {
		cnt2 += mp[y % 10];
		y /= 10;
	}
	if (cnt1 == cnt2)return flg;
	return cnt1 < cnt2;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n, cmp);
	for (int i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
	return 0;
}

P8732 [蓝桥杯 2020 国 ABC] 答疑 - 洛谷

知识点：贪心

排序往往不是单独的考点，而是作为贪心题目的实现方式。所谓贪心是将待处理的数据按照一定的顺序进行排列，贪心地处理局部最优，从而实现全局最优。要对数组排列，就需要一种满足题意的排序方式，这种方式不同于之前的题目是直接给出的，而是需要我们进行推导的。一种常见的思考方式是“微扰法”，即只考虑相邻两项在交换前和交换后的两种代价，通过假定某种代价更优，找到 cmp 函数的不等式写法。

本题中考虑相邻的学生为 则交换前两位同学的总代价为：

\[ (s_i + a_i)+(s_{i} + a_{i} + e_{i} + s_{i + 1} + a_{i + 1}) \]

交换后的总代价为：

\[ s_{i + 1} + a_{i + 1}+(s_{i + 1} + a_{i + 1} + e_{i+1} + s_{i} + a_{i}) \]

不妨假设交换前更优，则有：

\[ \begin{aligned} &(s_i + a_i)+(s_{i} + a_{i} + e_{i} + s_{i + 1} + a_{i + 1}) &<& \ s_{i + 1} + a_{i + 1}+(s_{i + 1} + a_{i + 1} + e_{i+1} + s_{i} + a_{i})\\ &2s_i + 2a_i + e_{i} + s_{i + 1} + a_{i + 1} &<& \ 2s_{i + 1} + 2a_{i + 1} + e_{i+1} + s_{i} + a_{i}\\ &s_i + a_i + e_{i} &<& \ s_{i + 1} + a_{i + 1} + e_{i+1} \end{aligned} \]

因此得到 cmp 函数的写法为将 的和较小的靠前放这一结论，这便是排序方式。

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
/*
	贪心
	要求发送消息的时刻最小，微扰法分析
	微扰：是用相邻两项进行交换从而验证两项其中的一个怎么样才会使得最后答案最优，并以此确定排序方式的方法
*/
struct node {
	ll s, a, e;
};
const int N = 1e3+9;
ll n, ans, now;
node st[N];

bool cmp(node x, node y) {
	return (x.s + x.a + x.e) < (y.s + y.a + y.e);
}
int main() {
	// 显然谁的总耗时更长谁应该更晚进入
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> st[i].s >> st[i].a >> st[i].e;
	}
	sort(st, st + n, cmp);
	for (int i = 0; i < n; i++) {
		ans += now + st[i].s + st[i].a;// 第 i 位同学发送消息的时刻不包括 st[i].e
		now += st[i].s + st[i].a + st[i].e;
	}
	cout<<ans;
	return 0;
}

B3623 枚举排列（递归实现排列型枚举） - 洛谷

知识点：深搜枚举集合，next_permutation 与去重

深搜过程以 \(n=3,k=2\) 举例：

img

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 <bits/stdc++.h>
using namespace std;
int n, k;
vector<int> ans;
bool vis[20];
void dfs() {
	if ((int)ans.size() == k) {
		for (auto t : ans) {
			cout << t << ' ';
		}
		puts("");
	}
	for (int i = 1; i <= n; i++) {// 此处顺序枚举保证了字典序
		if (vis[i] == 0) {
			vis[i] = 1;
			ans.push_back(i);
			dfs();
			ans.pop_back();
			vis[i] = 0;
		}
	}
}
int main() {
	cin >> n >> k;
	dfs();
	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<bits/stdc++.h>

using namespace std;

unordered_set<string> s;// 去重

int main() {
	int n, k;
	cin >> n >> k;

	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		a[i] = i + 1; // 初始化数组为1到n
	}

	do {
		vector<int> tmp(a.begin(), a.begin() + k); // 截取前 k 个数字
		string str;
		for (auto t : tmp) {
			str += t + '0';
		}
		if (s.count(str))continue;
		s.insert(str);
		for (auto t : tmp) {
			cout << t << " ";
		}
		cout << endl;
	} while (next_permutation(a.begin(), a.end())); // 生成下一个排列

	return 0;

P8599 [蓝桥杯 2013 省 B] 带分数 - 洛谷

知识点：next_permutation 用法，字符串划分，字符串转数字

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<bits/stdc++.h>
using namespace std;
using ll = long long;// 最大可表示 10^16
int ans, len;
ll n;
string s;
/*
	n = a + b/c <-> n * c = a * c + b
*/
ll str_to_num(int l,int r)// 左闭右闭
{
	ll ans = 0;
	for(int i = l;i<=r;i++)
	{
		// 左侧高位写法
		ans = ans*10+(s[i]-'0');
	}
	return ans;
}

void check() {
	// 对每个情况都切出三个数字，因此只需要两个标记，但要保证有三个数字
	for (int i = 0; i < len - 2; i++) {
		for (int j = i + 1; j < len - 1; j++) {
			long long a = str_to_num(0,i), b = str_to_num(i+1,j), c = str_to_num(j+1,len-1);
			if ( n * c == a * c + b)ans++;
		}
	}
}

int main() {
	cin >> n;
	s = "123456789";
	len = s.size();
	do {
		check();
	} while (next_permutation(s.begin(), s.end()));
	cout << ans;
	return 0;
}

P10385 [蓝桥杯 2024 省 A] 艺术与篮球 - 洛谷

知识点：c++ 手写日历，python 日期相关模块的使用

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;// 最大可表示 10^16
// 字符向数字映射
int mp[] = {13, 1, 2, 3, 5, 4, 4, 2, 2, 2}, ans = 0;
int y = 2000, m = 1, d = 1;
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 闰年闰月判断
int add() {
	return (m==2) && ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0);
}

bool check(int a, int b, int c) {
	int tmp = 0;
	for (int i = 0; i < 4; i++) {
		tmp += mp[a % 10];
		a /= 10;
	}
	for (int i = 0; i < 2; i++) {
		tmp += mp[b % 10];
		b /= 10;
	}
	for (int i = 0; i < 2; i++) {
		tmp += mp[c % 10];
		c /= 10;
	}
	return tmp > 50;
}

int main() {
	while (1) {
		if (check(y, m, d))ans++;
		if (y == 2024 && m == 4 && d == 13) {
			break;
		}
		// 日期变化
		d++;
		if(d>day[m]+add())
		{
			d = 1;
			m++;
			if(m>12)
			{
				m = 1;
				y++;
			}
		}

	}
	cout << ans;
	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
from datetime import datetime, timedelta

# 定义映射数组
mp = [13, 1, 2, 3, 5, 4, 4, 2, 2, 2]

# 定义检查函数
def check(y, m, d):
    tmp = 0
    for digit in str(y):// 转化为字符串后逐个映射
        tmp += mp[int(digit)]
    for digit in str(m).zfill(2):// 对字符串零填充
        tmp += mp[int(digit)]
    for digit in str(d).zfill(2):
        tmp += mp[int(digit)]
    return tmp > 50

# 初始化起始日期和结束日期
start_date = datetime(2000, 1, 1)
end_date = datetime(2024, 4, 13)

# 初始化答案计数
ans = 0

# 遍历日期
current_date = start_date
while current_date <= end_date:
    if check(current_date.year, current_date.month, current_date.day):
        ans += 1
    current_date += timedelta(days=1)// 更新日期

print(ans)

P8772 [蓝桥杯 2022 省 A] 求和 - 洛谷

知识点：前缀和、推式子

原始式子为：

\[ S = a_1(a_2 + a_3 + \cdots + a_n) + a_2(a_3 + \cdots + a_n) + \cdots + a_{n - 1}a_n \]

如果暴力求每一项，则总的时间复杂度为 。

观察到每一项乘积其实是 \(a_i\) 与 \(\sum_{k=1}^n a_k - \sum_{k=1}^i a_k\) 的积，而此处的求和式子可以用前缀和维护从而避免每次都循环计算，将求每项的复杂度从 降为 。推导出新的式子为：

\[ S = \sum_{i = 1}^{n}\left( a_{i} \times (\sum_{k = 1}^{n} a_{k} - \sum_{k = 1}^{i} a_{k})\right) \]

新式子的时间复杂度为外层求和，即

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N  = 2e5+9;
int n;
ll a[N],s[N];
ll ans;
int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
        if(i==1) s[i] = a[i];
        else s[i] += s[i-1]+a[i];
    }
    ll sum = s[n];//所有数的和
    for(int i = 1;i<=n;i++)
    {
        ans += a[i]*(sum - s[i]);
    }
    cout<<ans<<endl;
    return 0;
}

P8708 [蓝桥杯 2020 省 A1] 整数小拼接 - 洛谷

知识点：双指针

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// 双指针

ll n, k;

const int N = 1e5+9;

ll a[N], ans;

bool check(int i, int j) {
	// 库函数实现数字拼接
	//	return stoll(to_string(a[i])+to_string(a[j]))<=k;

	// 手写
	ll x = a[i], y = a[j];
	while (y) {
		x *= 10, y /= 10; // x 前移给 y 留出位置
	}
	return x + a[j] <= k;
}

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

	// 先保证有序
	sort(a + 1, a + 1 + n);

	int l = 1, r = n; // 双指针

	while (l < r) { // 不能是同一个数
		if (check(l, r)) {
			// 合法，说明这个 l 之后（l+1）到 r 的数字按照 l,r 的顺序拼接都合法
			ans += r - l;
			l++;// 左边界移动
		} else r--;
	}

	// 注意反向拼接也合法
	l = 1, r = n;// 重新赋值

	while (l < r) {
		if (check(r, l)) { // 只需要交换拼接的方式
			ans += r - l;
			l++;
		} else r--;
	}
	cout << ans;
	return 0;
}