前言

难度比较低，第一题是简单的最短路。第二题第三题都是比较基础的题目，第三题更加离谱，看起来很难，实际上非常水

第一题

现在小丽在城镇A，小明在城镇B。小丽要出发找小明。

城镇之间有双向通行的道路，通过道路要消耗一定的时间。

其中已知城镇C和城镇D之间有双向的传送门，可以不消耗时间瞬间传送过去

现在请你求出小丽从城镇A抵达城镇B的最短时间。保证从起点到终点有路径可达。

输入描述

第一行两个正整数n,m，以空格分开，表示总共有n个城镇，有m条道路相连
第二行两个正整数A,B，以空格分开，分别表示小丽所在城镇A，小明所在城镇B。
第三行两个正整数C，D，以空格分开，表示城镇C和城镇D之间有瞬间的双向传送门。
接下来m行，每行三个正整数u,v, c，以空格分开，表示城镇u和城镇v之间有道路，通过道路消耗时间c。
对于100%的数据保证 1<=n <=100,1<=m<=2*n，每条道路的时间花费在[1,10]之间

输出描述

一行，一个整教表示最短到达时间。

样例输入

4 3
1 4
1 3
1 2 1
2 3 1
2 4 1

样例输出

2

思路与代码

Floyd算法求最短路的经典应用。按照题意建图，并且手动更改城镇C和D之间的距离为0，进而跑最短路即可。

#include<iostream>
#include<cstring>
using namespace std;
int n,m,a,b,c,d;
int dis[555][555];
int main()
{
    memset(dis,0x3f, sizeof dis);
    cin>>n>>m;
    cin>>a>>b>>c>>d;
    for(int u,v,x,i = 1; i<=m; i++) {
        cin>>u>>v>>x;
        dis[u][v] = min(dis[u][v], x);
        dis[v][u] = min(dis[v][u], x);
    }
    dis[c][d] = dis[d][c] = 0;
    for(int k = 1; k<=n; k++) {
       for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        }     
    }
    cout << dis[a][b];

    return 0;
}#include<bits/stdc++.h>
using namespace std;
using gg = long long;

int main() {
 gg n; cin >> n;
 vector<gg> arr(n);
 for(int i = 0; i < n; i++) cin >> arr[i];
 vector<gg> have(n+1, 0), ans(n + 1);
 gg now = 1;
 for(int i = 0; i < n; i++) {
  have[arr[i]]++;
  while(now <= n && have[now]) {
   ans[now] = i + 1;
   now++;
  }
 }
 cout << ans[1];
 for(int i = 2; i <= n; i++) cout << ' ' << ans[i];
 cout << '\n';
 return 0;
} 

第二题

时间限制:4000MS 内存限制:589824KB

题目描述:

A市可以看作是一个n行m列的方格图，第i行第j列的坐标为(i,j)。其中一些坐标上有楼房，一些位置则为空。

这个区域内需要在(Xt,yt)这个坐标修一栋大楼，因此需要启用塔吊来完成这项建筑工作。但是塔吊不能安置在吊臂长度的范围内有其他楼房的位置。更准确地说，塔吊的吊管长度为R，设塔吊安装的坐标为(Xd,Yd)，楼房的坐标为(x,y)，那么所有楼房的坐标都必须满足|xd-x|+|yd-y|>R.

同时，塔吊吊臂必须能够到需要修大楼的位置，也就是|xd-xt|+|yd-yt|<=R。

你的任务是找出有多少个坐标可以安置这个塔吊。注意，你只能把塔吊安置在空地位置.

输入描述

第一行输入三个正整数n,m,R
接下来输入一个n行m列的字符矩阵，其中字符0表示这个地方为空地，1表示这个地方有一栋楼房，2表示需要修大楼的坐标，数据保证字符矩阵恰好有一个2.
对于100%的数据,1<=n,m,R<=400

输出描述

输出一个整数，表示能安置塔吊的坐标数量。

样例输入

4 5 2
01000
00010
00200
00001

样例输出

2

提示

可以放在(3,1)和(4,2)。

思路与代码

先维护出目标位置和每个有楼房的位置。然后枚举每个空地当做候选点，按照题意进行验证，满足要求则可以该位置安置塔吊，统计即可。

#include<iostream>
#include<vector>
using namespace std;
int n,m,r;
int a[555][555];
int tx, ty;
vector<pair<int, int> > vv;
int main()
{
    cin>>n>>m>>r;
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=m; j++) {
            scanf("%1d", &a[i][j]);
            if(a[i][j] == 2) tx = i, ty = j;
            if(a[i][j] == 1) vv.push_back(make_pair(i,j));
        }
    }
    int ans = 0;
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=m; j++) {
            if(a[i][j] != 0) continue;
            if(abs(i-tx) + abs(j-ty) > r) continue;
            int ok = 1;
            for(auto x : vv) {
                if(abs(x.first-i) + abs(x.second-j) <= r) {ok = 0;break;}
            }
            if(ok == 1) ans ++;
        }
    }
    cout << ans;
    return 0;
}#include<iostream>
#include<cstring>
using namespace std;
int n,m,a,b,c,d;
int dis[555][555];
int main()
{
    memset(dis,0x3f, sizeof dis);
    cin>>n>>m;
    cin>>a>>b>>c>>d;
    for(int u,v,x,i = 1; i<=m; i++) {
        cin>>u>>v>>x;
        dis[u][v] = min(dis[u][v], x);
        dis[v][u] = min(dis[v][u], x);
    }
    dis[c][d] = dis[d][c] = 0;
    for(int k = 1; k<=n; k++) {
       for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        }     
    }
    cout << dis[a][b];

    return 0;
}#include<bits/stdc++.h>
using namespace std;
using gg = long long;

int main() {
 gg n; cin >> n;
 vector<gg> arr(n);
 for(int i = 0; i < n; i++) cin >> arr[i];
 vector<gg> have(n+1, 0), ans(n + 1);
 gg now = 1;
 for(int i = 0; i < n; i++) {
  have[arr[i]]++;
  while(now <= n && have[now]) {
   ans[now] = i + 1;
   now++;
  }
 }
 cout << ans[1];
 for(int i = 2; i <= n; i++) cout << ' ' << ans[i];
 cout << '\n';
 return 0;
} 

第三题

时间限制: 2000MS内存限制: 65536KB

题目描述:

小明在玩一款全新的挂机游戏，小明有n个英雄，每天都在自动帮小明讨伐怪物获取赏金，渐渐地这些赏金无法满足小明的发展需求了，需要挑战更因难的关卡获得更多的赏金，小明要给这些英雄升级来满足更因难关卡的入门要求，而这个游戏的升级方式非常特别，唯一升级方式就是让玩家自己选择自己的两个英雄进行每日历练，如果这两个英雄等级相同，则不有任何事情发生。如果等级不同，等级高的那个英雄可以增加一级等级，而等级低的那个英维等级不会发生任何变化，小明想要挑战的下一个关卡需求至少一位英维等级达到2147483647级，小明想知道自己有多少个英雄有望达成这样的要求。

输入描述

第一行1个整数n，表示小明的英雄数量
第二行n个整数u1u2...un。表示小明英雄们的初始等级
对于100%的数据，1<=n<=50000，1<=ui<=100000

输出描述

输出一行，一个整数表示答案

样例输入

5
1 2 3 1 2

样例输出

3

思路与代码

由题意知，只要一个英雄可以被升级，那么就可以达到2147483647级。而只有最小等级的英雄不会被升级，其他等级的英雄都可以和最小等级的英雄一起历练从而升级。所以只需要统计有哪些英雄不是最小的等级的即可。

#include<iostream>

using namespace std;
int a[100005],n;
int mn = 1e9;
int main()
{
    cin>>n;
    for(int i = 1; i<=n; i++) {
        cin>>a[i];
        mn = min(a[i], mn);
    }
    int ans = n;
    for(int i = 1; i<=n; i++) {
        if(a[i] == mn) ans--;
    }
    cout << ans;
    return 0;
}