后续题目的出题人题解和参考代码
F
思路
本题改编自********* ************** ，是在考研书籍上看到的，恰巧看到史记上的这句话，加上ioi赛制和考研一样，因为样例数据范围的参差，实现的算法时间复杂度较高也会给一些分数，所以就把这题出了出来。
这题本身不难，但是很考验写题人的基本功，解题关键是想出类似摩尔投票的“抵消”的方法，其次是需要注意一些边界问题。本题其实具有一定误导性的是绝对众数这一概念可能对很多没有接触过的人会比较陌生，“占半数以上”或许会拿不稳这个“以上”，从而犹豫于出现分数一样多的情况下，到底会选哪一个。以及中位数大家可能会困惑于精准定义，是两个中的前一个/后一个还是平均值。
这个问题可以拆分为两个子问题：求绝对众数并加入优先队列，以及求两优先队列的中位数
1.求绝对众数并加入优先队列 我们可以遍历每个诸侯的意见数组，使用摩尔投票法求出绝对众数，如果不存在绝对众数，返回默认值 5
将每个诸侯的绝对众数加入一个优先队列，这样可以对所有的意见进行排序
将优先队列中的元素依次出队，存入一个数组，这样可以方便后续的计算
2.求两优先队列的中位数
对于第二个子问题，我们可以将两个优先队列中的元素分别存入两个有序数组，这样可以利用数组的索引
使用二分法，找出两个数组中第 k 小的元素，其中 k 为两个数组的总长度的一半
如果两个数组的总长度为偶数，还需要找出第 k+1 小的元素，然后取两个元素的平均值作为中位数
如果两个数组的总长度为奇数，直接返回第 k 小的元素作为中位数
参考代码
注：因为数据比较大，所有题解std均需要增加快读快写才能通过，由于篇幅限制，此处不展示快读快写相关代码
JAVA
import java.util.*;
public class Main {
/*
* 用于求出一个数组中的绝对众数，即出现次数超过一半的元素
* 如果不存在绝对众数，返回默认值 5
* 使用摩尔投票法，时间复杂度为 O(n)，空间复杂度为 O(1)
*/
public static int getAbsoluteMajority(int[] arr) {
int count = 0;
int candidate = 0;
for (int num : arr) {
if (count == 0) {
candidate = num;
}
if (num == candidate) {
count++;
} else {
count--;
}
}
count = 0;
for (int num : arr) {
if (num == candidate) {
count++;
}
}
if (count > arr.length / 2) {
return candidate;
} else {
return 5;
}
}
/*
* 该方法用于求出两个有序数组的中位数
* 如果两个数组的总长度为偶数，返回中间两个数的平均值
* 如果两个数组的总长度为奇数，返回中间的数
* 使用二分法，时间复杂度为 O(log(m+n))，空间复杂度为 O(1)
*/
public static double getMedian(int[] arr1, int[] arr2) {
int n = arr1.length;
int m = arr2.length;
int total = n + m;
if (total % 2 == 0) {
return (getKth(arr1, 0, n - 1, arr2, 0, m - 1, total / 2)
+ getKth(arr1, 0, n - 1, arr2, 0, m - 1, total / 2 + 1)) / 2.0;
} else {
return getKth(arr1, 0, n - 1, arr2, 0, m - 1, (total + 1) / 2);
}
}
/*
* 求出两个有序数组中第 k 小的元素
* 使用递归，每次比较两个数组的第 k/2 个元素，舍弃较小的一半
* 如果某个数组为空，直接返回另一个数组的第 k 小元素
* 如果 k 为 1，直接返回两个数组中较小的元素
*/
public static int getKth(int[] arr1, int start1, int end1, int[] arr2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
if (len1 > len2) {
return getKth(arr2, start2, end2, arr1, start1, end1, k);
}
if (len1 == 0) {
return arr2[start2 + k - 1];
}
if (k == 1) {
return Math.min(arr1[start1], arr2[start2]);
}
int i = start1 + Math.min(len1, k / 2) - 1;
int j = start2 + Math.min(len2, k / 2) - 1;
if (arr1[i] > arr2[j]) {
return getKth(arr1, start1, end1, arr2, j + 1, end2, k - (j - start2 + 1));
} else {
return getKth(arr1, i + 1, end1, arr2, start2, end2, k - (i - start1 + 1));
}
}
/*
* 根据炎帝部族和黄帝部族的诸侯的意见，求出两个部族的意见的中位数
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
PriorityQueue<Integer> pqn = new PriorityQueue<Integer>();
PriorityQueue<Integer> pqm = new PriorityQueue<Integer>();
int[] ys = new int[n];
int[] hs = new int[m];
for (int i = 0; i < n; i++) {
int numn = sc.nextInt();
int[] arr = new int[numn];
for (int j = 0; j < numn; j++) {
arr[j] = sc.nextInt();
}
int majority = getAbsoluteMajority(arr);
pqn.add(majority);
}
int index = 0;
while (!pqn.isEmpty()) {
ys[index++] = pqn.poll();
}
for (int i = 0; i < m; i++) {
int numm = sc.nextInt();
int[] arr = new int[numm];
for (int j = 0; j < numm; j++) {
arr[j] = sc.nextInt();
}
int majority = getAbsoluteMajority(arr);
pqm.add(majority);
}
index = 0;
while (!pqm.isEmpty()) {
hs[index++] = pqm.poll();
}
sc.close();
for (int i = 0; i < ys.length; i++) {
System.out.print(ys[i] + " ");
}
System.out.println();
for (int i = 0; i < hs.length; i++) {
System.out.print(hs[i] + " ");
}
System.out.println();
double median = getMedian(ys, hs);
System.out.println((int) median);
}
}
CPP
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
// 求出一个数组中的绝对众数，即出现次数超过一半的元素
// 如果不存在绝对众数，返回默认值 5
// 使用摩尔投票法，时间复杂度为 O(n)，空间复杂度为 O(1)
int getAbsoluteMajority(const std::vector<int>& arr) {
int count = 0;
int candidate = 0;
for (int num : arr) {
if (count == 0) {
candidate = num;
}
if (num == candidate) {
count++;
} else {
count--;
}
}
count = 0;
for (int num : arr) {
if (num == candidate) {
count++;
}
}
if (count > arr.size() / 2) {
return candidate;
} else {
return 5;
}
}
// 求出两个有序数组中第 k 小的元素
int getKth(const std::vector<int>& arr1, int start1, int end1, const std::vector<int>& arr2, int start2, int end2, int k);
// 该方法用于求出两个有序数组的中位数
// 如果两个数组的总长度为偶数，返回中间两个数的平均值
// 如果两个数组的总长度为奇数，返回中间的数
// 使用二分法，时间复杂度为 O(log(m+n))，空间复杂度为 O(1)
double getMedian(const std::vector<int>& arr1, const std::vector<int>& arr2) {
int n = arr1.size();
int m = arr2.size();
int total = n + m;
if (total % 2 == 0) {
return (getKth(arr1, 0, n - 1, arr2, 0, m - 1, total / 2)
+ getKth(arr1, 0, n - 1, arr2, 0, m - 1, total / 2 + 1)) / 2.0;
} else {
return getKth(arr1, 0, n - 1, arr2, 0, m - 1, (total + 1) / 2);
}
}
// 求出两个有序数组中第 k 小的元素
// 使用递归，每次比较两个数组的第 k/2 个元素，舍弃较小的一半
// 如果某个数组为空，直接返回另一个数组的第 k 小元素
// 如果 k 为 1，直接返回两个数组中较小的元素
int getKth(const std::vector<int>& arr1, int start1, int end1, const std::vector<int>& arr2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
if (len1 > len2) {
return getKth(arr2, start2, end2, arr1, start1, end1, k);
}
if (len1 == 0) {
return arr2[start2 + k - 1];
}
if (k == 1) {
return std::min(arr1[start1], arr2[start2]);
}
int i = start1 + std::min(len1, k / 2) - 1;
int j = start2 + std::min(len2, k / 2) - 1;
if (arr1[i] > arr2[j]) {
return getKth(arr1, start1, end1, arr2, j + 1, end2, k - (j - start2 + 1));
} else {
return getKth(arr1, i + 1, end1, arr2, start2, end2, k - (i - start1 + 1));
}
}
int main() {
int n, m;
std::cin >> n >> m;
std::priority_queue<int, std::vector<int>, std::greater<int>> pqn;
std::priority_queue<int, std::vector<int>, std::greater<int>> pqm;
std::vector<int> ys(n);
std::vector<int> hs(m);
for (int i = 0; i < n; i++) {
int numn;
std::cin >> numn;
std::vector<int> arr(numn);
for (int j = 0; j < numn; j++) {
std::cin >> arr[j];
}
int majority = getAbsoluteMajority(arr);
pqn.push(majority);
}
int index = 0;
while (!pqn.empty()) {
ys[index++] = pqn.top();
pqn.pop();
}
for (int i = 0; i < m; i++) {
int numm;
std::cin >> numm;
std::vector<int> arr(numm);
for (int j = 0; j < numm; j++) {
std::cin >> arr[j];
}
int majority = getAbsoluteMajority(arr);
pqm.push(majority);
}
index = 0;
while (!pqm.empty()) {
hs[index++] = pqm.top();
pqm.pop();
}
for (int num : ys) {
std::cout << num << " ";
}
std::cout << std::endl;
for (int num : hs) {
std::cout << num << " ";
}
std::cout << std::endl;
double median = getMedian(ys, hs);
std::cout << static_cast<int>(median) << std::endl;
return 0;
}
G
思路
本题改编自下一个更大的数,并且使用dp记忆相邻的数，以达到O(n*m)的复杂度，本题题面存在较大问题，主要是没有提到鱼雷在发现更浅处目标会立即前往（即分遇到下一个更小的数就计数），加上所给的数据范围令人费解，导致大家无法正确定位对应的问题。同时，因为本人主要以Java解题，Java的nextBoolean()方法会将大写的True\False自动转化为小写并识别给出对应布尔量，以至于std可以正确无误地通过样例及所有数据。在此深感抱歉。
本题其实是比较简单的，我们可以将求解不同方向上最多贯穿的目标数分为两个子问题：
1.计算每个分区开始发射时能贯穿的目标数
我们可以使用一个单调栈来存储分区的索引，这样我们就可以在遍历每个分区时，
快速地找到比当前分区目标深的分区，并将它们的目标数加到当前分区的结果上。
具体地，我们维护一个单调递减的栈，也就是说，栈顶的分区深度总是小于等于栈底的分区目标深度。
当我们遍历到一个新的分区时，我们先判断它对应的目标是否小于等于栈顶的分区深度，
如果是，说明我们可以从当前分区发射到栈顶的分区，并贯穿栈顶的目标，
如果不是，我们将栈顶的分区弹出，直到栈为空或者栈顶的分区深度小于当前分区深度为止，
最后自身加上栈中所余数量即为贯穿的目标数即可。
2.如何根据水流方向来决定遍历的方向。
对于第二个子问题，我们可以使用一个变量来表示水流方向，然后根据水流方向来决定遍历和发射的方向。
如果是右流，我们从右到左遍历每个分区，并只考虑顺流发射时能贯穿的目标数。
如果是左流，我们从左到右遍历每个分区，并只考虑逆流发射时能贯穿的目标数。
这样，我们就可以在一次遍历中完成计算和输出。
参考代码
注：因为数据比较大，所有题解std均需要增加快读快写才能通过，由于篇幅限制，此处不展示快读快写相关代码
JAVA
import java.util.*;
public class Main {
public static void main(String[] args) {
/*
* 结合输入的分区的数量，以初始化所用到的数据结构以及将各分区目标所在的深度存入
*/
Scanner scanner = new Scanner(System.in);
boolean current = scanner.nextBoolean();
int n = scanner.nextInt();
int[] d = new int[n];
int[] res = new int[n];
Stack<Integer> stack = new Stack<Integer>();
int start, end, step;
for (int i = 0; i < n; i++) {
d[i] = scanner.nextInt();
}
/*
* 根据水流的方向确定遍历的方向以及起终点
*/
if (current) {
start = n - 1;
end = -1;
step = -1;
} else {
start = 0;
end = n;
step = 1;
}
/*
* 根据方向遍历并维护单调栈,以获取连续的下一个更小的值
*/
for (int i = start; i != end; i += step) {
if (i == start) {
res[i] = 1;
} else if (d[i] >= d[i - step]) {
res[i] = res[i - step] + 1;
} else {
res[i] = 1;
while (!stack.isEmpty() && d[stack.peek()] > d[i]) {
stack.pop();
}
if (!stack.isEmpty()) {
res[i] += stack.size();
}
}
stack.push(i);
}
/*
* 输出对应结果
*/
for (int i : res) {
System.out.print(i + " ");
}
}
}
CPP
#include <iostream>
#include <vector>
#include <sstream>
#include <stack>
using namespace std;
int main() {
/*
* 结合输入的分区的数量，以初始化所用到的数据结构以及将各分区目标所在的深度存入
*/
string wind_str;
getline(cin, wind_str);
bool wind = (wind_str == "true");
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; i++) {
cin >> h[i];
}
vector<int> ans(n);
vector<int> res(n);
stack<int> stack;
int start, end, step;
/*
* 根据水流的方向确定遍历的方向以及起终点
*/
if (wind) {
start = n - 1;
end = -1;
step = -1;
} else {
start = 0;
end = n;
step = 1;
}
/*
* 根据方向遍历并维护单调栈,以获取连续的下一个更小的值
*/
for (int i = start; i != end; i += step) {
if (i == start) {
res[i] = 1;
} else if (step == 1 && i - step >= 0 && h[i] >= h[i - step]) {
res[i] = res[i - step] + 1;
} else {
res[i] = 1;
while (!stack.empty() && h[stack.top()] > h[i]) {
stack.pop();
}
if (!stack.empty()) {
res[i] += stack.size();
}
}
stack.push(i);
}
/*
* 输出对应结果
*/
for (int i : res) {
cout << i << " ";
}
cout << endl;
return 0;
}
H
思路
本题改编自陈越姥姥的7-13 最短工期,出这个题目是因为目前临近蓝桥杯和天梯赛等，这些比赛我校比较重视，发现它们图论中拓扑排序的题目出得比较多，一番甄选后选择了这个比较巧妙的题目。（因为防止直接用样例搜索到原题作弊，故样例只是随便生成了一个，但是原定生成50%联通图的随机数据生成器因为数据量太小恰巧没有生成到联通图，故比赛开始时的样例确实欠妥）
本题其实只需要进行加入判断成环的拓扑排序并获取最长的时间即可，
但是大家往往容易忽视的是还有一个关键知识点————关键路径问题
使我们在解题时产生诸多疑问。
拓扑排序 简单的说就是必须通过这个序列去依次完成任务
在这个形成的序列中，某一个元素，它的依赖关系一定在它前面。
全代码中最让人疑惑的一定是以下代码，找最快拼完的时间，为啥反而找最长？
int max0 = 0;
for (int i = 0; i < n; i++)
max0 = Math.max(max0, dis[i]); // 找出最大的完成时间
System.out.println(max0); // 输出最短时间
举一个例子，对于
9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4
很多人可能认为0-4这条路径。从0到1，0到2，只能依次走完故选择最小的路径，
这是完全错误的想法。其实两条路都要走，且可以同时走。
依据拓扑排序，在0到1，0到2，1到4，2到4都走完时才能进行4，即4点入度为0才能进行4
显然0->1->4消耗的时间为7而0->2->4的时间为5，走7还是走5呢？
显然选择7，因为选择5，花费7的任务并没有完成，也就不满足4入度为0的条件
也就是说最快拼完的时间实际上是找最长时间来保证先前所有任务的完成。
参考代码
Java
import java.io.*;
import java.util.*;
class Pair {
int key;
int value;
public Pair(int first, int second) {
this.key = first;
this.value = second;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
public class Main{
/*
* 初始化待用的全局变量及数据结构
*/
static int maxVertex = 100005;
static ArrayList<Pair>[] G = new ArrayList[maxVertex];
static int n, m;
static ArrayList<Integer> zerodu = new ArrayList<>();
static int[] rdu = new int[maxVertex];
static int[] dis = new int[maxVertex];
/*
* 利用基于BFS（以队列实现）的拓扑排序，获取最快拼完的时间，即最长时间
*/
static boolean toposort() {
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (rdu[i] == 0)
q.offer(i);
}
while (!q.isEmpty()) {
int father = q.poll();
zerodu.add(father);
for (Pair p : G[father]) {
int v = p.getKey();
int w = p.getValue();
rdu[v]--;
if (rdu[v] == 0)
q.offer(v);
dis[v] = Math.max(dis[v], dis[father] + w);
}
}
return zerodu.size() == n;
}
public static void main(String[] args) throws IOException {
/*
* 结合输入的n、m初始化待用的数据结构
*/
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < n; i++) {
G[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int x = sc.nextInt();int y = sc.nextInt();int w = sc.nextInt();
G[x].add(new Pair(y, w));
rdu[y]++;
}
/*
* 判断是否成环以及获取最快拼完的时间/最长时间
*/
if (toposort()) {
int max0 = 0;
for (int i = 0; i < n; i++)
max0 = Math.max(max0, dis[i])
System.out.println(max0);
} else {
System.out.println("NOWAY");
}
}
}
CPP
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
// 定义Pair类，用于存储键值对
class Pair {
public:
int key;
int value;
Pair(int first, int second) : key(first), value(second) {}
};
const int maxVertex = 100005;
std::vector<Pair> G[maxVertex];
int n, m;
std::vector<int> zerodu;
int rdu[maxVertex];
int dis[maxVertex];
// 基于BFS的拓扑排序，获取最快拼完的时间，即最长时间
bool toposort() {
std::queue<int> q;
for (int i = 0; i < n; i++) {
if (rdu[i] == 0)
q.push(i);
}
while (!q.empty()) {
int father = q.front();
q.pop();
zerodu.push_back(father);
for (Pair& p : G[father]) {
int v = p.key;
int w = p.value;
rdu[v]--;
if (rdu[v] == 0)
q.push(v);
dis[v] = std::max(dis[v], dis[father] + w);
}
}
return zerodu.size() == n;
}
int main() {
// 输入n、m初始化数据结构
std::cin >> n >> m;
for (int i = 0; i < n; i++) {
G[i].clear();
}
for (int i = 0; i < m; i++) {
int x, y, w;
std::cin >> x >> y >> w;
G[x].emplace_back(y, w);
rdu[y]++;
}
// 判断是否成环以及获取最快拼完的时间/最长时间
if (toposort()) {
int max0 = 0;
for (int i = 0; i < n; i++)
max0 = std::max(max0, dis[i]);
std::cout << max0 << std::endl;
} else {
std::cout << "NOWAY" << std::endl;
}
return 0;
}
I
思路
本题改编自2022年第十三届蓝桥杯大赛软件类决赛Java大学B组真题的J 好数之和,这个题目看着难度不太高，但实际和天梯赛L3-1一个难度，思路好想但具体实现比较困难 这段代码的目的是解决一个寻数的问题，即给定一个上界 N 和一个下界 M，计算 N 到 M 之间（包含 N 和 M）所有包含 2302 的数的和是多少。这个问题可以按照每个数的位数来分解问题，从高位到低位依次确定每一位的数字，同时记录一些状态，如前缀和后缀，来避免重复计算。
假设 num 是 12345678,具体来讲即是：
- 首先，判断 num 是否小于 2302，不是，所以继续。
- 然后，获取 num 的位数 n，为 8。
- 接着，初始化 x, y, z，为 2302，10000，1。
- 接着，从最高位到第四位循环，即从 0 到 4：
- 取出前缀 prefix，为 num / y，即 1234。
- 遍历当前位可以取的数字，即从 0 到 1233：
- 遍历后缀可以取的数字，即从 0 到 9：
- 构造一个数 m，为 j * y + x + k，例如，如果 j 是 1000，x 是 2302，k 是 8，那么 m 就是 10002302。
- 判断 m 的尾部是否包含 2302，不是，所以将 m 加入 res。
- 遍历后缀可以取的数字，即从 0 到 9：
- 判断临界情况，即当前位等于 prefix 的情况，用 flag 表示，为 (num / z) % 10000，即 5678。
- 确定后缀的上界 up，为 z，即 10，因为 flag 大于 2302。
- 遍历后缀可以取的数字，即从 0 到 9：
- 构造一个数 m，为 prefix * y + x + j，例如，如果 prefix 是 1234，x 是 2302，j 是 8，那么 m 就是 12342302。
- 判断 m 的尾部是否包含 2302，不是，所以将 m 加入 res。
- 更新 x, y, z 的值，分别乘以 10，即 23020，100000，10。
- 最后，返回 res，为 12342302 + 10002302 + ... + 123402302 + ... + 1234562302，即 37967062096。
参考代码
注：因为数据比较大，所有题解std均需要增加快读快写才能通过，由于篇幅限制，此处不展示快读快写相关代码
Java
import java.util.Scanner;
public class Main {
/*
* 1~l间的好数之和减去1~r间的好数之和即为l到r
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long l = sc.nextLong(), r = sc.nextLong();
System.out.println(dfs(r) - dfs(l - 1));
}
/*
* 按照需要搜索满足好数，并使res加上它们
*/
public static long dfs(long num) {
if (num < 2302)
return 0;
long n = getLength(num), x = 2302, y = 10000, z = 1;
long res = 0;
for (long i = 0; i < n - 3; i++) {
long prefix = num / y;
for (long j = 0; j < prefix; j++) {
for (long k = 0; k < z; k++) {
long m = (long) j * y + x + k;
res += isValid(m % (z * 1000L)) ? 0 : m;
}
}
long flag = (num / z) % 10000;
long up = flag == 2302 ? num % z + 1 : flag < 2302 ? 0 : z;
for (long j = 0; j < up; j++) {
long m = (long) prefix * y + x + j;
res += isValid(m % (z * 1000L)) ? 0 : m;
}
y *= 10;x *= 10;z *= 10;
}
return res;
}
/*
* 判断是否合法，即是否包含2302
*/
public static boolean isValid(long x) {
String s = String.valueOf(x);
return s.contains("2302");
}
/*
* 获得对应长度
*/
public static long getLength(long x) {
long res = 0;
while (x != 0) {
res++;
x /= 10;
}
return res;
}
}
CPP
#include <iostream>
#include <string>
// 判断是否合法，即是否包含2302
bool isValid(long x) {
std::string s = std::to_string(x);
return s.find("2302") != std::string::npos;
}
// 获得对应长度
long getLength(long x) {
long res = 0;
while (x != 0) {
res++;
x /= 10;
}
return res;
}
// 按照需要搜索满足好数，并使res加上它们
long dfs(long num) {
if (num < 2302)
return 0;
long n = getLength(num), x = 2302, y = 10000, z = 1;
long res = 0;
for (long i = 0; i < n - 3; i++) {
long prefix = num / y;
for (long j = 0; j < prefix; j++) {
for (long k = 0; k < z; k++) {
long m = j * y + x + k;
res += isValid(m % (z * 1000L)) ? 0 : m;
}
}
long flag = (num / z) % 10000;
long up = flag == 2302 ? num % z + 1 : flag < 2302 ? 0 : z;
for (long j = 0; j < up; j++) {
long m = prefix * y + x + j;
res += isValid(m % (z * 1000L)) ? 0 : m;
}
y *= 10; x *= 10; z *= 10;
}
return res;
}
int main() {
long l, r;
std::cin >> l >> r;
std::cout << dfs(r) - dfs(l - 1) << std::endl;
return 0;
}
京公网安备 11010502036488号