正文

PAT (Advanced Level) 1124~1127：1124模拟 1125优先队列 1126欧拉通路 1127中序后序求Z字形层序遍历

IP云
IP云V管理员/0 阅读
08/06
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
1124 Raffle for Weibo Followers（20 分）

题意：微博抽奖，有M个人，标号为1~M。从第S个人开始，每N个人可以获奖，但是已获奖的人不能重复获奖，需要跳过该人把机会留给下一个人。如果没有得奖的输出“Keep going...”。

分析：按题意模拟即可。cnt表示当前的人距离上一个获奖的人间隔的人数。若cnt==N表示当前人可以获奖，若该人已获奖，可将cnt--，继续判断下一个人。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<map>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
using namespace std;
map<string, int> mp;
int main(){
int M, N, S;
scanf("%d%d%d", &M, &N, &S);
bool ok = false;
int cnt = 0;
string s;
for(int i = 1; i <= M; ++i){
++cnt;
cin >> s;
if(i == S){
mp[s] = 1;
cout << s <<endl;
ok = true;
cnt = 0;
}
if(ok && cnt == N){
if(!mp.count(s)){
mp[s] = 1;
cnt = 0;
cout << s << endl;
}
else{
--cnt;
}
}
}
if(!ok) printf("Keep going...\n");
return 0;
}

1125 Chain the Ropes（25 分）

题意：将n段绳子连接成一段，每次连接只能两段相连组成新的一段，且新的一段的长度是原来两段长度和的一半，问n段绳子能连接成的最长长度，要求答案下取整。

分析：每次取最短的两段绳子相连，优先队列实现。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<map>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#include<queue>
using namespace std;
priority_queue<double, vector<double>, greater<double> > q;
int main(){
int N, x;
scanf("%d", &N);
while(N--){
scanf("%d", &x);
q.push((double)x);
}
while(q.size() > 1){
double top1 = q.top();
q.pop();
double top2 = q.top();
q.pop();
q.push((top1 + top2) / 2);
}
printf("%d\n", (int)q.top());
return 0;
}

1126 Eulerian Path（25 分）

题意：给定一个无向图，判断是Eulerian，Semi-Eulerian还是Non-Eulerian，并输出每个点的度数。

分析：

1、在一个连通图中若每个结点度数都是偶数，则一定含有欧拉回路，称为Eulerian；

2、在一个连通图中若只有两个结点度数是奇数，则一定含有欧拉通路，且该通路分别从其中一个度数为奇数的点出发，到达另一个度数为奇数的点，称为Semi-Eulerian。

3、因为Eulerian和Semi-Eulerian的前提是连通图，所以首先用并查集判连通。若不连通，则为Non-Eulerian，注意此时要输出每个点的度数。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<map>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN = 500 + 10;
vector<int> G[MAXN];
vector<int> ans;
set<int> st;
int fa[MAXN];
int Find(int x){
return fa[x] = (x == fa[x]) ? x : Find(fa[x]);
}
int main(){
int N, M;
scanf("%d%d", &N, &M);
for(int i = 1; i <= N; ++i) fa[i] = i;
int x, y;
for(int i = 0; i < M; ++i){
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
int tmpx = Find(x);
int tmpy = Find(y);
if(tmpx < tmpy) fa[tmpy] = tmpx;
else fa[tmpx] = tmpy;
}
for(int i = 1; i <= N; ++i) st.insert(Find(i));
int cnt = 0;
for(int i = 1; i <= N; ++i){
int len = G[i].size();
ans.push_back(len);
if(len % 2 == 1) ++cnt;
}
for(int i = 0; i < N; ++i){
if(i) printf(" ");
printf("%d", ans[i]);
}
printf("\n");
if(st.size() != 1){
printf("Non-Eulerian\n");
}
else{
if(cnt == 0){
printf("Eulerian\n");
}
else if(cnt == 2){
printf("Semi-Eulerian\n");
}
else{
printf("Non-Eulerian\n");
}
}
return 0;
}

1127 ZigZagging on a Tree（30 分）

题意：已知二叉树的中序遍历和后序遍历，求Z字形的层序遍历。即，若根结点为第1层，则偶数层从左到右遍历，奇数层从右到左遍历。

分析：离散化树的结点。递归建树，bfs层序遍历的同时，记录点的层数，然后输出Z字形遍历的结果。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<map>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
const int MAXN = 30 + 10;
map<int, int> mp;
int a[MAXN], inorder[MAXN], postorder[MAXN];
int lchild[MAXN], rchild[MAXN];
int cnt;
vector<pair<int, int> > tmp;
vector<int> ans;
int getId(int x){
if(mp.count(x)) return mp[x];
a[++cnt] = x;
return mp[x] = cnt;
}
int build(int iL, int iR, int pL, int pR, int root){
if(iL > iR) return 0;
int id = iL;
while(inorder[id] != root) ++id;
int num = id - iL;
root = getId(root);
lchild[root] = build(iL, id - 1, pL, pL + num - 1, postorder[pL + num - 1]);
rchild[root] = build(id + 1, iR, pL + num, pR - 1, postorder[pR - 1]);
return root;
}
void bfs(int st){
queue<int> x, deep;
x.push(st);
deep.push(1);
tmp.push_back(pair<int, int>(st, 1));
while(!x.empty()){
int tmpx = x.front();
int tmpdeep = deep.front();
x.pop();
deep.pop();
if(lchild[tmpx]){
x.push(lchild[tmpx]);
deep.push(tmpdeep + 1);
tmp.push_back(pair<int, int>(lchild[tmpx], tmpdeep + 1));
}
if(rchild[tmpx]){
x.push(rchild[tmpx]);
deep.push(tmpdeep + 1);
tmp.push_back(pair<int, int>(rchild[tmpx], tmpdeep + 1));
}
}
}
int main(){
int N;
scanf("%d", &N);
for(int i = 0; i < N; ++i){
scanf("%d", &inorder[i]);
}
for(int i = 0; i < N; ++i){
scanf("%d", &postorder[i]);
}
build(0, N - 1, 0, N - 1, postorder[N - 1]);
bfs(getId(postorder[N - 1]));
int l = tmp.size();
for(int i = 0; i < l; ++i){
if(tmp[i].second != 1 && tmp[i].second % 2 == 1){
stack<int> st;
while(tmp[i].second % 2 == 1){
st.push(tmp[i].first);
++i;
}
--i;
while(!st.empty()){
ans.push_back(st.top());
st.pop();
}
}
else{
ans.push_back(tmp[i].first);
}
}
int len = ans.size();
for(int i = 0; i < len; ++i){
if(i) printf(" ");
printf("%d", a[ans[i]]);
}
printf("\n");
return 0;
}