Shelter
0%

2022牛客多校训练营03

发表于 更新于
详细题解 我与队友一起在比赛 2022牛客多校训练营03 完成的题目

C-Concatenation

来源: 牛客多校训练营3 算法: 字符串 题目链接: https://ac.nowcoder.com/acm/contest/33188/C 补完: Yes 完成时间: August 25, 2022

题意

  • 给定\(n\)个五进制的数字
  • 将这\(n\)个数字串起来
  • 求串起来的数字字典序最小是多少？

解法

（按照赛时过的写法）凭运气过题

比较\(a+b\)和\(b+a\)的字典序大小，小的放前面

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
string a[2000010];
bool cmp(string c,string d){
	string ai=c+d,bi=d+c;
	return ai<bi;
}
int main(){
	std::ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n,cmp);
	for(int i=0;i<n;i++)cout<<a[i];
	return 0; 
}

J-Journey

来源: 牛客多校训练营3 算法: 图论, 最短路 题目链接: https://ac.nowcoder.com/acm/contest/33188/J 补完: Yes 完成时间: August 9, 2022

题解

得一个城市有若干十字路口, 每次进入一个十字路口, 右转出路口不需要等红灯, 左转/掉头/直行都要等红灯, 求从起点到终点最少要等几次红灯.

可以整理成以路为点, 以行驶方向为边, 等红灯为权建图, 以一个东西南北四向十字路口有例:

右转[0]: 南→东, 东→北, 北→西, 西→南.

左转[1]: 南→西, 东→南, 北→东, 西→北.

掉头[1]: 南→南, 东→东, 北→北, 西→西.

直行[1]: 南→北, 东→西, 北→南, 西→东.

建图跑最短路

题目给数据以十字路口标号\(c_{i,j}\),

表示从第\(i\)个路口出发的第\(j\)条路驶向第\(c_{i,j}\)个路口, 记为点\(c[i][j]\),

则若存在从第\(i\)个路口出发的第\(j_1\)条路\(u\)驶入路口\(k\), 则存在\(c[i][j_1]==k\),

同时对于此第\(k\)个个路口来说第\(j_2\)条路\(\overline u\)返回路口\(i\), 则存在\(c[k][j_2] ==i\),

确定\(i,k\)后可遍历四条边找到\(j_2\).

则若存在从第\(k\)个路口出发的第\(j_3\)条路\(v\)驶入路口\(l\), 则存在\(c[k][j_3] ==l\) ,

则有从第\(i\)个路口出发前往第\(l\)个路口的路在第\(k\)个路口经过了一次从\(j_2\)来, 往\(j_3\)去的一次转弯. 记为边\(<u,v>\)

题目给数据为逆时针出现路, 意为从第\(j\)条路驶入路口, 第\(j\%4+1\)条路驶出路口时为右转, 此时不用等红灯.

则若\(j_2\%4+1==j_3\), 此此转弯不用等红灯, 若\(j_2\%4+1!=j_3\),此次转弯要等红灯

代码

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
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 500005;

int c[MAXN][5];
int n, s1, s2, t1, t2;
map<int, bool> st[MAXN];

struct Node {
    int u;
    int v;
    int d;
    bool operator<(const Node &next) const {
        return d > next.d;
    }
};

int dijkstra(Node start) {
    priority_queue<Node> que;
    que.push(start);
    while (que.size()) {
        auto t = que.top();
        que.pop();
        if (st[t.u][t.v])continue;
        st[t.u][t.v] = true;
        if (t.u == t1 && t.v ==t2)return t.d;
        int from = 0;
        for (int j = 1; j <= 4; j++) {
            if (c[t.v][j] == t.u)
                from = j%4+1;
        }
        for (int j = 1; j <= 4; j++) {
            if (st[t.v][c[t.v][j]])continue;
            else que.push({t.v,c[t.v][j],t.d+(from != j)});
        }
    }
    return -1;
}

int main() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j<=4; j++) {
            cin>>c[i][j];
        }
    }
    cin>>s1>>s2>>t1>>t2;
    cout<<dijkstra({s1, s2, 0});
    return 0;
}