2021.9.11 PAT甲级考试满分代码

第1题 数组模拟

#include <iostream>
#include <cstdio>
using namespace std;
int n,m,q,start,length,tl=0,tr=0,ans=1;
int flag[10005];
struct node
{
	int add,num;
}p[1300000];
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int k=1;k<=n;k++)
	{
		cin>>start>>length;
		tl=tr;
		tr+=length;
		for(int i=tl;i<tr;i++)
		{
			p[i].add=start+4*(i-tl);
			p[i].num=k;
		}
	}
	while(m--)
	{
		cin>>q;
		if(q>=tr)
		{
			cout<<"Illegal Access"<<endl;
			continue;
		}
		cout<<p[q].add<<endl;
		flag[p[q].num]=1;
	}
	for(int i=10000;i>=1;i--)
		if(flag[i])
		{
			ans=i;
			break;
		}
	cout<<ans<<endl;
	return 0;
}

第2题 数组排序

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
	int num,pos,rank;
}p[10005];
int flag=1;
bool cmp(node a,node b)
{
	if(flag==1)
		return a.num>b.num;
	if(flag==2)
		return a.pos>b.pos;
}
struct Node
{
	int num,pos;
	bool operator < (const Node b) const
	{
		return num>b.num;
	}
}q[10005];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i].num;
		p[i].pos=i;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>q[i].num;
		q[i].pos=i;
	}
	sort(p+1,p+n+1,cmp);
	sort(q+1,q+n+1);
	for(int i=1;i<=n;i++)
		p[i].rank=i;
	flag=2;
	sort(p+1,p+n+1,cmp);
	//for(int i=1;i<=n;i++)
	//	cout<<p[i].num<<" "<<p[i].pos<<" "<<p[i].rank<<endl;
	cout<<q[p[1].rank].pos;
	for(int i=2;i<=n;i++)
		cout<<" "<<q[p[i].rank].pos;
	return 0;
}

第3题 图论DFS

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> G[105];
int n,m,u,v,temps,start,ans=0;
int vis[105];
void DFS(int pos,int dis)
{
	if(dis>ans||dis==ans&&temps<start)
	{
		start=temps;
		ans=dis;
	}
	int size=G[pos].size();
	for(int i=0;i<size;i++)
	{
		if(!vis[G[pos][i]])
		{
			vis[G[pos][i]]=1;
			DFS(G[pos][i],dis+1);
			break;
		}
	}
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	while(m--)
	{
		cin>>u>>v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	for(int i=1;i<=n;i++)
		sort(G[i].begin(),G[i].end());
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		temps=i;
		vis[i]=1;
		DFS(i,1);
	}
	cout<<start<<" "<<ans<<endl;
	return 0;
}

第4题 二叉树 递归建树+遍历

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> ans[2];
struct node
{
	int key,pri;
	bool operator < (const node b) const
	{
		return key<b.key;
	}
}a[35];
struct tree
{
	int data[2];
	tree *lchild,*rchild;
};
tree* build(int L,int R)
{
	if(L>R)
		return NULL;
	int k,min=199999999;
	for(int i=L;i<=R;i++)
		if(a[i].pri<min)
		{
			k=i;
			min=a[i].pri;
		}
	tree *root=new tree;
	root->data[0]=a[k].key;
	root->data[1]=a[k].pri;
	root->lchild=build(L,k-1);
	root->rchild=build(k+1,R);
	return root;
}
void BFS(tree *root)
{
	queue<tree*> q;
	q.push(root);
	while(!q.empty())
	{
		tree* t=q.front();
		q.pop();
		ans[0].push_back(t->data[0]);
		ans[1].push_back(t->data[1]);
		if(t->lchild)
			q.push(t->lchild);
		if(t->rchild)
			q.push(t->rchild);
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i].key>>a[i].pri;
	sort(a,a+n);
	//for(int i=0;i<n;i++)
	//	cout<<a[i].key<<" "<<a[i].pri<<endl;
	tree *root=build(0,n-1);
	BFS(root);
	int size=ans[0].size();
	cout<<ans[0][0];
	for(int i=1;i<size;i++)
		cout<<" "<<ans[0][i];
	cout<<endl<<ans[1][0];
	for(int i=1;i<size;i++)
		cout<<" "<<ans[1][i];
	return 0;
}