A：第一次，第二次，成交！

知识点：模拟、枚举

思路：先把每个人出的价格从小到大排序。从最小价格开始枚举。显然后面的人出的价格都比当前价格大。

答案就是当前价格*（m-当前位置+1）的最大值。再记录一下去最大值时的价格就好啦。注意n和m的大小关系。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,a[1005],maxn,ans;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i];
    sort(a+1,a+m+1);
    for(int i=m;i>=1;i--)
        if(a[i]*(m-i+1)>=maxn && m-i+1<=n)
            maxn=a[i]*(m-i+1),ans=a[i]; 
    cout<<ans<<" "<<maxn;
    return 0 ;
}

B：障碍迷宫

知识点：搜索、递推

思路：基本搜索类题目，从起点sx,sy进行搜索，若是到达了终点，则统计答案，返回，然后进行四个方向的枚举，注意不能越界，曾经未被访问并且还不能是障碍物，那么此时就可以访问一下该位置，进行深搜，结束了不要忘记在撤销掉此位置就可以了。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,t,ans;//n行m列t个障碍
int sx,sy,ex,ey;//起点和终点坐标
int x,y;//障碍的位置 
int a[11][11];//地图 
bool v[11][11];//标记 
int d[][2]={{0,1},{0,-1},{1,0},{-1,0}};
void dfs(int x,int y){
    if(x==ex && y==ey){
        ans++;
        return;
    }
    for(int i=0;i<4;i++){
        int xx=x+d[i][0],yy=y+d[i][1];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!v[xx][yy]&&!a[xx][yy]){
            v[xx][yy]=1;
            dfs(xx,yy);
            v[xx][yy]=0;
        }
    } 
} 
int main(){
    cin>>n>>m>>t>>sx>>sy>>ex>>ey;
    for(int i=1;i<=t;i++){
        cin>>x>>y;
        a[x][y]=1; 
    } 
    v[sx][sy]=1;//起点打标记 
    dfs(sx,sy);//从sx,sy出发
    cout<<ans; 
    return 0;
}

C：特殊的质数肋骨

知识点：质数、搜索

思路：首先，我们看到这题，第一个想法一定是枚举，然而这并不现实，所以我们想到枚举每一位，来构造质数。于是我们可以想到搜索。然后我们知道，只有开头能够出现2，5，其它数位不可能是偶数和5，所以枚举每一位数字的时候自然想到剪枝手段：跳过2,4,5,6,8.此外，另一个剪枝就是生成的数是否是质数，可以写个判断函数。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
bool pd(int x){
    for(int i=2;i*i<=x;i++)
        if(x%i==0)return 0;
    return 1;
}
void dfs(int s,int x){
    if(s>=n){
        cout<<x<<endl;
        return;
    }
    if(pd(x*10+1)) dfs(s+1,x*10+1);
    if(pd(x*10+3)) dfs(s+1,x*10+3); 
    if(pd(x*10+7)) dfs(s+1,x*10+7); 
    if(pd(x*10+9)) dfs(s+1,x*10+9); 
}
int main(){
    cin>>n;
    dfs(1,2);
    dfs(1,3);
    dfs(1,5);
    dfs(1,7);
    return 0;
}

D：聚会

知识点：最短路、Dijkstra

思路：

• 我们首先想到的是从每个点都求一遍到终点的最短路，这样会加大时间复杂度。
• 所以，我们可以反向建图，直接把单终点最短路转为单源最短路，只需要跑两次最短路算法，显然是稳过的。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,x,ans;//n头牛 m道路 x编号举行派对
int g[1001][1001],f[1001][1001],dis[1001],Dis[1001];
bool vis[1001];
struct node{
    int v,w;
};
void dijkstra(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        dis[i]=g[x][i];
    dis[x]=0;vis[x]=1;
    for(int i=1;i<n;i++){
        int minn=INT_MAX,pos=0;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&minn>dis[j])
                minn=dis[j],pos=j;
        if(!pos)break;vis[pos]=1;
        for(int j=1;j<=n;j++)
            dis[j]=min(dis[j],dis[pos]+g[pos][j]);
    }
} 
void Dijkstra(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        Dis[i]=f[x][i];
    Dis[x]=0;vis[x]=1;
    for(int i=1;i<n;i++){
        int minn=INT_MAX,pos=0;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&minn>Dis[j])
                minn=Dis[j],pos=j;
        if(!pos)break;vis[pos]=1;
        for(int j=1;j<=n;j++)
            Dis[j]=min(Dis[j],Dis[pos]+f[pos][j]);
    }
} 
int main(){
    cin>>n>>m>>x;
    memset(g,0x3f3f3f3f,sizeof(g));
    memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=1;i<=n;i++)g[i][i]=0,f[i][i]=0;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=c;//从a到b距离为c 
        f[b][a]=c;//从b到a距离为c 
    } 
    dijkstra();
    Dijkstra();
    for(int i=1;i<=n;i++)
        ans=max(ans,dis[i]+Dis[i]); 
    cout<<ans;
    return 0;
}