2023百度之星 题目详解 公园+糖果促销

2023百度之星题目详解

前言

这里为大家带来最新的2023百度之星的题目详解，后续还会继续更新，喜欢的小伙伴可以点个关注啦！

公园问题

今天是六一节，小度去公园玩，公园一共 N 个景点，正巧看到朋友圈度度熊也在这个公园玩，于是他们约定好一块去景点 N。 小度当前所在景点编号为 T，从一个景点到附近的景点需要消耗的体力是 TE，而度度熊所在景点编号为 F ，移动消耗为FE。 好朋友在一块，赶路都会开心很多，所以如果小度和度度熊一块移动(即在相同位置向相同方向移动)，每一步他俩的总消耗将会减少 S。
求他俩到景点 N 时，所需要的总消耗最少是多少？
输入格式：
第一行三个数值，TE,FE,S 分别代表小度移动消耗值，度度熊移动消耗值，一起移动的消耗减少值。1<=TE,FE,S<=40000,S<=TE+FE.
第二行四个数值，T,F,N,M ，分别代表小度出发点，度度熊出发点，目标节点，总路径数。
接下来 M 行，每行两个整数 ,X,Y，代表连通的两个景点。1≤X,Y≤N。

输出格式：
一个整数，即总消耗最小值。如果不能到达
1≤TE,FE,S≤40000,S≤TE+FE；
输出格式：
一个整数，即总消耗最小值。如果不能到达 N ， 输出-1。
样例 1
输入：

4 4 3
1 2 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8
1
2
3
4
5
6
7
8
9
10

输出：

22
1

题目详解

分成3次bfs 运算，每次针对一个点，记得先从 N 点开始；
遍历3个点中间的所有点，找到距离总和最小的那个店

#include 

using namespace std;
const int N =4e4 + 7,M=2*N;
// int h[N],e[M],ne[M],idx;
int te,fe,s;
int t,f,n,m;
int distT[N],distF[N],distN[N];
int st[N];
vector<int> a[N]; 
void bfs(int start ,int times,int dist[]){
    queue<int> q;
    st[start]++;
    q.push(start);
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        for(auto & y:a[t]){
            if(st[y]==times) continue;
            dist[y]=dist[t]+1;
            st[y]++;
            q.push(y);
        }
    }
}

int main()
{
    cin>>te>>fe>>s;
    cin>>t>>f>>n>>m;
    // memset(dist,-1,sizeof dist);
    // memset(h,-1,sizeof h);
    while(m--){
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
        // add(a,b);
        // add(b,a);
    }
    bfs(n,1,distN);
    if(!st[t] || !st[f]){
        cout<<-1;
        return 0;
    }
    bfs(t,2,distT);
    bfs(f,3,distF);
    int ans=1e9;
    for(int i=1;i<=n;i++){
        if(st[i]){
            ans=min(ans,distT[i]*te+distF[i]*fe+distN[i]*(te+fe-s));
        }
    }
    cout<<ans<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

夏日漫步问题

问题详情

夏日夜晚，小度看着庭院中长长的走廊，萌发出想要在上面散步的欲望，小度注意到月光透过树荫落在地砖上，并且由于树荫的遮蔽度不通，所以月光的亮度不同，为了直观地看到每个格子的亮度，小度用了一些自然数来表示它们的亮度。亮度越高则数字越大，亮度相同的数字相同。

走廊是只有一行地砖的直走廊。上面一共有
n 个格子，每个格子都被小度给予了一个数字 a i​ 来表示它的亮度。
小度现在站在 1 号格子，想要去到 n 号格子。小度可以正向或反向移动到相邻的格子，每次需要花费 1 的体力。
同时小度还有瞬移的能力，其可以花费 1 的体力来瞬移到与当前格子亮度相同的格子上。而且由于小度视野有限，只能瞬移到在当前格子后的第一次亮度相同的格子上。这也意味着不能反向瞬移。
小度想知道，到达 n 号格子需要花费的最小体力是多少。以此制定一个最优秀的散步方案。

格式
输入格式：
第一行一个整数 n ，表示走廊上一共有 n 个格子。
第二行 n 个整数，为自然数 a i 表示第 i 号格子的亮度。

输出格式：
一行，一个整数cost表示花费的最小体力。
样例 1
输入：
6
0 1 2 3 1 5
输出：
3

题目详解

用pair存储输入的数据，按光照亮度进行排序，亮度相同的点就汇集到一起了，记得这个节点是单向的，没排序之前相邻的节点是双向的。
*

#include
#include
#include
#include
using namespace std;
const int N =2e5 + 7,M=3*N;
typedef pair<int,int> PII;
PII a[N];
bool st[N];
int dist[N],e[M],ne[M],h[N],idx,n;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int bfs(){
    memset(dist,-1,sizeof dist);
    dist[1]=0;
    queue<int> q;
    q.push(1);
    st[1]=true;
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(!st[j]){
                dist[j]=dist[t]+1;
                q.push(j);
                st[j]=true;

            }
        }
    }
    return dist[n];
}
int main(){
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        a[i]={x,i};
    }
    sort(a+1,a+n+1);
    // for(int i=1;i<=n;i++){
    //     cout<<a[i].first<<' '<<a[i].second<<endl;
    // }
    for(int i=1;i<n;i++){
        add(i,i+1);
        add(i+1,i);
    }
    for(int i=1;i<n;i++){
        if(a[i].first==a[i+1].first){
            add(a[i].second,a[i+1].second);
        }
    }
    cout<<bfs()<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59