这道题里坑点很大：反而不利于深入学习过数据结构的同学做题。。
先贴代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<map> #include<string> #include<functional> #include<algorithm> #include<stack> #include<list> #include<cstring> #include<queue> #include<cstdio> #include<cmath> using namespace std; //Root is 1 //小顶堆 int n, m; int heap[1005]; int Hsize = 0; inline int lson(int x) { return x * 2; } inline int rson(int x) { return x * 2 + 1; } inline int father(int x) { return x / 2; } void PercolateUp(int node) { if (heap[node] < heap[father(node)]) { swap(heap[node], heap[father(node)]); PercolateUp(father(node)); } } void insert(int x) { heap[++Hsize] = x; PercolateUp(Hsize); } int _findNode(int v) { for (int i = 1; i <= n; i++) { if (v == heap[i])return i; } return -1; } bool isRoot(int v) { return heap[1] == v; } bool isSiblings(int v1, int v2) { int node = _findNode(v1); if (node % 2 == 1)return heap[node - 1] == v2; else return heap[node + 1] == v2; } bool isParent(int C,int F){ int node = _findNode(C); return heap[father(node)] == F; } bool isChild(int C, int F) { int node = _findNode(F); return heap[lson(node)] == C || heap[rson(node)] == C; } int Itype; //0 root,1 sibling,2 parent,3 child int Ix, Iy; char str[100]; void getInput() { scanf("%d", &Ix); scanf("%s", str); if (strcmp(str, "and") == 0) { Itype = 1; scanf("%d", &Iy); scanf("%s", str); scanf("%s", str); return; } scanf("%s", str); if (strcmp(str, "a") == 0) { Itype = 3; scanf("%s", str); scanf("%s", str); scanf("%d", &Iy); return; } scanf("%s", str); if (strcmp(str, "root") == 0) { Itype = 0; return; } Itype = 2; scanf("%s", str); scanf("%d", &Iy); return; } int main() { heap[0] = -100000; cin >> n >> m; for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); insert(x); } for (int i = 1; i <= m; i++) { getInput(); bool flag; switch (Itype) { case 0:flag = isRoot(Ix); break; case 1:flag = isSiblings(Ix, Iy); break; case 2:flag = isParent(Iy, Ix); break; case 3:flag = isChild(Ix, Iy); break; } cout << (flag ? "T" : "F")<< endl; } } |
对我来说的坑点：一个是数据范围是有负数的！！！还有一个，儿子、父亲节点不是广义儿子、父亲节点，只是直属的，有直接相连边的，间接连接的不算，还有一个是不能使用一次全部读入到数组里从n/2下标到n一起上滤的做法，必须插入一个，上滤一次，这种算法很辣鸡。