目录
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;
}