1144 The Missing Number（20 分）
题意：给定N个数的序列，输出不在序列中的最小的正整数。
分析：
1、给定的N个数可能为正，可能为负，可能重复。
2、由于N≤105,所以，当N个数互不重复，且都为正的情况下，所输出的数最大，为105+1。
3、将序列中的数标注后，枚举1~105+1，遇到的第一个未标注的数即为答案。
4、注意标注序列中的数时，大于105+1的数没必要标注（因为给定的数在int范围内），否则会下标越界。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN = 100000 + 10;
int a[MAXN];
bool vis[MAXN];
int main(){
int N;
while(scanf("%d", &N) == 1){
memset(vis, false, sizeof vis);
for(int i = 0; i < N; ++i){
scanf("%d", &a[i]);
if(a[i] > 0 && a[i] < MAXN) vis[a[i]] = true;
}
for(int i = 1; i < MAXN; ++i){
if(!vis[i]){
printf("%d", i);
break;
}
}
}
return 0;
}
1145 Hashing - Average Search Time（25 分）
题意：给定N个数，插入到长度为MSize的哈希表中，计算查找M个数的平均查找时间。
分析：
1、哈希函数：H(key)=key%MSize
2、题目中要求通过二次探查法解决冲突，且只考虑正增量。
（1）二次探查法的探查序列为Hi=(H(key)+i)%MSize,i取值依次为1*1，-1*1，2*2，-2*2，3*3，-3*3，...，(MSize-1)*(MSize-1),-(MSize-1)*(MSize-1)
（2）由于只考虑正增量，所以i取值为1*1，2*2，3*3，...，(MSize-1)*(MSize-1)
（3）对于i依次取值来解决冲突，如果所有的取值都冲突，则插入失败。
3、查询某数时所执行的操作与插入操作相同，如果查询到的位置为空，则表示该数字不在Hash表中；如果遍历所有的i都未找到，则查询总数加1。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int MAXN = 10000 + 10;
int MSize, N, M;
int Hash[MAXN];
bool judge_prime(int x){
if(x <= 1) return false;
for(int i = 2; i <= (int)(sqrt(x + 0.5)) + 1; ++i){
if(x % i == 0) return false;
}
return true;
}
int main(){
while(scanf("%d%d%d", &MSize, &N, &M) == 3){
memset(Hash, -1, sizeof Hash);
while(!judge_prime(MSize)) ++MSize;
int key;
while(N--){
scanf("%d", &key);
int Hkey = key % MSize;
bool ok = false;
if(Hash[Hkey] == -1){
Hash[Hkey] = key;
ok = true;
}
else{
for(int i = 1; i <= MSize - 1; ++i){
int tmp = (Hkey + i * i) % MSize;
if(Hash[tmp] == -1){
Hash[tmp] = key;
ok = true;
break;
}
}
}
if(!ok) printf("%d cannot be inserted.
", key);
}
int x;
int sum = 0;
for(int i = 0; i < M; ++i){
scanf("%d", &x);
int Hkey = x % MSize;
bool ok = false;
for(int j = 0; j < MSize; ++j){
int tmp = (Hkey + j * j) % MSize;
++sum;
if(Hash[tmp] == -1 || Hash[tmp] == x){
ok = true;
break;
}
}
if(!ok) ++sum;
}
printf("%.1lf
", sum * 1.0 / M);
}
return 0;
}
1146 Topological Order（25 分）
题意：给定一个有向图，判断所给的K个选项中哪个不是该图的拓扑排序。
分析：
1、遍历所给的拓扑序，边遍历边将该点所指向的点入度-1。
2、在进行上述操作的前提下，如果遍历到的每个点入度都为0，则该序列一定是拓扑序。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<map>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 1000 + 10;
vector<int> G[MAXN];
int indegree[MAXN];
int tmpindegree[MAXN];
vector<int> ans;
vector<int> v;
int N, M;
void init(){
for(int i = 1; i <= N; ++i) G[i].clear();
memset(indegree, 0, sizeof indegree);
ans.clear();
}
bool judge(){//判断是否为拓扑序列
int len = v.size();
for(int i = 0; i < len; ++i){
int cur = v[i];
if(!tmpindegree[cur]){
int l = G[cur].size();
for(int j = 0; j < l; ++j){
--tmpindegree[G[cur][j]];
}
}
else return false;
}
return true;
}
int main(){
while(scanf("%d%d", &N, &M) == 2){
init();
int st, ed;
for(int i = 0; i < M; ++i){
scanf("%d%d", &st, &ed);
G[st].push_back(ed);
++indegree[ed];
}
int K, x;
scanf("%d", &K);
for(int i = 0; i < K; ++i){
memcpy(tmpindegree, indegree, sizeof indegree);
v.clear();
for(int j = 0; j < N; ++j){
scanf("%d", &x);
v.push_back(x);
}
if(!judge()) ans.push_back(i);
}
int len = ans.size();
for(int i = 0; i < len; ++i){
if(i) printf(" ");
printf("%d", ans[i]);
}
printf("
");
}
return 0;
}
1147 Heaps（30 分）
题意：给定一个完全二叉树的层次遍历序列，问该二叉树是否为堆结构，并进一步判断是大顶堆还是小顶堆，最后输出该二叉树的后序遍历序列。
分析：
1、由于给定的N (1<N≤1000)个点数字各不相同，且大小都在int范围内，首先对N个点进行坐标离散化。
2、利用queue边读取边判断该二叉树是否为堆结构，同时记录每个点的左右子结点。
3、进行后序遍历。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<map>
#include<queue>
using namespace std;
const int MAXN = 100000 + 10;
int lchild[MAXN], rchild[MAXN];
map<int, int> mp1;
map<int, int> mp2;
queue<int> q;
vector<int> ans;
int root;
int cnt;
void init(){
memset(lchild, 0, sizeof lchild);
memset(rchild, 0, sizeof rchild);
mp1.clear();
mp2.clear();
while(!q.empty()) q.pop();
ans.clear();
}
void get_id(int x){//坐标离散化
++cnt;
mp1[x] = cnt;
mp2[cnt] = x;
}
int judge(int type_l, int type_r){
if(type_l == 1 && type_r != 2){
return 1;//Min Heap
}
else if(type_l == 2 && type_r != 1){
return 2;//Max Heap
}
else{
return 3;
}
}
void print_postorder(int x){
if(lchild[x]) print_postorder(lchild[x]);
if(rchild[x]) print_postorder(rchild[x]);
ans.push_back(mp2[x]);
}
int main(){
int M, N;
while(scanf("%d%d", &M, &N) == 2){
while(M--){
init();
cnt = 0;
int x;
scanf("%d", &x);
q.push(x);
get_id(x);
root = mp1[x];
int type = 0;
bool ok = true;
while(!q.empty()){
int top = q.front();
q.pop();
int type_l = 0;
int type_r = 0;
if(cnt < N){
scanf("%d", &x);
get_id(x);
lchild[mp1[top]] = mp1[x];
q.push(x);
if(top < x) type_l = 1;
else type_l = 2;
}
if(cnt < N){
scanf("%d", &x);
get_id(x);
rchild[mp1[top]] = mp1[x];
q.push(x);
if(top < x) type_r = 1;
else type_r = 2;
}
if(type == 0) type = judge(type_l, type_r);
else{
int tmptype = judge(type_l, type_r);
if(tmptype != type || type == 3) ok = false;
}
if(cnt == N) break;
}
if(!ok) printf("Not Heap
");
else{
if(type == 1) printf("Min Heap
");
else printf("Max Heap
");
}
print_postorder(root);
int len = ans.size();
for(int i = 0; i < len; ++i){
if(i) printf(" ");
printf("%d", ans[i]);
}
printf("
");
}
}
return 0;
}