前言

这是大学生涯中的最后几个比赛之一，无论最后命运最后指向何处，现有唯有努力。

蓝桥杯，也称暴力杯，暴力搜索在其中占了很大的成分，但是在2021年加入很多数学知识和DP的内容，所以准备起来也有一定的难度。

准备的内容分为以下几块：

  1. 历年题，近3年到近5年的真题
  2. 系统知识点（递推与递归，DP，贪心）
    1. 例题
    2. 习题
  3. 模拟赛

  • 省一至少写够200道题；国奖300道题以上

  • 多调试

int -2147483648 to 2147483647

题目描述 --> 抽象出模型（在脑海中暴搜所有能用的模型）

C++ 1秒钟可以算一亿次 10810^8

编写的算法位于 107−10810^7-10^8，则是符合要求的

image-20220203224422538

递归

每一个递归，都可以画出一个与之对应的递归搜索树

二进制 数量级
2152^{15} 3276832768
2162^{16} 6553665536
2202^{20} 10610^6
2632^{63} 101810^{18}

递归实现指数型枚举

从1~n这n个整数中随机选取任意多个，输出所有可能的选择方案

时间复杂度：O(n∗2n)O(n*2^n)

指数型枚举递归搜索树 
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;
const int N = 16;
int n;
bool st[N];
vector<vector<int>> v;

void dfs(int u) {
	if (u > n) {
		vector<int> way;
		for (int i = 1; i <= n; i++)
			if (st[i]) way.push_back(i); // 记录路径
		v.push_back(way);
		return;
	}
	st[u] = true; // 选
	dfs(u+1);
	st[u] = false; // 不选
	dfs(u+1);
}
int main() {
	scanf("%d", &n);
	dfs(1);
    for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v[i].size(); j++)
			printf("%d ", v[i][j]);
		puts("");
	}
	return 0;
}

递归实现排列型枚举

1~n的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int u) {
	if (u > n) {
		for (int i = 1; i <= n; i++)
			printf("%d ", ans[i]);
		printf("\n");
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (!st[i]) {
			ans[u] = i;
			st[i] = true; // 标记访问
			dfs(u+1);
			st[i] = false; // 恢复现场
			// 这里注意区别于指数型枚举
		}
	}	
}

递归实现组合型枚举

image-20220315131348049

进行组合型枚举时，我们是按照字典序来进行，意味着枚举的前一个数一定比后一个数小，来做到不重不漏

在进行上述枚举时，还可以进行剪枝。枚举过程中我们发现，枚举到u位置时，如果剩余的数不足以凑到m就可以提前退出了，即 u−1+n−start+1<mu-1+n-start+1<m

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>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int n, m;
int way[N];
void dfs(int u, int start) {
    if (u + n - start < m) return; // 剪枝
    if (u == m + 1) {
        for (int i = 1; i <= m; i++) printf("%d ", way[i]);
        puts("");
        return;
    }
    for (int i = start; i <= n; i++) {
        way[u] = i;
        dfs(u+1, i+1);
        way[u] = 0;
    }
}
int main() {
    scanf("%d%d", &n, &m); // 从n中选m个数
    dfs(1, 1); // 从第1个位置开始枚举，从第1个数开始枚举
    return 0;
}

竞赛-空间复杂度计算64MB

根据常识，int占4B

64MB=64∗220B=64∗106B=6.4∗107B64MB=64*2^{20}B=64*10^6B=6.4*10^7B

6.4∗107B/4B=1.6∗1076.4*10^7B/4B = 1.6*10^7

因此可以开大概1.6*10的七次方的int数组

带分数-嵌套DFS

题目要求

100 可以表示为带分数的形式：100 = 3 + 69258 / 714

还可以表示为：100 = 82 + 3546 / 197

注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。

类似这样的带分数，100 有 11 种表示法。

从标准输入读入一个正整数N (N<1000*1000)
　　程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
　　注意：不要求输出每个表示，只统计有多少表示法！

例如：
用户输入：

1
100

程序输出：

1
11

解题步骤

已知该式n=a+bcn=a+\frac{b}{c}满足题目要求

  1. 枚举a
  2. 对于每一个a，枚举一个c
  3. 判断ac是否满足题意
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
62
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 40;
bool st[N], backup[N];
int n;
int ans;

bool check(int a, int c) {
	int b = c*n - c*a; // 公式
	if (!a || !b || !c) return false; // abc均不能为0
	// 备份
	memcpy(backup, st, sizeof st);
    // 分析b的组成
	while(b) {
		int x = b % 10;
		b /= 10;
        // b中不能出现0且x不存在于ac中
		if (!x || backup[x]) return false;
		backup[x] = true;
	}
	// 1-9之间的数必须全部用到
	for (int i = 1; i <= 9; i++)
		if (!backup[i]) return false;
	
	return true;
}
// 枚举c的取值
void dfs_c(int u, int a, int c) {
	if (u > 9) return; // 数字都已枚举到则退出
	if (check(a, c)) ans++; // 用ac计算出b判断是否合法，合法则方案数+1
    // 排列型枚举
	for (int i = 1; i <= 9; i++) {
		if (!st[i]) {
			st[i] = true;
			dfs_c(u+1, a, c * 10 + i);
			st[i] = false;
		}
	}
}
// 枚举a的取值
void dfs_a(int u, int a) {
    // 因为bc不能为0，所以a必须小于n
	if (a >= n) return;
	if (a) dfs_c(u, a, 0); // 剪枝，嵌套
	// 全排列枚举
	for (int i = 1; i <= 9; i++) {
		if (!st[i]) {
			st[i] = true;
			dfs_a(u+1, a * 10 + i);
			st[i] = false;
		}
	}
}
int main() {
	scanf("%d", &n);
	dfs_a(0, 0); //已经用了多少个数字，从值为0开始枚举
	cout << ans << endl;
	
	return 0;
}

递推

先算子问题，然后用子问题去回答原问题。递归的逆过程

简单斐波那契

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    int a = 0, b = 1;
    for (int i = 1; i <= n; i++) {
        cout << a << ' ';
        int fn = a + b;
        a = b, b = fn;
    }
    return 0;
}

费解的开关

开关问题的共性：

  1. 每个开关只能按一次（按偶数次相当于没按）
  2. 按的顺序无关紧要

看了几个回答，感觉写的不太清晰，这里记录一下我的理解
这道题最重要的就是要得出，最后是否能全部点亮，与点亮的先后次序无关。意思就是说，只要确定了点哪些盏灯，那么无论哪个先，都会得到相同的答案。

  • 那么递推体现在哪个地方呢？

我们只要确定了第一行的操作方式，哪些动，哪些不去动它，结果也会随之被确定下来。往后的每一行，我们只需要根据前一行对应位置的亮灭情况，来决定是否操作。
以这样的方式，最终能否被全部点亮，都会在最后一行体现出来。只需要判断最后一行是否全亮就可以得到答案
这道题有状态压缩DP那意思，进一步强化了位运算。
难点在于这个递推比较难被发现出来

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 <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6;
char g[N][N], backup[N][N];
int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0};

void turn(int x, int y) {
    for (int i = 0; i < 5; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
        
        g[a][b] ^= 1;
    }
}

int main() {
    int T;
    cin >> T;
    
    while(T--) {
        for(int i = 0; i < 5; i++) cin >> g[i];
        int res = 10;
        for (int i = 0; i < (1 << 5); i++) { // 枚举第一行所有可能的操作方法
            memcpy(backup, g, sizeof g); // 保存最初始的状态
            int step = 0; // 记录操作次数
            for (int j = 0; j < 5; j++) {
                if (i >> j & 1) {
                    turn(0, j);
                    step++;
                }
            }
            for (int i = 0; i < 4; i++) //后面的每一行中的每一格是否操作，取决于它的上一格
                for (int j = 0; j < 5; j++) {
                    if (g[i][j] == '0') {
                        turn(i+1, j);
                        step++;
                    }
                }
            bool isdark = false; // 遍历最后一行是否全亮即可得到答案
            for (int i = 0; i < 5; i++)
                if (g[4][i] == '0') isdark = true;
            
            if (!isdark) res = min(res, step);
            memcpy(g, backup, sizeof backup); // 还原成最初始的状态
        }
        if (res > 6) res = -1;
        cout << res << endl;
    }
    
    return 0;
}

原题链接->费解的开关

整数上取整

⌈ab⌉=⌊a+b−1b⌋\lceil \frac{a}{b} \rceil=\lfloor \frac{a+b-1}{b} \rfloor

(a%b+b)%b

DP

DP问题常见的几种类型：

  • 01背包为代表的组合模型，不同选法
  • 路线模型，按照不同的规则走，如摘花生，数字三角形
  • 线性模型，如最长上升子序列

前缀和

前缀和复习链接

K倍区间

给定一个长度为N的数列，A1,A2,...ANA1, A2, ... AN，
如果其中一段连续的子序列Ai,Ai+1,...Aj(i<=j)Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗？

要求子区间，很容易就会想到前缀和

另外，要使区间为K的位数，即(s[j]-s[i-1]) % k=0

也就意味着(s[j] % k = s[i-1] % k，同余

我们可以巧用一个数组来进行计数，余数作为数组的下标，来存储这个余数出现的次数。

到某一前缀和时，计算它的余数在前面出现的次数，就可以计算出K倍区间出现的次数

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>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k;
LL s[N], cnt[N];

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n;i++) {
		scanf("%d", &s[i]);
		s[i] += s[i-1];
	}
	LL res = 0; 
	cnt[0] = 1; // // 第一次遇到区间和为0时，应该直接+1，s[i]=0指的是从1到i直接就是满足条件的
	for (int i = 1; i <= n; i++) {
		res += cnt[s[i]%k]; // 这个 s[i]%k 可以和前面取模为 s[i]%k的分别构成一个k倍区间
							// 所以此时又新增了cnt[s[i]%k]个K倍区间
		cnt[s[i]%k]++;
	}
	cout << res << endl;
	
	return 0;
}

枚举优化

以下列举的均为大题，大题也是蓝桥杯获奖的关键。

暴力也能求解，但我们探究出每道问题的最佳解法

连号区间数

在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：

如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。

此题需要发现一个规律，一个区间是不是连号的，要满足如下条件：

Max-Min=区间内数的个数

即区间内的最大值减去最小值，要恰好等于区间内数的个数

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;
const int N = 5e5 + 10, INF = 1e8;
int a[N];
int ans;

int main()
{
  	int n;
  	cin >> n;
  	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  	for (int i = 0; i < n; i++) {
  		int minv = INF, maxv = -INF;
  		for (int j = i; j < n; j++) {
  			minv = min(minv, a[j]);
  			maxv = max(maxv, a[j]);
  			if (maxv - minv == j - i) ans++;
		}
	}
	cout << ans << endl;
  	
	return 0;
}

递增三元组

给定三个整数数组
　　A = [A1, A2, … AN],
　　B = [B1, B2, … BN],
　　C = [C1, C2, … CN]，
　　请你统计有多少个三元组(i, j, k) 满足：

1. 1<=i,j,k<=N1 <= i, j, k <= N
　　2. Ai<Bj<CkA_i < B_j < C_k

对于30%的数据，1 <= N <= 100
对于60%的数据，1 <= N <= 1000
对于100%的数据，1 <= N <= 100000（O(nlogn)O(nlogn)）, 0 <= Ai, Bi, Ci <= 100000

此题用前缀和，排序+二分，双指针均能求解。这里使用最为特殊的前缀和。

通过数据量得出，只能进行一重for循环

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 <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int a[N], b[N], c[N];
int s[N], cnt[N];  
int va[N]; // va[i]表示在a[]中有多少个数小于b[i]
int vc[N]; // vc[i]表示在c[]中有多少个数大于b[i]

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]), a[i]++; // 所有数加1，便于前缀和
	for (int i = 0; i < n; i++) scanf("%d", &b[i]), b[i]++;
	for (int i = 0; i < n; i++) scanf("%d", &c[i]), c[i]++;
	// 计算va[i]，代表比b[i]小的数的个数 
	for (int i = 0; i < n; i++) cnt[a[i]]++;
	for (int i = 1; i < N; i++) s[i] = s[i-1] + cnt[i];
	for (int i = 0; i < n; i++) va[i] = s[b[i]-1];
	
	memset(s, 0, sizeof s);
	memset(cnt, 0, sizeof cnt);
    // 计算vc[i]，代表比b[i]大的数的个数
	for (int i = 0; i < n; i++) cnt[c[i]]++;
	for (int i = 1; i < N; i++) s[i] = s[i-1] + cnt[i];
	for (int i = 0; i < n; i++) vc[i] = s[N-1] - s[b[i]];
	
	LL res = 0;
    // 枚举b[i]
	for (int i = 0; i < n; i++) res += (LL) va[i]*vc[i];
	cout << res << endl;
	
	return 0;
}

模拟

一个数特含某几个数(Python)

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少？

1
2
3
4
5
6
7
8
9
10
11
import os
import sys
# 请在此输入您的代码
n = int(input())
sum = 0
for i in range(1, n+1):
  for j in str(i):
    if (j in '2019'):
      sum += i
      break
print(sum)

stringstream行读入

1
2
3
4
5
6
7
8
9
10
11
12
int cnt;
cin >> cnt; // 行数
string line;
cin.get(); // 去行末回车

while (cnt--) {
    getline(cin, line); // 读入行
    stringstream ssin(line);
    while(ssin >> a[n]) { // 将stringstream对象当作cin来使用
        n++;
    }
}

回文日期处理

找出某两个日期内的回文日期，日期格式为yyyymmdd

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 <iostream>
using namespace std;
int ans;
int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// 判断给定日期的年月日是否合法
bool check_valid(int date0) {
    int year = date0 / 10000;
    int month = date0 % 10000 / 100;
    int day = date0 % 100;
    
    if (month < 1 || month > 12) return false;
    if (day == 0 || month != 2 && day > months[month]) return false;
    if (month == 2) {
        int leap = (year % 100 && year % 4 == 0) || (year % 400); // 闰年判断表达式
        if (day > months[month]+leap) return false;
    }
    return true;
}

int main() {
    int date1, date2;
    cin >> date1 >> date2;
    // 枚举所有的回文日期，用前4位生成后4位
    for (int i = 1000; i < 10000; i++) {
        int date0 = i, x = i;
        // 回文生成过程
        while(x)  date0 = date0 * 10 + x % 10, x /= 10;
        // 判断是否在给定日期范围内，判断日期是否合法
        if (date1 <= date0 && date0 <= date2 && check_valid(date0)) ans++;
    }
    cout << ans << endl;
    
    return 0;
}

时差时区 & sscanf

输入

一个输入包含多组数据。

输入第一行为一个正整数 TT，表示输入数据组数。

每组数据包含两行，第一行为去程的起降时间，第二行为回程的起降时间。

起降时间的格式如下:

  1. h1:m1:s1 h2:m2:s2
  2. h1:m1:s1 h3:m3:s3 (+1)
  3. h1:m1:s1 h4:m4:s4 (+2)

第一种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间当日h2时m2分s2秒降落。

第二种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间次日h2时m2分s2秒降落。

第三种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间第三日h2时m2分s2秒降落。

1
2
3
4
5
6
7
3
17:48:19 21:57:24
11:05:18 15:14:23
17:21:07 00:31:46 (+1)
23:02:41 16:13:20 (+1)
10:19:19 20:41:24
22:19:04 16:41:09 (+1)

输出

对于每一组数据输出一行一个时间hh:mm:ss，表示飞行时间为hh小时mm分ss秒。

注意，当时间为一位数时，要补齐前导零，如三小时四分五秒应写为03:04:05。

1
2
3
04:09:05
12:10:39
14:22:05

这道题有两个难点：

  • 从我们这去中东，计算飞行时间要减去时差；从中东回来，需要加上时差

​ (飞行时间1-时差+飞行时间2+时差)/2=(飞行时间1+飞行时间2)/2，就能够得到飞行时间

  • 第二个难点是输入有些复杂，参考y总后，使用c_str()+sscanf(char str,"%d",&n)解决
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 <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
// 将时分秒统一转换为秒
int get_seconds(int h, int m, int s) {
    return h * 3600 + m * 60 + s;
}
// 处理读入
int get_time() {
    string line;
    getline(cin, line);
    if (line.back() != ')') line += " (+0)";
    int h1, m1, s1, h2, m2, s2, d;
    sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);
    return get_seconds(h2, m2, s2) - get_seconds(h1, m1, s1) + 24 * 3600 * d;
}
int main() {
    int T;
    cin >> T;
    cin.get();
    while (T--) {
        int time = (get_time() + get_time()) / 2; // 获取两个时间的秒数
        int hh = time / 3600, mm = time % 3600 / 60, ss = time % 60;
        printf("%02d:%02d:%02d\n", hh, mm, ss);
    }
    return 0;
}

外卖店优先级

“饱了么”外卖系统中维护着 N 家外卖店，编号 1∼N。

每家外卖店都有一个优先级，初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果优先级小于等于 3，则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优先缓存中。

这道题是具有一定难度的模拟题，由于数据表示的是有订单的情况，所以我们统一在有订单的时间进行处理

每次先处理t时刻以前，用last[]记忆本店上次处理订单的时间，就能够得到应该减去的优先级

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
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
int n, m, t;
int score[N], last[N];
bool st[N];
PII order[N];
int main() {
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 0; i < m; i++) {
        int ts, td;
        scanf("%d%d", &ts, &td);
        order[i] = {ts, td};
    }
    sort(order, order+m);
    for (int i = 0; i < m;) {
        // 找出同一时间同一店铺的订单数
        int j = i;
        while(j < m && order[j] == order[i]) j++;
        int ts = order[i].x, id = order[i].y, cnt = j - i;
        i = j;
        // 处理t时刻前
        score[id] -= ts - last[id] -1;
        if (score[id] < 0) score[id] = 0; // 不能减成负数
        if (score[id] <= 3) st[id] = false;
        // t时刻
        score[id] += 2 * cnt;
        if (score[id] > 5) st[id] = true;
        last[id] = ts;
    }
    for (int i = 1; i <= n; i++) {
        if (last[i] < t) { // 如果订单上一次的处理时间小于t
            score[i] -= t - last[i]; // 处理最后一次处理时间到t这段时间里的操作
            if (score[i] <= 3) st[i] = false;
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) res += st[i];
    cout << res << endl;
    
    return 0;
}

双指针

完全二叉树的权值

给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1,A2,⋅⋅⋅ANA1,A2,⋅⋅⋅AN，如下图所示：

QQ截图20191205124611.png

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？

如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 1。

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;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int a[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    LL maxv = -1e18;
    int level;
    for (int d = 1, i = 1; i <= n; i *= 2, d++) {
        LL s = 0;
        for (int j = i; j < i + (1 << (d-1)) && j <= n; j++) s += (LL)a[j];
        if (s > maxv) 
            maxv = s, level = d;
    }
    cout << level << endl;
    
    return 0;
}

Flood Fill

洪水漫灌式搜索，与普通的dfs和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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 25;
char g[N][N];
bool st[N][N];
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs(int x, int y) {
    int res = 1;
    st[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (st[a][b]) continue;
        if (g[a][b] != '.') continue;
        res += dfs(a, b);
    }
    return res;
}

int main() {
    
    while (cin >> m >> n, n || m) {
        for (int i = 0; i < n; i++) cin >> g[i];
        int x, y;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == '@') {
                    x = i, y = j;
                    break;
                }
        memset(st, false, sizeof st);
        cout << dfs(x, y) << endl;
    }
    
    return 0;
}

置换群

交换瓶子

有 N 个瓶子，编号 1∼N，放在架子上。

比如有 5 个瓶子：

1
2 1 3 5 4

要求每次拿起 2 个瓶子，交换它们的位置。

经过若干次后，使得瓶子的序号为：

1
1 2 3 4 5

对于这么简单的情况，显然，至少需要交换 2 次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

例如第一个数为2，本来应该在第2个位置上，这时我们找到第2个位置，发现不是2是1，2和1就形成了一个群

交换的次数=瓶子个数-群数

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;
const int N = 1e4 + 10;
int n;
int b[N];
bool st[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> b[i];
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!st[i]) {
            cnt++;
            int j = i;
            while (!st[j]) {
                st[j] = true;
                j = b[j];
            }
        }
    }
    cout << n - cnt << endl;
    
    return 0;
}

贪心

数据规模 策略
106−10710^6-10^7 O(n)O(n)
10510^5 O(nlogn)O(nlogn),排序贪心
10001000 O(n2)O(n^2)
100100 O(n3)O(n^3)

重复覆盖问题

重复覆盖经典问题的优化方法：

  1. 迭代加深

糖果

糖果店的老板一共有 MM 种口味的糖果出售。

为了方便描述，我们将 MM 种口味编号 1∼M1∼M。

小明希望能品尝到所有口味的糖果。

遗憾的是老板并不单独出售糖果，而是 KK 颗一包整包出售。

幸好糖果包装上注明了其中 KK 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。

给定 NN 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

矩阵乘法求解斐波那契

利用线性代数中的矩阵乘法，求解出斐波那契数列

(fnfn+1)∗(0111)=(fn+1fn+2)\begin{pmatrix} f_n & f_{n+1} \end{pmatrix}*\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} f_{n+1} & f_{n+2} \end{pmatrix}

加上前n项和

(fnfn+1Sn)∗(010111001)=(fn+1fn+2Sn+1)\begin{pmatrix} f_n & f_{n+1} & S_n \end{pmatrix}*\begin{pmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} f_{n+1} & f_{n+2} & S_{n+1} \end{pmatrix}

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 <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 3;
int n, m;
// 1x3*3x3
void mul(int c[], int a[], int b[][N]) {
    int temp[N] = {0};
    
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;
    
    memcpy(c, temp, sizeof temp);
}
// 3x3*3x3
void mul(int c[][N], int a[][N], int b[][N]) {
    int temp[N][N] = {0};
    
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;
    
    memcpy(c, temp, sizeof temp);
}

int main() {
    scanf("%d%d", &n, &m);
    
    int f[N] = {1, 1, 1};
    int A[N][N] = {
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1},
    };
    n--;
    // 快速幂
    while (n) {
        if (n & 1) mul(f, f, A);
        mul(A, A, A);
        n >>= 1;
    }
    printf("%d\n", f[2]);
    
    return 0;
}

树状树组

可更新的前缀和

主要用处为：

  1. 给某一个位置加上一个数（单点修改）
  2. 求某一个前缀和（区间查询）

两个操作时间复杂度均为O(logn)O(logn)

x在第k层取决于其二进制末尾有k个0

lowbit(x)=x&−x=x&(∼x+1)=2klowbit(x)=x \& -x=x \&(\sim x + 1)=2^k

树状数组C[x]=(x−lowbit(x),x]=(x−2k,x]C[x] = (x-lowbit(x), x]=(x-2^k, x]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int a[N], tr[N]; // 树状数组下标从1开始存储
// 2^k
int lowbit(int x) {
    return x & -x;
}
// 单点修改，为某一个位置加上一个数，同步变化之后的值
void add(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
// 区间查询，1~x之间的和
int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

树状数组的作用：动态求连续区间和

《算法竞赛进阶指南》-谜一样的牛(树状数组+二分)

参考资料

  1. 由数据范围反推算法复杂度以及算法内容
  2. AcWing蓝桥杯C++ AB组辅导课