蓝桥杯学习笔记（一）

Foolish-Han Lv3
  2025-03-28 23:07:28 2025-03-28 23:07:28 创建   2025-04-21 18:16:25 2025-04-21 18:16:25 更新    7.2k 字  29 分钟  

这是蓝桥杯 2023 年十四届省赛大学 A 组真题的刷题记录~

事故记录:

我们称笔记（一）的文件为，笔记（二）的文件为。

在已经完成笔记(一），准备撰写笔记(二)时，我首先创建了空文件。为了省事（懒得写文件头的 title、categories、tags 信息），我计划先把的内容复制到。但在粗心大意之下，我进行了错误的文件操作，把的内容复制到了自身而非。然后我就误把当成，删除了的正文内容并撰写了笔记（二）。这直接导致笔记（一）的内容丢失，过了很久我才发现这个问题。

为了救回我的笔记（一），我试图从谷歌云盘的备份、typora 的历史记录中去寻找，未果。于是，我不得不将部署后的静态文件进行版本回退，找回笔记（一）正常时的网页，然后将其转换为代码（这玩意还算好用），进行校正（latex 公式和代码未能有效转换），于是才有了这篇失而复得笔记（一）。

然而，事故发生时我其实是一口气写了笔记（一）的后三题和笔记（二），这导致笔记（一）的后两题并没有提交去生成静态文件，也就无从从网页进行手动恢复。悲哉！于是手动重写了笔记（一）的后三题。

这次事故给了我几个教训：

  • 莫偷懒，写个文件头不费事
  • 勤备份，源文件要版本管理

经此一役，我直接把源文件同时在 github 和服务器上进行备份

平方差-3213

输入两个整数和，输出的值。

对于所有评测数据，

最初学习 C 语言时，高精度计算的问题一直想做而没有做，这次终于借着刷题的机会给它解决掉了~

这里是把大整数封装为一个类，重载其加减乘运算符。

加减法

通过归纳总结不难发现，加减运算本质上是两种类型不同的操作

  • 对于操作数符号一致的加法和操作数符号不一致的减法，从最低位开始向较大数的最高位遍历，求和、进位
  • 对于操作数符号不一致的加法和操作数符号一致的减法，从最低位开始向被减数的最高位遍历，作差、借位
1
2
3
4
5
6
7
8
9
10
enum Sign {
	POS,
	NEG,
}; 

class MyInt {
public:
	string num;
	Sign sign;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static string add(const string& str1, const string& str2)  {
    int l = str1.length() - 1;
    int r = str2.length() - 1;
    int carry = 0;
    string res;

    while (l >= 0 || r >= 0 || carry) {
        int sum = carry;
        if (l >= 0) {
       		sum += str1[l--] - '0';
        }
        if (r >= 0) {
        	sum += str2[r--] - '0';
        }

        carry = sum / 10;
        res.push_back((sum \mod 10) + '0');
    }

    reverse(res.begin(), res.end());
    return res;
}
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
static string sub(const string& str1, const string& str2) {
    int l = str1.length() - 1;
    int r = str2.length() - 1;
    int borrow = 0;
    string res;

    while (l >= 0) {
        int diff = (str1[l] - '0') - borrow;
        if (r >= 0) {
        	diff -= (str2[r] - '0');
        	r--;
    	}

        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }

        res.push_back(diff + '0');
        l--;
    }

    while (res.length() > 1 && res.back() == '0') {
    	res.pop_back();
    }

    reverse(res.begin(), res.end());
    return res;
}

注意到，这里的减法总是默认被减数为较大的数，实际上我们可以先行以字符串的方式比较出两个数的绝对值大小，然后再决定结果的符号。字符串的比较规则如下：

对于两个字符串和：

  • 如果存在最小的使得，则当且仅当。
  • 如果是的前缀，且，则。

除此之外，在 ASCII 码中也自小到大排列，这意味着我们可以按照如下规则比较两个无符号数的大小：

  • 长度较大的数绝对值较大
  • 长度一致时，两个数的大小关系与字典序关系一致
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
MyInt operator+(const MyInt& other) const {
    MyInt result;
    if(sign == other.sign) {
        result.sign = sign;
        result.num = add(num, other.num);
    } else {
    	int tmp = num.length() - other.num.length();
        if (tmp == 0) {
            tmp = num.compare(other.num); 
        }
        if (tmp > 0) {
            result.sign = sign;
            result.num = sub(num, other.num);
        } else if (tmp < 0) {
            result.sign = other.sign;
            result.num = sub(other.num, num);
        } else {
            result.sign = POS;
            result.num = '0';
        }
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
MyInt operator-(const MyInt& other) const {
    MyInt result;
    if (sign == other.sign) {
        int tmp = num.length() - other.num.length();
        if (tmp == 0) {
            tmp = num.compare(other.num); 
        }
        if (tmp > 0) {
            result.sign = sign;
            result.num = sub(num, other.num);
        } else if (tmp < 0) {
            result.sign = (sign == POS)? NEG: POS;
            result.num = sub(other.num, num);
        } else {
            result.sign = POS;
            result.num = '0';
        }
    } else {
        result.sign = sign;
        result.num = add(num, other.num);
    }
    return result;
}

在具体实现中需要注意的是，慎重对待字符和整数混合运算的问题，切忌出现字符和字符相加的情况。

乘法

乘法实现的原理是模拟竖式计算的过程。

两个数相乘的结果的位数不会超过其位数之和，于是我们可以轻松地知道每个位置上的数相乘之后对结果的影响。我们从低位到高位遍历，累加乘积和进位到相应的位置上，最后再去除无用的前导零即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static string mul(const string& str1, const string& str2) {
    int l = str1.length();
    int r = str2.length();
    string res(l + r, '0');
    for (int i = l - 1; i >= 0; --i) {
        for (int j = r - 1; j >= 0; --j) {
            int tmp = (str1[i] - '0') * (str2[j] - '0') + (res[i + j + 1] - '0');
            res[i + j + 1] = (tmp \mod 10) + '0';
            res[i + j] += tmp / 10;
        }
    }

    auto pos = res.find_first_not_of('0');
    if (pos != string::npos) {
        return res.substr(pos);
    }
    return "0";
}

幸运数-3491

小蓝认为如果一个数含有偶数个数位，并且前面一半的数位之和等于后面一半的数位之和，则这个数是他的幸运数字。例如是一个幸运数字, 因为它有个数位, 并且。现在请你帮他计算从至之间共有多少个不同的幸运数字。

这种题只需要简单的遍历计数即可。

先计算数字的位数，再计算出每个位上的数值进行分组累加比较即可判断出是否位为幸运数。

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
bool is_lucky_number(int num) {
	int base = 1;
	int digit_cnt = 0;
	while (num / base) {
		base *= 10;
		digit_cnt++;
	}
	if ((digit_cnt & 1) == 0) {
		int sum_l = 0;
		int sum_r = 0;
		int half = digit_cnt / 2;
		
		while (digit_cnt > half) {
			sum_r += (num \mod base) / (base / 10);
			base /= 10;
			digit_cnt--;
		}
		
		while (digit_cnt > 0) {
			sum_l += (num \mod base) / (base / 10);
			base /= 10;
			digit_cnt--;
		}
		
		return sum_l == sum_r;
	}
	return false;
}

在题解中，看到了一种没有采用遍历模拟的比较高效的做法。

从幸运数的定义，数位之和入手，我们可以统计出位数中数位之和为的数字总数。由于我们仅关注一半的数位之和，所以工作量从一亿被压缩到了一万。

1
2
3
4
5
6
7
8
9
10
void count(int num, vector<vector<int>>& cnt) {
	int digit_cnt = 0;
	int sum = 0;
	while (num) {
		digit_cnt++;
		sum += num \mod 10;
		num /= 10;
	}
	cnt[digit_cnt][sum]++;
}

由于左半边一定是没有前导零的，所以我们得到的是能够囊括所有幸运数的情况的；而右半边是可以加前导零的，所以需要遍历从到实际位数的才能囊括所有情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int>> cnt(5, vector<int>(50, 0));

for (int i = 1; i < 10000; ++i) {
    count(i, cnt);
}

int sum = 0;
for (int i = 1; i <= 4; ++i) {
    for (int j = 1; j <= i; ++j) {
        for (int k = 1; k <= 9 * j; ++k) {
            sum += cnt[i][k] * cnt[j][k];
        }
    }
}
cout << sum << endl;

这种做法在运行速度上要快得多。

有奖问答-3497

小蓝正在参与一个现场问答的节目。活动中一共有道题目, 每题只有答对和答错两种情况, 每答对一题得分，答错一题分数归零。

小蓝可以在任意时刻结束答题并获得目前分数对应的奖项，之后不能再答任何题目。最高奖项需要分, 所以到达分时小蓝会直接停止答题。请注意小蓝也可能在不到分时停止答题。

已知小蓝最终实际获得了分对应的奖项, 请问小蓝所有可能的答题情况有多少种?

这题没什么难度，不过受限于思维定式，想到递归深度不过层，我就直接暴力递归了。

1
2
3
4
5
6
7
8
9
10
11
void simulate(int score, int turn) {
	if (score == 100 || turn == 31) {
		return;
	}
	
	simulate(0, turn + 1);
	simulate(score + 10, turn + 1);
	if(score == 60) {
		sum++;
	}
}

不过这毕竟是个动态规划的题，用表示第轮结束后，得分为的方案总数。则有转移方程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dp[31][11] = {0};
dp[1][0] = 1;
dp[1][1] = 1;
for (int i = 2; i <= 30; ++i) {
    for (int j = 0; j <= 9; ++j) {
        dp[i][0] += dp[i - 1][j];
    }
    for (int j = 1; j <= 10; ++j) {
        dp[i][j] = dp[i - 1][j - 1];
    }
}
for (int i = 1; i <= 30; ++i) {
    sum += dp[i][7];
}

更小的数-3503

小蓝有一个长度均为且仅由数字字符组成的字符串，下标从到，你可以将其视作是一个具有位的十进制数字，小蓝可以从中选出一段连续的子串并将子串进行反转，最多反转一次。小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字满足条件，请你帮他计算下一共有多少种不同的子串选择方案，只要两个子串在中的位置不完全相同我们就视作是不同的方案。

注意，我们允许前导零的存在，即数字的最高位可以是，这是合法的。

动态规划

看到这题，第一眼想到的是计算逆序数，准备以归并排序解决。再细看之后，面对端点相同的情况，需要收缩区间进一步考虑，于是得到了动态规划做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool dp[5005] = {false};
string num;

cin >> num;

int n = num.length();
int sum = 0;

for (int i = 1; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
        if ( (num[i] < num [j]) || (num[i] == num[j] && dp[j + 1]) ){
            dp[j] = true;
            sum++;
        } else {
            dp[j] = false;
        }
    }
}

cout << sum << endl;

颜色平衡树-3504

给定一棵树，结点由至编号，其中结点是树根。树的每个点有一个颜色。

如果一棵树中存在的每种颜色的结点个数都相同，则我们称它是一棵颜色平衡树。

求出这棵树中有多少个子树是颜色平衡树。

输入的第一行包含一个整数，表示树的结点数。

接下来行，每行包含两个整数，用一个空格分隔，表示第个结点的颜色和父亲结点编号。

特别地，输入数据保证为，也即号点没有父亲结点。

保证输入数据是一棵树。

对树一类的内容研究的少之又少，做这种题自然是只会暴力遍历的。但没有想到的是，这也能保证Missing argument for \mod80\mod的测试点不超时。

大体思路是，从根结点开始深度优先遍历。在对一个结点 node 进行搜索的时：

  1. 获取其各个子树的各个颜色数量并协同 node 自身的颜色，得到以 node 为根结点的子树的颜色分布映射 colors
  2. 遍历 colors，将每个颜色的数量添加到集合 tmp 中进行去重
  3. 若 tmp 的大小为 1，则说明以 node 为根结点的子树只有一种颜色数量，颜色平衡树的数量加一

这种做法固然直接简单，但由于每次获取以 node 为根结点的颜色分布时，都需要遍历所有的子树重构颜色分布（尽管采取了一定的空间换时间的策略），造成了较大的重复计算开销。具体而言，在每次搜索 node 结点时，还要进行相当于各个子树的颜色种类和次的操作，这导致颜色种类数与结点总数接近时会达到的复杂度。

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
struct Node {
	int color;
	vector<Node *> children;
	unordered_map<int, int> colors;
	static int cnt;
	
	Node(int c): color(c) {
		
	}
	
	void add_son(Node * son) {
		children.push_back(son);
	}
	
	void dfs() {
		colors[color] = 1;
		
		for (Node * child: children) {
			child->dfs();
			for (const auto & pair: child->colors) {
				colors[pair.first] += pair.second;
			}
			delete child;
		}
		
		set<int> tmp;
		
		for (const auto & pair: colors) {
			tmp.insert(pair.second);
		}
		
		if (tmp.size() == 1) {
			cnt++;
		}
	}
};

树上启发式合并

为了解决上面重复统计的问题，我们采用了树上启发式合并的算法。这种算法适用于数据结构为树且 每个节点的答案由其子树和其本身得到 的场景。以这道题为例

  1. 将结点 node 的子树分为一个重儿子（结点数在子树中最多）和若干个轻儿子
  2. 遍历每个轻儿子，统计其颜色平衡树数量，但不保留其颜色分布
  3. 遍历重儿子，统计其颜色平衡树数量，保留其颜色分布
  4. 再次遍历每个轻儿子，将其颜色分布累加到重儿子的颜色分布中
  5. 根据颜色分布判断以 node 为根结点的树是否为颜色平衡树

（注意，上面遍历两遍轻儿子是为了节省空间，将颜色分布存储的空间复杂度控制在）

树上启发式合并示例
树上启发式合并示例

我们把连向重儿子的边称为重边，连向轻儿子的边称为轻边。由于遍历的递归属性，每个轻儿子也会有自己的重儿子。因此，对于任一结点而言，其访问次数等于从根结点到该结点的轻边数再加一。由于轻儿子“轻”，故其规模不会超过父结点的一半。假设从根结点到某一具有个结点的子树共有条轻边，则必有，则有。

综上，则有时间复杂度。

代码如下：

首先，以的复杂度统计子树大小，找到重儿子。

1
2
3
4
5
6
7
8
9
10
void find_heavy_son(int node) {
	size_of[node] = 1;
	for (int child: children_of[node]) {
		find_heavy_son(child);
		size_of[node] += size_of[child];
		if (size_of[child] > size_of[heavy_son_of[node]]) {
			heavy_son_of[node] = child;
		}
	}	
}

接着，从根结点开始深度优先遍历。按照上面的规则，保留或删去子树的颜色分布。

关于如何判断颜色平衡，这里采用了一种巧妙的方式，即，颜色平衡等价于颜色最多的那几种颜色的数量和等于所有颜色的数量和。通过这种方式，我们可以进行动态维护而无需遍历颜色分布（由于不知道有效颜色有哪几种，所以这种方法实际上是个麻烦事儿）来判断是否达到颜色平衡。

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
void store(int node, bool record) {
	int color = color_of[node];
	num_of[color] += 1;
	if (num_of[color] > max_color_cnt) {
		max_color_cnt = num_of[color];
		max_color_sum = num_of[color];
	} else if(num_of[color] == max_color_cnt) {
		max_color_sum += max_color_cnt;
	}
	
	for (int child: children_of[node]) {
		if (child == heavy_son_of[node] && record) {
			continue;
		}
		
		store(child, false);
	}
}

void remove(int node) {
	num_of[color_of[node]] -= 1;
	for (int child: children_of[node]) {
		remove(child);
	}
}

void dfs(int node, bool record) {
	for (int child: children_of[node]) {
		if (child == heavy_son_of[node]) {
			continue;
		}
		dfs(child, false);
	}
	
	if (heavy_son_of[node]) {
		dfs(heavy_son_of[node], true);
	}
	
	store(node, true);
	
	if (max_color_sum == size_of[node]) {
		res++;		
	}
	
	if (!record) {
		max_color_cnt = 0;
		max_color_sum = 0;
		remove(node);
	}
}

买瓜-3505

小蓝正在一个瓜摊上买瓜。瓜摊上共有个瓜，每个瓜的重量为。

小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。

小蓝希望买到的瓜的重量的和恰好为。

请问小蓝至少要劈多少个瓜才能买到重量恰好为的瓜。如果无论怎样小蓝都无法得到总重恰好为的瓜，请输出。

看到这个题，最基本策略就是对每个瓜枚举不选、选择但不切半、选择且切半三种情况，从中找出能够满足重量要求且切割次数最少的那一种。的范围为也告诉我们递归深度不会太大，可以放心进行递归。但是直接进行暴力计算显然是不可取的，我们必须想办法进行剪枝来降低时间复杂度：

  1. 最基本的，如果当前总重已经超过要求，则停止递归
  2. 进一步的，如果剩余的瓜的重量已经不可能满足要求，也停止递归，这需要我们计算瓜的重量的后缀和
  3. 倘若切割次数已经多于某个已知的较小的切割次数，则停止计算。为了加快结果的收敛，我们可以对瓜的重量进行降序排序

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void dfs(int idx, int sum, int cnt) {
	if (cnt >= res) {
		return;
	}
	if (sum == m && cnt < res) {
		res = cnt;
	}
	if (idx >= n || sum >= m || sum + sum_of[idx] < m) {
		return;
	}
	dfs(idx + 1, sum + weight_of[idx], cnt);
	dfs(idx + 1, sum + weight_of[idx] / 2, cnt + 1);
	dfs(idx + 1, sum, cnt);
}

int main() {
	//...
    sort(weight_of, weight_of + n, greater<int>());	
	for (int i = n - 1; i >= 0; --i) {
		sum_of[i] = sum_of[i + 1] + weight_of[i];
	}
	dfs(0, 0, 0);
	//...
}

网络稳定性-3506

有一个局域网，由个设备和条物理连接组成，第条连接的稳定性为。

对于从设备到设备的一条经过了若干个物理连接的路径，我们记这条路径的稳定性为其经过所有连接中稳定性最低的那个。

我们记设备到设备之间通信的稳定性为至的所有可行路径的稳定性中最高的那一条。

给定局域网中的设备的物理连接情况，求出若干组设备和之间的通信稳定性。如果两台设备之间不存在任何路径，请输出。

最初看到这题时，当然是没有任何思路的。即使是尝试性地写了一些暴力枚举的算法，正确性也难以在短时间之内保证。在学习了大牛的思路之后，也算是能自己写下来了。

稀疏表

稀疏表（sparse table）用于对一系列静态数据（不改变）进行快速的查询操作。比如给定一个长度为的数组，如何快速查找任意一个区间内的最大值？

为了解决这个问题，我们首先构造一个二维数组，其中，表示区间之内的数字最大值。那么，当查询区间之间的最大值时，我们计算，则区间之间的最大值为。

为什么区间和区间就能将区间包含在内呢？我们从二进制的角度考虑，实际上就代表了区间长度中最高位的，那么两倍的就代表将最高位的左移一位，一定是大于的，故区间和区间能将区间包含在内。

为什么要用这样的表呢？因为构建时间复杂度和空间复杂度都是，而查询的时间开销为。构建的时候，我们外层循环遍历区间长度，内层循环遍历区间左端点，通过就可以构建出来。

可以看到，稀疏表起到了快速跳跃的作用，能够在数组中迅速定位到目标。

最近公共祖先

LCA (Lowest Common Ancestor) 是指一棵树中任意两个结点间深度最大的公共祖先。为了寻找 LCA，我们构造稀疏表，用表示结点的级祖先，即是的祖先且深度比小。设树共有个结点，则有，取即可。

为了寻找结点和(不妨设比深) 的 LCA，我们首先将二者调整到同一深度。设，我们按照的二进制各位依次向上跳跃，即可调整二者到同一高度。

当二者同一高度后，我们从二者的级祖先依次向下遍历，若二者的级祖先相同，则说明 LCA 的深度较大；若二者的级祖先不同，则说明二者的 LCA 的深度较小，并用二者的级祖先替代和，继续遍历。遍历结束时，与即被设置为其 LCA。

这是什么原理呢？不妨设其 LCA 与和(调整到同一高度后) 的高度差为，我们从向下遍历，就是依次去掉的最高位，最终使得高度差为 0，从而找到 LCA。

网络稳定性

铺垫了这么多，我们开始解题。

这个题的神来之笔是把图降级为树，采用 Kruskal 算法（优先选择权重最高的边）来找到图的生成树。在这个“降级”的过程中，我们如何确保不对结果产生影响？换句话说，如何保证任意两个设备间稳定性最高的路径一定在生成树中？

我们假设存在两个设备和，存在路径不在生成树中，路径在生成树中，其中的稳定性在所有路径中最高，则中必然存在一条边的权重低于中一条不在生成树中的边。根据 Kruskal 算法，但没被选中而被选中，一定是因为选中会导致回路，那么说明和之间已经存在一条路径，且稳定性不低于，这与假设相矛盾，说明稳定性最高的路径必然在生成树中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int find(int node) {
	return node == parent[node]? node: parent[node] = find(parent[node]);
} 
 
void kruskal() {
	sort(begin(edges), begin(edges) + m, [](const Edge& e1, const Edge& e2) {
		return e1.w > e2.w;	
	});
	for (int i = 0; i < m; i++) {
		auto u = edges[i].u;
		auto v = edges[i].v;
		auto w = edges[i].w;
		
		int ru = find(u);
		int rv = find(v);
		if (ru != rv) {
			parent[rv] = ru;
			adj[u].emplace_back(v, w);
			adj[v].emplace_back(u, w);
		}		
	}
}

在确定树形结构的边之后，我们需要为 LCA 准备稀疏表。对于 Kruskal 算法并查集森林中的任意一棵树，我们任选其中一个结点作为根结点开始遍历，并同时确定每个结点的深度。上面提到的稀疏表，我们要寻找区间的最值，而区间本身又是数组的索引。但对于树形结构而言，我们需要使用去记录结点的祖先结点，相当于“索引”；此外，我们还需要使用去记录“区间”的“值”。在构造和的过程中，我们根据“区间长度”从小到大开始构造，由此确保不会遗漏。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(int node, int p) {
	visited[node] = true;
	st[node][0] = p;
	depth[node] = depth[p] + 1;
	for (int i = 0; i < K; i++) {
		if (st[node][i] > 0) {
			st[node][i + 1] = st[st[node][i]][i];
			cost[node][i + 1] = min(cost[node][i], cost[st[node][i]][i]);
		}
	}
	for (auto pa: adj[node]) {
		auto son = pa.first;
		auto weight = pa.second;
		if (son != p) {
			cost[son][0] = weight;
			dfs(son, node);
		}
	}	
}

最后，我们通过寻找 LCA 来确定路径的稳定性。类似于前面稀疏表中提到的，我们实际上是要找路径这个“数组”中的最小值。我们只需要在逼近 LCA 的过程中，根据区间的最小值不断更新路径的最小值即可。

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
int lca(int x, int y) {
	if (depth[x] > depth[y]) {
		swap(x, y);
	}
	int tmp = depth[y] - depth[x];
	int ans = inf;
	for (int j = 0; tmp > 0; j++, tmp >>= 1) {
		if (tmp & 1) {
			ans = min(ans, cost[y][j]);
			y = st[y][j];
		}
	}
	
	if (x == y) {
		return ans;
	}
	
	for (int j = K; j >= 0; j--) {
		if (st[x][j] != st[y][j]) {
			ans = min(ans, min(cost[x][j], cost[y][j]));
			x = st[x][j];
			y = st[y][j];
		}
	}
	ans = min(ans, min(cost[x][0], cost[y][0]));
	return ans;
}

主函数如下

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
struct Edge {
	int u;
	int v;
	int w;
};

const int N = 1e5 + 5; // n 上限 
const int M = 3e5 + 5; // M 上限 
const int K = ceil(log2(N)); // 稀疏表宽度 
const int inf = 1e6;

int n; // 设备数 
int m; // 物理连接数 
int q; // 询问数 
int parent[N]; // 并查集中结点的父结点 
Edge edges[M];	// 初始边集 
vector<pair<int, int>> adj[N]; // 图的生成树：相邻点 + 权重 
bool visited[N];
int st[N][K + 1]; // 稀疏表
int cost[N][K + 1]; // 代价数组
int depth[N];

int main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < m; i++) {
		cin >> edges[i].u >> edges[i].v >> edges[i].w;
	} 
	kruskal();
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			dfs(i, 0);
		}
	}
	for (int i = 0; i < q; i++) {
		int x;
		int y;
		cin >> x >> y;
		if (find(x) != find(y)) {
			cout << -1 << endl;
		} else {
			cout << lca(x, y) << endl;
		}
	}
	return 0;
}

异或和之和-3507

给定一个数组，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足的，求出数组中第至第个元素的异或和。然后输出每组得到的结果加起来的值。

看到这个题时，我脑中浮现的即为动态规划。用表示从开始的个元素的异或和，即。则有转移方程。优化一下空间，则有如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - i; j++) {
			dp[j] = dp[j] ^ num[j + i];
			sum += dp[j];
		}
	}
	cout << sum << endl;
}

然而，这种方法并没有充分利用异或的性质，只能通过Missing argument for \mod90\mod的测试点。

实际上，我们可以考虑一下前缀和。我们用表示上面的，那么问题就转化为求所有的之和。我们从二进制的角度考虑一下这个问题，，那么我们的任务就是对任意的，把所有的累加起来。而仅仅取决于和的第位是否互异，同时我们统计的又是任意和的组合，那么为的组合的数量就等于数组中第位为的数量和数组中第位为的数量的乘积。

这样，我们只需要统计数组中每个二进制位和的数量即可，便有如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> num[i];
		num[i] ^= num[i - 1];
	}
	for (int i = 0; i <= K; i++) {
		for (int j = 0; j <= n; j++) {
			cnt[i][(num[j] >> i) & 1]++;	
		}
	}
	for (int i = 0; i <= K; i++) {
		sum += cnt[i][0] * cnt[i][1] * (1 << i);
	}
	cout << sum << endl;
}

时间复杂度成功控制到了。

像素放置-3508

小蓝最近迷上了一款名为《像素放置》的游戏，游戏在一个的网格棋盘上进行，棋盘含有行，每行包含个方格。玩家的任务就是需要对这个方格进行像素填充，填充颜色只有黑色或白色两种。有些方格中会出现一个整数数字，这表示当前方格加上周围八个方向上相邻的方格（分别是上方、下方、左方、右方、左上方、右上方、左下方、右下方）共九个方格内有且仅有个方格需要用黑色填充。

玩家需要在满足所有数字约束下对网格进行像素填充，请你帮助小蓝来完成。题目保证所有数据都有解并且解是唯一的。

有一说一，这个题并不难，只需要枚举每种可能性，进行深度优先遍历，并进行及时的剪枝即可。但由于边界条件控制不好，我试错了好久才把这个题拿下。

这个题的关键在于剪枝，而剪枝的关键在于：当对某个方格填充之后，能判断哪个方格上的数字无法被满足？如果我们按照从左到右，从上到下的顺序遍历，最基本的，左上角的格子（若有）可以判断出来。此外还有以下规则：

  1. 在最右下角的格子，其上方的格子（若有），其左侧的格子（若有），其自身需要判断
  2. 在最后一列，其上方的格子（若有）需要判断
  3. 在最后一行，其左侧的格子（若有）需要判断

则有如下代码：

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
63
64
65
66
bool check(int p, int q) {
	if (!(1 <= p && p <= n && 1 <= q && q <= m) || num[p][q] == '_') {
		return true;
	}
	int cnt = 0;
	for (int i = -1; i <= 1; i++) {
		for (int j = -1; j <= 1; j++) {
			cnt += res[p + i][q + j];
		}
	}
	return cnt == (num[p][q] - '0');
}


void print_res() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << res[i][j];
		}
		cout << endl;
	}
}

void dfs(int p, int q) {
	if (p > n) {
		print_res();
		return;
	}
	
	int np = p;
	int nq = q + 1;
	
	res[p][q] = 1;
	
	bool flag = check(p - 1, q - 1);
	if (p == n) {
		flag = flag && check(p, q - 1);
	}
	if (q == m) {
		np++;
		nq = 1;
		flag = flag && check(p - 1, q);
	}
	if (p == n && q == m) {
		flag = flag && check(p, q);
	}
	if (flag) {
		dfs(np, nq);
	}
	
	res[p][q] = 0;
	
	flag = check(p - 1, q - 1);
	if (p == n) {
		flag = flag && check(p, q - 1);
	}
	if (q == m) {
		flag = flag && check(p - 1, q);
	}
	if (p == n && q == m) {
		flag = flag && check(p, q);
	}
	if (flag) {
		dfs(np, nq);
	}
}

翻转硬币

给定个按顺序摆好的硬币，一开始只有第个硬币朝下，其他硬币均朝上。你每次操作可以选择任何一个整数并将所有满足的位置的硬币翻转。

求最少需要多少次操作可以让所有硬币都朝上。

看到这个题时，隐约感觉和质数有千丝万缕的关系。但看到的数据范围，便没有任何想法了。看了题解之后，更知道此题非我所能解。于是，就决定留个坑，以后再来填。

推荐阅读
蓝桥杯学习笔记（二） 蓝桥杯学习笔记（二） OS-Shell Challenge OS-Shell Challenge 力扣刷题笔记（一） 力扣刷题笔记（一）
推荐阅读
蓝桥杯学习笔记（二） 蓝桥杯学习笔记（二） OS-Shell Challenge OS-Shell Challenge
目录
蓝桥杯学习笔记（一）
  1. 1. 平方差-3213
    1. 1.1. 加减法
    2. 1.2. 乘法
  2. 2. 幸运数-3491
  3. 3. 有奖问答-3497
  4. 4. 更小的数-3503
    1. 4.1. 动态规划
  5. 5. 颜色平衡树-3504
    1. 5.1. 树上启发式合并
  6. 6. 买瓜-3505
  7. 7. 网络稳定性-3506
    1. 7.1. 稀疏表
    2. 7.2. 最近公共祖先
    3. 7.3. 网络稳定性
  8. 8. 异或和之和-3507
  9. 9. 像素放置-3508
  10. 10. 翻转硬币