[2] 博丽神社例大祭

题意

出题人：蔡培伟

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

设矩阵上两个点的位置为 (x1,y1),(x2,y2)(x_1, y_1),(x_2,y_2)(x1​,y1​),(x2​,y2​) ，那么点与点之间之间的距离为 ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2|∣x1​−x2​∣+∣y1​−y2​∣ 。

思路

知识点：多源 BFS 。

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

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

代码

c++ 代码。

#include 
using namespace std;
template  constexpr T inf = std::numeric_limits::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(n + 2));vector dis(n + 2, vector(n + 2, inf));for (int i{}; i <= n + 1; i ++) {a[i][0] = a[0][i] = a[n + 1][i] = a[i][n + 1] = true;  // 标记边界}queue> 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> 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 && !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 q = new LinkedList<>();ArrayList 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] 无所谓，我会出手

出题人：陈文静

题意

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

思路

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

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

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

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

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

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

代码实现

C++ 实现 (1)

#include 
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 
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 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 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] 数据结构大师

出题人：周鑫

606060分做法

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

但是为什么只有606060分？

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

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

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

100100100分解法111

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

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

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

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

我们令集合SSS为
S=(A∪B)−(A∩B)S = (A \cup B) - (A \cap B) S=(A∪B)−(A∩B)

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

显然，若SSS是空集，那么A=BA=BA=B

(A∪B)−(A∩B)=∅→(A∪B)=(A∩B)→A=B\begin{aligned} &(A \cup B) - (A \cap B) = \varnothing \\ \rightarrow &(A \cup B) = (A \cap B)\\ \rightarrow& A = B \end{aligned} →→​(A∪B)−(A∩B)=∅(A∪B)=(A∩B)A=B​

考虑维护这个集合SSS。

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

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

1. x∈Ax \in Ax∈A
2. x∉Ax \not\in Ax​∈A

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

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

1. x∈Sx \in Sx∈S
2. x∉Sx \not\in Sx​∈S

由于x∉Ax \not\in Ax​∈A，则如果第一种情况发生，则是x∈Bx \in Bx∈B，按照SSS的定义我们把xxx从SSS中移去；如果是第二种情况发生，则是x∉Bx \not\in Bx​∈B发生，则我们将xxx插入SSS中即可。

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

时间复杂度为O(nlog⁡n)O(n\log n)O(nlogn)

#include 
using namespace std;
#define endl '\n'
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int Q;cin >> Q;vector> s(2);//s[0] 表示 A,s[1] 表示 B.set 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;
}

100100100分解法222

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

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

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

考虑这样一个函数
f:S→Nf: S \rightarrow \text{N} f:S→N

它满足以下两个性质：

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

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

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

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

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

以下是参考代码

#include 
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> s(2);vector 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] 小学计算题

出题人：周鑫

题意

求数组长度为nnn的bbb的个数

∑i=1naibi=K−a0\sum_{i=1}^{n} a_{i}b_{i}=K - a_{0} i=1∑n​ai​bi​=K−a0​
其中bi∈{−1,1}b_{i} \in \{-1,1\}bi​∈{−1,1}。

做法

010101背包变形。

bib_{i}bi​只要两种决策（−1-1−1和111），010101背包也只有两种决策（取或不取）。

考虑动态规划。

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

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

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

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

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

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

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

时间复杂度为O(n×(n×max(∣ai∣)+K))O(n\times (n\times \mathcal{max}(|a_i |)+ K))O(n×(n×max(∣ai​∣)+K))

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

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

#include 
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 
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 a(n + 1);for (int i = 0; i <= n; ++i)cin >> a[i];K -= a[0];vector dp(bs * 2);dp[bs] = 1;for (int i = 1; i <= n; ++i){vector 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 using namespace std;constexpr int md = 998244353;int T, n, m;
int k;map 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] 导弹拦截特别版

出题人：周鑫

题意

给出一个长度为nnn的数组hhh和bbb，找到一个长度为kkk的序列ppp，满足以下条件

1. p1
2. hp1
3. 最大化∑i=1kbpi\sum_{i = 1}^{k} b_{p_{i}}∑i=1k​bpi​​

只需输出∑i=1nbpi\sum_{i = 1}^{n} b_{p_{i}}∑i=1n​bpi​​即可。

满分做法111

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

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

具体为
ai×10+0,ai×10+1,ai×10+2,⋮ai×10+bi−1\begin{aligned} &a_{i}\times 10 +0 , \\ &a_{i}\times 10 +1 , \\ &a_{i}\times 10 +2 ,\\ &\vdots \\ &a_{i} \times 10 + b_{i} -1 \\ \end{aligned} ​ai​×10+0,ai​×10+1,ai​×10+2,⋮ai​×10+bi​−1​

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

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

时间复杂度为O((n+∑i=1nbi)log⁡(n+∑i=1nbi))O((n + \sum_{i =1 }^{n} b_{i} )\log({n + \sum_{i =1 }^{n} b_{i} }) )O((n+∑i=1n​bi​)log(n+∑i=1n​bi​))

参考代码

#include 
using namespace std;
using LL = long long;
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector 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 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 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;
}

满分做法222

考虑动态规划

设dpidp_{i}dpi​为从第111个考虑到第iii个答案的最大值，容易写出状态转移方程

dpi=max⁡(dpj+bi)(hi>hj)dp_{i} = \max(dp_{j} + b_{i}) \quad (h_{i} > h_{j}) dpi​=max(dpj​+bi​)(hi​>hj​)

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

[2] Kth-Number

出题人：林贝宁

题目陈述

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

分数设置

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

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

算法实现

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

复杂度分析

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

算法二：集合/优先队列

思路引入

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

思路推进

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

考虑复杂度

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

实现

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

#include 
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 ans;set 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]个贝贝数，那么将u1∼uiu_1\sim u_iu1​∼ui​每个数都会乘以3,5,7再次放入一个队列中
• 如果当前数是由un=uj×3u_n=u_j\times 3un​=uj​×3得到的，那么下一个因为乘以3而得到的贝贝数，必然是由uj+1×3u_{j+1}\times 3uj+1​×3得到的（后面的数乘以3，必然大于这个数）,对于5,7同理
• 所以我们可以利用这个单调性，维护三个指针，每个指针指向队列中的一个数，依次比较三个指针所指向的数所生成的新贝贝数，即可O(n)O(n)O(n)得出第n个贝贝数
• 即维护i，j，k指针，其中i,j,k分别为指向下一个因为乘以3,5,73,5,73,5,7而得到的贝贝数的位置，我们就可以在三个指针所对应的数的乘以相应的数的运算结果中，找到下一个贝贝数

代码实现

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

#include 
using namespace std;
/*因为担心题解冗余代码太长了，
此处填上题目给定的struct Z和BigInt*/
int main()
{int i = 0, j = 0, k = 0;BigInt now;       // i,j,k分别为指向下一个*3,*5,*7可能成为下一个贝贝数的数的位置的指针vector 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 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!)O(n!)O(n!)。
• 空间复杂度，定义了动态数组ans，和数组vis，为O(n)O(n)O(n)

算法二：数位DP+set维护

算法思路

• 显然上述算法还是会TLE的，所以我们仍然需要优化
• 做题的时候，如果我们想到了上述的暴力写法并且打了出来，那么我们可以根据已有的代码，打表找规律
• 约定：开头是递增的称为上升序列，否则称为下降序列
• 如果在长度为3的上升序列1,3,2{1,3,2}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)P(len,i,f)P(len,i,f)代表长度为lenlenlen以iii开头的波浪形序列，f=1f=1f=1为上升序列，f=0f=0f=0为下降序列
• 此处我先给出下降序列的状态转移方程
  dpn,i,0=∑j=1i−1dpn−1,j,1dp_{n,i,0}=\displaystyle \sum_{j=1}^{i-1} dp_{n-1,j,1}dpn,i,0​=j=1∑i−1​dpn−1,j,1​
• 再看我的解释，应该就更好理解P(n−1,j,1)P(n-1,j,1)P(n−1,j,1)如何变换到P(n,i,0)P(n,i,0)P(n,i,0)，其中j
• 我们假如在P(4,1,1)P(4,1,1)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)P(5,2,0)P(5,2,0)，就不符合1对1的映射
• 接下来我们来总结一下变换的步骤

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

• 故所以对于所有j dpn,i,0=∑j=1i−1dpn−1,j,1dp_{n,i,0}=\displaystyle \sum_{j=1}^{i-1} dp_{n-1,j,1}dpn,i,0​=j=1∑i−1​dpn−1,j,1​

上升序列的DP方程

• 此处依旧先给出dp方程
  dpn,i,1=∑j=in−1dpn−1,j,0dp_{n,i,1}=\displaystyle \sum_{j=i}^{n-1} dp_{n-1,j,0}dpn,i,1​=j=i∑n−1​dpn−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-1,j,0)P(n−1,j,0)都可以变换为唯一一个P(n,i,1)P(n,i,1)P(n,i,1)，其中i≤j≤n−1i\le j\le n-1i≤j≤n−1，即状态转移方程为dpn,i,1=∑j=in−1dpn−1,j,0dp_{n,i,1}=\displaystyle \sum_{j=i}^{n-1} dp_{n-1,j,0}dpn,i,1​=j=i∑n−1​dpn−1,j,0​

再次推进

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

复杂度分析

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

代码实现

C++

 #include 
using namespace std;typedef long long LL;int T, n, m;
typedef vector 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 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 (jans[i-3])):#当前位置是山谷，即开头是递增now=inc[Len][m]if k<=now:vis[j]=1#这个数被使用过了ans.append(j)#放入答案breakelse:k-=nowreturn ans