PAT 甲級 1026~1030

目錄

1027 Colors in Mars （20 分）（簡單進制轉換）

1028 List Sorting （25 分）（cmp函數）

1029 Median （25 分）（思維）

1030 Travel Plan （30 分）（dijkstra+遞歸）

1027 Colors in Mars （20 分）（簡單進制轉換）

【代碼】比較簡單，直接放代碼，做得比較暴力

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int r,g,b;
	scanf("%d%d%d",&r,&g,&b);
	printf("#");
	int r1=0,r2=0,g1=0,g2=0,b1=0,b2=0;
	r1=r/13,r2=r%13;	
	g1=g/13,g2=g%13;
	b1=b/13,b2=b%13;
	if(r1>=10)printf("%c",r1-10+'A');
	else printf("%d",r1);
	if(r2>=10)printf("%c",r2-10+'A');
	else printf("%d",r2);
	if(g1>=10)printf("%c",g1-10+'A');
	else printf("%d",g1);
	if(g2>=10)printf("%c",g2-10+'A');
	else printf("%d",g2);
	if(b1>=10)printf("%c",b1-10+'A');
	else printf("%d",b1);
	if(b2>=10)printf("%c",b2-10+'A');
	else printf("%d\n",b2);
	
}
           

1028 List Sorting （25 分）（cmp函數）

【代碼】

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
struct node{
	int id;
	string name;
	int score;
}a[maxn];
bool cmp1(node x,node y){return x.id<y.id;}
bool cmp2(node x,node y){return x.name<=y.name;}
bool cmp3(node x,node y){return x.score!=y.score?x.score<=y.score:x.id<y.id;}

int main()
{
	int n,c;
	scanf("%d%d",&n,&c);
	for(int i=0;i<n;++i)
	{
		scanf("%d",&a[i].id);
		cin>>a[i].name;
		scanf("%d",&a[i].score);
	}
	if(c==1)sort(a,a+n,cmp1);
	else if(c==2)sort(a,a+n,cmp2);
	else if(c==3)sort(a,a+n,cmp3);
	for(int i=0;i<n;++i)
	{
		printf("%06d ",a[i].id);
		cout<<a[i].name;
		printf(" %d\n",a[i].score);
	}
}
           

1029 Median （25 分）（思維）

【題意】給出兩串遞增序列，注意是遞增的，題上有說明的！然後求出這兩串序列合起來的中位數

【分析】

剛拿到題，想想，這麼簡單嘛，不就排個序嘛。然後就vector存一下再sort，然後就好多記憶體超限...

然後我把long long改成int，發現少了一個記憶體超限？？

還是思路有問題啦，這道題會卡sort（pat肯定不會考sort一下就能過的簡單題吧）

既然是遞增的，對于第二個序列，邊讀邊進行比較。如果到達中間位置就輸出；

手動給數組末尾指派以省去末尾判斷

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;
int k[maxn];

int main()
{
	int n; scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&k[i]);
	int m;scanf("%d",&m);
	int temp,cnt=0,i=1;
	k[n+1]=0x7fffffff;//long int的最大值;手動加末尾，省去while判斷 
	int midpos=(n+m+1)/2;
	for(int j=1;j<=m;j++)
	{
		scanf("%d",&temp);
		while(k[i]<temp)
		{
			cnt++;
			if(cnt==midpos)cout<<k[i];
			i++;
		}
		cnt++;
		if(cnt==midpos)cout<<temp;
	}
	while(i<=n)
	{
		cnt++;
		if(cnt==midpos)cout<<k[i];
		i++;
	}
	return 0;
}
           

1030 Travel Plan （30 分）（dijkstra+遞歸）

【題意】給出兩城市之間的cost和dist，求最短路，若相同，取cost最小的

【分析】用dijkstra求出單源最短路，求的同時若有相同dist進行記錄。再遞歸周遊求最小cost；

【代碼】

#include<bits/stdc++.h>
using namespace std;

const int maxn=510;
const int inf=0x3f3f3f3f;
int dis[maxn][maxn];
int cost[maxn][maxn];
int d[maxn];
int book[maxn];
int n,m,st,ed;

vector<int>path[maxn];
vector<int>v;

int min_cost=inf;
vector<int>t,tt;
int pre,now;

void dijkstra(int x)
{
	memset(d,inf,sizeof(d));
	memset(book,0,sizeof(book));
	d[x]=0;
	for(int i=0;i<n;++i)
	{
		int now=-1,minn=inf;
		for(int j=0;j<n;++j)
			if(!book[j] && d[j]<minn)
				minn=d[j],now=j;
		if(now==-1)break;
		book[now]=1;
		for(int j=0;j<n;++j)
		{
			if(!book[j] && dis[now][j])
			{
				if(d[j]>d[now]+dis[now][j])
				{
					d[j]=d[now]+dis[now][j];
					path[j].clear();
					path[j].push_back(now);
				}
				else if(d[j]==d[now]+dis[now][j])
					path[j].push_back(now);
				
			}
		}
	}
}
void dfs(int x)
{
	if(x==st)
	{	
		t.push_back(x);
		int sumcost=0,sumdis=0;
		for(int i=t.size()-1;i>0;--i)
		{
			int u=t[i];
			int v=t[i-1];
			sumcost+=cost[u][v];
		}
		if(min_cost>sumcost)min_cost=sumcost,tt=t;
		t.pop_back(); //該節點已完成，彈出，防止幹擾同層次其他節點的通路 
		return;
	}
	t.push_back(x);
	for(int i=0;i<path[x].size();++i)
		dfs(path[x][i]);
	t.pop_back(); //同上 
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&st,&ed);
	memset(dis,inf,sizeof(dis));
	memset(cost,inf,sizeof(cost));
	while(m--)
	{
		int u,v,x,y;
		scanf("%d%d%d%d",&u,&v,&x,&y);
		dis[u][v]=dis[v][u]=x;
		cost[u][v]=cost[v][u]=y;
	}
	dijkstra(st);//求st到各點的最短路；那麼st →ed則為d[ed] 
	dfs(ed);
	//cout<<"tt.size()="<<tt.size()<<"\n";
	reverse(tt.begin(),tt.end());
	for(int i=0;i<tt.size();++i)cout<<tt[i]<<" ";
	cout<<d[ed]<<" "<<min_cost<<endl;
}