“蔚来杯“2022牛客暑期多校训练营3

C. Concatenation

给出一些由0,1,2,3,4组成的字符串，输出通过连接可以得到的最小的数。

思路：直接sort+卡常就可以过，注意sort自定义排序方式，返回a+b

AC Code：

#include 
 
const int N=2e6+5;
std::string s[N];
 
bool cmp(std::string &a,std::string &b){
	return a+b
}
 
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
	int n;
	std::cin>>n;
	for(int i=1;i<=n;++i)
	std::cin>>s[i];
	std::sort(s+1,s+n+1,cmp);
	for(int i=1;i<=n;++i)
	std::cout<
	return 0;
}

os：一开始看到了下面的提示，三个人想了半天O(n)的做法，结果最后还是sort+卡一些常过的，就离谱QWQ

A. Ancestor

给出两棵树和一个序列，问去掉序列中某一个剩下的所有点的LCA中，A大于B有多少。

思路：预处理关键点序列在树A和B上的前缀LCA和后缀LCA，枚举去掉的点计算剩余节点的LCA比较权值即可。

AC Code：

#include 
 
const int N=1e5+5;
int n,k,ans;
int t[N];
 
struct node{
    int f[17][N];
    int w[N],pre[N];
    int suf[N],dep[N];
    std::vector<int>vec[N];
    void dfs(int u){
        for(auto it:vec[u]){
            dep[it]=dep[u]+1;
            dfs(it);
        }
    }
    int lca(int x,int y){
        if(x==0||y==0) return x+y;
        if(dep[x]swap(x,y);
        for(int i=17-1;i>=0;i--){
            if(dep[x]-(1<=dep[y]) x=f[i][x];
        }
        if(x==y) return x;
        for(int i=17-1;i>=0;i--){
            if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
        }
        return f[0][x];
    }
    void init(){
        for(int i=1;i<=n;i++){
            std::cin>>w[i];
        }
        for(int i=2;i<=n;i++){
            int x; std::cin>>x;
            f[0][i]=x;
            vec[x].push_back(i);
        }
        dfs(1);
        for(int i=1;i<17;i++){
            for(int j=1;j<=n;j++){
                f[i][j]=f[i-1][f[i-1][j]];
            }
        }
        for(int i=1;i<=k;i++){
            pre[i]=lca(pre[i-1],t[i]);
        }
        for(int i=k;i>0;i--){
            suf[i]=lca(suf[i+1],t[i]);
        }
    }
    int query(int x){
        return w[lca(pre[x-1],suf[x+1])];
    }
}a,b;
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>n>>k;
    for(int i=1;i<=k;i++){
        std::cin>>t[i];
    }
    a.init(),b.init();
    for(int i=1;i<=k;i++){
        if(a.query(i)>b.query(i)) ans++;
    }
    std::cout<'\n';
    return 0;
}

os：我能说我LCA还没学么。。。

J. Jouney

给定一个城市中有多个十字路口，可以左转，右转，直行，掉头，右转不需要等红灯，问起点到终点所需要的最短时间。

思路：利用队列优化的Dijkstra，从起点到终点寻找红灯最少的路径，优先队列需要自定义红灯较少的排序方式。

AC Code：

#include 
 
const int N=5e5+5;
int t,n,m,s1,s2,t1,t2;
int cross[N][5];
std::map<int,bool>st[N];
 
struct node{
    int u,v,w;
    bool operator <(const node &a) const{
        return w>a.w;
    }
};
 
int getnext(int u,int v){
    for(int i=0;i<4;i++){
        if(cross[v][i]==u) return (i+1)%4;
    }
    return -1;
}
 
int Dijkstra(){
    std::priority_queuepq;
    pq.push({s1,s2,0});
    while(!pq.empty()){
        auto [u,v,w]=pq.top();
        pq.pop();
        if(st[u][v]) continue;
        st[u][v]=true;
        if(t1==u&&t2==v) return w;
        int next=getnext(u,v);
        for(int i=0;i<4;i++){
            if(st[v][cross[v][i]]) continue;
            if(i==next) pq.push({v,cross[v][i],w});
            else pq.push({v,cross[v][i],w+1});
        }
    }
    return -1;
}
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=0;j<4;j++){
            std::cin>>cross[i][j];
        }
    }
    std::cin>>s1>>s2>>t1>>t2;
    std::cout<<Dijkstra()<<'\n';
    return 0;
}

os：这个题看代码的话感觉还好，但是有一些细节需要处理，，问题是赛时签到的一题都搞了好久，我是什么菜比欸

其他的搞不定了。。。