蓝桥杯学习笔记（二）

Foolish-Han Lv3
  2025-03-28 23:07:28 2025-03-28 23:07:28 创建   2025-04-21 18:13:36 2025-04-21 18:13:36 更新    3.3k 字  13 分钟  

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

选数异或 - 2081

给定一个长度为的数列和一个非负整数, 给定次查询, 每次询问能否从某个区间中选择两个数使得他们的异或等于。

有一说一，只要想明白了，这个题其实并不难。但可惜的是，我在做题的时候囿于定论，看到题目下方“线段树”的标签，便苦思冥想试图用线段树去解决问题，最终也没有憋出个所以然来。看了题解之后，豁然开朗，才感觉到自己的愚笨。

最基本的，要判断区间是否满足条件，实际上等同于在区间内存在一个数，且也在区间内。那么最基本的，我们可以用一个数组去记录每个数左端最近的匹配数。即等价于且不存在使得。这样，我们在判断区间是否符合条件时只需遍历判断其是否在内即可。

然而这样每次的查询代价太大了，是否可以进一步优化呢？实际上，我们并不关心某一个数的匹配数，我们关心的是区间内是否存在匹配数。那么我们就可以定义表示区间符合要求且不存在符合要求。则相应的有转移方程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main() {
	cin >> n >> m >> x;
	for (int i = 1; i <= n; i++) {
		int tmp;
		cin >> tmp;
		record[i] = (record[i - 1] > last[tmp ^ x]) ? record[i - 1]: last[tmp ^ x];
		last[tmp] = i;
	}		
	for (int i = 0; i < m; i++) {
		int l;
		int r;
		cin >> l >> r;
		if (record[r] < l) {
			cout << "no" << endl;
		} else {
			cout << "yes" << endl;
		}
	}
	return 0;
}

算法问题一定要放开想，要不就会被一道简简单单的动态规划题难住了…

爬树的甲壳虫 - 2085

有一只甲壳虫想要爬上一颗高度为的树，它一开始位于树根，高度为，

当它尝试从高度爬到高度为的位置时有的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。

输入第一行包含一个整数表示树的高度。

接下来行每行包含两个整数，用一个空格分隔，表示。

输出一行包含一个整数表示答案, 答案是一个有理数, 请输出答案对质 数取模的结果。

其中有理数对质数取模的结果是整数满足且。

由于是第一次做这种期望 DP 题（也是第一次见），自然是没有什么思路。这个题的难点有两个，一是取模运算中对除法的处理，二是转移方程的寻找。

逆元

关于模运算，我们很清楚的是关于加减乘法的运算性质。需要注意的是，模运算是不允许出现负数的，因此需要加上使结果变为非负数。比如

那么有没有关于除法的运算性质呢？

在整数运算中，除法是乘法的逆运算，也即等价于。但是，在模意义下，我们不能直接做除法，而是需要转换成乘法。 即，在模下，如果我们要计算：

等价于我们要找到一个数使得：

这实际上等价于：

在模下，除法就是找一个数，使得乘回去得到原数，这正是乘法逆元的定义。

数在模下的逆元是满足：

的数。

如果我们将除法转换成乘法逆元运算：

那么验证一下：

这和原来的等式是一致的，因此：

那么逆元该怎么求呢？我们都知道最基本的寻找两个数的最大公因数的方法——欧几里得方法，即直到时，即为最大公因数。

扩展欧几里得算法不仅求，还可以找到整数和，使得：

假设：

根据模运算的定义有：

代入整理得：

由此可得：

我们如何确保存在对应的和呢？因为递归的出口时，必然存在和这组解。

于是我们有如下扩展欧几里得算法：

1
2
3
4
5
6
7
8
9
10
11
12
int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int gcd = extended_gcd(b, a \mod b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}

在模运算下，如果和互质，则有，那么根据扩展欧几里得算法：

取模：

因此，就是。

不过在实际中，我们更常用的是费马小定理计算逆元。

如果是素数（注意，这里的条件相对于扩展欧几里得算法里的两数互质的要求较为苛刻），则根据费马小定理：

两边同时除以，可得：

这意味着：

这样，我们可以用快速幂算法计算来得到逆元。

期望 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
ll qpow(ll x, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1) {
			res = res * x \mod MOD;
		}
		x = x * x \mod MOD;
		n >>= 1;
	}
	return res;
}

ll inv(ll x) {
	return qpow(x, MOD - 2);
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x[i];
		cin >> y[i];
	}
	for (int i = 1; i <= n; i++) {
		ll q = (y[i] - x[i]) * inv(y[i]) \mod MOD;
		e[i] = (e[i - 1] + 1) \mod MOD * inv(q) \mod MOD;
	}
	cout << e[n];
}

还有一种方法比较好理解。用表示从第层到达第层还需的时间，则有。这个公式乍一看，似乎没办法处理，但由于，我们可以确认表达式有的形式，我们代入递推式就可得到和的递推式，由此求出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i];
        cin >> y[i];
    }
    ll a = x[n - 1] * inv(y[n - 1]) \mod MOD;
    ll b = 1;
    for (int i = n - 2; i >= 0; i--) {
        ll p = x[i] * inv(y[i]) \mod MOD;
        ll q = (y[i] - x[i]) * inv(y[i]) \mod MOD;
        a = (q * a \mod MOD + p) \mod MOD;
        b = (q * b \mod MOD + 1) \mod MOD;
    }
    cout << (-b * qpow(a - 1, MOD - 2) \mod MOD + MOD) \mod MOD;
}

最长不下降子序列 - 2088

给定一个长度为的整数序列:。现在你有一次机会, 将其中连续的个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长, 请输出这个最长的长度。

最长不下降子序列是指序列中的一个子序列, 子序列中的每个数不小于在它之前的数。

关于不带修改的最长不下降子序列问题，我们一般有归并、二分、树状数组、线段树四种的做法。对于这个题，我们应该在哪种算法的基础上进行改进呢？我们分析一下这个问题。

允许连续修改个数值，我们首先可以确定的是，修改之后的方案一定不差于修改之前的方案。对于任意一个不下降子序列，我们可以在其中间添加若干个符号要求的值，使得不下降子序列变长。比如，时，我们可以把变为。

从这里我们可以看出，一个不下降子序列可以分为三部分，左边、右边和中间长度为的序列。那如果中间长度不足怎么办？因为个数是相同的值，所以我们即使把原来符合要求的值修改掉也不会变糟， 比如时的可变为。因此，我们可以认为不下降子序列中间有固定长度为的部分。

进一步的，我们就把问题转换一下。用表示的最长不下降子序列长度，用表示的最长不下降子序列长度，那么我们的任务就变为寻找，其中且。很显然，只要我们求出和，这就是一个的动态规划任务。

怎么求和呢？我们考虑二分方法，首先从左往右遍历一遍。用数组维护当前找到的不下降子序列信息，其中的长度表示当前找到的最长不下降子序列长度，记录当前找到的以为长度的不下降子序列的最后一个元素的最小值，就可完成一般的最长不下降子序列问题。我们用记录每一步数组的长度，即为上面提到的；我们再用记录每一步中最后一个元素的值，即为的最长不下降子序列中的最大值。

类似的方法，我们可以从右向左再遍历一遍，相当于找从到的最长不上升子序列，便可求出上面提到的。于是我们有如下代码：

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
// longest_non_decreasing_subsequence.cpp

#include <bits/stdc++.h>

const int N = 1e5 + 5;
const int K = 1e5 + 5;

int n;
int k;

int arr[N];
int dpl[N];  
int recordl[N]; 
int dpr[N];   
int recordr[N];

using namespace std;

int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  vector<int> lis;
  for (int i = 0; i < n; i++) {
    auto it = upper_bound(lis.begin(), lis.end(), arr[i]);
    if (it == lis.end()) {
      lis.push_back(arr[i]);
    } else {
      *it = arr[i];
    }
    dpl[i] = lis.size();
    recordl[i] = lis.back();
  }
  lis.clear();
  auto cmp = [](const int &l, const int &r) { return l > r; };
  for (int i = n - 1; i >= 0; i--) {
    auto it = upper_bound(lis.begin(), lis.end(), arr[i], cmp);
    if (it == lis.end()) {
      lis.push_back(arr[i]);
    } else {
      *it = arr[i];
    }
    dpr[i] = lis.size();
    recordr[i] = lis.back();
  }
  int res = k;
  for (int i = n - 1; i - k - 1 >= 0; i--) {
    if (recordl[i - k - 1] <= recordr[i]) {
    	res = max(res, dpl[i - k - 1] + dpr[i] + k);
  	}
  }
  if (n > k) {
    res = max(res, dpr[k] + k);
    res = max(res, dpl[n - k - 1] + k);
  }
  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
52
53
54
55
56
57
58
59
60
// longest_non_decreasing_subsequence.cpp

#include <bits/stdc++.h>

const int N = 1e5 + 5;
const int K = 1e5 + 5;

int n;
int k;

int arr[N];
int dpl[N];     // 以 i 为终点的 LIS 长度
int recordl[N]; // 以 i 为终点的 LIS 最大元素值
int dpr[N];     // 以 i 为起点的，最小元素值不小于左侧的 LIS 长度

using namespace std;

int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  vector<int> lis;
  for (int i = 0; i < n; i++) {
    auto it = upper_bound(lis.begin(), lis.end(), arr[i]);
    if (it == lis.end()) {
      lis.push_back(arr[i]);
    } else {
      *it = arr[i];
    }
    dpl[i] = lis.size();
    recordl[i] = lis.back();
  }
  lis.clear();
  auto cmp = [](const int &l, const int &r) { return l > r; };
  for (int i = n - 1; i - k >= 0; i--) {
    auto it = upper_bound(lis.begin(), lis.end(), arr[i], cmp);
    if (it == lis.end()) {
      lis.push_back(arr[i]);
    } else {
      *it = arr[i];
    }
    if (i == k) {
      dpr[i] = lis.size();
    } else {
      it = upper_bound(lis.begin(), lis.end(), recordl[i - k - 1], cmp);
      dpr[i] = it - lis.begin();
    }
  }
  int res = k;
  for (int i = n - 1; i - k - 1 >= 0; i--) {
    res = max(res, dpl[i - k - 1] + dpr[i] + k);
  }
  if (n > k) {
    res = max(res, dpr[k] + k);
    res = max(res, dpl[n - k - 1] + k);
  }
  cout << res;
  return 0;
}

扫描游戏 - 2089

有一根围绕原点顺时针旋转的棒, 初始时指向正上方 (轴正向)。 在平面中有若干物件, 第个物件的坐标为, 价值为。当棒扫到某个 物件时, 棒的长度会瞬间增长, 且物件瞬间消失（棒的顶端恰好碰到物件也 视为扫到), 如果此时增长完的棒又额外碰到了其他物件, 也按上述方式消去 (它和上述那个点视为同时消失)。

如果将物件按照消失的时间排序, 则每个物件有一个排名, 同时消失的物 件排名相同, 请输出每个物件的排名, 如果物件永远不会消失则输出。

推荐阅读
蓝桥杯学习笔记（一） 蓝桥杯学习笔记（一） OS-Shell Challenge OS-Shell Challenge 力扣刷题笔记（一） 力扣刷题笔记（一）
推荐阅读
蓝桥杯学习笔记（一） 蓝桥杯学习笔记（一） OS-Shell Challenge OS-Shell Challenge
目录
蓝桥杯学习笔记（二）
  1. 1. 选数异或 - 2081
  2. 2. 爬树的甲壳虫 - 2085
    1. 2.1. 逆元
    2. 2.2. 期望 DP
  3. 3. 最长不下降子序列 - 2088
  4. 4. 扫描游戏 - 2089