天梯赛-练习集1_天梯赛题目

1.插松枝

题面：

人造松枝加工场的工人需要将各种尺寸的塑料松针插到松枝干上，做成大大小小的松枝。他们的工作流程（并不）是这样的：

• 每人手边有一只小盒子，初始状态为空。
• 每人面前有用不完的松枝干和一个推送器，每次推送一片随机型号的松针片。
• 工人首先捡起一根空的松枝干，从小盒子里摸出最上面的一片松针 —— 如果小盒子是空的，就从推送器上取一片松针。将这片松针插到枝干的最下面。
• 工人在插后面的松针时，需要保证，每一步插到一根非空松枝干上的松针片，不能比前一步插上的松针片大。如果小盒子中最上面的松针满足要求，就取之插好；否则去推送器上取一片。如果推送器上拿到的仍然不满足要求，就把拿到的这片堆放到小盒子里，继续去推送器上取下一片。注意这里假设小盒子里的松针片是按放入的顺序堆叠起来的，工人每次只能取出最上面（即最后放入）的一片。
• 当下列三种情况之一发生时，工人会结束手里的松枝制作，开始做下一个：

（1）小盒子已经满了，但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里，推送器上取到的松针压回推送器，开始下一根松枝的制作。

（2）小盒子中最上面的松针不满足要求，但推送器上已经没有松针了。此时将手中的松枝放到成品篮里，开始下一根松枝的制作。

（3）手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。

现在给定推送器上顺序传过来的 N 片松针的大小，以及小盒子和松枝的容量，请你编写程序自动列出每根成品松枝的信息。

输入格式：

输入在第一行中给出 3 个正整数：N（≤103），为推送器上松针片的数量；M（≤20）为小盒子能存放的松针片的最大数量；K（≤5）为一根松枝干上能插的松针片的最大数量。

随后一行给出 N 个不超过 100 的正整数，为推送器上顺序推出的松针片的大小。

输出格式：

每支松枝成品的信息占一行，顺序给出自底向上每片松针的大小。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

8 3 4
20 25 15 18 20 18 8 5

输出样例：

20 15
20 18 18 8
25 5

 题解：

#include<stdio.h>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
int n, m, k;
queue<int> q;
stack<int> s;
void solve() {
	while (1) {
		vector<int> v;
		bool flag = 0;
		while (1) {
			if (v.empty()) 
			{
				if (!s.empty())
				{
					v.push_back(s.top());
					s.pop();
				}
				else if (!q.empty())
				{
					v.push_back(q.front());
					q.pop();
				}
				else 			
					break;
			}
			else 
			{
				if (!s.empty() && s.top() <= v.back())
				{
					v.push_back(s.top());
					s.pop();
				}
				else
				{
					while (!q.empty() && s.size() <= m)
					{
						auto t = q.front();
						if (t <= v.back()) 
						{
							q.pop();
							v.push_back(t);
							break;
						}
						else {
							if (s.size() == m)
							{
								flag = 1;
								break;
							}
							else
							{
								s.push(t);
								q.pop();
							}
						}
					}
					if (q.empty() && (s.empty() || s.top() > v.back())) 
					{
						break;
					}
				}
			}
			if (flag || v.size() == k) 
				break;
		}
		for (int i = 0; i < v.size(); i++) {
			if (i != v.size() - 1) {
				cout << v[i] << ' ';
			}
			else {
				cout << v[i] << endl;
			}
		}
		if (s.empty() && q.empty()) {
			break;
		}
	}
}
 
int main()
{
 
	cin >> n >> m >> k;
 
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		q.push(x);
	}
 
	solve();
 
	return 0;
}

2.老板的作息表

题面：

新浪微博上有人发了某老板的作息时间表，表示其每天 4:30 就起床了。但立刻有眼尖的网友问：这时间表不完整啊，早上九点到下午一点干啥了？

本题就请你编写程序，检查任意一张时间表，找出其中没写出来的时间段。

输入格式：

输入第一行给出一个正整数 N，为作息表上列出的时间段的个数。随后 N 行，每行给出一个时间段，格式为：

hh:mm:ss - hh:mm:ss

其中 hh、mm、ss 分别是两位数表示的小时、分钟、秒。第一个时间是开始时间，第二个是结束时间。题目保证所有时间都在一天之内（即从 00:00:00 到 23:59:59）；每个区间间隔至少 1 秒；并且任意两个给出的时间区间最多只在一个端点有重合，没有区间重叠的情况。

输出格式：

按照时间顺序列出时间表中没有出现的区间，每个区间占一行，格式与输入相同。题目保证至少存在一个区间需要输出。

题解：

先对各段时间进行排序，然后前面的时间与上一个的后面的时间连不上的打出来，还需要添加头时间00：00：00和尾时间23：59：59

#include<stdio.h>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<pair<string, string>> q;
int main() 
{
    cin >> n;
    while (n--)
    {
        string a, b, c;
        cin >> a >> b >> c;
        q.push_back({ a, c });
    }
    q.push_back({ "", "00:00:00" });
    q.push_back({ "23:59:59", "" });
    sort(q.begin(), q.end());
    int m = q.size();
    for (int i = 0; i < m - 1; i++)
        if (q[i].second != q[i + 1].first)
            cout << q[i].second << " - " << q[i + 1].first << endl;
    return 0;
}

3.龙龙送外卖

题面：

龙龙是“饱了呀”外卖软件的注册骑手，负责送帕特小区的外卖。帕特小区的构造非常特别，都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树，根结点是外卖站，树上的结点就是要送餐的地址。

每到中午 12 点，帕特小区就进入了点餐高峰。一开始，只有一两个地方点外卖，龙龙简单就送好了；但随着大数据的分析，龙龙被派了更多的单子，也就送得越来越累……

看着一大堆订单，龙龙想知道，从外卖站出发，访问所有点了外卖的地方至少一次（这样才能把外卖送到）所需的最短路程的距离到底是多少？每次新增一个点外卖的地址，他就想估算一遍整体工作量，这样他就可以搞明白新增一个地址给他带来了多少负担。

输入格式:

输入第一行是两个数 N 和 M (2≤N≤105, 1≤M≤105)，分别对应树上节点的个数（包括外卖站），以及新增的送餐地址的个数。

接下来首先是一行 N 个数，第 i 个数表示第 i 个点的双亲节点的编号。节点编号从 1 到 N，外卖站的双亲编号定义为 −1。

接下来有 M 行，每行给出一个新增的送餐地点的编号 Xi​。保证送餐地点中不会有外卖站，但地点有可能会重复。

为了方便计算，我们可以假设龙龙一开始一个地址的外卖都不用送，两个相邻的地点之间的路径长度统一设为 1，且从外卖站出发可以访问到所有地点。

注意：所有送餐地址可以按任意顺序访问，且完成送餐后无需返回外卖站。

输出格式:

对于每个新增的地点，在一行内输出题目需要求的最短路程的距离。

题解：

#include<stdio.h>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
int aa[100010], beg = 0;
int  bj[100010], maxl = 0;
int dfs(int i, int l) {
	if (i == beg || bj[i] != 0) {
		maxl = max(maxl, bj[i] + l);
		return l * 2;
	}
	int p = dfs(aa[i], l + 1);
	bj[i] = bj[aa[i]] + 1;
	return p;
}
 
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> aa[i];
		if (aa[i] == -1)
			beg = i;
	}
	int sum = 0;
	while (m-- != 0) {
		int i;
		cin >> i;
		sum += dfs(i, 0);
		cout << sum - maxl << endl;
	}
 
}

4.大众情人

题面：

人与人之间总有一点距离感。我们假定两个人之间的亲密程度跟他们之间的距离感成反比，并且距离感是单向的。例如小蓝对小红患了单相思，从小蓝的眼中看去，他和小红之间的距离为 1，只差一层窗户纸；但在小红的眼里，她和小蓝之间的距离为 108000，差了十万八千里…… 另外，我们进一步假定，距离感在认识的人之间是可传递的。例如小绿觉得自己跟小蓝之间的距离为 2，则即使小绿并不直接认识小红，我们也默认小绿早晚会认识小红，并且因为跟小蓝很亲近的关系，小绿会觉得自己跟小红之间的距离为 1+2=3。当然这带来一个问题，如果小绿本来也认识小红，或者他通过其他人也能认识小红，但通过不同渠道推导出来的距离感不一样，该怎么算呢？我们在这里做个简单定义，就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。

一个人的异性缘不是由最喜欢他/她的那个异性决定的，而是由对他/她最无感的那个异性决定的。我们记一个人 i 在一个异性 j 眼中的距离感为 Dij​；将 i 的“异性缘”定义为 1/maxj∈S(i)​{Dij​}，其中 S(i) 是相对于 i 的所有异性的集合。那么“大众情人”就是异性缘最好（值最大）的那个人。

本题就请你从给定的一批人与人之间的距离感中分别找出两个性别中的“大众情人”。

输入格式：

输入在第一行中给出一个正整数 N（≤500），为总人数。于是我们默认所有人从 1 到 N 编号。

随后 N 行，第 i 行描述了编号为 i 的人与其他人的关系，格式为：

性别 K 朋友1:距离1 朋友2:距离2 …… 朋友K:距离K

其中 性别 是这个人的性别，F 表示女性，M 表示男性；K（<N 的非负整数）为这个人直接认识的朋友数；随后给出的是这 K 个朋友的编号、以及这个人对该朋友的距离感。距离感是不超过 106 的正整数。

题目保证给出的关系中一定两种性别的人都有，不会出现重复给出的关系，并且每个人的朋友中都不包含自己。

输出格式：

第一行给出自身为女性的“大众情人”的编号，第二行给出自身为男性的“大众情人”的编号。如果存在并列，则按编号递增的顺序输出所有。数字间以一个空格分隔，行首尾不得有多余空格。

#include<stdio.h>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
const int N = 510;
int g[N][N], sex[N], d[N];
int main()
{
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i == j) g[i][j] = 0;
			else g[i][j] = 1e9;
 
	for (int i = 1; i <= n; i++)
	{
		char op; int k; scanf(" %c %d", &op, &k);
		if (op == 'F') sex[i] = 1;
		else sex[i] = 2;
		for (int j = 1; j <= k; j++)
		{
			int a, b; scanf("%d:%d", &a, &b);
			g[i][a] = b;
		}
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
 
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (sex[i] != sex[j])
				d[i] = max(d[i], g[j][i]);
 
	int d1 = 1e9, d2 = 1e9;
	for (int i = 1; i <= n; i++)
	{
		if (sex[i] == 2) d1 = min(d1, d[i]);
		else d2 = min(d2, d[i]);
	}
 
	vector<int> a, b;
	for (int i = 1; i <= n; i++)
	{
		if (sex[i] == 2) continue;
		if (d[i] == d2) a.push_back(i);
	}
 
	for (int i = 1; i <= n; i++)
	{
		if (sex[i] == 1) continue;
		if (d[i] == d1) b.push_back(i);
	}
 
	printf("%d", a[0]);
	for (int i = 1; i < (int)a.size(); i++)
		printf(" %d", a[i]);
 
	puts("");
 
	printf("%d", b[0]);
	for (int i = 1; i < (int)b.size(); i++)
		printf(" %d", b[i]);
 
	return 0;
}

5.千手观音

题面:

人类喜欢用 10 进制，大概是因为人类有一双手 10 根手指用于计数。于是在千手观音的世界里，数字都是 10 000 进制的，因为每位观音有 1 000 双手 ……

千手观音们的每一根手指都对应一个符号（但是观音世界里的符号太难画了，我们暂且用小写英文字母串来代表），就好像人类用自己的 10 根手指对应 0 到 9 这 10 个数字。同样的，就像人类把这 10 个数字排列起来表示更大的数字一样，ta们也把这些名字排列起来表示更大的数字，并且也遵循左边高位右边低位的规则，相邻名字间用一个点 . 分隔，例如 pat.pta.cn 表示千手观音世界里的一个 3 位数。

人类不知道这些符号代表的数字的大小。不过幸运的是，人类发现了千手观音们留下的一串数字，并且有理由相信，这串数字是从小到大有序的！于是你的任务来了：请你根据这串有序的数字，推导出千手观音每只手代表的符号的相对顺序。

注意：有可能无法根据这串数字得到全部的顺序，你只要尽量推出能得到的结果就好了。当若干根手指之间的相对顺序无法确定时，就暂且按它们的英文字典序升序排列。例如给定下面几个数字：

pat
cn
lao.cn
lao.oms
pta.lao
pta.pat
cn.pat

我们首先可以根据前两个数字推断 pat < cn；根据左边高位的顺序可以推断 lao < pta < cn；再根据高位相等时低位的顺序，可以推断出 cn < oms，lao < pat。综上我们得到两种可能的顺序：lao < pat < pta < cn < oms；或者 lao < pta < pat < cn < oms，即 pat 和 pta 之间的相对顺序无法确定，这时我们按字典序排列，得到 lao < pat < pta < cn < oms。

输入格式：

输入第一行给出一个正整数 N (≤105)，为千手观音留下的数字的个数。随后 N 行，每行给出一个千手观音留下的数字，不超过 10 位数，每一位的符号用不超过 3 个小写英文字母表示，相邻两符号之间用 . 分隔。

我们假设给出的数字顺序在千手观音的世界里是严格递增的。题目保证数字是 104 进制的，即符号的种类肯定不超过 104 种。

输出格式：

在一行中按大小递增序输出符号。当若干根手指之间的相对顺序无法确定时，按它们的英文字典序升序排列。符号间仍然用 . 分隔。

题解：

buhui

6.关于深度优先搜索和逆序对的题应该不会很难吧这件事

题面：

给定一棵 n 个节点的树，其中节点 r 为根。求该树所有可能的 DFS 序中逆序对数量之和。

输入格式

第一行输入两个整数 n，r（2≤n≤3×105，1≤r≤n）表示树的大小与根节点。

对于接下来的 (n−1) 行，第 i 行输入两个整数 ui​ 与 vi​（1≤ui​,vi​≤n），表示树上有一条边连接节点 ui​ 与 vi​。

输出格式

输出一行一个整数，表示该树所有可能的 DFS 序中逆序对数量之和。由于答案可能很大，请对 10^9+7 取模后输出。

题解：

#include<stdio.h>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N = 300010, P = 1e9 + 7;
vector<int> g[N];
int sz[N], tr[N];
int n, root;
int sum = 1, s1, s2;
void add(int x, int y)
{
	for (int i = x; i < N; i += (i & -i))
		tr[i] += y;
}
int query(int x)
{
	int res = 0;
	for (int i = x; i; i -= (i & -i))
		res += tr[i];
	return res;
}
void dfs(int u, int fa)
{
	add(u, 1);
	s1 = (s1 + query(n) - query(u)) % P;
 
	sz[u] = 1;
	int cnt = 0;
	for (auto& j : g[u])
	{
		if (j == fa) continue;
		dfs(j, u);
		sz[u] += sz[j];
		cnt++;
	}
	for (int i = 1; i <= cnt; i++)
		sum = (LL)sum * i % P;
	s2 = (s2 + n - query(n) - sz[u] + 1) % P;
	add(u, -1);
}
int main()
{
	scanf("%d%d", &n, &root);
	for (int i = 0; i < n - 1; i++)
	{
		int a, b; scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(root, -1);
	int ans = ((LL)s1 * sum + (LL)s2 * sum % P * (P + 1) / 4) % P;
	printf("%d\n", ans);
	return 0;
}