前言
该博客保存了博主本人的刷题记录，博客中题源来自学长博客和CUMTOJ，但是由于本人记性不好，忘记了CUMTOJ的密码T T，如有错误敬请指正！
该博客的解题代码很大程度上参照了Acwing的模板，例如在链表题中常用数组来模拟。
实验一
问题 A: 一排里的位置交换
体育课上，老师把一排里的两个身高不同的同学的位置交换了一下以方便安排分组训练。你能编程模拟这个过程吗？
输入
第一行是自然数n(n小于100)，表示有n个数，第二行是n个表示身高的数据，第三行是要交换的两个同学的序号(按左起从1开始依次排序)。
输出
交换位置后的一排身高值。中间用空格间隔。
样例输入 Copy
5
152 155 120 145 160
2 5
样例输出 Copy
152 160 120 145 155
#include<iostream>
using namespace std;
int N;
int a[10010];
int main(){
cin>>N;
for(int i = 0 ; i < N ; i++) scanf("%d",&a[i]);
int m,n;
cin>>m>>n;
swap(a[m-1],a[n-1]);
for(int i = 0 ; i < N ; i++) printf("%d ",a[i]);
}
问题 B: 围成圈
假如有一次班里组织户外活动，同学们随机围坐成一圈做游戏，每个同学都记住了左右同学的编号，活动结束后，老师想让你帮忙复原当时大家坐的位置，你能通过每个同学记录的左右同学的编号，把当时大家坐的一圈情况复原吗？
输入
第一行是人数n(n<100)。从第二行开始n行，分别表示1-n编号的同学左右两个同学的编号。最后一行某个同学的编号K。
输出
围坐的这个圈里，从第K个同学开始顺时针的序列。
样例输入 Copy
5
4 5
5 3
2 4
3 1
1 2
3
样例输出 Copy
3 2 5 1 4
#include<iostream>
using namespace std;
const int N = 110;
int el[110],er[110];
int idx = 0;
int main(){
int n;
cin>>n;
for(int i = 1; i <= n; i++){
int a,b;
cin>>a>>b;
er[i] = a;
el[i] = b;
}
int k;
cin>>k;
int t = k;
do{
cout<<k<<' ';
k = er[k];
}while(k!=t);
}
问题 C: 十进制整数转二进制
二进制是计算机运算的基础，给你一个十进制整数，你能编程实现转二进制吗？
输入
第一行n，表示接着下边有n个十进制整数，每个占一行。
输出
对应每个十进制整数输出相应二进制数占一行。
样例输入 Copy
2
5
16
样例输出 Copy
101
10000
#include<iostream>
#include<stack>
using namespace std;
void Dec_to_Bin(int x){
stack<int> s;
int temp;
while(x){
temp = x%2;
s.push(temp);
x/=2;
}
while(!s.empty()){
cout<<s.top();
s.pop();
}
cout<<endl;
}
int main(){
int n;
cin>>n;
for(int i = 0; i < n; i++) {
int t;
cin>>t;
Dec_to_Bin(t);
}
}
问题 D: 进出栈
设栈S的初始状态为空，元素a, b, c, d, e, f, g 依次入栈，给你一个出栈序列，请编程判断出栈序列是否正确。
输入
占一行，为出栈序列。
输出
如果出栈学列是可能的，输出True，否则输出False。
样例输入 Copy
a b c d e f g
样例输出 Copy
True
#include<iostream>
#include<stack>
using namespace std;
const string alphabet = "abcdefg";
int main(){
char str[10];
for(int i = 0; i < 7 ; i++) cin>>str[i];
stack<char> s;
int k = 0;
for(int i = 0 ; i < 7 ; i++){
s.push(alphabet[i]);
while(s.top()==str[k]) {
s.pop();
k++;
if(s.empty()) break;
}
}
if(s.empty()) cout<<"True";
else cout<<"False";
return 0;
}
问题 E: 栈容量
设栈S的初始状态为空，元素a，b，c，d，e，f，g依次入栈，出栈顺序为b，d，c，f，e，a，g那么栈容量至少应该是3。如果任意给你一个出栈序列，你能编程判断相应的栈容量至少是多少吗？
输入
元素a，b，c，d，e，f，g依次入栈情况下的一种出栈序列。
输出
对应出栈序列的栈容量至少是多少。
样例输入 Copy
b d c f e a g
样例输出 Copy
3
问题 F: 自创语言
学了一段英语课之后，小名同学发现英语单词就是26个字母中若干个组合在一起的，于是他想自己也创立一种语言，为了简化单词，他计划只选26个小写字母的前n个符号构造长度也为n个符号的单词，构造好单词后，先要编写个词典，给每个单词有个解释以便人们学习他自创的语言。你能编程帮助按字典序输出所有长度为n的单词吗？
输入
占一行，为整数n(n<26)。
输出
所有由前n个符号构造长度也为n个符号的单词，按字典序每行输出一个单词。
样例输入 Copy
2
样例输出 Copy
aa
ab
ba
bb
#include<iostream>
using namespace std;
int k;
void printWord(string s, int n)
{
if (s.length() == n) {
cout << s << endl;
return;
}
for (char ch='a'; ch<='a'+k-1; ch++) {
printWord(s+ch, n);
}
}
int main(){
string s="";
cin>>k;
printWord(s,k);
return 0;
}
问题 G: 离队
体育课上，班上的同学排成了一排，结果有个同学突然感觉不适，需要去医院，就离队了，你能编程模拟离队后的状态吗？
输入
第一行是整数n(n<100),第二行有n个整数，第三行是k，表示从左开始第k个离队。
输出
输出离队后的数字序列。
样例输入 Copy
5
120 125 135 126 145
3
样例输出 Copy
120 125 126 145
#include<iostream>
using namespace std;
const int N = 110;
int e[N],ne[N];
int idx,head;
void init(){
head = -1;
idx = 0;
}
void del(int k){
ne[k] = ne[ne[k]];
}
void insert(int m,int k){
e[idx] = m; ne[idx] = ne[k];ne[k] = idx;idx++;
}
void insert_head(int m){
e[idx] = m; ne[idx] = head;head = idx;idx++;
}
int main(){
init();
int n;
cin>>n;
for(int i = 0; i < n ; i++){
int temp;
cin>>temp;
ne[idx] = idx+1;
e[idx] = temp;
idx++;
}
ne[idx-1] = -1;
head = 0;
int m,k;
cin>>m>>k;
insert(m,k-2);
int t = head;
while(t!=-1){
cout<<e[t]<<' ';
t = ne[t];
}
return 0;
}
问题 H: 入队
体育课上，上课铃响后，大家排成了一排，结果有一个同学迟到了，老师让他插在这一排的某个位置，你能编程模拟这个过程吗？
输入
第一行是整数n(n<100),第二行n个整数，第三行是整数m和要插入的位置k(位置从左往右依次从1排序)。
输出
入队后的n+1个数据序列。
样例输入 Copy
5
123 125 128 121 145
136 2
样例输出 Copy
123 136 125 128 121 145
#include<iostream>
using namespace std;
const int N = 110;
int e[N],ne[N];
int idx,head;
void init(){
head = -1;
idx = 0;
}
void del(int k){
ne[k] = ne[ne[k]];
}
void insert(int m,int k){
e[idx] = m; ne[idx] = ne[k];ne[k] = idx;idx++;
}
void insert_head(int m){
e[idx] = m; ne[idx] = head;head = idx;idx++;
}
int main(){
init();
int n;
cin>>n;
for(int i = 0; i < n ; i++){
int temp;
cin>>temp;
ne[idx] = idx+1;
e[idx] = temp;
idx++;
}
ne[idx-1] = -1;
head = 0;
int m,k;
cin>>m>>k;
insert(m,k-2);
int t = head;
while(t!=-1){
cout<<e[t]<<' ';
t = ne[t];
}
return 0;
}
实验二
问题 A: 满二叉树的前序遍历
题目描述
给你一个满二叉树的层次遍历序列，请编程输出该二叉树的前序遍历序列。
输入
第一行是n（n小于26）,表示有n个节点。第二行是该满二叉树的节点对应字母的层次遍历序列。
输出
输出该满二叉数的前序遍历序列。
样例输入 Copy
3
B A C
样例输出 Copy
BAC
#include<iostream>
using namespace std;
const int N = 100;
int n;
char a[N];
void visit(int idx)
{
if(idx > n) return;
cout<<a[idx];
visit(idx*2);
visit(idx*2+1);
}
int main(){
cin>>n;
for(int i = 1; i <= n; i++){
cin>>a[i];
}
visit(1);
return 0;
}
问题 B: 满二叉树的中序遍历
题目描述
给你一个满二叉树的层次遍历序列，请编程输出该二叉树的中序遍历序列。
输入
第一行是n（n小于26）,表示有n个节点。第二行是该满二叉树的节点对应字母的层次遍历序列。
输出
输出该满二叉数的中序遍历序列。
样例输入 Copy
3
B A C
样例输出 Copy
ABC
#include<iostream>
using namespace std;
const int N = 100;
int n;
char a[N];
void visit(int idx)
{
if(idx > n) return;
visit(idx*2);
cout<<a[idx];
visit(idx*2+1);
}
int main(){
cin>>n;
for(int i = 1; i <= n; i++){
cin>>a[i];
}
visit(1);
return 0;
}
问题 C: 满二叉树的后序遍历
题目描述
给你一个满二叉树的层次遍历序列，请编程输出该二叉树的后序遍历序列。
输入
第一行是n（n小于26）,表示有n个节点。第二行是该满二叉树的节点对应字母的层次遍历序列。
输出
输出该满二叉数的后序遍历序列。
样例输入 Copy
3
B A C
样例输出 Copy
ACB
#include<iostream>
using namespace std;
const int N = 100;
int n;
char a[N];
void visit(int idx)
{
if(idx > n) return;
visit(idx*2);
visit(idx*2+1);
cout<<a[idx];
}
int main(){
cin>>n;
for(int i = 1; i <= n; i++){
cin>>a[i];
}
visit(1);
return 0;
}
问题 D: 任意二叉树的前序遍历
题目描述
有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的前序遍历序列。
输入
第一行是n（n小于100）,表示有n个节点，每个节点按从1到n依次编号。第一行后有n行，每行三个正整数i、l、r，分别表示节点i及对应的左右孩子的编号，如果不存在孩子则以-1表示。三个整数之间用一个空格隔开。
输出
输出该二叉数的前序遍历序列。
样例输入 Copy
4
1 2 4
3 1 -1
2 -1 -1
4 -1 -1
样例输出 Copy
3 1 2 4
注：下列三题过于相似，此处只给出中序遍历结果，先序和后序遍历结果仅需调换visit函数中输出顺序即可。
#include<iostream>
using namespace std;
const int N = 110;
int el[N],er[N];
int n;
void visit(int root){
if(root > n || root == -1) return;
visit(el[root]);
cout<<root<<' ';
visit(er[root]);
}
int main(){
cin>>n;
for(int i = 1 ; i <= n; i++){
int k,l,r;
cin>>k>>l>>r;
el[k] = l;
er[k] = r;
}
int hash[n+1];
for(int i = 1; i <= n; i++) hash[i] = 1;
for(int i = 1; i <= n; i++){
if(el[i]) hash[el[i]] = 0;
if(er[i]) hash[er[i]] = 0;
}
int root;
for(int i = 1; i <= n; i++){
if(hash[i]) {
root = i;
break;
}
}
visit(root);
return 0;
}
问题 E: 任意二叉树的中序遍历
题目描述
有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的中序遍历序列。
输入
第一行是n（n小于100）,表示有n个节点，每个节点按从1到n依次编号。第一行后有n行，每行三个正整数i、l、r，分别表示节点i及对应的左右孩子的编号，如果不存在孩子则以-1表示。三个整数之间用一个空格隔开。
输出
输出该二叉数的中序遍历序列。
样例输入 Copy
4
1 2 4
3 1 -1
4 -1 -1
2 -1 -1
样例输出 Copy
2 1 4 3
略
问题 F: 任意二叉树的后序遍历
题目描述
有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的后序遍历序列。
输入
第一行是n（n小于100）,表示有n个节点，每个节点按从1到n依次编号。第一行后有n行，每行三个正整数i、l、r，分别表示节点i及对应的左右孩子的编号，如果不存在孩子则以-1表示。三个整数之间用一个空格隔开。
输出
输出该二叉数的后序遍历序列。
样例输入 Copy
4
1 2 4
4 -1 -1
2 -1 -1
3 1 -1
样例输出 Copy
2 4 1 3
略
问题 G: FBI树
题目描述
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为 B 串，全“1”串称为 I 串，既含“0”又含“1”的串则称为 F 串。
FBI 树是一棵二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为 2N 的“01”串 S 可以构造出一棵 FBI 树 T，递归的构造方法如下：
(1) T 的根结点为 R，其类型与串 S 的类型相同；
(2) 若串 S 的长度大于 1，可将串 S 从中间分开，分为等长的左右子串 S1 和 S2；由左子串 S1 构造 R 的左子树 T1，由右子串 S2 构造 R 的右子树 T2。
现在给定一个长度为 2N 的“01”串，请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。
输入
第一行是一个整数 N（0≤N≤10），第二行是一个长度为 2N 的“01”串。
输出
包括一行，这一行只包含一个字符串，即 FBI 树的后序遍历序列。
样例输入 Copy
3
10001011
样例输出 Copy
IBFBBBFIBFIIIFF
#include<iostream>
using namespace std;
int n;
string s;
void visit(int l,int r){
if(r>l){
visit(l,(l+r)/2);
visit((l+r)/2+1,r);
}
int is_B=1;
int is_I=1;
for(int i = l; i <=r ; i++){
if(s[i]=='1') is_B = 0;
if(s[i]=='0') is_I = 0;
}
if(is_B) cout<<'B';
else if(is_I) cout<<'I';
else cout<<'F';
}
int main(){
cin>>n>>s;
int len = s.size()-1;
visit(0,len);
return 0;
}
问题 H: 满二叉树的深度
题目描述
给你一个满二叉树的层次遍历序列，请编程输出该二叉树的深度。
输入
第一行是n（n小于26）,表示有n个节点。第二行是该满二叉树的节点对应字母的层次遍历序列。
输出
输出该满二叉数的深度。
样例输入 Copy
3
B A C
样例输出 Copy
2
#include<iostream>
using namespace std;
int depth(int n){
if(n == 1) return 1;
for(int h = 2;h < n;h++){
if((1<<(h-1)) - 1 < n && (1<<h)- 1 >= n){
return h;
}
}
}
int main(){
int n;
cin>>n;
for(int i = 0; i < n; i++){
int k;
cin>>k;
}
cout<<depth(n);
return 0;
}
实验三
问题 A: 任意二叉树的层次遍历
题目描述
有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的层次遍历序列。
输入
第一行是n（n小于100）,表示有n个节点，每个节点按从1到n依次编号。第一行后有n行，每行三个正整数i、l、r，分别表示节点i及对应的左右孩子的编号，如果不存在孩子则以-1表示。三个整数之间用一个空格隔开。
输出
输出该二叉数的层次遍历序列。
样例输入 Copy
4
1 2 4
3 1 -1
2 -1 -1
4 -1 -1
样例输出 Copy
3 1 2 4
#include<iostream>
#include<queue>
using namespace std;
const int N = 110;
int el[N],er[N];
int n;
void visit(int root){
queue<int> q;
q.push(root);
while(!q.empty()){
int tmp = q.front();
q.pop();
cout<<tmp<<' ';
if(el[tmp] != -1) q.push(el[tmp]);
if(er[tmp] != -1) q.push(er[tmp]);
}
}
int main(){
cin>>n;
for(int i = 1 ; i <= n; i++){
int k,l,r;
cin>>k>>l>>r;
el[k] = l;
er[k] = r;
}
int hash[n+1];
for(int i = 1; i <= n; i++) hash[i] = 1;
for(int i = 1; i <= n; i++){
if(el[i]) hash[el[i]] = 0;
if(er[i]) hash[er[i]] = 0;
}
int root;
for(int i = 1; i <= n; i++){
if(hash[i]) {
root = i;
break;
}
}
visit(root);
return 0;
}
问题 B: 小根堆的判定
题目描述
堆是以线性连续方式存储的完全二叉树，小根堆的每一个元素都不大于其左右孩子，现在给你n个完全二叉树数组存储序列，请编程判定相应完全二叉树数组存储序列是否为小根堆。
输入
第一行n（n<100），表示有n组测试用例。后边的n行，每一行都是相应完全二叉树数组存储序列(序列最长为100)。
输出
对应相应完全二叉树数组存储序列，判定为小根堆的输出True，否则输出False。
样例输入 Copy
2
30 26 27 88
5 6 7 8 9 10
样例输出 Copy
False
True
#include<iostream>
#include<queue>
using namespace std;
const int N = 110;
int a[N];
int idx=1;
void init(){
for(int i = 0; i < 110; i++) a[i] = 0;
idx = 1;
}
int judge(){
int t = 1;
int flag = 1;
while(t*2 < idx && t*2 + 1 < idx){
if(a[t] > a[2*t]) {
flag = 0;break;
}
if(a[t] > a[2*t+1]) {
flag = 0;break;
}
t+=1;
}
if(flag) return 1;
else return 0;
}
int main(){
int n;
cin>>n;
int k=0;
int flag[n];
for(int i = 0 ; i < n; i++){
init();
int num;
while(cin>>num){
a[idx++] = num;
if(cin.get() == '\n') break;
}
flag[k++] = judge();
}
for(int i = 0; i < n ; i++){
if(flag[i]) cout<<"True"<<endl;
else cout<<"False"<<endl;
}
return 0;
}
问题 C: 最小堆的形成
题目描述
现在给你n个结点的完全二叉树数组存储序列，请编程调整为最小堆，并输出相应最小堆的存储序列。
输入
第一行是n，第二行是n个结点的完全二叉树数组存储序列。
输出
输出相应最小堆的存储序列。
样例输入 Copy
8
53 17 78 23 45 65 87 9
样例输出 Copy
9 17 65 23 45 78 87 53
#include<iostream>
using namespace std;
const int n = 10010;
int idx;
int h[n];
void up(int x){
while(h[x] < h[x/2] && h[x/2] > 0){
swap(h[x],h[x/2]);
x/=2;
}
}
void down(int x){
int t = x;
if(2*x < idx && h[t] > h[2*x] ) t = 2*x;
if(2*x < idx && h[t] > h[2*x+1]) t = 2*x+1;
if(t!=x) {
swap(h[t],h[x]);
down(t);
}
}
int main(){
int n;
cin>>n;
for(int i = 1; i <= n;i++){
cin>>h[++idx];
up(idx);
}
for(int i = 1; i <= n;i++){
cout<<h[i]<<' ';
}
return 0;
}
问题 D: 无向图的深度优先搜索
题目描述
已知一个无向图G的顶点和边，顶点从0依次编号，现在需要深度优先搜索，访问任一邻接顶点时编号小的顶点优先，请编程输出图G的深度优先搜索序列。
输入
第一行是整数m和n（1 < m,n<100），分别代表顶点数和边数。后边n行，每行2个数，分别表示一个边的两个顶点。
输出
该图从0号顶点开始的深度优先搜索序列。
样例输入 Copy
5 5
0 1
2 0
1 3
1 4
4 2
样例输出 Copy
0 1 3 4 2
#include<iostream>
#include<stack>
using namespace std;
int m,n;
int edge[110][110];
int book[110];
void dfs(){
stack<int> s;
s.push(0);
book[0] = 1;
while(!s.empty()){
int temp = s.top();
cout<<temp<<' ';
s.pop();
for(int i = m; i >= 0; i--){
if(edge[temp][i] || edge[i][temp]){
if(!book[i]) {
s.push(i);
book[i] = 1;
}
}
}
}
}
int main(){
cin>>m>>n;
for(int i = 0 ; i < n ; i++){
int p,q;
cin>>p>>q;
edge[p][q] = 1;
}
dfs();
return 0;
}
问题 E: 无向图的广度优先搜索
题目描述
已知一个无向图G的顶点和边，顶点从0依次编号，现在需要广度优先搜索，访问任一邻接顶点时编号小的顶点优先，请编程输出图G的广度优先搜索序列。
输入
第一行是整数m和n（1<m,n<100），分别代表顶点数和边数。后边n行，每行2个数，分别表示一个边的两个顶点。
输出
该图从0号顶点开始的广度优先搜索序列。
样例输入 Copy
5 5
0 1
2 0
1 3
1 4
4 2
样例输出 Copy
0 1 2 3 4
#include<iostream>
#include<queue>
using namespace std;
int m,n;
int edge[110][110];
int book[110];
void dfs(){
queue<int> q;
q.push(0);
book[0] = 1;
while(!q.empty()){
int temp = q.front();
cout<<temp<<' ';
q.pop();
for(int i = 0; i < m; i++){
if(edge[temp][i] || edge[i][temp]){
if(!book[i]) {
q.push(i);
book[i] = 1;
}
}
}
}
}
int main(){
cin>>m>>n;
for(int i = 0 ; i < n ; i++){
int p,q;
cin>>p>>q;
edge[p][q] = 1;
}
dfs();
return 0;
}
问题 F: 最小生成树
题目描述
已知一个无向图G的顶点和边，顶点从0依次编号，请编程输出图G的最小生成树对应的边权之和。
输入
第一行是整数m和n（1<m,n<100），分别代表顶点数和边数。后边n行，每行3个数，分别表示一个边的两个顶点和该边的权值。
输出
最小生成树对应的边权之和。
样例输入 Copy
4 5
0 1 6
0 2 9
2 1 12
1 3 10
3 2 3
样例输出 Copy
18
注：此处采用Kruskal算法，Prim算法比较难写。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200010;
struct Edge{
int a;
int b;
int w;
bool operator<(const Edge &W) const{
return w < W.w;
}
}edges[N];
int p[N];
int n,m;
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main(){
cin>>n>>m;
for(int i = 0 ; i < m; i++){
int u,v,w;
cin>>u>>v>>w;
edges[i].a = u;
edges[i].b = v;
edges[i].w = w;
}
sort(edges, edges+m);
for(int i = 1; i <=n ;i++) p[i] = i;
int res = 0;
int cnt = 0;
for(int i = 0; i < m ; i++){
int a = edges[i].a; int b = edges[i].b; int w = edges[i].w;
a = find(a); b = find(b);
if(a!=b){
p[a] = b;
res+=w;
cnt++;
}
}
if(cnt < n - 1) cout<<"impossible";
else cout<<res;
return 0;
}
实验四
问题 A: 折半查找的次数
题目描述
给你一个无重复数的有序序列，如果采用折半查找的方式，对于给定的数，需要比较几次找到，请编程实现。
输入
第一行是N，表示序列中数的个数，序列最长1000，第二行是一个有序序列，第三行是要找的数x。
输出
如果找到x，输出折半比较的次数，否则输出NO。
样例输入 Copy
11
5 13 19 21 37 56 64 75 80 88 92
19
样例输出 Copy
2
注：注意二分边界问题
#include<iostream>
using namespace std;
const int N = 1010;
int a[N];
int key;
int cnt;
void bsearch(int l, int r){
while(l < r){
int mid = (l + r)/2;
cnt++;
if(a[mid]==key) return;
if(a[mid] > key) r = mid;
else l = mid+1;
}
}
int main(){
int n;
cin>>n;
int i;
for(i = 0 ; i < n ; i++){
cin>>a[i];
}
cin>>key;
int l = 0;
int r = i;
bsearch(l,r-1);
cout<<cnt;
return 0;
}
问题 B: 二叉搜索树中的查找
题目描述
给你一个数据序列，请构造一个二叉搜索树，然后计算出找到给定数据需比较的次数。
输入
第一行是N，表示序列中数的个数，序列最长1000，第二行是一个数据序列，第三行是要找的数x。
输出
如果找到x，输出比较的次数，没找到则输出NO。
样例输入 Copy
5
1 2 3 5 4
5
样例输出 Copy
4
#include<iostream>
using namespace std;
const int N = 1010;
int key,cnt;
struct Node{
int data;
Node *l=NULL,*r=NULL;
};
void insert(int x,Node* root){
if(x < root->data){
if(root->l == NULL){
root->l = new Node;
root->l->data = x;
}
else insert(x,root->l);
}
if(x > root->data){
if(root->r == NULL){
root->r = new Node;
root->r->data = x;
}
else insert(x,root->r);
}
}
void search(int key,Node* root){
if(key == root->data){
cnt++;
return;
}
if(key < root->data){
cnt++;
if(root->l == NULL) return;
else search(key,root->l);
}
if(key > root->data){
cnt++;
if(root->r == NULL) return;
else search(key,root->r);
}
}
int main(){
int n;
cin>>n;
int num;
cin>>num;
Node*root = new Node;
root->data=num;
for(int i = 1 ; i < n ; i++){
int x;
cin>>x;
insert(x,root);
}
cin>>key;
search(key,root);
cout<<cnt;
return 0;
}
问题 C: 有向图的最短路径长度
题目描述
已知一个有向图，每个边都有一个正整数表示边长，请编程求出其中两个顶点间的最短路径长度。
输入
第一行是M、N，分别表示顶点数和有向边数（0<M，N<=100》），紧接着N行的每一行是X、Y、H，分别表示有向边的起点和终点以及边长。最后一行是要求其最短路径的两个顶点。
输出
相应两个顶点的最短路径值。
样例输入 Copy
5 7
A B 10
B C 50
A E 100
A D 30
C E 10
D C 20
D E 60
A E
样例输出 Copy
60
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 550;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra(int s, int e){
memset(dist,0x3f,sizeof dist);
dist[s] = 0;
for(int i = 0; i < n;i++){
int t = -1;
for(int j = 0; j <=n ; j++)
if(!st[j] &&(t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
for(int j = 1; j <=n; j++)
dist[j] = min(dist[j], dist[t]+g[t][j]);
}
if(dist[e] == 0x3f3f3f3f) return -1;
return dist[e];
}
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i = 0; i < m ; i++){
char a,b;
int c;
int x,y;
cin>>a>>b>>c;
x = a - 'A' + 1;
y = b - 'A' + 1;
g[x][y] = min(g[x][y],c);
}
char start,end;
cin>>start>>end;
int s = start - 'A' + 1;
int e = end - 'A' + 1;
int t = dijkstra(s,e);
cout<<t;
return 0;
}
问题 D: 有向图的最短路径
题目描述
已知一个有向图，每个边都有一个正整数表示边长，请编程求出其中两个顶点间的最短路径长度。
输入
第一行是M、N，分别表示顶点数和有向边数（0 < M，N<=100），紧接着N行的每一行是X、Y、H，分别表示有向边的起点和终点以及边长。最后一行是要求其最短路径的两个顶点。
输出
相应两个顶点的最短路径经过的顶点序列。
样例输入 Copy
5 7
A B 10
B C 50
A E 100
A D 30
C E 10
D C 20
D E 60
A E
样例输出 Copy
A D C E
注：pre[ x ]代表该节点前一个节点是谁(边松弛时符合条件的)
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 550;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int pre[N];
int dijkstra(int s, int e){
memset(dist,0x3f,sizeof dist);
memset(pre,-1,sizeof(pre));
dist[s] = 0;
for(int i = 0; i < n;i++){
int t = -1;
for(int j = 0; j <=n ; j++)
if(!st[j] &&(t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
for(int j = 1; j <=n; j++){
if(dist[t]+g[t][j]<dist[j]) pre[j] = t;
dist[j] = min(dist[j], dist[t]+g[t][j]);
}
}
if(dist[e] == 0x3f3f3f3f) return -1;
return dist[e];
}
void dfs(int x){
if(x == -1) return;
else{
dfs(pre[x]);
char ch = x + 'A' -1;
cout<<ch<<' ';
}
}
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i = 0; i < m ; i++){
char a,b;
int c;
int x,y;
cin>>a>>b>>c;
x = a - 'A' + 1;
y = b - 'A' + 1;
g[x][y] = min(g[x][y],c);
}
char start,end;
cin>>start>>end;
int s = start - 'A' + 1;
int e = end - 'A' + 1;
int t = dijkstra(s,e);
dfs(e);
return 0;
}
问题 E: 5个数的从大到小排序
题目描述
数学课上，老师公布了一个小组的5名同学的成绩，你能编程把成绩从大到小排序吗，以便老师知道考试名次？
输入
5个整数，用空格间隔开。
输出
从大到小的5个数，中间用空格间隔。
样例输入 Copy
86 78 99 100 66
样例输出 Copy
100 99 86 78 66
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int a[5];
for(int i = 0; i < 5; i++) cin>>a[i];
sort(a,a+5);
for(int i = 4; i >= 0; i--) cout<<a[i]<<' ';
return 0;
}
问题 F: 病人排队
题目描述
病人登记看病，编写一个程序，将登记的病人按照以下原则排出看病的先后顺序：
1.老年人（年龄 >= 60岁）比非老年人优先看病。
2.老年人按年龄从大到小的顺序看病，年龄相同的按登记的先后顺序排序。
3.非老年人按登记的先后顺序看病。
输入
第1行，输入一个小于100的正整数，表示病人的个数；
后面按照病人登记的先后顺序，每行输入一个病人的信息，包括：一个长度小于10的字符串表示病人的ID（每个病人的ID各不相同且只含数字和字母），一个整数表示病人的年龄，中间用单个空格隔开。
输出
按排好的看病顺序输出病人的ID，每行一个。
样例输入 Copy
5
021075 40
004003 15
010158 67
021033 75
102012 30
样例输出 Copy
021033
010158
021075
004003
102012
#include<iostream>
#include<algorithm>
using namespace std;
struct Patient{
string id;
int age;
int prior;
bool operator<(const Patient &P)const{
return age<P.age;
}
}patients[110];
bool cmp(const Patient x,const Patient y){
if(x.age<60 && y.age<60){
return x.prior<y.prior;
}
if(x.age == y.age){
return x.prior<y.prior;
}
return x.age>y.age;
}
int main(){
int n;
cin>>n;
for(int i = 1; i <= 5 ;i++){
string s;
int age;
cin>>s>>age;
patients[i].id = s;
patients[i].age = age;
patients[i].prior = i;
}
sort(patients+1,patients+n+1,cmp);
for(int i = 1; i <= 5 ;i++){
cout<<patients[i].id<<endl;
}
return 0;
}