PAT 2018年浙大复试机试

本文主要是介绍PAT 2018年浙大复试机试，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 PAT 甲级 1144 The Missing Number

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int vec[N];
int main() {int n; cin>>n;for(int i=0; i<n; ++i) {cin>>vec[i];}for(int i=0; i<n; ++i) {if(vec[i]<=0 ||vec[i]>n){vec[i] = n+1;}}for(int i=0; i<n; ++i) {int hash_key = abs(vec[i]);if(hash_key != n+1) {if(vec[hash_key-1] > 0){vec[hash_key-1] *= -1;}}}int ans = n+1;for(int i=0; i<n; ++i) {if(vec[i]>0) {ans = i+1;break;}}cout<<ans<<"\n";
}

2 PAT 甲级 1145 Hashing - Average Search Time

#include<bits/stdc++.h>
using namespace std;const int N = 1e4+10;
int m_size, n, m;bool IsPrime(int n) {if(n<=3) {return n>1;}int x = sqrt(n)+0.5;for(int i=2; i<=x; ++i) {if(n%i == 0) return false;}return true;
}void AdjustToPrime(int &n){while(!IsPrime(n)) ++n;
}int table[N];
void InitHashTable(){memset(table, -1, sizeof(table));
}
void Insert(int val) {int pos = val%m_size;for(int step = 0; step <= m_size; ++step) {pos = (val + step * step)%m_size;if(table[pos]==-1){table[pos] = val;return;}}printf("%d cannot be inserted.\n", val);
}int Find(int val) {int cnt = 0;int pos = val%m_size;for(int step = 0; step <= m_size; ++step) {cnt += 1;pos = (val + step * step)%m_size;if(table[pos]==val || table[pos] == -1){break;}}return cnt;
}int main() {cin>>m_size>>n>>m;AdjustToPrime(m_size);InitHashTable();while(n--){int key;cin>>key;Insert(key);}int tot_cnt = 0;for(int i=0; i<m; ++i){int key;cin>>key;tot_cnt += Find(key);}printf("%.1f\n", tot_cnt*1.0/m);
}

3 PAT 甲级 1146 Topological Order

#include<bits/stdc++.h>
using namespace std;const int N = 1010;
set<int> to[N];
int in_degree[N];int n, m;bool JudgeHelper(vector<int> &seq, int begin) {if(begin == seq.size()) return true;int now = seq[begin];if(in_degree[now]!=0) return false;for(auto next: to[now]) {in_degree[next]--;}bool ans = JudgeHelper(seq, begin+1);for(auto next: to[now]) {in_degree[next]++;}return ans;
}bool Judge(vector<int> &seq) {return JudgeHelper(seq, 0);
}int main() {cin>>n>>m;for(int i=0; i<m; ++i) {int x, y; cin>>x>>y;to[x].insert(y);in_degree[y]++;}int k; cin>>k;vector<int> ans;for(int i=0; i<k; ++i) {vector<int> seq(n);for(int i=0; i<n; ++i) cin>>seq[i];if(!Judge(seq)){ans.push_back(i);}}for(int i=0; i<ans.size(); ++i){if(i!=0) cout<<" ";cout<<ans[i];}
}

4 PAT 甲级 1147 Heaps

#include<bits/stdc++.h>
using namespace std;const int N = 1010;
int m, n;
int tree[N];int lchild(int pos) {int child = 2*pos + 1;return child>=n ? -1: child;
}int rchild(int pos) {int child = 2*pos + 2;return child>=n ? -1: child;
}void PostOrder(int idx, vector<int>& vec) {if(idx == -1) return;PostOrder(lchild(idx), vec);PostOrder(rchild(idx), vec);vec.push_back(tree[idx]);
}bool IsMaxHeap(int idx) {if(lchild(idx) == -1) return true;if(rchild(idx) == -1) {return tree[idx]>=tree[lchild(idx)] && IsMaxHeap(lchild(idx));}return tree[idx]>=tree[lchild(idx)] &&tree[idx]>=tree[rchild(idx)] &&IsMaxHeap(lchild(idx)) &&IsMaxHeap(rchild(idx));
}bool IsMinHeap(int idx) {if(lchild(idx) == -1) return true;if(rchild(idx) == -1) {return tree[idx]<=tree[lchild(idx)] && IsMinHeap(lchild(idx));}return tree[idx]<=tree[lchild(idx)] &&tree[idx]<=tree[rchild(idx)] &&IsMinHeap(lchild(idx)) &&IsMinHeap(rchild(idx));
}int main() {cin>>m>>n;for(int i=0; i<m; ++i){for(int j=0; j<n; ++j) {cin>>tree[j];}if(IsMaxHeap(0)) printf("Max Heap\n");else if(IsMinHeap(0)) printf("Min Heap\n");else printf("Not Heap\n");vector<int> path;PostOrder(0, path);for(int i=0; i<path.size(); ++i) {if(i!=0) printf(" ");printf("%d", path[i]);}printf("\n");}
}