7-1 Balloon Popping
#include <bits/stdc++.h>
using namespace std;
int main(){
int i;
int n,m;
scanf("%d%d",&n,&m);
int j;
int ans=0;
int a[n];
int bh=0;
int q=0;
for(i=0;i<n;i++)scanf("%d",&a[i]);
for(i=0;i<n;i++){
int cnt=1;
for(j=i+1;j<n;j++){
if(a[j]-a[i]<=m)cnt++;
else break;
}
if(cnt>ans){
bh=i;
q=j-1;
ans=cnt;
}
}
int r=a[q]-m;
cout<<r<<" "<<ans<<endl;
system("pause");
}7-2 The Second Run of Quicksort
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
int i;
while(n--){
int m;
scanf("%d",&m);
int a[m];
for(i=0;i<m;i++){
scanf("%d",&a[i]);
}
int l[m];
int r[m];
bool left[m];
bool right[m];
memset(left,0,sizeof(left));
memset(right,0,sizeof(right));
for(i=0;i<m;i++){//统计左面的最大值
if(i)l[i]=max(l[i-1],a[i]);
else l[i]=a[i];
}
for(i=m-1;i>=0;i--){//统计右面的最小值
if(i!=m-1)r[i]=min(r[i+1],a[i]);
else r[i]=a[i];
}
int j;
for(i=0;i<m;i++){//找到满足左面都小于该元素、右面都大于该元素的下标
if(l[i]==r[i]){
if(i==0)left[i]=1;//特殊情况处理
for(j=i+1;j<m;j++){//left代表左面有一个符合上述要求的元素
left[j]=1;
}
break;
}
}
for(i=m-1;i>=0;i--){
if(l[i]==r[i]){//right代表右面有一个符合上述要求的元素
if(i==m-1)right[i]=1;
for(j=i-1;j>=0;j--){
right[j]=1;
}
break;
}
}
for(i=0;i<m;i++){
if(l[i]==r[i]&&left[i]&&right[i])break;//都符合
}
if(i==m){
printf("No\n");
}
else printf("Yes\n");
}
system("pause");
}7-3 Leader of the Opinion Leaders
#include <bits/stdc++.h>
using namespace std;
int main(){//主要就是是leader的leader必须首先是leader，然后leader的leader必须在leader里面找到最大值
int n,m;
scanf("%d%d",&n,&m);
int i;
int j;
int a[n+1];
int in[n+1];//跟随他的人
int out[n+1];//他跟随的人
vector<int>t[n+1];
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for(i=0;i<n;i++){
int m;
scanf("%d",&m);
out[i+1]=m;
for(j=0;j<m;j++){
int v;
scanf("%d",&v);
t[i+1].push_back(v);
in[v]++;
}
}
int ans[n+1];
memset(ans,0,sizeof(ans));
int mx=0;
for(i=1;i<=n;i++){
if(in[i]/out[i]>=m){
for(j=0;j<t[i].size();j++){
ans[t[i][j]]++;
}
}
}
for(i=1;i<=n;i++){
if(in[i]/out[i]>=m){
mx=max(mx,ans[i]);
}
}
bool flag=1;
for(i=1;i<=n;i++){
if(in[i]/out[i]>=m&&ans[i]==mx&&flag){
printf("%d",i);
flag=0;
}
else if(in[i]/out[i]>=m&&ans[i]==mx){
printf(" %d",i);
}
}
system("pause");
}7-4 Pseudo-completeness
#include <bits/stdc++.h>
using namespace std;
struct tree{
int data;
tree *left=NULL;
tree *right=NULL;
int h;
};
int in[2010];
bool issame=1;
int pre[2010];
int h=-1;
int last=INT_MIN;
bool sign=1;
vector<tree*>s;
int mx=INT_MIN;
void creat(tree *(&root),int l,int r,int n,int v,int index){//建树
if(n==0)return ;
root=new tree;
if(last<v)last=v;//统计最大深度
root->data=pre[r];
root->h=v;//统计深度
s.push_back(root);//将所有的节点摘下来，2000个输入，复杂度不高可以直接遍历
if(index>mx)mx=index;
if(n==1){
if(h!=-1){
if(v!=h){
sign=0;//判断叶子节点是不是都在同一高度
}
}
else h=v;//如果是刚到叶子节点就更新叶子节点高度
return ;
}
int i;
for(i=l;pre[r]!=in[i];i++);
int llen=i-l;
int rlen=n-llen-1;
creat(root->left,l,r+1,llen,v+1,2*index);//根据index是否等于节点数目判断是否为完全二叉树
creat(root->right,i+1,r+llen+1,rlen,v+1,2*index+1);
if((root->left&&root->right==NULL)||(root->right&&root->left==NULL)){
sign=0;//如果有孩子的话必须两个都有
}
}
bool flag=1;
void postorder(tree *root){
if(root==NULL)return ;
postorder(root->left);
postorder(root->right);
if(flag){
printf("%d",root->data);
flag=0;
}
else printf(" %d",root->data);
}
int main(){
int n;
scanf("%d",&n);
int i;
for(i=0;i<n;i++){
scanf("%d",&in[i]);
}
for(i=0;i<n;i++){
scanf("%d",&pre[i]);
}
tree *root=NULL;
creat(root,0,0,n,0,1);
int height=-1;
for(i=0;i<s.size();i++){//对于第三种而言
if(s[i]->h==last||s[i]->h==last-1)continue;//去掉最后一层那么倒数第二层和倒数第一层都不用看，只需要看上层是否满足条件即可
if(s[i]->left&&s[i]->right==NULL)break;
else if(s[i]->right&&s[i]->left==NULL)break;
else if(s[i]->right==NULL&&s[i]->left==NULL)break;
}
if(sign){
printf("1\n");
}
else if(mx==n){
printf("2\n");
}
else if(i==s.size()&&issame){
printf("3\n");
}
else printf("0\n");
postorder(root);
system("pause");
}PAT总结：一定利用好时间把PAT甲级题库里面的题刷会，不要求速度，但是一定要要求质量，每天刷了几道题不重要，重要的是你学到了多少东西，不要和别人比什么速度，也不要只看大佬，人这一生不是和别人比，是和自己比的，做不出来不要慌，全力以赴不留遗憾，接受自己的不完美，就是自己做出的最完美的选择，感谢这个暑假，我懂了很多东西，这次PAT考试也没有辜负我的努力，头一次感觉到了努力就有回报，但是前提真的是接受不完美的自己，天高任鸟飞，海阔凭鱼跃，希望能在这个基点，我能走的更远！
2022-9-16
版权声明：本文为weixin_61168459原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。