2022年本校寒假第二次蓝桥杯进阶培训题解
前言：
题目地址： https://vjudge.net/contest/481606
本页基于何大佬写的题解进行讲解，当然也会说我的一些与何学长不同的做法（大概思路都一样）
何大佬的题解：https://dour-truck-e2f.notion.site/data-structures-puls-puls-f08adddfaf554332a8382536db07b87d
A. 自动机
这道题题意就是给你几个条件, 比如:
- x1 = x2, x2 = x3, x3 = x4, x4 ≠ x1
x1 = x2, x2 = x3, x3 ≠ x4, x3 = x1
请问上面那个样例的逻辑是正确的，那个是错误的，
逻辑正确打印yes，错误打印no提示： 数据范围： 有n个逻辑 (n ∈ [1, 1e6]), 每一个逻辑的变量数据范围是[1, 1e9]
很明显这道题应该使用并查集, 但是需要思考一下，是不是按照输入的顺序一个一个来？还有就是这个数据范围太大了，如果规规矩矩的使用并查集，你的数组肯定要爆掉！（离散）显然，我们应该优先合并逻辑相等的，处理完后再去查询逻辑不同的
在逻辑不等于中，如果找到一个 a 与 b 的根是同一个，那么必然逻辑错误，直接跳出循环打印
否则逻辑正确
附上并查集模板代码：int find(int x) {
if (f[x] == x) return x;
return f[x] = find(f[x]);
}
bool some(int x, int y) {
return find(x) == find(y);
}
void merge(int x, int y) {
int _1 = find(x);
int _2 = find(y);
if (_1 != _2) f[_1] = _2;
}
B. 复写纸
题意：给你两个初始化好了的图，编号一样，只是边不同，你可以在这两个图中随意连接节点， 但是在其中一个图中连接后(a - b)， 那么在另外一个图中也要连接(a - b), 那么请问，在不导致两个图自环的情况下，最多能连多少条这样的边，并打印出来
个人分析：
- 数据范围较小，不用考虑开long long的情况，(数据范围：1000， 时间限制： 1s) => 允许o(n^2)算法
- 看似是图论问题，实际上其实是并查集的使用
- 我们将两个图分别转换为两个并查集，因为允许o(n^2), 所以我们直接暴力即可
C. 密码
题意： 给你一个密码列表，对于两个密码，具有等价性规则：
1、两个密码存在相同的一个字母就视为等价( abcdd <=> agjk)
2、如果两个密码a, b之间存在密码c 使得 a <=> c, b <=> c, 那么 a <=> b
请问最少有多少个密码，使得包含所有密码都等价
个人分析：
+ 数据范围：密码列表长度 => [1, 2* 1e5]; 对于单个密码长度不超过50, 时限：1s => o(nlogn)
+ 非常明显的并查集算法，主要是对于字符串的处理, 单论路径压缩的并查集时间复杂度为o(log*n)
if n <= 1 : log* n = 0;
else log* n = 1 + log*(logn)
非常明显是要比o(logn)还要快，近似等于o(1), 但是比o(1)慢点
+ 因为题目中说道只要存在同一个字母相同，则视为等价，那么我们可以直接遍历字符串即可
+ 题目中问的问题就是问我们有多少个并查集的根
核心代码如下：
for (int i = 0; i < n; i ++ ) {
if (s[i].length() == 1) continue; // 根
for (int j = 1; j < s[i].length(); j ++ ) {
merge(s[i][j] - 'a' + 1, s[i][0] - 'a' + 1); // 将字符串后面的所有字母，合并到第一个字母上
}
}
int ans = 0;
for (int i = 0; i < n; i ++ ) {
int m = find(s[i][0] - 'a' + 1);
if (vis[m]) continue; // 标记这个集合我已经查过了
vis[m] = true;
ans ++;
}
printf("%d\n", ans);
D.操作树
题意：给你一个数组，该数组如果满足以下要求，则满足题意
- 有且只有一个索引, 符合 pr = r， 其中顶点r是树的根
- 对于剩下的n-1个顶点表示为 连接(i - pi)这条边
现在可以修改数组中的值，请问最少修改多少次，可以满足题意
个人思路(WA了五六次, 没有解决好自环的情况 直接去看何带佬写的思路吧)
E.谎言
我还暂时没做，直接去看何带佬的题解吧。
F. 整数问题
题目：
小明给出了一个序列，需要你帮他处理如下两种询问。
“C a b c”表示给 [a,b] 区间中的值全部增加c∈[-1e4, 1e4]
“Q a b” 询问[a, b][a,b] 区间中所有值的和。
数据范围和时限只允许我们最高只用o(nlogn) 不超过o(n^2)应该都可以
个人分析：
- 题目已经非常明显了，懂得都懂,模板题，会的可以直接跳过了，如果对线段树不了解的可以往下看看
- 我们知道，对于一个数组，我们如果直接查询数组中 [l, r] 的总和，可以利用前缀和的思想
而对于要让数组中 [l, r] 的元素全部加上一个数，我们可以利用差分的思想
先简单讲一下前缀和、差分吧：
前缀和的意思是，An是源数据，Sn是前n项和
就是把一个数列的全部前n项和存下来， 查询的时候直接查sn就可以了， 不需要再去一个一个加an
求 [l, r]的和
=> s[r] - s[l - 1]
=> a[1] + ... + a[r] - (a[1] + ... + a[l - 1])
=> a[l] + ... + a[r]
而差分的意思是，An是源数据，也是Cn的前n项和
那么就是说，构造一个数列使得源数据是该数列的前n项和
An的[l, r]区间全部 +1， 是不是就是C[l]这个元素 +1， 也就对应了An [l，+无穷) +1
然后再C[r +1] - 1， 那就对应了An[r +1，+无穷) -1
那么这两个操作下来，对应的就是，An[l, r] 区间+1， 最后再遍历Cn就可以还原An了对于前缀和的时间复杂度来说：查询是o(1), 但是更新是o(n);
而对于差分来说： 更新是o(1), 查询是o(n);
显然这对于本题来说就非常不又好了，所以引入一个新的知识点：线段树
对于每一个操作，线段树的更新和查询的时间复杂度都是o(logn)， 所以总体上的时间复杂度是o(nlogn)，允许范围内
具体详情可以参考一下这篇博客线段树详解 - Xenny - 博客园
G. 区间
大概题意： 给定一个区间 [1, n]，以及 m 个操作,每个操作有 a, b, c 三个数，对于每个操作要实现： [a, b] 里面选 c 个数(以及被选了的不能重复被选), 请问最少可以选多少个数.
数据范围：n <= 100, m <= 500, a, b, c <= n; 时限: 1s => 所以可以运行我们使用o(n^2)直接暴力枚举
但是要在贪心的一个思想上来做这道题，我们按照右边界进行升序排序，优先选右边的数
那么第 i 个的左边界如果比第 i - 1 个的右边界小 (区间重合)， 那么我们必然能拿到第i - 1个区间中的数，并且为了保证我们能拿到最多，所以我们从右到左，以此选择，
而整个程序的复杂度分析：
sort 对数组排序 o(nlogn)
枚举每一个区间 n, 对每一个区间进行c次循环, 因为c <= n 所以复杂度为 o(n^2)
综上所述，总体时间复杂度为o(n^2);
H. 加强数据版区间 (G题利用线段树的思想来解决)
更新一个区间的值需要o(logn), 查询一个区间的值需要o(logn),
我们只需要在G题贪心的思想上，优化对每个区间进行c此循环优化，使其 n 降为 logn 就可以了
先查询前面已经选了x个了，然后在从剩下可以选的数中选择c-x个 => query + update
那么总体上就时间复杂度就是=> o(nlogn + 2nlogn) = o(nlogn)
I.颜色
小明现在有 n 家买染料的店铺,分别是 a1, a2, …, an ,最开始它们的收益为 0 并且颜色编号 1. 现在你实现小明的 q 个操作, 操作如下:
- Color l r c: 第al,al+1,…ar家店铺更改为售卖染料颜色为 c的染料.
- Add c x: 当前颜色为c的所以染料店铺增加 x 的收入
- Query i: 询问店铺ai的收入.
废话不多说，建议直接看何带佬的题解，我在下面放下我个人对带佬的代码的一个翻译代码(有注释)
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
ll tree[4 * N], c[4 * N], col[N], n, m;
/*
tree 收益
c当前节点的颜色
col 所有颜色对应的收益
*/
bool vis[4 * N]; // vis[i] 表示 第 i个节点的左右孩子是否为同一个颜色
int l_node(int node) {
return 2 * node;
}
int r_node(int node) {
return l_node(node) + 1;
}
void push_down(int node, int lNode, int rNode) {
/*
如果当前节点的左右孩子是同一个颜色
那么
左孩子的收益和右孩子的收益分别加上父节点的收益，
因为非叶子节点是不像标准线段树，是要存[l, r]的总和的
因为可能会存在左右节点不是同一个颜色，那么这时候存总和的话，就完全没有意义
然后将更新后的颜色赋值给左右孩子(lazy),
颜色只有一个状态，不能存在累加情况
*/
if (vis[node]) {
tree[lNode] += tree[node];
tree[rNode] += tree[node];
c[lNode] = c[rNode] = c[node];
tree[node] = 0;
}
}
void push_up(int node, int lNode, int rNode) {
/*
如果左孩子和右孩子的颜色相同，并且左右孩子的子节点也是相同颜色的(前面说过，可能会存在不是一样的)
*/
if (c[lNode] == c[rNode] && vis[lNode] && vis[rNode]) {
vis[node] = true; // 标记该节点的左右孩子是同一个节点
c[node] = c[lNode]; // 更新父节点为子节点的颜色(因为左右节点颜色相同)
} else vis[node] = false; // 如果上面条件不满足，那么左右节点颜色必定不同
}
void build(int node, int L, int R) {
vis[node] = true; // 最开始每一个元素都是的左右孩子都是同一个颜色
c[node] = 1; // 最开始都是颜色1
if (L != R) {
int mid = (L + R) >> 1;
build(l_node(node), L, mid);
build(r_node(node), mid + 1, R);
// 这里不需要进行返回，因为最开始都是同一个颜色，我们不需要返回判断父节点什么状态
// push_up(node, l_node(node), r_node(node));
}
}
void update(int node, int L, int R, int l, int r, int x) {
if (l <= L && R <= r && vis[node]) {
tree[node] += col[c[node]] - col[x];
/*
比如是先染色x -> y，后增加 y
那么先染色就对应了
update -> tree = tree - x入 + x出 - y入 + y出
如果是先增x，后染色 x -> y
update -> tree = tree - x入 + x出(x入+m) - y入 + y出 (无论你加没加)
还有一种情况是添加后直接查询，那么我们很难去更新
所以col出的数据我们可以不忙更新，等查询的时候追加在后面即可，只保留原始数据
tree[node] += col[c[node]] - col[x];
val += col[x](x出) - col[y](y进)
而最开始col默认为0， 所以第一步的时候就是
tree(0) += col[x](0) - col[y](y进: 0)
而最后面如果增加收益了的话
val = tree + col[y] => tree(0) = -col[y](y进: 0) + col[y](y出：m) = m
显然符合题意
*/
c[node] = x;
return;
}
// 懒标记往下更新
push_down(node, l_node(node), r_node(node));
int mid = (L + R) >> 1;
if (l <= mid) update(l_node(node), L, mid, l, r, x);
if (mid < r) update(r_node(node), mid + 1, R, l, r, x);
// 更新完子节点后，再更新自己 , 可能更新完后出现左右节点不同颜色
push_up(node, l_node(node), r_node(node));
}
ll query(int node, int L, int R, int idx) {
// 这里上面的 update 讲过了,
if (L == R && L == idx) return tree[node] + col[c[node]];
// 向下传递之前可能出现的懒标记
push_down(node, l_node(node), r_node(node));
// 因为是从上面传递过来的懒标记， 所以我们不需要再去做父节点的判断， 他必然是原来的值
// push_up(node, l_node(node), r_node(node));
// 由于我们是单点查询，所以只需要返回其中一个就可以了
int mid = (L + R) >> 1;
if (idx <= mid) return query(l_node(node), L, mid, idx);
return query(r_node(node), mid + 1, R, idx);
}
int main() {
scanf("%lld%lld", &n, &m);
build(1, 1, n);
while (m -- ) {
string ss;
cin >> ss;
if (ss == "Color") {
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
update(1, 1, n, l, r, c);
} else if (ss == "Add") {
int c, x;
scanf("%d%d", &c, &x);
col[c] += x;
/*
添加收益的时候我们直接更新数组即可
因为我们已经记录了之前的状态了
*/
} else {
int l;
scanf("%d", &l);
printf("%lld\n", query(1, 1, n, l));
}
}
return 0;
}
微信
支付宝
