PAT (甲级) 2022年秋季考试 c++ 满分题解

7-3 Leader of the Opinion Leaders

分数 25

原题

算法标签

图 模拟

思路

依题意模拟， 具体思路见代码

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include
#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pb push_back
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
const int N = 10005, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
const double Exp=1e-8;
// in[i] 关注用户i的人 out[i]用户i关注的人
vector in[N], out[N], res;
bool st[N];
inline int rd(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n=rd(), t=rd();rep(i, 1, n+1){int x=rd();while(x--){int y=rd();in[y].pb(i);out[i].pb(y);}}// 标记精神领袖rep(i, 1, n+1){if(in[i].size()>=out[i].size()*t){st[i]=true;}}int mx=0;rep(i, 1, n+1){int m=0;// 统计粉丝数rep(j, 0, in[i].size()){if(st[in[i][j]]){m++;}}if(st[i]){// 更新最大粉丝数 清空原领袖if(m>mx){mx=m;res.clear();res.pb(i);}else if(m==mx){// 更新领袖res.pb(i);}}}printf("%lld", res[0]);rep(i, 1, res.size()){printf(" %lld", res[i]);	}return 0;
}

7-4 Pseudo-completeness

分数 30

原题

算法标签

树 dfs 模拟

思路

po[]存储后序遍历序列，d为层序遍历从左到右的序号（从0开始），f标记当前序号有无结点，mx为最大深度；
从前往后遍历第一个未被标记的节点序号：
①为n，且结点数量为2的n次方减1，则为perfect binary tree；
②为n，且结点数量不为2的n次方减1，则为complete binary tree；
③不为n，且在mx减1层的结点之后，则为pseudo-complete binary tree。

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include
#define int long long
#define xx first
#define yy second
#define ump unordered_map
#define us unordered_set
#define pb push_back
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
const int N = 10005, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
const double Exp=1e-8;
int pre[N], in[N], po[N], f[N];
bool st[N];
int mx, p;
inline int rd(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
void dfs(int u, int l, int r, int d, int le){if(l>r){return;}f[d]=true;mx=max(mx, le);int t=l;while(pre[u]!=in[t]){t++;}dfs(u+1, l, t-1, d*2+1, le+1);dfs(u+1+(t-l), t+1, r, d*2+2, le+1);po[p++]=pre[u];
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n=rd();rep(i, 1, n+1){in[i]=rd();}rep(i, 1, n+1){pre[i]=rd();}dfs(1, 1, n, 0, 1);rep(i, 0, n+1){if(!f[i]){if(i==n&&log2(n+1)==(int)log2(n+1)){puts("1");}else if(i==n){puts("2");}else if(i>=pow(2, mx-1)){puts("3");}else{puts("0");}break;}}printf("%lld", po[0]);rep(i, 1, n){printf(" %lld", po[i]);	}return 0;
}

参考文献

【PAT乙级+甲级题解】2022年秋季PAT乙级+甲级题解 By小柳 2022-9-4 19:00

原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈