2023 - 04 - 03 2016天梯赛初赛(L2)练习
7-12 关于堆的判断
分数 25
全屏浏览题目
切换布局
作者 陈越
单位 浙江大学
将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种：
x is the root：x是根结点；x and y are siblings：x和y是兄弟结点；x is the parent of y：x是y的父结点；x is a child of y：x是y的一个子结点。
输入格式：
每组测试第1行包含2个正整数N（≤ 1000）和M（≤ 20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[−10000,10000]内的N个要被插入一个初始为空的小顶堆的整数。之后M行，每行给出一个命题。题目保证命题中的结点键值都是存在的。
输出格式：
对输入的每个命题，如果其为真，则在一行中输出T，否则输出F。
输入样例：
5 4
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10
输出样例：
F
T
F
T#include<bits/stdc++.h>using namespace std;
const int MAX = 10001;
int N, M, num;
string str;
int Heapmin[MAX];int find(int x)
{for (int i = 1; i <= N; i++)if (Heapmin[i] == x)return i;return 0;
}int nums(string s)
{bool fs = 0;//区间[−10000,10000]int sum = 0;for (int i = 0; i < s.size(); i++){if(s[i] == '-')fs = 1;if (isdigit(s[i])){if (!sum)sum = s[i] - '0';else{if (s[i] - '0' == 0)sum *= 10;else{sum *= 10;sum += s[i] - '0';}}}}if(fs)return -sum;return sum;
}int main()
{//建堆cin >> N >> M;for (int i = 1; i <= N; i++){cin >> Heapmin[i];int k = i;while (k > 1 && Heapmin[k] < Heapmin[k / 2]){swap(Heapmin[k], Heapmin[k / 2]);k /= 2;}}while (M--){cin >> num;getline(cin, str);if (str.find("root") != str.npos){if (Heapmin[1] == num)cout << "T" << endl;else cout << "F" << endl;}else if (str.find("and") != str.npos){int T = nums(str);if (find(num) / 2 == find(T) / 2)cout << "T" << endl;else cout << "F" << endl;}else if (str.find("parent") != str.npos){int T = nums(str);if (find(num) == find(T) / 2)cout << "T" << endl;else cout << "F" << endl;}else if (str.find("child") != str.npos){int T = nums(str);if (find(num) / 2 == find(T))cout << "T" << endl;else cout << "F" << endl;}str.clear();}return 0;
}优化
#include<bits/stdc++.h>
using namespace std;//优化 使用map容器进行查找操作
const int MAX = 10001;
int N, M, num;
string str;
int Heapmin[MAX];
map<int, int>root;
int nums(string s)
{bool fs = 0;//区间[−10000,10000]int sum = 0;for (int i = 0; i < s.size(); i++){if (s[i] == '-')fs = 1;if (isdigit(s[i])){if (!sum)sum = s[i] - '0';else{if (s[i] - '0' == 0)sum *= 10;else{sum *= 10;sum += s[i] - '0';}}}}if (fs)return -sum;return sum;
}int main()
{//建堆cin >> N >> M;for (int i = 1; i <= N; i++){cin >> Heapmin[i];int k = i;while (k > 1 && Heapmin[k] < Heapmin[k / 2]){swap(Heapmin[k], Heapmin[k / 2]);k /= 2;}}for (int i = 1; i <= N; i++)root[Heapmin[i]] = i;while (M--){cin >> num;getline(cin, str);if (str.find("root") != str.npos){if (Heapmin[1] == num)cout << "T" << endl;else cout << "F" << endl;}else if (str.find("and") != str.npos){int T = nums(str);if (root[num] / 2 == root[T] / 2)cout << "T" << endl;else cout << "F" << endl;}else if (str.find("parent") != str.npos){int T = nums(str);if (root[num] == root[T] / 2)cout << "T" << endl;else cout << "F" << endl;}else if (str.find("child") != str.npos){int T = nums(str);if (root[num] / 2 == root[T])cout << "T" << endl;else cout << "F" << endl;}str.clear();}return 0;
}
7-10 排座位(并查集操作)
布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。
输入格式：
输入第一行给出3个正整数：N（≤100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：宾客1 宾客2 关系，其中关系为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。
这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。
输出格式：
对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出No problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK but...；如果他们之间只有敌对关系，则输出No way。
输入样例：
7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2
输出样例：
No problem
OK
OK but...
No way#include<bits/stdc++.h>
using namespace std;
const int MAX = 110;
//首先对于关系分为朋友 敌对 无交集
//其中 敌对只有一对一的情况 但是朋友关系存在相交集 即有共同朋友的情况 但不用考虑共同敌对关系
bool enemy[MAX][MAX];
int frend[MAX];
int N,M,K;
//对于朋友网,可以通过查集合的根,若存在公共根说明在一个朋友圈中间
int find_frend(int x)
{if(frend[x] == x){//如果自己就是根return x;}return frend[x] = find_frend(frend[x]);
}
void Union(int A,int B)
{int x = find_frend(frend[A]);//将A的朋友圈进行压缩int y = find_frend(frend[B]);//将B的朋友圈进行压缩if(x != y)//俩人不在一个朋友圈中间frend[x] = y;//将A拉入B的朋友圈里
}
int main()
{cin>>N>>M>>K;//初始关系网for(int i = 1; i<=N;i++)frend[i] = i;int A,B,C;while(M--){cin>>A>>B>>C;if(C == 1){Union(A,B);}else{enemy[A][B] = enemy[B][A] = 1;}}while(K--){cin>>A>>B;if(find_frend(A) == find_frend(B) && !enemy[A][B])cout<<"No problem"<<endl;else if(find_frend(A) == find_frend(B) && enemy[A][B])cout<<"OK but..."<<endl;else if(enemy[A][B])cout<<"No way"<<endl;else cout<<"OK"<<endl;}return 0;
}7-9 抢红包
没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。
输入格式：
输入第一行给出一个正整数N（≤104），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：
KN1P1⋯NKPK
其中K（0≤K≤20）是发出去的红包个数，Ni是抢到红包的人的编号，Pi（>0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。
输出格式：
按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。
输入样例：
10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10
输出样例：
1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32#include<bits/stdc++.h>
using namespace std;
const int MAX = 10001;
int N, K;
//结构体(类)写法
class people
{
public:int name;int num = 0;//抢到红包个数double Money = 0;//
}p[MAX];bool mysort(people A, people B)
{if (A.Money != B.Money)return A.Money > B.Money;else{if (A.num != B.num)return A.num > B.num;else return A.name < B.name;}
}int main()
{cin >> N;for (int i = 1; i <= N; i++){p[i].name = i;double sum = 0;cin >> K;int n;double m;while (K--){cin >> n >> m;p[n].Money += m;p[n].num++;sum += m;}p[i].Money -= sum;}sort(p + 1, p + N + 1, mysort);for (int i = 1; i <= N; i++){cout << p[i].name << " ";p[i].Money /= 100;printf("%.2lf\\n", p[i].Money);}return 0;
}7-11 玩转二叉树
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> in;
vector<int> pre;
class Tree
{
public:int val;Tree* L;Tree* R;vector<int> ans;Tree(int N){val = N;L = R = NULL;}void CX(Tree* root){queue<Tree*> Q;Q.push(root);while (!Q.empty()){ans.emplace_back(Q.front()->val);if (Q.front()->L)Q.push(Q.front()->L);if (Q.front()->R)Q.push(Q.front()->R);Q.pop();}for (int i = 0; i < ans.size(); i++){cout << ans[i];if (i != ans.size() - 1)cout << " ";}}
};Tree* Re(Tree* root)
{if (!root) return NULL;Tree* LL = Re(root->L);Tree* RR = Re(root->R);root->L = RR;root->R = LL;return root;
}Tree* Built(int prel, int prer, int inl, int inr)
{if (prel > prer)return NULL;Tree* root = new Tree(pre[prel]);int i;for (i = inl; i < inr; i++)if (pre[prel] == in[i])break;int j = i - inl;root -> L= Built(prel + 1, prel + j, inl, i - 1);root -> R= Built(prel + j + 1, prer, i + 1, inr);return root;
}int main()
{cin >> N;int num;for (int i = 0; i < N; i++){cin >> num;in.emplace_back(num);}for (int i = 0; i < N; i++){cin >> num;pre.emplace_back(num);}Tree* root;root = Built(0, N - 1, 0, N - 1);root = Re(root);root->CX(root);return 0;
}
