题解 | 桂林学院2023年天梯赛省赛专题训练【1队、2队】

7-1 股票涨了吗

题目

马克吐温曾说：“10月，这是炒股最危险的月份；其他危险的月份有7月、1月、9月、4月、11月、5月、3月、6月、12月、8月和2月。"然而股票是那么的迷人，总有韭菜前仆后继的加入，并且有无数的韭菜自命不凡，想要从不可捉摸的市场中捕获出一些有趣的信息。

韭菜小CC在观察A股许多天后，终于下手买了一只走势优异、老板下周的回国的股票——乐视网(300104.SZ)。在入手之后，股价涨涨跌跌，老板却没有回国。股票好不容易涨了起来，却又跌了下去，又回到了几天前，这段时间便没有任何收益。现在，小CC想要知道以往离今天最近的且股价不低于今天的日子，看一看自己浪费了多少时间。

给出N天的股票价格，对每一天，分别输出此前价格不低于当天且离当天最近的日子（序号从0开始），如果不存在，则输出-1。

例如，连续6天的股价依次是4,3,10,8,8,9。

第0天前没有信息，因此输出−1；

第1天的价格是3，而第0天价格是4，不低于它且离它最近，因此输出0；

第2天的价格是10，此前没有不低于它的价格，因此输出是−1；

第5天的价格是9，第4天价格是8，低于它，因此继续向前看，第3天价格是8，同样低于，继续向前查找，直到第2天价格为10，不低于它，因此输出2。

综上，不低于当天且离当天最近的日子的序号分别是第−1,0,−1,2,3,2日。

输入格式:
第一行是正整数N≤10 
5，表示有N天的股价。
第二行是空格分割的N个非负整数，范围为[0,2 
31−1]，分别是每天的股价。输出格式:
仅一行，共N个数字，分别是此前价格不低于当天且离当天最近日子的序号，以空格分隔，行末没有多余的空格。以换行结束。输入样例:
6
4 3 10 8 8 9
输出样例:
-1 0 -1 2 3 2

思路

循环时定义一个max变量，记录前n-1个数的最大值。

当当前值大于max时直接输出-1，否则再开一个循环向前遍历，碰到第一个大于等于当前值的数就输出并break。

（不知道有没有类似upper_bound的函数就是倒序碰到第一个大于等于本身的数就输出下标并跳出循环）

参考代码(c++)

#include <bits/stdc++.h>
using namespace std;int main() {long long int n, flag = 0, max;cin >> n;int a[n];for (int i = 0; i < n; i++) {cin >> a[i];}cout << "-1";max = a[0];for (int i = 1; i < n; i++) {if (a[i] > max) {max = a[i];cout << " -1";} else {for (int j = i - 1; j >= 0; j--) {if (a[j] >= a[i]) {cout << " " << j;break;}}}}
}

7-2 都是黑幕

题目

*国选美大赛，总共有 n 个选手(编号从1到 n )， m 个评委。每个评委只能拿到一张选票，每张选票可以为编号 L 到 R 的选手加上一分。得分最高的选手就可以原地出道，走向人生巅峰。现在让您找出得分最高的选手。

输入格式:
第一行两个整数 n,m (1<=n,m<=100000)
接下来m行，每行输入两个整数 L 和 R (1<=L<=R<=n)输出格式:
按递增顺序输出每个选手的编号(注意不要有行末空格)输入样例:
在这里给出一组输入。例如：5 8
2 3
2 4
3 5
4 4
2 4
3 3
4 5
2 3
输出样例:
在这里给出相应的输出。例如：3

思路

暴力做法是for循环l到r区间，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，时间复杂度就会变成O(n*m)。过不了的。

使用差分算法才能过所有案例

差分算法介绍

参考代码(c++)

#include <bits/stdc++.h>
using namespace std;const int N = 100010;
int a[N], b[N];void insert(int l, int r) {b[l] += 1;b[r + 1] -= 1;
}int main() {int n, m, l, r, max = 0, flag = 0;cin >> n >> m;for (int i = 0; i < m; i++) {cin >> l >> r;insert(l, r);}for (int i = 1; i <= n; i++) {a[i] = a[i - 1] + b[i];if (a[i] > max) {max = a[i];}}for (int i = 1; i <= n; i++) {if (a[i] == max) {if (flag == 1) {cout << " ";}cout << i;if (flag == 0) {flag = 1;}}}
}

7-3 红豆生南国

题目

有诗云：

相思 （王维 唐）

红豆生南国， 春来发几枝。

愿君多采撷， 此物最相思。
那么，我们来采红豆吧！

假设红豆树是这个样子的：

这种红豆树的特点是：

每个结点都有一个正整数编号，标在结点内部。结点的编号各不相同。
最上方一层结点是 “红豆”（图中红圈所示的5个结点），这一层被称之为红豆层。
树的根结点、左子结点、右子结点、左子树、右子树等的定义与“数据结构”中的“二叉树”相同，但它毕竟是“自然界中的树”，树根在最下方，如图中的结点5
图中这棵红豆树是“完全二叉红豆树”，类似“数据结构”中的“完全二叉树”。（“完全二叉树”的定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是完美二叉树。对于一个有N个结点的二叉树，若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点，这样的树就是完全二叉树） 从图上看，就是：要么每一层（包括红豆层）的结点数达到最大值，要么只在红豆层的最右边缺少一些结点。
对于红豆树，我们定义两种遍历顺序：

正序遍历：先访问树根结点，再正序遍历其左子树，最后正序遍历其右子树
逆序遍历：先逆序遍历其右子树，再逆序遍历其左子树，最后访问树根结点
对于给定的一棵完全二叉红豆树以及一些要采撷的结点，计算每次采撷能采到的红豆数量。

注意：我们采的点，可能是红豆，也可能不是红豆。采撷一个结点的意思是，把这个结点及这个结点的子树的全部结点从树中采下来。

例如：若采结点7，这是红豆结点，我们将获得1颗红豆；若采结点11，这不是红豆结点（而是一个枝结点！），我们将获得红豆树的一枝，包含2个红豆结点（8和2）。

输入格式:
输入有四行。

第一行是一个不超过60的正整数N，表示完全二叉红豆树中的结点数量。

第二行是N个不超过1000的结点编号序列，以空格间隔，表示的是这棵树的逆序遍历序列。

第三行是一个不超过N的正整数K，表示进行K次采撷。

第四行是K个正整数，依次表示每次要采的结点编号。

输出格式:
输出包含K+1行，

前K行，对于输入的每个采撷的点，在一行输出相应获得的红豆数量。如果这个点已经被采掉了，则输出Zao Jiu Cai Diao Le!。如果这个点在原树中根本不存在，则输出Kan Qing Chu Le?。

最后一行，输出采撷结束之后，这棵红豆树的正序遍历序列，用空格分隔，最后一个结点之后没有空格。如果采撷结束之后树已空，则输出Kong Le!

输入样例1:
对于题目中给出的图，对应的输入是：12
10 4 3 12 6 7 1 2 8 11 9 5
4
15 12 11 2
输出样例1:
Kan Qing Chu Le?
1
2
Zao Jiu Cai Diao Le!
5 9 1 7 6
输入样例2:
对于题目中给出的图，对应的输入是：12
10 4 3 12 6 7 1 2 8 11 9 5
1
5
输出样例2:
5
Kong Le!

思路

没写出来

参考代码(c++)

没写出来

7-4 超级玛丽

题目

假定有n个城堡，编号为1至n，有的城堡之间有道路直接相连，有的城堡之间没有道路直接相连。马里奥现在准备从一个城堡出发前往另一个城堡，它有一个魔法棒，可以瞬时通过一条道路，即以0时间通过这条道路，但魔法棒最多只能用一次。马里奥想以最短的时间到达目的地，请编写程序为马里奥选定一条路线以及在什么地方使用魔法棒。假定所有道路为双向，保证从起点肯定能到达目的地。

输入格式:
输入第一行为4个整数n、s、t、m，分别表示城堡数（编号为1至n，n不超过10000），马里奥所在的起点s和想去的终点t，城堡间的道路数目。接下来m行，每行为3个正整数a、b、c，表示城堡a和城堡b之间有一条道路直接相连，通过该道路需要c分钟。

输出格式:
输出为空格间隔的2个整数，第1个整数为马里奥从起点到目的地所需的最短时间；第2个整数表示使用魔法棒的地点，即城堡编号，若有多个可能的地点，则输出编号最小者。

输入样例:
4 1 4 4
1 2 9
2 4 1
1 3 3
3 4 5
输出样例:
1 1

思路

将一条边长度设置0（一次循环，时间m），找最短路Dijska（时间nlogn），总时间m*nlogn

参考代码(c++)

没写完。。。。。。

没写出来

乱写的🔽

#include <bits/stdc++.h>
using namespace std;//将一条边长度设置0（一次循环，时间m），找最短路Dijska（时间nlogn），总时间m*nlogn
int r[10005][10005] = {0};
int liantong[10005][10005] = {0};int dij(int begin, int end) {if (liantong[begin][end] != -1) {return r[begin][end];} else {//		d[i][j - 1]}
}
int main() {int n, s, t, m, b, e, l;cin >> n >> s >> t >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {liantong[i][j] = -1;}}for (int i = 1; i <= m; i++) {cin >> b >> e >> l;r[b][e] = l;liantong[b][e] = 0;}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= n; j++) {
//			cout << r[i][j] << " ";
//		}
//		cout << endl;
//	}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= n; j++) {
//			cout << liantong[i][j] << " ";
//		}
//		cout << endl;
//	}dij(s, t);
}