题目库链接：团体程序设计天梯赛-练习集
目录
OP
\
L2-001 紧急救援 (25 分)
dijkstra（迪杰斯特拉）算法
大佬说SPFA也可以做，mark一下，接下来学
思路
可以参考这里来了解迪杰斯特拉的基本原理；
此题的主要特定是最短路可能有多种规划路线，而最优解只有一个，即需要同时处理距离和人数两个维度的信息；
主要思想是将所有点分为已达点与未达点两个集合（代码中用一个数组进行01标记），最开始时，已达点集合仅有出发点，未达点集合包含其余所有点；
主要过程是每一次循环遍历所有未达点，对于每一个未达点 pj ，如果可以通过一条道路（长度 ki ）连接至已达点 pi ，则记录由此未达点到达初始点的最短距离（设 pi 点到起始点的最短距离 li， l j = m i n ( l i + k i ) l_j=min(l_i+k_i) lj=min(li+ki)），并记录所有能使 lj 取最小值的 i ，作为到达此点的方案数；
在所有未达点中选择距离初始点最短的点，将其加入已达点集合，并在所有可行方案（ i ）中选择积累人数最多的点作为最终与其连接的点，新点的累计人数即为与其连接点的累积人数和新点原有人数的和；
如此循环，直到目标点已达；
最后按顺序找出整个路径上的各个点并输出即可。
代码注释已加
进行人数存储的部分可优化，即smp变量不必要
时间复杂度O(n3)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
struct
{
vector<int>fr;//存储其上游的点，即from i
int strd=100000000;//存储距离初始点的距离，默认无穷大
int p=0;//存储此点的人数
int smp=0;//存储从初始点到此点的累计人数
}cty[502];
int main()
{
int n,m,f,t,a,b,l;//n为城市数，m为道路书，abl为接收道路用变量
int r[502][502]={0},rch[502]={0};//r即road，存储道路，长度为0即无路，此处可优化
//rch数组存储已达点及方案数，0为未达
cin>>n>>m>>f>>t;
cty[f].fr.push_back(f);//初始化处理开始点
rch[f]=1;
cty[f].strd=0;
for(int i=0;i<n;i++)
{
cin>>cty[i].p;
cty[i].smp=cty[i].p;
}//接收城市救援人数
for(int i=0;i<m;i++)//接收路，对称加入存储
{
cin>>a>>b>>l;
if(r[a][b])r[a][b]=min(r[a][b],l);
else r[a][b]=l;
if(r[b][a])r[b][a]=min(r[b][a],l);
else r[b][a]=l;
}
while(!rch[t])//如果目标点未达，则持续循环
{
int mnr=100000000-8,mnm=-1;//mnr存储未达点距离初始点的距离最小值
//mnm存储满足mnr点的编号
for(int i=0;i<n;i++)
{
if(!rch[i])//如果未达
{
cty[i].fr.clear();//初始化
cty[i].strd=100000000;
for(int j=0;j<n;j++)
{
if(rch[j]&&r[i][j])//遍历每一条通往可达点的道路
{
if(cty[j].strd+r[i][j]<cty[i].strd)//更小值
{
cty[i].strd=cty[j].strd+r[i][j];//更新最小值
cty[i].fr.clear();//情况方案
cty[i].fr.push_back(j);//j加入方案
}
else if(cty[j].strd+r[i][j]==cty[i].strd)//与最小值相等的值
{
cty[i].fr.push_back(j);//j加入方案
}
}
}
if(cty[i].strd<mnr)//更新此次循环的最小距离
{
mnr=cty[i].strd;
mnm=i;
}
}
}
int mxp=0,mxm=-1;//mxp记录最多积累人数，mxm记录mxp对应的城市编号
for(int j:cty[mnm].fr)
{
rch[mnm]+=rch[j];//到达新点的最终方案数为每一个可行方案对应的点方案数之和
if(cty[j].smp>mxp)//更新
{
mxp=cty[j].smp;
mxm=j;
}
}
cty[mnm].fr.clear();//清空方案
cty[mnm].fr.push_back(mxm);//并将积累人数最多的方案定为最终方案
cty[mnm].smp+=cty[mxm].smp;//更新积累人数
//printf("%d %d\n",mnm,rch[mnm]);
}
printf("%d %d\n",rch[t],cty[t].smp);//输出方案数和最优方案人数
stack<int>stk;//栈存储路径结点
int now=t;
stk.push(t);
stk.push(cty[now].fr[0]);
now=cty[now].fr[0];
//printf("*%d",stk.top());
while(stk.top()!=f)
{
stk.push(cty[now].fr[0]);
now=cty[now].fr[0];
//printf("*%d",stk.top());
}
printf("%d",stk.top());//输出开始
stk.pop();
while(stk.size())
{
printf(" %d",stk.top());
stk.pop();
}
return 0;
}
L2-002 链表去重 (25 分)
数据结构
思路
存住上一个节点，按要求更新处理即可；
要握住两个链表的起始点；
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
struct
{
int num;
int nxt;
}vtr[100005];
int main()
{
int f1,n,g,f2=-1;
cin>>f1>>n;
for(int i=1;i<=n;i++)
{
cin>>g;
cin>>vtr[g].num>>vtr[g].nxt;
}//接收结束
int now=f1,a[10004]={0},lst=0,now2;//a用来桶去重，now为正在处理的节点，lst为上一个节点，now2为另一个链表的末尾
while(now!=-1)//未到f1的结尾则继续循环
{
if(a[abs(vtr[now].num)])
{
vtr[lst].nxt=vtr[now].nxt;
if(f2==-1)f2=now,now2=now,now=vtr[now].nxt,vtr[now2].nxt=-1;//若另一链表未被建立
else
{
vtr[now2].nxt=now;
now2=now;
now=vtr[now].nxt;
vtr[now2].nxt=-1;
}
}
else
{
a[abs(vtr[now].num)]=1;
lst=now;
now=vtr[now].nxt;
}
}
now=f1;
while(now!=-1)
{
printf("%05d %d ",now,vtr[now].num);
if(vtr[now].nxt==-1)printf("%d\n",-1);
else printf("%05d\n",vtr[now].nxt);//注意要求保留位数
now=vtr[now].nxt;
}
now=f2;
while(now!=-1)
{
printf("%05d %d ",now,vtr[now].num);
if(vtr[now].nxt==-1)printf("%d\n",-1);
else printf("%05d\n",vtr[now].nxt);
now=vtr[now].nxt;
}
return 0;
}
L2-003 月饼 (25 分)
模拟，贪心
思路
模拟即可，优先卖单价高的；
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
struct mooncake
{
double w;
double m;
}mnk[1003];
bool cmp(const mooncake a,const mooncake b)
{
return 1.0*a.m/a.w>1.0*b.m/b.w;
}
//money per weight 按单价降序排序
int main()
{
int t;
double n;
cin>>t>>n;
for(int i=1;i<=t;i++)cin>>mnk[i].w;
for(int i=1;i<=t;i++)cin>>mnk[i].m;
sort(mnk+1,mnk+t+1,cmp);
double s=0;
for(int i=1;i<=t&&n;i++)
{
if(n>=mnk[i].w)
{
n-=mnk[i].w;
s+=mnk[i].m;
}
else
{
s+=1.0*n*mnk[i].m/mnk[i].w;
n=0;
}
}
printf("%.2lf",s);
return 0;
}
L2-004 这是二叉搜索树吗？ (25 分)
树的前序遍历
思路
对于题目中描述的二叉搜索树，满足以下性质：
对于一棵树前序遍历 [ l , r ] ，第一个元素必为根节点；
设从第二个节点开始，第一个大于等于根节点的节点编号为mk，
m
a
x
[
l
,
m
k
−
1
]
<
r
o
o
t
,
m
i
n
[
m
k
,
r
]
<
=
r
o
o
t
max [ l , mk - 1 ]<root,min[ mk , r ]<=root
max[l,mk−1]<root,min[mk,r]<=root；
镜像树类似；
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
queue<int>que;
int a[1003];
bool ju(int l,int r,int dir)//dir=1即为正向树，dir=0即为镜像树
{
int i,root=a[l],ans=1,mk=r+1,mi=root,mx=root-1;
//root存储子树根节点的值，mk为右子树的根节点
//mi为目标子树的最小值，mx为目标字数的最大值
/*if(l==r) //防呆代码，实际上用不到
{
que.push(a[l]);
return 1;
}
else if(l>r)
{
return 1;
}*/
if(dir)
{
for(i=l+1;i<=r;i++)
{
if(a[i]>=root)mk=min(mk,i);
if(mk==r+1)mx=max(mx,a[i]);//mk==r+1说明此处仍为左子树
else mi=min(mi,a[i]);
}
if(mk!=l+1&&mx>=root||mk!=r+1&&mi<root)//对于mk的判据可以删除
{
//printf("%d %d %d %d %d\n",l,r,mi,mx,mk);
return 0;
}
}
else
{
for(i=l+1;i<=r;i++)
{
if(a[i]<root)mk=min(mk,i);
if(mk==r+1)mi=min(mi,a[i]);
else mx=max(mx,a[i]);
}
if(mk!=r+1&&mx>=root||mk!=l+1&&mi<root)
{
//printf("%d %d %d %d %d\n",l,r,mi,mx,mk);
return 0;
}
}
if(mk!=l+1)//若左子树存在
{
ans*=ju(l+1,mk-1,dir);
}
if(mk!=r+1)//若右子树存在
{
ans*=ju(mk,r,dir);
}
que.push(root);//根节点入栈，栈内即为后序遍历
return ans;
}
int main()
{
int n,i,f=1;
cin>>n;
for(i=1;i<=n&&f;i++)cin>>a[i];
{
if(a[1]>a[2])f=ju(1,n,1);//正向树
else f=ju(1,n,0);//镜像树
if(f)
{
printf("YES\n",que.size());
while(!que.empty())
{
printf("%d",que.front());
if(que.size()!=1)printf(" ");
que.pop();
}
}
else printf("NO");
}
return 0;
}