织梦网站 数据库,最新网站查询工具,建设一个网站需要些什么材料,东莞市住建局官网查询题目再现
题目内容#xff1a;
给定一个物种演化图#xff0c;
关系的表示方式如下#xff1a;
x y : 表示x为y的先祖。
一个物种只会有一个先祖#xff0c;
一个先祖可以有很多个演化出来的物种#xff0c;
请你找出每个问题询问物种的祖父物种(先祖的先祖)#xff0c;…
题目再现
题目内容
给定一个物种演化图
关系的表示方式如下
x y : 表示x为y的先祖。
一个物种只会有一个先祖
一个先祖可以有很多个演化出来的物种
请你找出每个问题询问物种的祖父物种(先祖的先祖)
每个物种会使用一个不重复的编号来表示
如果该物种没有祖父物种的话或是不存在
那么请将他的祖父物种当是0。(凭空而生)
保证所有物种间一定有所关连
且不会有重复演化的现象发生
即演化图只会是一棵树。输入格式:
只有一组测资。
第一行会有两个数字N、Q代表总共有N个物种及Q个问题。
接下来N-1行每一行有两个数字x、y
意义如题目所述。
接下来的Q行每一行有一个数字Z
代表要询问的物种编号。
测资范围
1 N 10000
0 Q 1000
0 x, y, z 1000000输出格式
对于每一个询问的物种编号将他们的祖父物种编号加总后再输出。输入样例
6 3
1000 2000
1000 3000
2000 4000
3000 5000
5000 6000
5000
6000
1234输出样例
4000时间限制100ms内存限制16000kb算法实现
1. 简单数组下标查找法 通过题目的要求这里可以使用最简单的方法因为输入的x , y中y的值是确定不变的所以这里可以定义一个y的取值范围那么大的数组下标就是y的值内容就是x的值这样查找起来十分方便时间复杂度是O(1)但是空间上就会浪费比较多了。
#include stdio.h
#include string.hint main(){int arrBucket[1000000];int N, Q;int x, y, z;long long sum 0;memset(arrBucket, 0, sizeof(arrBucket));scanf(%d %d, N, Q);while(N -- 1){scanf(%d %d, x, y);arrBucket[y] x;}while(Q --){scanf(%d, z);if(arrBucket[z] ! 0){if(arrBucket[arrBucket[z]] ! 0){sum arrBucket[arrBucket[z]];}}}printf(%lld, sum);return 0;
}
2. Hash表实现 因为方法1中浪费空间严重所以这里使用Hash表实现。
#include stdio.h
#include stdlib.h
#define NULLKEY -1typedef struct {int *elem; //元素 int *elemP; //父元素 int count;
}HashTable;int Hash(HashTable H, int k){return k % H.count;
}void InitHashTable(HashTable *H){int i;H-elem (int *)malloc(sizeof(int) * H-count);H-elemP (int *)malloc(sizeof(int) * H-count);for(i 0; i H-count; i ){H-elem[i] NULLKEY;H-elemP[i] NULLKEY; }
}void InsertHash(HashTable *H, int key, int value){int addr;addr Hash(*H, key);while(H-elem[addr] ! NULLKEY){addr (addr 1) % H-count;}H-elem[addr] key;H-elemP[addr] value;
}int FindHash(HashTable *H, int key, int *addr){*addr Hash(*H, key);while(H-elem[*addr] ! key){*addr (*addr 1) % H-count;if(H-elem[*addr] NULLKEY || *addr Hash(*H, key)){return 0;}}return 1;
}int main(){int N, Q;int x, y, z, addr;long long sum 0;HashTable H;scanf(%d %d, N, Q);H.count N - 1;InitHashTable(H);while(N -- 1){scanf(%d %d, x, y);InsertHash(H, y, x);}while(Q --){scanf(%d, z);if(FindHash(H, z, addr)){if(FindHash(H, H.elemP[addr], addr)){sum H.elemP[addr];}}}printf(%lld, sum);return 0;
}
3. 用C的map来实现 看着用C实现起来相对来说实现的各个功能都要自己写这里看一下用C的STL里面的map来实现上面的题目非常简单不得不说STL真的很好用但是不如HashTable速度快空间上也不如HashTable占用的小
#include iostream
#include map
using namespace std;int main() {int n, q;cin n q;mapint,int mp; mapint,int::iterator it;int x, y, z;for (int i1; in; i) { cin x y;mp.insert(pairint,int(y,x)); }int sum 0;for (int i0; iq; i) {cin z;it mp.find(z); if (it ! mp.end()) {it mp.find(it-second); if (it ! mp.end())sum it-second; }}cout sum;return 0;
} 博客名称王乐平博客 博客地址http://blog.lepingde.com CSDN博客地址http://blog.csdn.net/lecepin
