天梯赛备战的一些杂题

发表于 2022-05-26 | 更新于 2022-05-30

武士女孩帽子剑雨天 Ůսʿ guweiz 4k高清壁纸_彼岸图网

杂题选做

7-2 出栈序列的合法性

给定一个最大容量为 M 的堆栈，将 N 个数字按 1, 2, 3, …, N 的顺序入栈，允许按任何顺序出栈，则哪些数字序列是不可能得到的？例如给定 M=5、N=7，则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 }，但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。

输入格式：

输入第一行给出 3 个不超过 1000 的正整数：M（堆栈最大容量）、N（入栈元素个数）、K（待检查的出栈序列个数）。最后 K 行，每行给出 N 个数字的出栈序列。所有同行数字以空格间隔。

输出格式：

对每一行出栈序列，如果其的确是有可能得到的合法序列，就在一行中输出YES，否则输出NO。

输入样例：

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

输出样例：

YES
NO
NO
YES
NO

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;

const int N = 1010;

int n, m, k;
int in[N], out[N], stk[N];
int tt;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	scanf("%d%d%d", &m, &n, &k);
	for(int i = 0; i < n; i ++ )
		in[i] = i + 1;
	while(k -- ) {
		int flag = 0;
		for(int i = 0; i < n; i ++ )
			scanf("%d", &out[i]);
		tt = -1;
		for(int i = 0, j = 0; i < n;) {
			if(in[i] != out[j]) {
			// 鍏ユ爤
				if(tt == m - 1) break;
				stk[++ tt] = in[i];
				i ++ ;
			} else {
				if(tt == m - 1) break;
				i ++ ; j ++ ;
				while(tt > -1) {
					if(stk[tt] == out[j])
						j ++, tt --;
					else break;	
				}
			}
		}
		if(tt == -1) puts("YES");
		else puts("NO");
	}

    return 0;
}

7-16 根据后序和中序遍历输出先序遍历

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

输入格式:

第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:

在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:

1
2
3

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

1	Preorder: 4 1 3 2 6 5 7

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 35;

int n;
int last[N], in[N];
int flag = 0;

void PrePrintf(int root, int l, int r) {
	if(l > r) return ;
	int i = l;
	while(i < r && last[root] != in[i]) i ++ ;
    if(flag) printf(" ");
	flag = 1;
	printf("%d",in[i]);
    // 根节点减右子树的长度（r - i + 1)
	PrePrintf(root - r - 1 + i, l, i - 1);
	PrePrintf(root - 1, i + 1, r);
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &last[i]);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &in[i]);

	printf("Preorder: ");
	PrePrintf(n, 1, n);

    return 0;
}

7-5 树的遍历

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

1
2
3

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

1	4 1 6 3 5 7 2

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 35;

struct Tree {
	int data;
	struct Tree *left, *right;
};

int n;
int last[N], in[N];
int flag = 0;
queue<Tree*> q;

Tree* PrePrintf(int root, int l, int r) {
	Tree *T = NULL;
	if(l > r) return T;
	int i = l;
	while(i < r && last[root] != in[i]) i ++ ;
	T = (Tree *) malloc(sizeof(Tree));
	T->data = in[i];
	T->left = PrePrintf(root - r - 1 + i, l, i - 1);
	T->right = PrePrintf(root - 1, i + 1, r);
	return T;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &last[i]);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &in[i]);

	Tree *root;
	root = PrePrintf(n, 1, n);
	q.push(root);
	while(!q.empty()) {
		auto t = q.front();
		q.pop();
		if(flag) printf(" ");
		flag = 1;
		printf("%d", t->data);
		if(t->left != NULL) q.push(t->left);
		if(t->right != NULL) q.push(t->right);
	}
    return 0;
}

7-7 N个数求和 (20 分)

本题的要求很简单，就是求N个数字的和。麻烦的是，这些数字是以有理数分子/分母的形式给出的，你输出的和也必须是有理数的形式。

输入格式：

输入第一行给出一个正整数N（≤100）。随后一行按格式a1/b1 a2/b2 ...给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符号一定出现在分子前面。

输出格式：

输出上述数字和的最简形式 —— 即将结果写成整数部分分数部分，其中分数部分写成分子/分母，要求分子小于分母，且它们没有公因子。如果结果的整数部分为0，则只输出分数部分。

输入样例1：

1 2	5 2/5 4/15 1/30 -2/60 8/3

输出样例1：

3 1/3

输入样例2：

1
2

2
4/3 2/3

输出样例2：

输入样例3：

1 2	3 1/3 -1/6 1/8

输出样例3：

7/24

思路：

读入分子分母，储存在数组中，声明三个变量来储存答案。
分数的加减通常分三步：
- 通分，找到分母的最小公倍数。
- 计算，分子按照分母扩大的倍数扩大相应倍数，然后计算加减。
- 约分，如果分子大于分母则计算出整数部分，当分子小于分母时说明已经到了最小，找到分子和分母的最大公约数，同除即可。
注意：输出格式，答案为0的时候的输出，有负数的输出，注意符号。

AC代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 110;

// resz 是答案分子，resm是答案分母，resk是答案整数 
LL n, resm, resz, resk;
LL a[N], b[N]; 

// 最大公约数 
LL maxYab(LL a, LL b) {
	return b ? maxYab(b, a % b) : a;
}
// 最小公倍数 
LL minMab(LL a, LL b) {
	return a*b/maxYab(a,b);
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) {
		scanf("%lld/%lld",&a[i], &b[i]);
	}
	LL k = 0;
	for(int i = 1; i <= n; i ++ ) {
		for(int j = i + 1; j <= n; j ++ ) {
			k = max(k, minMab(b[i], b[j]));
		}
	}
	LL sumz = 0;
	resm = k;
	for(int i = 1; i <= n; i ++ ) {
		sumz += a[i] * (k / b[i]);
	}
	int sign = 1;
	if(sumz < 0) {
		sign = -1;
		sumz *= sign;
	}
	resz = sumz;
	if(sumz >= k) {
		resk = sumz / resm;
		resz = sumz - resk * resm;
	}
	LL t = maxYab(resz, resm);
	resz /= t;
	resm /= t;
	int flag = 0;
	if(resz == 0 && sign == -1) resk *= sign;
	if(resk != 0) {
		printf("%lld", resk);
		flag = 1;
	}
	if(resz != 0){
		if(flag) printf(" ");
		printf("%lld/%lld", resz * sign, resm);
	}
	if(resz == 0 && resk == 0)
		printf("0");
	
	return 0; 
}

7-8 A-B (20 分)

本题要求你计算A−B。不过麻烦的是，A和B都是字符串 —— 即从字符串A中把字符串B所包含的字符全删掉，剩下的字符组成的就是字符串A−B。

输入格式：

输入在2行中先后给出字符串A和B。两字符串的长度都不超过104，并且保证每个字符串都是由可见的ASCII码和空白字符组成，最后以换行符结束。

输出格式：

在一行中打印出A−B的结果字符串。

输入样例：

1 2	I love GPLT! It's a fun game! aeiou

输出样例：

1	I lv GPLT! It's fn gm!

AC代码：

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>

using namespace std;

const int N = 10010;

string str, t;
int cnt;

int main() {
	getline(cin, str);
	getline(cin, t);
	for(int i = 0; i < str.size(); i ++ ) {
		if(t.find(str.at(i)) != t.npos)
			continue;
		else
		    printf("%c", str.at(i));
	}

	return 0; 
}

7-10 多项式A除以B (25 分)

这仍然是一道关于A/B的题，只不过A和B都换成了多项式。你需要计算两个多项式相除的商Q和余R，其中R的阶数必须小于B的阶数。

输入格式：

输入分两行，每行给出一个非零多项式，先给出A，再给出B。每行的格式如下：

1	N e[1] c[1] ... e[N] c[N]

其中N是该多项式非零项的个数，e[i]是第i个非零项的指数，c[i]是第i个非零项的系数。各项按照指数递减的顺序给出，保证所有指数是各不相同的非负整数，所有系数是非零整数，所有整数在整型范围内。

输出格式：

分两行先后输出商和余，输出格式与输入格式相同，输出的系数保留小数点后1位。同行数字间以1个空格分隔，行首尾不得有多余空格。注意：零多项式是一个特殊多项式，对应输出为0 0 0.0。但非零多项式不能输出零系数（包括舍入后为0.0）的项。在样例中，余多项式其实有常数项-1/27，但因其舍入后为0.0，故不输出。

输入样例：

1 2	4 4 1 2 -3 1 -1 0 -1 3 2 3 1 -2 0 1

输出样例：

1 2	3 2 0.3 1 0.2 0 -1.0 1 1 -3.1

思路：

多项式除法：https://baike.baidu.com/item/%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%99%A4%E6%B3%95/2703247
用map储存每个多项式以指数为索引，用到temp来作为运算过程中的减数，每次用A去减temp最后A中储存的多项式即为余数。
答案由每次取出A的最高次与B的差和比值作为指数和系数，即ope是A和B的最高指数之差，opc是凑出A减temp为零的系数项，每次把ope和opc储存在res中，运算结束后res储存的即为商。
有可能会出现0多项式，按照题目要求输出就可以了。
分数到小数可能会有误差，所以用相减的值去和0.0000001比较，如果大于即认定该项为0。
注：系数保留1位小数，所以如果是<0.05的系数四舍五入后为0即不输出，所以要判断一下是否有要输出的多项式，如果没有直接输出题目要求的零多项式即可。

AC代码：

#include <iostream>
#include <algorithm>
#include <math.h>
#include <map>

using namespace std;

const int N = 10010;

int n;
map<int, double> a, b, t, res;
int maxa = -1, maxb = -1, maxres = -1, maxt = -1;

int main() {
	int e, c;
	// 读入 A 
	scanf("%d", &n);
	for(int i = 0; i < n; i ++ ) {
		scanf("%d%d", &e, &c);
		a[e] = c;
		maxa = max(maxa, e); 
	}
	// 读入 B 
	scanf("%d", &n);
	for(int i = 0; i < n; i ++ ) {
		scanf("%d%d", &e, &c);
		b[e] = c;
		maxb = max(maxb, e);
	}
	
	int ope;
	double opc;
	
	while(maxa >= maxb) {
		maxt = -1;
		ope = maxa - maxb;
		opc = 1.0 * a[maxa] / b[maxb];
		res[ope] = opc;
		maxres = max(maxres, ope);
		
		// 求减数
		for(int i = maxb; i >= 0; i -- ) {
			t[i + ope] = b[i] * opc;
		}
		// 运算减法
		for(int i = maxa; i >= 0; i -- ) {
			a[i] = a[i] - t[i];
			if(fabs(a[i]) >= 0.00000001) {
				maxt = max(maxt, i);
			}
		}
		maxa = maxt;
	}
	
	// 输出 
	// 商输出
	int cnt = 0;
	for(int i = maxres; i >= 0; i -- ) {
		if(fabs(res[i]) >= 0.05) cnt ++;
	}
	if(cnt == 0) printf("0 0 0.0\n");
	else {
		printf("%d", cnt);
		for(int i = maxres; i >= 0; i -- ) {
			if(fabs(res[i]) >= 0.05) {
				printf(" %d %0.1lf", i, res[i]);
			}
		}
		printf("\n");
	}
	// 余数输出
	cnt = 0;
	for(int i = maxa; i >= 0; i -- ) {
		if(fabs(a[i]) >= 0.05) cnt ++;
	}
	if(cnt == 0) printf("0 0 0.0");
	else {
		printf("%d", cnt);
		for(int i = maxa; i >= 0; i -- ) {
			if(fabs(a[i]) >= 0.05) {
				printf(" %d %0.1lf", i, a[i]);
			}
		}
	}
	
	return 0; 
}

7-8 圆形体体积计算器 (20 分)

本题要求实现一个常用圆形体体积的计算器。计算公式如下：

球体体积 V=34πr3，其中r是球体半径。
圆柱体体积 V=πr2h，其中r是底圆半径，h是高。
圆锥体体积 V=31πr2h，其中r是底圆半径，h是高。

输入格式：

在每次计算之前，要求输出如下界面：

1-Ball
2-Cylinder
3-Cone
other-Exit
Please enter your command:

然后从标准输入读进一个整数指令。

输出格式：

如果读入的指令是1或2或3，则执行相应的体积计算；如果是其他整数，则程序结束运行。

当输入为1时，在计算球体体积之前，打印Please enter the radius:，然后读入球体半径，完成计算；
当输入为2时，在计算圆柱体体积之前，打印Please enter the radius and the height:，然后读入底圆半径和高，完成计算；
当输入为3时，在计算圆锥体体积之前，打印Please enter the radius and the height:，然后读入底圆半径和高，完成计算。

计算结果在一行内输出，保留小数点后两位。

输入样例：

输出样例：

1-Ball
2-Cylinder
3-Cone
other-Exit
Please enter your command:
Please enter the radius:
33.51
1-Ball
2-Cylinder
3-Cone
other-Exit
Please enter your command:
Please enter the radius and the height:
18.10
1-Ball
2-Cylinder
3-Cone
other-Exit
Please enter your command:

思路：

把每个要求的面积单独做出来，按题给方式输入，分类去求各个面积。
圆周率要精确到小数点后10位，不然有5分拿不到。

AC代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100;


double f1(double r) {
	return 4.0 / 3.0 * 3.14159265357 * r * r * r;
}
double f2(double r, double h) {
	return 3.14159265357 * r * r * h;
}
double f3(double r, double h) {
	return 1.0 / 3.0 *3.14159265357 * r * r * h;
}
void print() {
	puts("1-Ball");
	puts("2-Cylinder");
	puts("3-Cone");
	puts("other-Exit");
	puts("Please enter your command:");
}
int main() {
	int x;
	double r, h;
	while(1) {
		print();
		scanf("%d", &x);
		if(x != 1 && x != 2 && x != 3) break;
		if(x == 1) {
			puts("Please enter the radius:");
			scanf("%lf", &r);
			double t = f1(r);
			if(t == 0) printf("0\n");
			else
				printf("%.2lf\n", f1(r));
		} else if (x == 2) {
			puts("Please enter the radius and the height:");
			scanf("%lf%lf", &r, &h);
			double t = f2(r, h);
			if(t == 0) printf("0\n");
			else
				printf("%.2lf\n", f2(r, h));
		} else if (x == 3) {
			puts("Please enter the radius and the height:");
			scanf("%lf%lf", &r, &h);
			double t = f3(r, h);
			if(t == 0) printf("0\n");
			else
				printf("%.2lf\n", f3(r, h));
		}
	}
	
	return 0;
}

7-9 出栈序列的合法性 (25 分)

输入格式：

输出格式：

对每一行出栈序列，如果其的确是有可能得到的合法序列，就在一行中输出YES，否则输出NO。

输入样例：

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

输出样例：

YES
NO
NO
YES
NO

思路：

模拟入栈和出栈。
如果两个指针指向的元素不相等，则先判断栈的长度有没有超出，再把入栈序列入栈。
如果两个指针指向的元素相等，则两个指针同时向后移动一位，然后再检查栈顶的元素与出栈序列的元素是否相同，若相同则弹出同时出栈指针后移，出栈时先判断栈的长度有没有超出。
最后用栈是否为空判断序列是否合法。

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;

const int N = 1010;

int n, m ,k;
int a[N], b[N];

int main() {
	scanf("%d%d%d", &m, &n, &k);
	for(int i = 1; i <= n; i ++ ) {
		a[i] = i;
	}
	while(k -- ) {
		stack<int> stk;
		for(int i = 1; i <= n; i ++ ) {
			scanf("%d", &b[i]);
		}
		int i = 1, j = 1;
		while(i <= n) {
			if(a[i] != b[j]) {
				if(stk.size() == m) break;
				stk.push(a[i]);
				i ++;
			} else {
				if(stk.size() == m) break;
				i ++; j ++;
				while(!stk.empty()) {
					if(stk.top() == b[j])
					    j ++, stk.pop();
					else break; 
				}
			}
		}
		if(!stk.empty()) puts("NO");
		else puts("YES");
	}
	
	
	return 0;
}

7-10 前序序列创建二叉树 (25 分)

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以二叉链表存储）。例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，代表一棵空树。然后再对二叉树进行中序遍历，输出遍历结果。

输入格式:

多组测试数据，每组测试数据一行，该行只有一个字符串，长度不超过100。

输出格式:

对于每组数据，

输出二叉树的中序遍历的序列，每个字符后面都有一个空格。

每组输出一行，对应输入的一行字符串。

输入样例:（及其对应的二叉树）

1	abc##de#g##f###

输出样例:

1	c b e g d f a

思路：

创建结构体储存二叉树，用一个独立指针去遍历输入字符串的每一个值，每次询问结束后把指针归零。
创建二叉树，中序遍历调用递归即可。

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdlib.h>

using namespace std;

const int N = 110;

struct node {
	char x;
	struct node *l;
	struct node *r;
};

char str[N];
int k;

node* creatTree() {
	if(str[k] == '#'){
		k ++; 
		return NULL;
	}
	node* root = (node*)malloc(sizeof(node));
	root->x = str[k];
	k ++;
	root->l = creatTree();
	root->r = creatTree();
	return root;
}
void inPrint(node* root) {
	if(root == NULL) return;
	if(root->l != NULL)
		inPrint(root->l);
	printf("%c ", root->x);
	if(root->r != NULL)
	    inPrint(root->r); 
}
int main() {
	while(scanf("%s", str) != EOF) {
		node* head = creatTree();
		inPrint(head);
		k = 0;
		puts("");
	}
	
	return 0;
}

L1-8 均是素数 (20 分)

在给定的区间 [m,n] 内，是否存在素数 p、q、r（p<q<r），使得 pq+r、q**r+p、r**p+q 均是素数？

输入格式：

输入给出区间的两个端点 0<m<n≤1000，其间以空格分隔。

输出格式：

在一行中输出满足条件的素数三元组的个数。

输入样例：

1 35

输出样例：

样例解读

满足条件的 10 组解为：

2, 3, 5
2, 3, 7
2, 3, 13
2, 3, 17
2, 5, 7
2, 5, 13
2, 5, 19
2, 5, 31
2, 7, 23
2, 13, 17

思路：

筛出范围内的素数，然后三重循环求答案。
注：判断是否为素数的函数，如果循环中发现不是素数，直接return即可，否则会很慢，然后超时。

AC代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
int primes[N], cnt;
int st[N];

int isprime(int x) {
	if(x <= 1) return 0;
	for(int i = 2; i * i <= x; i ++ ) {
		if(x % i == 0) return 0;
	}
	return 1;
}
void getprimes(int x) {
	for(int i = 2; i <= n; i ++ ) {
		if(!st[i]) primes[cnt ++ ] = i;
		for(int j = 0; primes[j] * i <= n; j ++ ) {
			st[primes[j] * i] = 1;
			if(i % primes[j] == 0) break;
		}
	}
}
int find(int x) {
	if(isprime(x)) return 1;
	return 0;
}
int main() {
	scanf("%d%d", &m, &n);
	getprimes(n);
	int l, r;
	l = 0;
	for(int i = 0; i < cnt; i ++ ) {
		if(primes[i] >= m) {
			l = i;
			break;
		}
	}
	r = cnt; 
	for(int i = 0; i < cnt; i ++ ) {
		if(primes[i] >= n) {
			r = i;
			break;
		}
	}
	int res = 0;
	for(int p = l; p <= r; p ++ ) {
		for(int q = p + 1; q <= r; q ++ ) {
			for(int j = q + 1; j <= r; j ++ ) {
				if(find(primes[p]*primes[q] + primes[j])
					&& find(primes[q]*primes[j] + primes[p])
					&& find(primes[j]*primes[p] + primes[q])) {
						res ++; 
					}
			}
		}
	}
	printf("%d\n", res);
	
	return 0;
}

本文作者: weienhua

本文链接: https://weienhua.github.io/2022/05/26/%E5%A4%A9%E6%A2%AF%E8%B5%9B%E5%A4%87%E6%88%98%E7%9A%84%E4%B8%80%E4%BA%9B%E6%9D%82%E9%A2%98/