本次比赛的出题表如下：

退役一年，勋总还是那么强呜呜呜

填空题

[1] 十甚至九

出题人：陈文静

题意

计算 $(homo{)}_{10}=(114{)}_5+(141{)}_9+(198{)}_{10}$ ，其中 $(x{)}_y$ 代表数字 $x$ 是用 $y$ 进制表示的。

思路

按权展开计算十进制结果，并求和。

$(114{)}_5=(1\times 5^2+1\times 5^1+4\times 5^0{)}_{10}=(34{)}_{10}$

$(141{)}_9=(1\times 9^2+4\times 9^1+1\times 9^0{)}_{10}=(118{)}_{10}$

$(homo{)}_{10}=(34{)}_{10}+(118{)}_{10}+(198{)}_{10}=(350{)}_{10}$

因此 $homo$ 是 $350$

拓展

[蓝桥杯] $X$ 进制减法

第十三届蓝桥杯C/C++省赛B组 E题

进制规定了数字在数位上逢几进一。

$X$ 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某种 $X$ 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则X 进制数 $321$ 转换为十进制数为 $65$。

现在有两个 $X$ 进制表示的整数 $A$ 和 $B$，但是其具体每一数位的进制还不确定，只知道 $A$ 和 $B$ 是同一进制规则，且每一数位最高为 $N$ 进制，最低为二进制。请你算出 $A-B$ 的结果最小可能是多少。

请注意，你需要保证 $A$ 和 $B$ 在 $X$ 进制下都是合法的，即每一数位上的数字要小于其进制。

输出一行一个整数，表示 $X$ 进制数 $A-B$ 的结果的最小可能值转换为十进制后再模 $1000000007$ 的结果。

实际上进位计数制，更重要的是计数。我们可以根据进位的规则，从 $0$ 开始不断加 $1$ ，根据进位规则产生新的数字。最后我们既可以通过进位表示得出某个数字表示的大小，也可以通过某个数字的大小得到进位表示。

$X_i$	$X_0$	$X_1$	$X_2$	$X_3$	$X_4$	$X_5$	$X_6$	$X_7$	$X_8$
$Bas{e}_{10}$	0	1	2	3	4	5	6	7	8
$Bas{e}_2$	0	1	10	11	100	101	110	111	1000
$Bas{e}_5$	0	1	2	3	4	10	11	12	13

现在给定一个数字 $X$ ，只要知道 $X$ 之前有多少个数字就可以确定 $X$ 的大小。

举一个十六进制的例子：$(ABC{)}_{16}=(A00+B0+C{)}_{16}$ ，假设我们现在想知道 $(ABC{)}_{16}$ 在五进制下表示是什么，我们可以考虑 $(A00{)}_{16},(B0{)}_{16},(C{)}_{16}$ 分别在五进制下的表示是什么，最后将这三者用五进制加法加起来即可。

对于 $(A00{)}_{16}$ ，我们可以固定最高位为 $[(0{)}_{16},(9{)}_{16}]$ 这个范围的数，那么低两位任意取 $[(0{)}_{16},(F{)}_{16}]$ 中的任意值组合一定都小于 $(A00{)}_{16}$，根据计数乘法原理可以知道低两位存在 $(F+1{)}_{16}\times (F+1{)}_{16}$ 种组合可能，最后再乘上最高位可能取值的数量。 $(A00{)}_{16}$ 用十六进制乘法表示就是 $(9+1{)}_{16}\times (F+1{)}_{16}\times (F+1{)}_{16}$ ，于是可以将乘法的十六进制数转换为五进制数进行乘法就得到了 $(A00{)}_{16}$ 在五进制下的表示，即 $(14+1{)}_5\times (30+1{)}_5\times (30+1{)}_5$ 。

最终可以得到
$$\begin{array}{rl}(ABC{)}_{16}& =(A00{)}_{16}+(B0{)}_{16}+(C{)}_{16}\\ & =(9+1{)}_{16}\times (F+1{)}_{16}\times (F+1{)}_{16}+(A+1{)}_{16}\times (F+1{)}_{16}+(C{)}_{16}\\ & =(14+1{)}_5\times (30+1{)}_5\times (30+1{)}_5+(20+1{)}_5\times (30+1{)}_5+(22{)}_5\end{array}$$
根据五进制加法就可以得到五进制的表示，另外乘法本质上也是加法。观察每一个数位，乘的数值始终是一致的，因此可以把这个固定值称为权，以上式子展开的过程称为按权展开。

对于蓝桥杯的这道题，可以先考虑 $X$ 进制如何转换为 $10$ 进制，我们可以参考上面的思考过程。因为每一个数位的进位基数可能是不一样的，因此每一位的权就变为更低位进位基数的连乘积。因为 $X$ 进制的每一位的进制基数是不确定的，但是我们知道位权是由更低位进制基数决定的，那么贪心的想，每一位的进位基数尽可能小就可以让数的整体尽可能小，但是基数不能小于或等于 $A,B$ 对应位的最大值（这是进位制的限制）。

此外还需要考虑减法借位是否会影响贪心的策略：[1] 不产生借位，不影响贪心策略 [2] 产生借位，在确定高位进位基数的情况下，借位对高位的影响一致，而当前位进位基数越小借位后的数值越小，且进位基数越小高位的权越小。因此减法借位不会影响贪心策略。

最后生活中常见的 $X$ 进制即时分秒，进位基数分别为 $24,60,60$ 。

[2] 九大于十

出题人：陈文静

题意

区间 $[1919,114514]$ 中的正整数构成数对 $<x,y>$，按字典序比较满足 $x>y$ 的数对的数量。

思路

可以写一个复杂度为 $O(n^2)$ 的程序枚举所有数对，将数字转换为字符串比较并统计答案，C++耗时大概 $40$ 分钟左右。

也可以考虑先对 $n$ 个数字按字典序排序，时间复杂度 $O(n\log n)$，那么字典序大于排序后第 $i$ 个数字的有 $n-i$ 个，最后求和即可。

可以考虑：对于 $n$ 个数字，一共进行 $n\times n$ 次比较，其中 $n$ 个数对的比较是相等的。剩下 $n\times n-n$ 个数对一半是满足小于关系，一半满足大于关系，因此满足大于关系的数量为 $\frac{n\times n-n}{2}$ ，代入公式时间复杂度 $O(1)$。

区间长度 $n=114514-1919+1=112596$ ，因此最终答案为 $\frac{112596\times 112595}{2}=6338873310$

C++计算时需要注意类型，答案超过 int 范围。

[3] N皇后

出题人：林贝宁

使用深度优先搜索算法先写出代码，然后用代码跑出答案即可，最后答案为2279184。因为是填空题没有时间限制要求，所以不需要状态压缩优化也可以在2分钟内跑出来。

下面是我用JAVA写的状态压缩版dfs搜索的代码，语法大致同C++，供参考

import java.util.*;public class Main {private static int n, allOne, answerNumber;// 三个变量分别表示：n个皇后问题， 一行n个位置棋盘全部赋1的状态， 解的数量public static void findAnswer(int[] chessBoard, int row, int nowState, int mainDiagonal, int deputyDiagonal) {if (row == n) //找到一组合法解{answerNumber ++ ;return;}int remainingColumn = allOne & (~ (nowState | mainDiagonal | deputyDiagonal));//剩余的还能填写的列 = n个1 - （已经填写的列+主副对角线被占用的位置）int nowPosition;// 当前需要填写的位置状态int nextState, nextMain, nextDeputy;//下一层搜索，列被占用的状态,主对角线占用状态,副对角线占用状态for (int i = 0; i < n; i++) {if (((remainingColumn >> i) & 1) == 0) //当前行第i个位置不能填continue;nowPosition = 1 << i; //第i个位置的位状态chessBoard[row] = i; //第row行，皇后放在第i列的位置上面nextState = nowState | nowPosition;//下一层搜索，列被占用的状态nextMain = (mainDiagonal | nowPosition) >> 1;//下一层搜索，主对角线占用状态nextDeputy = (deputyDiagonal | nowPosition) << 1;//下一层搜索，副对角线占用状态findAnswer(chessBoard, row + 1, nextState, nextMain, nextDeputy);//进入下一层搜索}return;}public static void main(String[] args) {Scanner readScanner = new Scanner(System.in);n = readScanner.nextInt();allOne = (int) (1L << n) - 1; int[] chessBoard = new int[n]; //chessBoard[i]表示第i行，皇后摆放在当前行第几个位置findAnswer(chessBoard, 0, 0, 0, 0);if(answerNumber == 0){System.out.println("No Solution"); //无解System.exit(0); //直接结束程序}System.out.println("There are a total of " + answerNumber + " answers"); //有多少组解}
}

签到题

[1] JMU最强蓝人

出题人 ：林贝宁

输出YES即可。

#include <bits/stdc++.h>
int main()
{std::cout << "YES" << std::endl;return 0;
}

[2] 哪有赌狗一直输

出题人：吴杰

当市场价 $s_i$ 大于成本 $X$ 时，累加概率。最后输出时特判。

#include<bits/stdc++.h>
using namespace std;
const int N = 104;int p[N], s[N];int main(){int n,X;cin>>n>>X;for(int i=1;i<=n;i++) cin>>p[i];for(int i=1;i<=n;i++) cin>>s[i];int ans=0;for(int i=1;i<=n;i++){if(s[i]>X) ans+=p[i];}if(ans==0) cout<<"shu ma le"<<endl;else if(ans==100) cout<<"ying ma le"<<endl;else cout<<ans<<endl;return 0;
}

[3] 元胞自动机

出题人：陈文静

题意

给一个长度为 $n$ 的一维元胞自动机和初始序列，元胞的染色情况由元胞数值的奇偶决定，问 $T=t$ 时刻元胞自动机的染色情况

思路

按题意模拟即可，直接累加会爆int类型，但溢出不影响奇偶性。

也可以对三个数奇偶性进行讨论，若出现三个奇数相加结果仍然奇数，两个奇数一个偶数相加结果为偶数，一个奇数两个偶数相加结果为奇数，三个偶数相加结果为偶数。序列初始值为 $0$ 或 $1$ ，上面的讨论相当于是异或运算，因此也可以将加法改为异或。

状态更新取决于上个状态，因此不能直接用一维数组模拟，可以使用二维数组模拟，使用滚动数组对二维数组进行空间优化。

代码实现

C++ 实现

#include <bits/stdc++.h>
using namespace std;
int S[1001][101];
int main()
{int n, t;cin >> n >> t;for (int i = 1; i <= n; i++) cin >> S[0][i]; /*初始状态*/for (int i = 1; i <= t; i++)for (int j = 1; j <= n; j++)S[i][j] = S[i - 1][j - 1] ^ S[i - 1][j] ^ S[i - 1][j + 1]; /*异或 / 加法都可以*/for (int i = 1; i <= n; i++)cout << (S[t][i] ? "B" : "W"); /*输出最终状态染色情况*/return 0;
}

Java 实现

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int t = in.nextInt();int[][] S = new int[1001][101];for (int i = 1; i <= n; i++) {S[0][i] = in.nextInt();}for (int i = 1; i <= t; i++) {for (int j = 1; j <= n; j++) {S[i][j] = S[i - 1][j - 1] ^ S[i - 1][j] ^ S[i - 1][j + 1];}}for (int i = 1; i <= n; i++)System.out.print(S[t][i] == 1 ? "B" : "W");in.close();}
}

Python 实现

n, t = map(int, input().split())S = [[0 for i in range(0, 101)] for j in range(0, 1001)]
S[0] = [0]+list(map(int, input().split()))+[0]
for i in range(1, t+1):for j in range(1, n+1):S[i][j] = S[i-1][j-1] ^ S[i-1][j] ^ S[i-1][j+1]
for i in range(1, n+1):if S[t][i]:print("B", end='')else:print("W", end='')

简单题

[1] 酒馆战旗

出题人： 吴杰

瓶盖兑矿泉水炉石版，虽然游戏马上要寄了

因为 $Z<Y$，答案一定是下降的，直接模拟即可。

#include<bits/stdc++.h>
using namespace std;int main(){int T;cin>>T;while(T--){int X,Y,Z;cin>>X>>Y>>Z;int ans=0;while(X>=Y){ // 能购买随从int t=X/Y; // 买入 t 个随从, 自动下取整X%=Y; // 剩余铸币, 写 X-=t*Y 也行ans+=t; // 统计答案X+=t*Z; // 把买入的 t 个随从卖出获得 t*Z 铸币}cout<<ans<<endl;}return 0;
}

[2] 博丽神社例大祭

题意

出题人：蔡培伟

在一个 $n\times n$ 的矩阵内给定 $k$ 个特殊点，问所有点到特殊点的最短距离的总和是多少。

设矩阵上两个点的位置为 $(x_1,y_1),(x_2,y_2)$ ，那么点与点之间之间的距离为 $|x_1-x_2|+|y_1-y_2|$ 。

思路

知识点：多源 BFS 。

假设我们只有一个点 $v$ ，从这个点开始进行 bfs ，就像类似于从一个着火点开始，逐步蔓延至周边的其他位置，搜索到的点顺序是按照其距离源点 $v$ 的距离由近到远进行排序。

在这道题中有多个源点，我们只需要将这几个点加入 bfs 的队列，直接进行 bfs ，就能得到每个点到其最近源点的距离，累加起来就是答案了。

代码

c++ 代码。

#include <bits/stdc++.h>
using namespace std;
template <class T> constexpr T inf = std::numeric_limits<T>::max() / 2;
using ll = long long;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n, k;cin >> n >> k;vector a(n + 2, vector<bool>(n + 2));vector dis(n + 2, vector<int>(n + 2, inf<int>));for (int i{}; i <= n + 1; i ++) {a[i][0] = a[0][i] = a[n + 1][i] = a[i][n + 1] = true;  // 标记边界}queue<pair<int,int>> q;// 标记源点并加入队列中for (int i{}; i < k; i ++) {int x, y;cin >> x >> y;a[x][y] = true;dis[x][y] = 0;	// 源点距离初始化为 0q.emplace(x, y);}// 四个方向vector<pair<int,int>> D = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// BFSwhile (!q.empty()) {auto [x, y] = q.front();q.pop();for (auto [dx, dy] : D) {int nx = dx + x, ny = y + dy;if (dis[nx][ny] == inf<int> && !a[nx][ny]) {dis[nx][ny] = dis[x][y] + 1;q.emplace(nx, ny);}}}// 统计答案ll ans{};for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {ans += dis[i][j];}}cout << ans << '\n';
}

java 代码。

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;class Info {Info() {}Info(int x, int y) { this.x = x; this.y = y; }public int x, y;
}public class Main {static Scanner cin = new Scanner(System.in);static PrintWriter cout = new PrintWriter(System.out);public static void main(String[] args) {Solve();cin.close();cout.close();}public static void Solve() {int n = cin.nextInt(), k = cin.nextInt();int[][] dis = new int[n + 2][n + 2];for (int i = 1; i <= n; i ++) {dis[i][0] = dis[0][i] = dis[n + 1][i] = dis[i][n + 1] = 0;for (int j = 1; j <= n; j ++) {dis[i][j] = Integer.MAX_VALUE;}}Queue<Info> q = new LinkedList<>();ArrayList<Info> D = new ArrayList<>();D.add(new Info(-1, 0));D.add(new Info(1, 0));D.add(new Info(0, -1));D.add(new Info(0, 1));while (k --> 0) {int x = cin.nextInt(), y = cin.nextInt();dis[x][y] = 0;q.offer(new Info(x, y));}while (!q.isEmpty()) {var tmp = q.poll();int x = tmp.x, y = tmp.y;for (var dd : D) {int nx = x + dd.x, ny = y + dd.y;if (dis[nx][ny] == Integer.MAX_VALUE) {dis[nx][ny] = dis[x][y] + 1;q.offer(new Info(nx, ny));}}}long ans = 0;for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {ans += dis[i][j];}}cout.println(ans);}
}

py代码。

import queueinf = 1 << 30def Solve() -> None:n, k = map(int, input().split())a = [[False] * (n + 2) for i in range(n + 2)]dis = [[inf] * (n + 2) for i in range(n + 2)]q = queue.Queue()for i in range(0, n + 2):dis[i][0] = dis[0][i] = dis[n + 1][i] = dis[i][n + 1] = 0for i in range(k):x, y = map(int, input().split())a[x][y] = Truedis[x][y] = 0q.put((x, y))D = [(-1, 0), (1, 0), (0, -1), (0, 1)]while not q.empty():x, y = q.get()for dx, dy in D:nx = x + dx; ny = y + dyif dis[nx][ny] == inf:dis[nx][ny] = dis[x][y] + 1q.put((nx, ny))ans = 0for i in range(1, n + 1):for j in range(1, n + 1):ans += dis[i][j]print(ans)return Noneif __name__ == '__main__':Solve()

[3] 无所谓，我会出手

出题人：陈文静

题意

一天可以建造一台机器，若机器在第 $x$ 天建造，第 $x+1$ 天 $0$ 点运行，并于第 $x+d+1$ 天 $0$ 点报废，建造机器时刻的取值范围为 $[0,+\infty )$。给出 $n$ 个不同的时刻，每个时刻都需要有至少 $a$ 台机器同时工作，问是否存在一种方案建造机器使得对于给出的 $n$ 个时刻至少都有 $a$ 台机器同时工作，如果存在至少需要多少台。

思路

第 $t$ 天建造的机器只在 $[t+1,t+d+1)$ 时间段工作。

对于第 $t_i$ 天，我们只需要检查 $[\max (0,t_i-d),t_i-1]$ 天建造的机器数量，如果数量不足 $a$ ，可以利用贪心思想从后往前依次枚举可以建造的时刻补充机器至 $a$ 台并标记补充建造的时刻（贪心：建造机器的时间尽可能靠后）。同时只需要满足 $a\le d$ 且 $a\le t_1$ 一定存在解，当然也可以在枚举的过程中判断是否有解。

排除无解情况以后，可以考虑第 $t_i$ 天，$[t_{i-1},t_i)$ 区间在考虑第 $t_i$ 天之前不可能建造过机器，最坏情况是这个区间都建造机器才能满足第 $t_i$ 天同时工作机器数量大于或等于 $a$。因此我们可以维护建造时刻的队列 $q$，队首建造时刻保持机器对 $t_i$ 时刻有效，需要增加机器的数量即 $\max (0,a-q.size())$ ，且增加机器建造的时间为 $[t_{i-1},t_i)$ 区间从后往前连续的天数（贪心）。

本题定位为简单题，没有卡掉前一种做法，只需要想到贪心思路即可通过本题，且Java和Python(pypy3)使用第一种做法也可以通过。

代码实现给出C++两种做法实现、Java和Python第二种做法的实现。

当然本题输出 No 可以骗两分。虽然一般比赛会避免只输出一个 Yes / No 的情况，但是如果写不出正解，可以尝试写一些朴素算法或者判断一些特殊情况骗分 (仅限于有部分分数的比赛)。

代码实现

C++ 实现 (1)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int T[maxn];
int main()
{int n, a, d;cin >> n >> a >> d;/*红色怪鱼的数量*//*击败红色怪鱼所需同时工作机器的数量*//*机器报废的天数*/bool flag = true; /*是否存在解*/int ans = 0;      /*答案统计*/for (int i = 1; i <= n && flag; i++){int t, sum = 0; /*第i只红色怪鱼出现的时刻*/cin >> t;for (int j = 1; j <= d; j++) /*计算对时刻t有效的机器数量*/{if (t - j >= 0) /*t-j即建造机器的时刻*/{sum += T[t - j]; /*累积机器数量*/}}for (int j = 1; j <= d && sum < a; j++) /*对时刻t有效的机器数量不够增加机器*/{if (t - j < 0) /*无法继续建造*/{flag = false; /*无解*/}else if (!T[t - j]) /*t-j时刻没建造过机器*/{ans++;        /*建造一台机器*/sum++;        /*增加对时刻t有效的机器数量*/T[t - j] = 1; /*t-j时刻建造一台机器*/}}if (sum < a) /*机器数量仍然不够*/{flag = false; /*无解*/}}if (flag) /*输出答案*/{cout << "Yes\n";cout << ans;}else{cout << "No";}return 0;
}

C++ 实现 (2)

#include <bits/stdc++.h>
using namespace std;int main()
{int n, a, d, t;cin >> n >> a >> d >> t;/*红色怪鱼的数量*//*击败红色怪鱼所需同时工作机器的数量*//*机器报废的天数*//*第一只红色怪鱼到达的时间*/if (a > d || a > t) /*无解情况*/{cout << "No";}else{int ans = 0;  /*统计建造数量*/queue<int> q; /*建造时间队列*/for (int i = t - a; i < t; i++)q.push(i), ans++; /*处理第一只红色怪鱼所需机器*/for (int i = 1; i < n; i++){cin >> t;                               /*对剩下n-1只红色怪鱼到达时间处理*/while (!q.empty() && q.front() + d < t) /*队列不空且队首建造时间对t时刻无效*/q.pop();                            /*弹出队首元素直到满足对t时刻有效*/int add = a - q.size();                 /*需要增加机器的数量*/for (int i = t - add; i < t; i++)       /*从后t-1时刻往前贪心建造机器，但维护队列需要从前往后添加*/q.push(i), ans++;                   /*新建机器*/}cout << "Yes\n"; /*输出答案*/cout << ans;     /*输出答案*/}return 0;
}

Java 实现

import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static Scanner cin = new Scanner(System.in);static PrintWriter cout = new PrintWriter(System.out);public static void main(String[] args) {Solve();cin.close();cout.close();}public static void Solve() {int n = cin.nextInt(), a = cin.nextInt(), d = cin.nextInt(), t = cin.nextInt();if (a > d || a > t) {cout.println("No");return;}int ans = 0;Queue<Integer> q = new LinkedList<>();for (int i = t - a; i < t; i ++) {q.add(i);ans ++;}for (int i = 1; i < n; i ++) {t = cin.nextInt();while (!q.isEmpty() && Integer.compare(q.peek() + d, t) == -1) {q.poll();}int add = a - q.size();for (int j = t - add; j < t; j ++) {q.add(j);ans ++;}}cout.println("Yes");cout.println(ans);}
}

Python 实现

from collections import dequedef Solve() -> None:n, a, d = map(int, input().split())t = int(input())if a > d or a > t:print("No")returnans = 0q = deque()for i in range(t - a, t, 1):q.append(i); ans += 1for i in range(1, n, 1):t = int(input())while len(q) > 0:tmp = q.popleft()if tmp + d >= t:q.appendleft(tmp)breakadd = a - len(q)for j in range(t - add, t, 1):q.append(j); ans += 1print("Yes")print(ans)return Noneif __name__ == '__main__':Solve()

中档题

[1] 数据结构大师

出题人：周鑫

$60$分做法

利用C++中的set直接进行模拟可以得到$60$的分数。

但是为什么只有$60$分？

科普一下set中“==”的逻辑：

1. 若两个集合的大小不相同，则返回false
2. 而后对两个集合同时进行遍历，进行逐个比对，若出现两个元素不相同，则返回false，若全部元素均相同，则返回true。

也就是说，在最坏情况下，两个集合进行比较的时间复杂度是$O(n)$的。故用这个做法本题最坏的时间复杂度是$O(n^2)$，不能通过此题。

$100$分解法$1$

回忆一下高中乃至小学学过的知识：如何判断两个数或两个式子相等？

一个显然的想法是：对两个式子做差，如果差值为$0$，则两个式子相等。

我们利用这个思想来解决这个问题。

显然判断一个集合是否为空集是简单的：只要判断该集合大小是否为$0$即可。

我们令集合$S$为
$$S=(A\cup B)-(A\cap B)$$

其中$A,B$为题意中所表示的两个集合

显然，若$S$是空集，那么$A=B$

$$\begin{array}{rl}& (A\cup B)-(A\cap B)=\varnothing \\ \to & (A\cup B)=(A\cap B)\\ \to & A=B\end{array}$$

考虑维护这个集合$S$。

如何维护？ 看下面这个例子。

现在我们需要将数$x$插入$A$中，在插入前，会有以下两种情况中的其中一种发生

1. $x\in A$
2. $x\notin A$

对于第一种情况 我们忽略即可。

那么对于第二种情况，则也有以下两种情况的其中一种发生

1. $x\in S$
2. $x\notin S$

由于$x\notin A$，则如果第一种情况发生，则是$x\in B$，按照$S$的定义我们把$x$从$S$中移去；如果是第二种情况发生，则是$x\notin B$发生，则我们将$x$插入$S$中即可。

对于每次查询，只需要判断$S$是否为空集即可。

时间复杂度为$O(n\log n)$

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int Q;cin >> Q;vector<set<int>> s(2);//s[0] 表示 A,s[1] 表示 B.set<int> S;while (Q--){int op;cin >> op;if (op == 1 || op == 2){op--;int x;cin >> x;if (s[op].count(x))continue;if (S.count(x))S.erase(x);elseS.insert(x);s[op].insert(x);}else{if (S.empty())cout << "Yes" << endl;elsecout << "No" << endl;}}return 0;
}

$100$分解法$2$

回忆一下我们在$60$分做法中遇到的困难：set直接比较的复杂度太高，无法直接比较。

而判断两个整数相等的时间复杂度是$O(1)$，那么我们自然而然就有一个想法：能否把一个集合“转换成一个整数”，然后进行比较？

在本题中想完美的解决这个问题是很困难的，幸运的是，在允许一定程度的错误的情况下，这个问题是很简单的。

考虑这样一个函数
$$f:S\to \text{N}$$

它满足以下两个性质：

1. 若$A=B$，则$f(A)=f(B)$
2. 若$f(A)=f(B)$，则$A$和$B$大概率相等

用人话说，$f(S)$是一个哈希函数。

故我们只要对集合进行哈希，每次查询时判断二者的哈希值是否相等即可。

至于哈希函数的设计，有许多方法，这里不在赘述。

利用哈希，时间复杂度可以降到$O(n)$。

以下是参考代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'
struct set_hash
{LL val;static const LL num1 = 114514, num2 = 1919810;static const LL mod = 12346789000;set_hash(LL val = 0) : val(val){};void insert(LL x){LL num = (x + num1) * (x + num2);val = (val + num) % mod;}bool operator==(const set_hash &rhs) const {return (val == rhs.val);}
};
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int Q;cin >> Q;vector<unordered_set<int>> s(2);vector<set_hash> h(2);while (Q--){int op;cin >> op;if (op == 1 || op == 2){op--;int x;cin >> x;if (s[op].count(x))continue;s[op].insert(x);h[op].insert(x);}else{if (h[0] == h[1])cout << "Yes" << endl;elsecout << "No" << endl;}}return 0;
}

[2] 小学计算题

出题人：周鑫

题意

求数组长度为$n$的$b$的个数

$$\sum _{i=1}^n{a}_i{b}_i=K-a_0$$
其中bi∈{−1,1}b_{i} \in \{-1,1\}bi​∈{−1,1}。

做法

$01$背包变形。

$b_i$只要两种决策（$-1$和$1$），$01$背包也只有两种决策（取或不取）。

考虑动态规划。

设$dp[i][j]$为考虑到第$i$个数，且当前值为$j$的方案数，不难写出状态转移方程

$$dp[i][j]=dp[i-1][j-a[i]]+dp[i-1][j+a[i]]$$

第一个是选择了$+1$的决策，第二个是选择了$-1$的决策。

显然答案为$dp[n][K-a[0]]$

但是直接这么做会有一个问题：下标会是负数。

有两种方案可以解决这个问题：

1. 将第二维的下标加一些值使最小值也能大于$0$（加偏移）。
2. 利用$map$来允许访问负下标，缺点是时间复杂度会多个$\log$。

时间复杂度为$O(n\times (n\times max(|a_i|)+K))$

值得一提的是这个过程可以利用滚动数组优化空间复杂度，但是在本题中并没有卡大家的空间复杂度。

以下是代码（使用滚动数组和刷表法，故写法可能跟上述描述有点不同）。

#include <bits/stdc++.h>
using namespace std;
constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x)
{if (x < 0)x += P;if (x >= P)x -= P;return x;
}
template <class T>
T power(T a, long long b)
{T res = 1;for (; b; b /= 2, a *= a){if (b % 2)res *= a;}return res;
}
struct Z
{int x;Z(int x = 0) : x(norm(x)) {}int val() const{return x;}Z operator-() const{return Z(norm(P - x));}Z inv() const{assert(x != 0);return power(*this, P - 2);}Z &operator*=(const Z &rhs){x = i64(x) * rhs.x % P;return *this;}Z &operator+=(const Z &rhs){x = norm(x + rhs.x);return *this;}Z &operator-=(const Z &rhs){x = norm(x - rhs.x);return *this;}Z &operator/=(const Z &rhs){return *this *= rhs.inv();}friend Z operator*(const Z &lhs, const Z &rhs){Z res = lhs;res *= rhs;return res;}friend Z operator+(const Z &lhs, const Z &rhs){Z res = lhs;res += rhs;return res;}friend Z operator-(const Z &lhs, const Z &rhs){Z res = lhs;res -= rhs;return res;}friend Z operator/(const Z &lhs, const Z &rhs){Z res = lhs;res /= rhs;return res;}friend std::istream &operator>>(std::istream &is, Z &a){i64 v;is >> v;a = Z(v);return is;}friend std::ostream &operator<<(std::ostream &os, const Z &a){return os << a.val();}
};
//利用结构体Z可以不写取模 实际上可以不用
const int bs = 3e4 + 2000;
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, K;cin >> n >> K;vector<int> a(n + 1);for (int i = 0; i <= n; ++i)cin >> a[i];K -= a[0];vector<Z> dp(bs * 2);dp[bs] = 1;for (int i = 1; i <= n; ++i){vector<Z> f(bs * 2);for (int j = 0; j < f.size(); ++j){if (j + a[i] >= 0 && j + a[i] < bs * 2)f[j + a[i]] += dp[j];if (j - a[i] >= 0 && j - a[i] < bs * 2)f[j - a[i]] += dp[j];}dp = f;}cout << dp[bs + K];return 0;
}

动态规划的map实现代码

• 以及验题人贝给定的带log的map做法（每一层都是跑不满的，最初的时限也可以过）

#include <bits/stdc++.h>using namespace std;constexpr int md = 998244353;int T, n, m;
int k;map<int, long long> dp[105];
int a[105];int main()
{cin >> n >> k;++ n;for(int i = 1; i <= n; i ++ )cin >> a[i];dp[1][a[1]] = 1;for(int i = 2; i <= n; i ++ ){for(auto [ans, num] : dp[i - 1]){dp[i][ans + a[i]] += num;dp[i][ans + a[i]] %= md;dp[i][ans - a[i]] += num;dp[i][ans - a[i]] %= md;}}cout << dp[n][k];
}

难题

[1] 导弹拦截特别版

出题人：周鑫

题意

给出一个长度为$n$的数组$h$和$b$，找到一个长度为$k$的序列$p$，满足以下条件

1. $p_1<p_2<p_3<\cdots <p_k$
2. $h_{p_1}<h_{p_2}<h_{p_3}<\cdots <h_{p_k}$
3. 最大化${\sum }_{i=1}^k{b}_{p_i}$

只需输出${\sum }_{i=1}^n{b}_{p_i}$即可。

满分做法$1$

注意到$b_i$的值很小，我们可以把这个问题转化一下。

对于每个导弹 我们可以把它拆成若干个数

具体为
$$\begin{array}{rl}& a_i\times 10+0,\\ & a_i\times 10+1,\\ & a_i\times 10+2,\\ & ⋮\\ & a_i\times 10+b_i-1\end{array}$$

按照原来顺序组合成一个新的数组$d$。

容易发现，$d$的最长上升子序列就是题目的答案。

时间复杂度为$O((n+{\sum }_{i=1}^n{b}_i)\log (n+{\sum }_{i=1}^n{b}_i))$

参考代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<LL> a(n), b(n);for (int i = 0; i < n; ++i)cin >> a[i];for (int i = 0; i < n; ++i)cin >> b[i];vector<LL> d;for (int i = 0; i < n; ++i){a[i] *= 10;for (int j = 0; j < b[i]; ++j)d.push_back(a[i] + j);}vector<LL> v;LL ans = 0;for (int i = 0; i < d.size(); ++i){if (v.empty() || v.back() < d[i])v.push_back(d[i]);else{auto it = lower_bound(v.begin(), v.end(), d[i]);*it = d[i];}ans = v.size();}cout << ans << endl;return 0;
}

满分做法$2$

考虑动态规划

设$d{p}_i$为从第$1$个考虑到第$i$个答案的最大值，容易写出状态转移方程

$$d{p}_i=\max (d{p}_j+b_i)(h_i>h_j)$$

利用离散化和线段树可以将时间复杂度优化到$O(n\log n)$， 这里不在赘述。

[2] Kth-Number

出题人：林贝宁

题目陈述

描述：把只包含质因子2、3和5的数称作贝贝数（Ugly Number）。例如6、8都是贝贝数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个贝贝数。求按从小到大的顺序的第N个贝贝数。

分数设置

• 会set做法，但是不会用给定的类$10/25$分
  • 出题人认为本题核心是考查算法思想，使用的类是次要，故给了大头的分数。
  • 但是，出题人给了这个类的过于详细的使用方法，以及很多提醒点，如果再只拿这个档次的分数，其实有点说不过去了。
  • 再者蓝桥允许查阅给定得C++API，一定程度上考查了选手现场使用、学习文档的能力
  • （原本这个档次设置的为$4/25$分）
• 会set做法，且会用给定的类，不会离线，$14/25$分
• 会set做法，且会用给定的类，会离线，$18/25$分
• 会三指针做法，会用给定得类，不会离线，$14/25$分
• 会三指针做法，会用给定得类，会离线，代码实现的常数大，$18/25$分
• 会三指针做法，会用给定得类，会离线，代码实现的常数小，$ 25/25$分

算法一：质因数分解（暴力）

算法实现

• 一个很朴素的做法
• 从$1\sim \infty$每次+1，一直枚举，直到找到地N个贝贝数为止
• 那么还有一个待解决的问题，如何判断当前数字是不是贝贝数呢？
• 我们总结一下贝贝数的性质：只能分解为3,5,7的如干次幂相乘的数，即设第$i$个贝贝数为$u_n$，则$u_n=3^x\times 5^y\times 7^z$
• 那么我们只需要通过质因数分解，判断他分解3,5,7后，是否为1，如果为1，则说明没有其他的因数，否则则有其他因数，那么他就不是一个贝贝数

复杂度分析

• 时间复杂度$O(u_n)$，其中$u_n$为第n个贝贝数的大小，因为贝贝数增长非常快，非常巨大，所以这是一个很差的复杂度，预期得分$0$分

算法二：集合/优先队列

思路引入

• 我们试一下能否找到相邻贝贝数之间的规律，或者贝贝数生成的规律？
• 比较遗憾的是，我们通过模拟发现，相邻的贝贝数之间并没有规律，那么这题的另一个切入点，就是生成贝贝数

思路推进

• 我们可以发现，对于$u_n$,它必然是由$u_i(i\in [1,n-1])$乘以3或5或7生成的
• 如果对于$i$也有$i>1$，那么必然也有$u_j,(j\in [1,i-1])$乘以3或5或7生成$u_i$
• 所以，如果知道前面n-1个贝贝数，我们可以每个数都乘以3,5,7，然后检查出里面跟前面n-1个贝贝数不重复的并且是最小的数,得到的便是第n个贝贝数

考虑复杂度

• 不借助set，每次检查重复的复杂度为$O(n)$，每个贝贝数生成三个新的，最多有$(n-1)$个贝贝数，时间复杂度$O(3n^2)$
• 如果借助set去重,每次检查重复的复杂度为$O(\log n)$,时间复杂度$O(3n\log n)$
• 取出最小值，如果借助堆的话，对于维护堆，每次插入一个数，花费$O(\log (3n))$,最多插入3n次，每次取出最小值，花费$O(1)$

实现

• 注意，此处，进入小顶堆的元素可能会有重复，比如($ 3\times 5$和$5\times 3$)，所以我们需要去重，这一点我们可以用STL容器中的set，内嵌红黑树，begin即是最小的元素,插入和删除的代价都是$O(\log 2n)$
• 如果每个询问都再求解一次贝贝数，会造成大量的重复计算，我们离线处理，只需要计算所有询问中最大的那个$n$，然后其余的答案也就顺便计算出来了
• 此处没有离线计算，复杂度为$O(T\times n)$，可以拿到$14/25$分，如果离线的话，复杂度为$O(n\log n)$可以拿到$18/25$分

#include <bits/stdc++.h>
using namespace std;
/*因为担心题解冗余代码太长了，
此处填上题目给定的struct Z和BigInt*/
int t[11];
int main() {int q;cin >> q;int mx = 0;for(int i =1; i <= q;i ++ ){cin >> t[i];mx = max(t[i], mx); //离线，获取最大的询问}vector<BigInt> ans;set<BigInt> st; //堆的作用，同时起到去重的作用st.insert(1);while (ans.size() <= mx) {auto ret = *st.begin();st.erase(st.begin()); //弹出堆中最小值ans.push_back(ret);//获取新的贝贝数st.insert(ret * 3);st.insert(ret * 5);st.insert(ret * 7);}  for(int i =1; i <= q;i ++ )cout << ans[t[i] - 1] << '\n';
}

算法三：三指针做法+离线

算法思路

• 我们会发现判断是否跟前面重复这个过程，以及维护小顶堆，会花费大量时间，不妨想一想能不能省略去这个过程？
• 我们可以发现，如果已经知道[1~i]个贝贝数，那么将$u_1\sim u_i$每个数都会乘以3,5,7再次放入一个队列中
• 如果当前数是由$u_n=u_j\times 3$得到的，那么下一个因为乘以3而得到的贝贝数，必然是由$u_{j+1}\times 3$得到的（后面的数乘以3，必然大于这个数）,对于5,7同理
• 所以我们可以利用这个单调性，维护三个指针，每个指针指向队列中的一个数，依次比较三个指针所指向的数所生成的新贝贝数，即可$O(n)$得出第n个贝贝数
• 即维护i，j，k指针，其中i,j,k分别为指向下一个因为乘以$3,5,7$而得到的贝贝数的位置，我们就可以在三个指针所对应的数的乘以相应的数的运算结果中，找到下一个贝贝数

代码实现

• 注意，下面的if,不能写成if-else，因为可能出现v[i]*2==v[j]*3这样的情况，这种情况我们就需要同时移动i,j
• 否则，数组v中就可能出现重复的元素，导致错误答案
• 如果不离线处理，依旧只能拿$14/25$分，离线处理，若常数大只能拿$18/25$分，常数小可以拿$25/25$满分。题目给出了可能被卡常的多数情况，可谓是非常良心了
• （最后我还是难以理解$O(n\log n)$居然被勋总给卡过去了，“真·卡常大师”，跑的比标程还快）

#include <bits/stdc++.h>
using namespace std;
/*因为担心题解冗余代码太长了，
此处填上题目给定的struct Z和BigInt*/
int main()
{int i = 0, j = 0, k = 0;BigInt now;       // i,j,k分别为指向下一个*3,*5,*7可能成为下一个贝贝数的数的位置的指针vector<BigInt> v; //放入1个1v.push_back(BigInt(1));int idx = 3e5;BigInt ti, tj, tk;while (v.size() < idx){  // v中的数量为为idx时候，停止循环   ti = v[i] * 3;tj = v[j] * 5;tk = v[k] * 7;          now = min(ti, min(tj, tk)); //三个指针运算的结果中找，下一个贝贝v.push_back(now); //将下一个贝贝数入队if (ti == now)i++; //下一个贝贝数可以由v[i]*3得到，则i指针后移if (tj == now)j++; //下一个贝贝数可以由v[j]*5得到，则j指针后移if (tk == now)k++; //下一个贝贝数可以由v[k]*7得到，则k指针后移//此处不能写if -else ，因为可能存在v[i]*3==v[j]*5这种情况//那么在下一次循环中，v[j]*3就会被再次选中，这样就会造成v中有重复元素出现}int T, x;cin >> T;for (int t = 1; t <= T; t++){cin >> x;cout << v[x - 1] << '\n';}
}

压轴题：Kth-Wave

出题人：林贝宁

题目陈述

大意：定义波浪形序列为：序列中间的每个数都大于他的相邻的数或者小于他相邻的数。大小定义为字典序大小，求长度为n的序列中第k个波浪型的序列。

算法一：朴素算法（暴力）

算法思路

• 一个很显然的思路，就是暴力枚举，字典序递增算出每一个序列，直到第k个
• 开一个vector来记录当前的序列，第i层代表当前要填写的是第i个数字，那么递归边界就是n+1层（前面n个数字都已经填写完毕）
• 那么我们该如何按字典序搜索？对于同一个位置填写的i，下一个位置如果填写的下降的，显然比上升的字典序来的小，所以应该先搜索下降的，再搜索上升的
• 如果确定了前两个数的关系，整个序列的山顶和山谷的位置也就确定了，只需要定义一个f_inc不断在0,1翻转就行了

代码实现

typedef long long LL;
typedef vector<int> vci;
#define pb push_back
const int N = 22;
class Solution
{
public:bool vis[N], findAns;vci ans;LL num;void dfs(int now, int last, bool f_inc, int &n, LL &k){if (now == n + 1)//获得一个合法的序列{num++;if (num == k)//需找到答案{findAns = 1;return;}return;}if (!f_inc){ //当前位置是山顶for (int i = last + 1; i <= n; i++){if (!vis[i])//如果i未使用{ans.pb(i);//记录vis[i] = 1;//标记已经使用dfs(now + 1, i, f_inc ^ 1, n, k);//下一个位置跟当前位置的f_inc相反if (findAns)return;vis[i] = 0;ans.pop_back();//删除i}}}else{for (int i = 1; i < last; i++){ //当前位置是山谷if (!vis[i])//i未被使用过{ans.pb(i);//记录vis[i] = 1;//标记已经使用dfs(now + 1, i, f_inc ^ 1, n, k);//下一个位置跟当前位置的f_inc相反if (findAns)return;vis[i] = 0;//还原ans.pop_back();//删除I}}}return;}vci stick(int n, LL k){ans.clear();num=0;findAns=0;memset(vis, 0, sizeof vis);for (int i = 1; i <= n; i++){ans.push_back(i);//记录vis[i] = 1;dfs(2, i, 1, n, k); //第一个位置是山顶，下一个位置是山谷(f_inc==1)//因为对于同样一个i，下一个位置如果越小，则字典序更小//所以下一个位置优先是山谷，f_inc=1if (findAns)//如果找到答案则返回{return ans;}dfs(2, i, 0, n, k); //第一个位置是山谷，下一个位置是山顶(f_inc==0)//搜索下一个位置是山顶的情况，即f_inc=0if (findAns)return ans;vis[i] = 0;ans.pop_back();//将尾巴弹出}return {};}
};

复杂度分析

• 时间复杂度，对于第一个位置上面都填写的i,综合开头上升和开头下降来看，比他小的所有数，和比他大的所有数，都会被枚举一遍，对于第j个位置类似，已经选取j个数字，剩下的n-j个数字都会在第j+1个位置枚举一遍，故时间复杂度为$O(n!)$。
• 空间复杂度，定义了动态数组ans，和数组vis，为$O(n)$

算法二：数位DP+set维护

算法思路

• 显然上述算法还是会TLE的，所以我们仍然需要优化
• 做题的时候，如果我们想到了上述的暴力写法并且打了出来，那么我们可以根据已有的代码，打表找规律
• 约定：开头是递增的称为上升序列，否则称为下降序列
• 如果在长度为3的上升序列$1,3,2$前面加上4，那么就得到了长度为4的下降序列。
• 我们不妨大胆猜测，长度为n-1的上升序列，是否存在着某种转换，可以变为长度为n的下降序列？
• 下面我们思路继续推进

思路推进

打表

• 我们可以打表（暴力或者自己写）得到以下的序列
• 长度为4的波浪形序列

1 3 2 4 
1 4 2 3 
2 1 4 3 
2 3 1 4
2 4 1 3
3 1 4 2
3 2 4 1
3 4 1 2
4 1 3 2
4 2 3 1

• 还有长度为5的

1 3 2 5 4 
1 4 2 5 3 
1 4 3 5 2 
1 5 2 4 3 
1 5 3 4 2 
2 1 4 3 5
2 1 5 3 4
2 3 1 5 4
2 4 1 5 3
2 4 3 5 1
2 5 1 4 3
2 5 3 4 1
3 1 4 2 5
3 1 5 2 4
3 2 4 1 5
3 2 5 1 4
3 4 1 5 2
3 4 2 5 1 
3 5 1 4 2
3 5 2 4 1
4 1 3 2 5
4 1 5 2 3
4 2 3 1 5
4 2 5 1 3
4 3 5 1 2
4 5 1 3 2
4 5 2 3 1
5 1 3 2 4
5 1 4 2 3
5 2 3 1 4
5 2 4 1 3

序列的变换——状态转移方程

• 约定：$P(len,i,f)$代表长度为$len$以$i$开头的波浪形序列，$f=1$为上升序列，$f=0$为下降序列
• 此处我先给出下降序列的状态转移方程
  $$d{p}_{n,i,0}=\sum _{j=1}^{i-1}d{p}_{n-1,j,1}$$
• 再看我的解释，应该就更好理解$P(n-1,j,1)$如何变换到$P(n,i,0)$，其中$j<i$
• 我们假如在$P(4,1,1)$前面加上一个2，如
  {1,3,2,4}-->{2,1,3,2,4}那么他是不是一个长度为5的序列？
• 当然我们还得把原本的那个2给换成5，就变成了{2,1,3,5,4}，肯定有读者想问显然这依旧不是一个波浪形序列？
• 对的，所以还需要再变换{2,1,3,5,4}-->{2,1,5,3,4}将5和3、4中小的那个交换,这样就得到了一个下降序列
• 肯定有同学想问，为什么要跟小的那个交换，就不能直接换成{n,最小,次小}的格式吗，我们看下面的例子

{1,3,2,4}-->{2,1,5,3,4}
{1,4,2,3}-->{2,1,4,3,5}

• 如果我们按照上述的同学的方法来做的话，显然第二个序列和第一个序列就会映射到同一个$P(5,2,0)$，就不符合1对1的映射
• 接下来我们来总结一下变换的步骤

1. 将i放在最前面
2. 将原本的i改为n
3. 因为n必然是最大的数，所以要使他变为山峰，将n跟他左右中较小的数交换
4. （如果n在最右边就跟左边那个数交换）

• 故所以对于所有$j<i$的数，都可以从$P(n-1,j,1)$变换到$P(n,i,0)$，即状态转移方程为
  $$d{p}_{n,i,0}=\sum _{j=1}^{i-1}d{p}_{n-1,j,1}$$

上升序列的DP方程

• 此处依旧先给出dp方程
  $$d{p}_{n,i,1}=\sum _{j=i}^{n-1}d{p}_{n-1,j,0}$$
• 理解了下降序列的状态转移方程，现在理解上升序列的状态转移方程应该容易一些
• 下面我们分类讨论j的情况

对于j==i的变换方式

2 1 4 3-->2 5 1 4 3，对于P(n-1,i,0)，只需要在i后面添加上n，因为n必然是最大的，所以也就变成了上升序列

对于j>i，且i的原位置是山顶

• 我们在j前面加上i，{3,4,1,2}-->{2,3,4,1,2}
• 再把原本的2换成5，因为2原本就是山顶，故换完之后无需变换,{2,3,4,1,2}-->{2,3,4,1,5}

对于j>i，且i的原位置是山谷

• 因为n比所有数都要打，故换完之后需要调整
• 调整方式跟下降序列的调整方式一样
• {3,2,4,1}-->{2,3,2,4,1}-->{2,3,5,4,1}-->{2,5,3,4,1}

故每一个$P(n-1,j,0)$都可以变换为唯一一个$P(n,i,1)$，其中$i\le j\le n-1$，即状态转移方程为$d{p}_{n,i,1}=\sum _{j=i}^{n-1}d{p}_{n-1,j,0}$

再次推进

• 现在我们已经得知dp方程如下：
  $$d{p}_{n,i,0}=\sum _{j=1}^{i-1}d{p}_{n-1,j,1}$$
  $$d{p}_{n,i,1}=\sum _{j=i}^{n-1}d{p}_{n-1,j,0}$$
• 接下来我们就是利用dp方程来求解答案了，因为是字典序递增的，且第k个序列必然存在，所以我们可以遍历找到第个字典序开头的数字是哪一个
• 接下来我们要寻找的长度减少了1，我们也知道n-1对应的dp方程，但是已经使用过一个数了，里面的数不一定是1-n怎么办？
• 我们可以理解成一种哈希映射，将他们排个序，依次映射到1-n，序列的个数依旧不变
• 既能排序又能记录去掉的数，显然这个容器，set无疑

复杂度分析

• 时间复杂度，求解dp数组为$O(n^2)$,求解答案序列的第i个数字为$O(n)$,总共有n个数字，求解答案序列总得为$O(n^2)$，故整个算法的时间复杂度为$O(n^2)$。
• 空间复杂度，定义了上升和、下降和为$O(n)$，定义了答案序列为$O(n)$，定义了dp数组为$O(n^2)$，总得为$O(n^2)$

代码实现

C++

 #include <bits/stdc++.h>
using namespace std;typedef long long LL;int T, n, m;
typedef vector<int> vci;
const int N = 22;LL dp[N][N][2];
//归类一下，序列可以分为有两种
// dp[n][k][0,1]代表序列长度为n位，首位是k，
//先下降(0表示)或先上升(1表示)的序列数量
LL decSum[N], incSum[N];
vci solve(int n, LL k)
{incSum[0] = 0;dp[1][1][0] = dp[1][1][1] = 1;//因为要考虑长度为len时，//对于len-1很多状态会改变，很多地方可以加入新的数len//所以借助辅助数组inc,incSumfor (int len = 2; len <= n; len++){decSum[len] = 0;for (int i = 1; i < len; i++){incSum[i] = incSum[i - 1] + dp[len - 1][i][1];// incSum代表长度为len-1的序列中，开头为1~i的上升序列的数量的前缀和}for (int i = len - 1; i >= 0; i--){decSum[i] = decSum[i + 1] + dp[len - 1][i][0];// decSum代表长度为len-1的序列中，开头为i~len-1的下降序列的数量的后缀和}for (int i = 1; i <= len; i++){dp[len][i][0] = incSum[i - 1]; //下降序列的数量，等于1~i-1的前缀和dp[len][i][1] = decSum[i];     //上升序列的数量，等于k~len-1对的后缀和}}int last;   //记录上一个位置填写的是set中第几小的数字set<int> s; //记录哪些数字被用过了vci ans;    //储存答案for (int i = 1; i <= n; i++)s.insert(i);bool f_inc;for (int i = 1; i <= n; i++){//此处应该先比较下降序列的，再比较上升序列的//顺序不能调换，字典序原因if (dp[n][i][0] < k){                     //说明还不在范围内，此处我们也可以用一个sum累加然后和k比较k -= dp[n][i][0]; //继续缩小范围}else{last = i;ans.push_back(i); //放入答案中f_inc = 1;        //下一个位置是山顶s.erase(i);       //从维护的set中删除i,表示已经被用过了break;}if (dp[n][i][1] < k){k -= dp[n][i][1];}else{last = i;ans.push_back(i); //放入答案中f_inc = 0;        //下一个位置是山谷s.erase(i);       //从维护的set中删除i,表示已经被用过了break;}}int idx;//上升代表当前位置是山谷，下降代表当前位置是山顶//长度逐渐减小的时候，dp数组中代表的1-n就可以理解成为离散化后的结果//可以理解成为哈希映射后的结果for (int len = n - 1; len >= 1; len--){if (f_inc)idx = 1; //如果当前位置是山谷，则从1开始枚举//实际枚举区间为[1,last]，但是因为必然存在，故i到达len之前就已经breakelseidx = last; //如果当前位置是山顶，则从last开始枚举//实际枚举区间为[last,len]//之前的last已经被删除了for (int j = idx; j <= len; j++){if (dp[len][j][f_inc] < k)k -= dp[len][j][f_inc]; //继续缩小范围，分而治之else{auto it = s.begin();for (int q = 1; q < j; q++)it++; //因为迭代器不能直接+(j-1),故找set中第j小的数字得一步一步找last = j; //对于下次来说，上次找的是第j小的数ans.push_back(*it);s.erase(it);break;}}f_inc ^= 1; //下一个位置，跟当前位置相反}return ans;
}int main()
{int n;LL k;cin >> n >> k;vci ans = solve(n, k);for (int i = 0; i < ans.size(); i++){if (i > 0)cout << ' ';cout << ans[i];}
}

python

此处写了实现类，需要选手自己调用

class Solution:def stick(self, n, k):inc = []ans = []now = 0dec =[[0 for i in range(n + 1)] for j in range(n + 1)]#python不能用连环等号#如果此处用连续等号，后面的dp数组会有问题inc = [[0 for i in range(n + 1)] for j in range(n + 1)]  # n+1个n+1个0，二维数组inc[1][1] = 1dec[1][1] = 1  # 初始长度为1vis = [0 for i in range(n + 1)]for Len in range(2, n + 1):  # 长度从2到nfor i in range(1, Len + 1):  # 开头的数字从1到Lenfor m in range(1, i):  # 下降由上升1-（i-1）的和转移过来dec[Len][i] += inc[Len - 1][m]for m in range(i, Len):  # 上升由下降i-(Len-1)的和转移过来inc[Len][i] += dec[Len - 1][m]for i in range(1, n + 1):  # i从1到n，当前需要枚举的位置m = 0now = 0Len =n-i+1#剩余需要枚举的长度for j in range(1, n + 1):if (not vis[j]):  # 没有访问过m += 1#相当于C++中的set来储存#第i层计算ans中的第i个数，下标为ans[i-1]if i == 1:now = inc[Len][m] + dec[Len][m]elif (j > ans[i - 2] and (i == 2 or ans[i - 2] < ans[i - 3])):#当前位置是山顶，即开头递减now=dec[Len][m]elif (j<ans[i-2] and (i==2 or ans[i-2]>ans[i-3])):#当前位置是山谷，即开头是递增now=inc[Len][m]if k<=now:vis[j]=1#这个数被使用过了ans.append(j)#放入答案breakelse:k-=nowreturn ans