2022牛客蔚来杯第三场A C J

2022牛客蔚来杯第三场A C J
2022牛客蔚来杯第三场
文章目录
- 2022牛客蔚来杯第三场
- C.Concatenation
  J.Journey
  A.Ancestor
C.Concatenation
- 题意
给n个字符串，最后拼接成一个字典序最小的大串
- 题解
  - 正解是Trie树，不会。
  - 题目其实可以转换成，哪个串放在前面是最优的，即存在可以比较出来的最优贡献顺序
  假设a串放在前面更优
  
  则有a+b
  a✖️26¹+b < b✖️26²+a (字符哈希思路，[a]代表a串的长度)
  
  化简得 a/(26³-1) < b/(26⁴-1)
  
  即每个串都可以通过自身的价值来判断是否更优，所以可以以此为排序式子排出最优的顺序，最后直接输出即可
- 代码
```
#include 
#include 
#include 

using namespace std;
const int N=2e6+10;

string s[N];
bool cmp(string &s1,string &s2) {
    return s1+s2>n;
    for(int i=0;i>s[i];
    sort(s,s+n,cmp);
    for(int i=0;i
```
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
J.Journey
- 题意
  - 给定n个十字路口，以及每个路口逆时针四个方向对着的路口是哪个
  - 在路口只有右转不需要等红灯，转向其他方向都需要等红灯
  - 给定起始边和终点边，问最少经历多少个红灯
- 题解
  - 抽象题目，可以发现是一个最短路问题
  - 建图，把每条路(cross_a,cross_b)视作点，而把每个十字路口看作边，等红灯看做边权为1，不等红灯看做边权为0
  - 如何确定边权是0还是1，即如何确定从某点（某条路）到下一个点（下一条路）是否为向右转。
    
    以0，1，2，3作为四个方向(逆时针数值增大)，当一条路(u,v)即u->v，想知道下一个点(下一条路)是不是右转，即到点(v,m)是否右转，我们只需要比对中心v指向u的方向和v指向m的方向，是不是可以逆时针可以u到达m。即v路口指向u的方向数值加一是不是v指向m方向。
  - 正权最短路，直接dijkstra就行
- 代码
```
#include 
#include 
#include 

using namespace std;
const int N=5e5+10;

int n,s1,s2,t1,t2;
int cross[N][4];
map st[N];
struct Node{
    int u,v,w;
    bool operator<(const Node &t) const{//优先队列排序和重载是反的，从小到大排序后优先选择边权小的走
        return w>t.w;
    }
};

int get_dir(int u,int v){//得到u->v这条路右转的方向是什么
    for(int i=0;i<4;i++)
        if(cross[v][i]==u)//找到v->u的方向再逆时针转动90度，即v->u方向数值+1
            return (i+1)%4;
    return -1;
}

int dijkstra() {
    priority_queue q;
    q.push({s1,s2,0});//起点
    
    while(q.size()) {
        auto [u,v,w]=q.top();
        q.pop();
        
        if(st[u][v]) continue;//如果走过就下一个点
        st[u][v]=1;//走过标记
        
        if(u==t1&&v==t2) return w;//到达终点输出距离
        
        int dir=get_dir(u,v);//得到下一个右转的方向数值
        for(int i=0;i<4;i++) {//扩展路线
            if(st[v][cross[v][i]]) continue;//如果下一个点已经走过，舍弃
            if(dir==i) q.push({v,cross[v][i],w});//右转，边权+0
            else q.push({v,cross[v][i],w+1});//非右转，边权+1
        }
    }
    return -1;//走不到终点
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=0;j<4;j++)
            cin>>cross[i][j];//第i个路口的j方向是哪个路口
    cin>>s1>>s2>>t1>>t2;
    cout<
```
- 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
A.Ancestor
- 题意
- 题解
  - lca板子题
- 代码
```
1
```
1. b ↩︎
2. a ↩︎
3. a ↩︎
4. b ↩︎

2022牛客蔚来杯第三场

文章目录

C.Concatenation

J.Journey

A.Ancestor