布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。
输入第一行给出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
很迷的题面，令人头秃。训练的时候有一个点没过（因为当时开始写了-1的最短路，最外层循环只for到2……我也不知道当时怎么想的）
#include "bits/stdc++.h" using namespace std; const int maxn = 200; int mp[maxn][maxn], fri[maxn][maxn], ene[maxn][maxn]; int main() { int n, m, k; cin >> n >> m >> k; int a, b, c; for (int i = 1; i <= m; i++) { cin >> a >> b >> c; mp[a][b] = c; mp[b][a] = c; if (c == 1) { fri[a][b] = c; fri[b][a] = c; } else { ene[a][b] = c; ene[b][a] = b; } } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (fri[i][k] == 1 && fri[k][j] == 1) { fri[i][j] = 1; } } } } while (k--) { cin >> a >> b; if (mp[a][b] == -1 && fri[a][b] == 0) { cout << "No way" << endl; } else if (mp[a][b] == -1 && fri[a][b] == 1) { cout << "OK but..." << endl; } else if (mp[a][b] == 0) { cout << "OK" << endl; } else cout << "No problem" << endl; } return 0; }
给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。
在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
7
1 2 3 4 5 6 7
4 1 3 2 6 5 7
4 6 1 7 5 3 2用递归可以从一个树得到其遍历序列，那么从遍历序列得到树将其递归反过来就行。反转操作可以忽略，在bfs的时候先插入右儿子就可以了
#include "bits/stdc++.h" using namespace std; const int maxn = 100; int dlr[maxn], ldr[maxn]; int n; typedef struct node { int val; node *l, *r; } *tree; tree root = NULL; void build(tree &t, int start, int lasttime, int len) { if (len <= 0) { t = NULL; return; } int now; t = (tree) malloc(sizeof(node)); t->val = dlr[start]; for (int i = 0; i < n; i++) { if (ldr[i] == dlr[start]) { now = i; break; } } int lenl = now - lasttime; build(t->l, start + 1, lasttime, lenl); int lenr = len - 1 - lenl; build(t->r, start + lenl + 1, now + 1, lenr); } void bfs() { queue<tree> q; q.push(root); int flag = 0; tree temp; while (!q.empty()) { if (flag) printf(" "); flag = 1; temp = q.front(); q.pop(); cout << temp->val; if (temp->r != NULL) q.push(temp->r); if (temp->l != NULL) q.push(temp->l); } } int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> ldr[i]; } for (int i = 0; i < n; i++) { cin >> dlr[i]; } build(root, 0, 0, n); bfs(); return 0; }
将一系列给定数字顺序插入一个初始为空的小顶堆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判断两个节点是兄弟只要判断他们的父亲是同一个节点就可以了，比赛的时候写了判断他们相邻且一个在奇数节点一个在偶数节点。。。。
// make_heap(heap + 1, heap + 1 + i, greater<int>());
//c++自带的建树函数，默认建大根堆
#include "bits/stdc++.h" using namespace std; const int maxn = 1e5; const int base = 11000; int heap[maxn]; int ver[maxn]; int n, m; void up(int p) { while (p > 1) { if (heap[p] < heap[p / 2]) { swap(heap[p], heap[p / 2]); p /= 2; } else break; } } int main() { cin >> n >> m; int x; for (int i = 1; i <= n; i++) { cin >> x; heap[i] = x; up(i); // make_heap(heap + 1, heap + 1 + i, greater<int>()); //c++自带的建树函数，默认建大根堆 } for (int i = 1; i <= n; i++) { ver[heap[i] + base] = i;//去掉负数 } char str[10000]; int a, b; while (m--) { scanf("%d", &a); scanf("%s", str); if (str[0] == ‘a‘) { scanf("%d", &b); scanf("%s", str); scanf("%s", str); if (ver[a + base] / 2 == ver[b + base] / 2) {//a和b是兄弟 cout << "T" << endl; } else cout << "F" << endl; } else { scanf("%s", str); if (str[0] == ‘a‘) { scanf("%s", str); scanf("%s", str); scanf("%d", &b); if (ver[a + base] / 2 == ver[b + base])//a是b的儿子 cout << "T" << endl; else cout << "F" << endl; } else { scanf("%s", str); if (str[0] == ‘r‘) {//a是树根 if (heap[1] == a) cout << "T" << endl; else cout << "F" << endl; } else { scanf("%s", str); scanf("%d", &b); if (ver[a + base] == ver[b + base] / 2)//a是b的父亲 cout << "T" << endl; else cout << "F" << endl; } } } } return 0; }
本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。
输入在第一行给出两个正整数N（2 ≤ N ≤ 500）和M，分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行，每行按如下格式给出一条道路的信息：
V1 V2 one-way length time
其中V1和V2是道路的两个端点的编号（从0到N-1）；如果该道路是从V1到V2的单行线，则one-way为1，否则为0；length是道路的长度；time是通过该路所需要的时间。最后给出一对起点和终点的编号。
首先按下列格式输出最快到达的时间T和用节点编号表示的路线：
Time = T: 起点 => 节点1 => ... => 终点
然后在下一行按下列格式输出最短距离D和用节点编号表示的路线：
Distance = D: 起点 => 节点1 => ... => 终点
如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。
如果这两条路线是完全一样的，则按下列格式输出：
Time = T; Distance = D: 起点 => 节点1 => ... => 终点
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
5 4 0 2 3
5 9 1 1 4
0 6 0 1 1
7 3 1 1 2
8 3 1 1 2
2 5 0 2 2
2 1 1 1 1
1 5 0 1 3
1 4 0 1 1
9 7 1 1 3
3 1 0 2 5
6 3 1 2 1
5 3
Time = 6: 5 => 4 => 8 => 3
Distance = 3: 5 => 1 => 3
7 9
0 4 1 1 1
1 6 1 3 1
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 3 1
3 2 1 2 1
4 5 0 2 2
6 5 1 2 1
3 5
Time = 3; Distance = 4: 3 => 2 => 5读题读题读题，比赛时读题要尽量的慢，准，稳。
#include "bits/stdc++.h" using namespace std; const int maxn = 600; int timemap[maxn][maxn], lenmap[maxn][maxn]; int lendist[maxn], lt[maxn], tl[maxn], timedist[maxn], timepre[maxn], timevis[maxn]; int lenpre[maxn], lenvis[maxn]; int n, m, s, d; vector<int> ans1, ans2; bool check() { if (ans1.size() != ans2.size()) return false; for (int i = 0; i < ans1.size(); i++) { if (ans1[i] != ans2[i]) return false; } return true; } void dij1() { memset(timedist, 0x3f, sizeof(timedist)); memset(timevis, 0, sizeof(timevis)); memset(timepre, -1, sizeof(timepre)); memset(lendist, 0x3f, sizeof(lendist)); memset(lenvis, 0, sizeof(lenvis)); memset(lenpre, -1, sizeof(lenpre)); memset(lt, 0x3f, sizeof(lt)); memset(tl, 0x3f, sizeof(lt)); timedist[s] = 0; lendist[s] = 0; lt[s] = 1; tl[s] = 0; for (int i = 1; i < n; i++) { int x = -1; for (int j = 0; j < n; j++) { if (!timevis[j] && (x == -1 || timedist[j] < timedist[x])) x = j; } timevis[x] = 1; for (int j = 0; j < n; j++) { if (timedist[x] + timemap[x][j] < timedist[j]) { timedist[j] = timedist[x] + timemap[x][j]; tl[j] = tl[x] + lenmap[x][j]; timepre[j] = x; } else if (timedist[x] + timemap[x][j] == timedist[j] && tl[x] + lenmap[x][j] < tl[j]) { tl[j] = tl[x] + lenmap[x][j]; timepre[j] = x; } } x = -1; for (int j = 0; j < n; j++) { if (!lenvis[j] && (x == -1 || lendist[j] < lendist[x])) x = j; } lenvis[x] = 1; for (int j = 0; j < n; j++) { if (lendist[x] + lenmap[x][j] < lendist[j]) { lendist[j] = lendist[x] + lenmap[x][j]; lenpre[j] = x; lt[j] = lt[x] + 1; } else if (lendist[x] + lenmap[x][j] == lendist[j] && lt[x] + 1 < lt[j]) { lenpre[j] = x; lt[j] = lt[x] + 1; } } } ans1.push_back(d); int x = timepre[d]; while (x != -1) { ans1.push_back(x); x = timepre[x]; } ans2.push_back(d); x = lenpre[d]; while (x != -1) { ans2.push_back(x); x = lenpre[x]; } if (check()) { printf("Time = %d; Distance = %d: ", timedist[d], lendist[d]); int flag = 0; for (int i = ans1.size() - 1; i >= 0; i--) { if (flag) printf(" => "); flag = 1; printf("%d", ans1[i]); } printf("\n"); return; } printf("Time = %d: ", timedist[d]); int flag = 0; for (int i = ans1.size() - 1; i >= 0; i--) { if (flag) printf(" => "); flag = 1; printf("%d", ans1[i]); } printf("\n"); printf("Distance = %d: ", lendist[d]); flag = 0; for (int i = ans2.size() - 1; i >= 0; i--) { if (flag) printf(" => "); flag = 1; printf("%d", ans2[i]); } printf("\n"); } int main() { //freopen("input.txt", "r", stdin); memset(lenmap, 0x3f, sizeof(lenmap)); memset(timemap, 0x3f, sizeof(timemap)); cin >> n >> m; int a, b, c, dd, e; for (int i = 0; i < m; i++) { cin >> a >> b >> c >> dd >> e; if (!c) { timemap[b][a] = e; lenmap[b][a] = dd; } timemap[a][b] = e; lenmap[a][b] = dd; } cin >> s >> d; dij1(); return 0; }
原文：https://www.cnblogs.com/albert-biu/p/10534087.html