[数据结构与算法]PAT甲级备战

2021.8.21

1155 Heap Paths (30 分)

题目大意：
给出一棵完全二叉树，需打印出所有从根节点到叶子节点的路径（从右往左输出），并判断出该二叉树是小顶堆还是大顶堆或者不是堆。

从根节点到叶子结点的路径：先序遍历；从右往左输出：先序遍历的镜像。
记录路径：dfs一边搜索，一边记录，然后打印输出
vector存储路径，通过push和pop回溯，维护路径
判断是否是堆：
如果满足：父节点均大于/小于他的所有子节点，则是大顶堆/小顶堆；否则啥也不是。

#include<bits/stdc++.h>
#define pb push_back
#define mpi make_pair
#define fi first
#define se second
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pi acos(-1)
using namespace std;
const int maxn=1e5+10;
const int mod=1e9+7;
typedef long long ll;
inline ll lowbit(ll x){ return x&(-x);}
int a[maxn];
vector<int>v;
int vis[maxn];
int n;
void dfs(int x){
	int lc=2*x;
	int rc=2*x+1;
	if(lc>n&&rc>n){
		if(x<=n){//打印路径
			cout<<v[0];
			for(int i=1;i<v.size();i++){
				cout<<" "<<v[i];
			}
			cout<<endl;
		}
		return;
	}
	//先搜右子树，在搜左子树（相当于先序遍历的镜像）
	v.pb(a[rc]);
	dfs(rc);
	v.pop_back();//回溯！！！
	v.pb(a[lc]);
	dfs(lc);
	v.pop_back();
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	v.pb(a[1]);
	dfs(1);
	int flag=0;
	if(a[1]>a[2]) flag=1;//大顶堆
	else flag=2;//小顶堆
	for(int i=2;i<=n;i++){
		int lc=2*i;
		int rc=2*i+1;
		if(flag==1&&((lc<=n&&a[i]<a[lc])||(rc<=n&&a[i]<a[rc]))){
			flag=0;
			break;
		} 
		if(flag==2&&((lc<=n&&a[i]>a[lc])||(rc<=n&&a[i]>a[rc]))){
			flag=0;
			break;
		}
	}	
	if(flag==1){
		puts("Max Heap");
	}
	else if(flag==2){
		puts("Min Heap");
	}
	else puts("Not Heap");
	return 0;
}

1154 Vertex Coloring (25 分)

题目大意：
同一条边的两个顶点颜色不能相同。
判断某涂色方案是否符合上述条件，若符合，统计不同颜色的个数，否则输出no

简单粗暴：先存图（事实证明，不管用结构体存还是vector邻接表存都可以，不会超时），然后统计颜色个数（set）
最后遍历所有边，如果出现同一边的两个顶点同色的情况，直接结束。
一直在想会不会超时，可能是acm赛制做太多了，搞的心理恐惧，pat怕啥？交了再说>_<

#include<bits/stdc++.h>
#define pb push_back
#define mpi make_pair
#define fi first
#define se second
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pi acos(-1)
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
typedef long long ll;
inline ll lowbit(ll x){ return x&(-x);}
int col[maxn];
vector<int>e[maxn];
set<int>s;
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	while(m--){
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].pb(v);
		e[v].pb(u);
	} 
	int k;
	scanf("%d",&k);
	while(k--){
		int num=0;
		s.clear();
		for(int i=0;i<n;i++){
			scanf("%d",&col[i]);
			s.insert(col[i]);
		}
		int flag=0;
		for(int i=0;i<n;i++){
			for(auto j:e[i]){
				if(col[i]==col[j]){
					flag=1;
					break;
				}
			}
			if(flag) break;
		}
		if(flag) puts("No");
		else printf("%d-coloring\n",s.size());		
	}
	return 0;
}

1153 Decode Registration Card of PAT (25 分)

用结构体记录信息，将card number拆成四个部分：等级、考场号、考试时间、座位号
对于第一种询问：同样用结构体将同一等级的人的card number和考试成绩记录下来，然后排序输出
对于第二种查询：直接遍历结构体，将对应考场的学生成绩相加即可
对于第三种查询：用unordered_map统计相同考场的人数（map会超时），然后按value值排序。
注意：查询输入时什么样，输出就什么样，不要忽略前缀零
！
如：输入查询 2 00107
则输出 2 00107
而不是 2 107。。。

#include<bits/stdc++.h>
#define pb push_back
#define mpi make_pair
#define fi first
#define se second
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pi acos(-1)
using namespace std;
const int maxn=1e4+10;
const int mod=1e9+7;
typedef long long ll;
inline ll lowbit(ll x){ return x&(-x);}
struct stu{
	string id;
	char type;
	int site,date,num,grade;
}s[maxn],t[maxn];
bool cmp(stu a,stu b){
	if(a.grade!=b.grade) return a.grade>b.grade;
	else return a.id<b.id;
}
unordered_map<int,int>mp;
vector<pair<int,int> >v;
bool cmp1(const pair<int,int> &p1,const pair<int,int> &p2)
{
	if(p1.se!=p2.se) return p1.se>p2.se;
	else return p1.fi<p2.fi;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		string t;
		int g;
		cin>>t>>g;
		s[i].id=t;
		s[i].type=t[0];
		s[i].site=stoi(t.substr(1,3));
		s[i].date=stoi(t.substr(4,6));
		s[i].num=stoi(t.substr(10,3));
        s[i].grade=g;
	}
	for(int i=0;i<m;i++){
		int ty;
		cin>>ty;
		printf("Case %d: %d ",i+1,ty);
		if(ty==1){
			char ch;
			cin>>ch;
			printf("%c\n",ch);
			int k=0;
			for(int j=0;j<n;j++){
				if(s[j].type==ch){
					t[k].id=s[j].id;
					t[k++].grade=s[j].grade;
				}
			}
			if(k==0) puts("NA");
			else{
				sort(t,t+k,cmp);
				for(int j=0;j<k;j++){
					cout<<t[j].id<<" ";
					printf("%d\n",t[j].grade);
				}
			}
		}
		if(ty==2){
			string ad;
			cin>>ad;
		    cout<<ad<<endl;
		    int add=stoi(ad);
			int sum=0;
			int ans=0;
			for(int j=0;j<n;j++){
				if(s[j].site==add){
					ans++;
					sum+=s[j].grade;
				}
			}
			if(ans==0) puts("NA");
			else printf("%d %d\n",ans,sum);
		}
		if(ty==3){
			string ti;
			cin>>ti;
			cout<<ti<<endl;
			int time=stoi(ti);
			int flag=0;
			mp.clear();
			for(int j=0;j<n;j++){
				if(s[j].date==time){
					flag=1;
					mp[s[j].site]++;
				}
			}
			if(flag==0) puts("NA");
			else{
				v.clear();
				unordered_map<int,int>::iterator it;
				for(it=mp.begin();it!=mp.end();++it){
					v.pb(mpi(it->first,it->second));
				}
				sort(v.begin(),v.end(),cmp1);
				vector<pair<int,int> >::iterator it2;
			    for (it2=v.begin();it2!=v.end();++it2){
			    	if(it2->second==0) break;
			        printf("%03d %d\n",it2->first,it2->second);
			    }
			}
		}
	}
	return 0;
}