2022.7.25 "蔚来杯"2022牛客暑期多校训练营3 赛后总结

比赛成绩

AC：5

RANK：85

试题订正

A.Ancestor

难度：easy

首先发现一个重要结论，当存在一对节点 $(x, y)$ 的最近公共祖先为 $k$ 个 $key\ number$ 所有节点的公共祖先时，只要 $x$ 和 $y$ 没有被删去，最近公共祖先就是固定的。

对于 $A$ ， $B$ 两棵树都可以找到这样的节点，最后对这四个点分别删除就好了。

时间复杂度： $O (n l o g n)$ 。

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
struct node
{
    vector<int>G[MAXN];
    int dep[MAXN],fa[MAXN][21];
    void dfs(int x,int father)
    {
        dep[x]=dep[father]+1;
        fa[x][0]=father;
        for(int i=1;i<=20;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
        int si=G[x].size();
        for(int i=0;i<si;++i)
        {
            int y=G[x][i];
            dfs(y,x);
        }
    }
    int lca(int x,int y)
    {
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=20;i>=0;--i)
            if(dep[fa[x][i]]>=dep[y])
                x=fa[x][i];
        if(x==y) return x;
        for(int i=20;i>=0;--i)
            if(fa[x][i]!=fa[y][i])
                x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
}A,B;
int a[MAXN],b[MAXN],num[MAXN],tmp[4];
int n,k;
bool del(int x)
{
    int fathera=-1;
    for(int i=1;i<=k;++i)
    {
        if(i==x) continue;
        if(fathera!=-1) fathera=A.lca(fathera,num[i]);
        else fathera=num[i];
    }
    int fatherb=-1;
    for(int i=1;i<=k;++i)
    {
        if(i==x) continue;
        if(fatherb!=-1) fatherb=B.lca(fatherb,num[i]);
        else fatherb=num[i];
    }
    return a[fathera]>b[fatherb];
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=k;++i) scanf("%d",&num[i]);
    int father;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=2;i<=n;++i) scanf("%d",&father),A.G[father].push_back(i);
    for(int i=1;i<=n;++i) scanf("%d",&b[i]);
    for(int i=2;i<=n;++i) scanf("%d",&father),B.G[father].push_back(i);
    A.dfs(1,0),B.dfs(1,0);
    int fathera=num[1],a1=1,a2;
    for(int i=2;i<=k;++i)
    {
        int f=A.lca(fathera,num[i]);
        if(f!=fathera)
        {
            a1=i;
            fathera=f;
        }
    }
    for(int i=1;i<=k;++i)
    {
        if(i==a1) continue;
        if(A.lca(a1,num[i])==fathera)
        {
            a2=i;
            break;
        }
    }
    int fatherb=num[1],b1=1,b2;
    for(int i=2;i<=k;++i)
    {
        int f=B.lca(fatherb,num[i]);
        if(f!=fatherb)
        {
            b1=i;
            fatherb=f;
        }
    }
    for(int i=1;i<=k;++i)
    {
        if(i==b1) continue;
        if(B.lca(b1,num[i])==fatherb)
        {
            b2=i;
            break;
        }
    }
    tmp[0]=a1,tmp[1]=a2,tmp[2]=b1,tmp[3]=b2;
    sort(tmp,tmp+4);
    int len=unique(tmp,tmp+4)-tmp;
    int ans=0;
    if(a[fathera]>b[fatherb]) ans+=k-len;
    for(int i=0;i<len;++i) ans+=del(tmp[i]);
    cout<<ans;
    return 0;
}

B.Boss

难度：hard

听了雨巨学姐的图论班后来补题了！！！

首先这题可以建出一个费用流模型，比较显然这里不赘述。

但这样肯定会超时，因为人太多了。

接着我们有这样一个思路：

$1$ .先把所有人放在城市 $1$ ,答案累加总费用。

$2$ .考虑城市 $2$ 时，从城市 $1$ 向城市 $2$ 连一条费用为 $\min{c[i][2]-c[i][1]}$ 。

$3$ .用spfa求最短路，顺便记录前驱，更新答案，模仿 EK 算法的 update 更新每个城市的人（注意更新后的人不仅要向其后所有点连还要向前面的点连，模仿网络流退流）。

代码实现：

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pa;
const int MAXN=1e5+5;
const int MAXK=11;
int a[MAXK],c[MAXN][MAXK];
priority_queue< pa,vector<pa>,greater<pa> >G[MAXK][MAXK];
long long dis[MAXK];
int pre[MAXK],pos[MAXK][MAXK],in[MAXN];
bool vis[MAXK];
long long ans=0;
int n,k;
void spfa(int s,int t)
{
    queue<int>q;
    memset(dis,0x3f,sizeof(dis));
    q.push(s),dis[s]=0,vis[s]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        vis[x]=0;
        for(int y=2;y<=t;++y)
        {
            if(x==y || G[x][y].empty()) continue;
            int z=G[x][y].top().first;
            if(dis[y]>dis[x]+z)
            {
                dis[y]=dis[x]+z,pre[y]=x;
                if(!vis[y]) q.push(y),vis[y]=0;
            }
        }
    }
}
void work(int t)
{
    for(int x=1;x<=t;++x)
        for(int y=1;y<=t;++y)
            while(!G[x][y].empty() && in[G[x][y].top().second]!=x)
                G[x][y].pop();
    spfa(1,t),ans+=dis[t];
    int x=t;
    while(x!=1)
    {
        int y=pre[x];
        in[G[y][x].top().second]=x;
        int tmp=G[y][x].top().second;
        for(int i=1;i<=t;++i) if(i!=x) G[x][i].push({c[tmp][i]-c[tmp][x],tmp});
        x=y;
    }
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=k;++i) scanf("%d",&a[i]);
    for(int i=1;i<=n;++i) for(int j=1;j<=k;++j) scanf("%d",&c[i][j]);
    for(int i=1;i<=n;++i) ans+=c[i][1],in[i]=1;
    for(int j=2;j<=k;++j)
    {
        for(int i=1;i<=n;++i) G[in[i]][j].push({c[i][j]-c[i][in[i]],i});
        for(int i=1;i<=a[j];++i) work(j);
    }
    cout<<ans;
    return 0;
}

C.Concatenation

难度：check-in

签到题，用sort排一下就好了，注意要关掉输入输出流。（最后加个换行就过了）

#include<bits/stdc++.h>
using namespace std;

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

D.Directed

难度：medium

E.Electrician

难度：hard

F.Fief

难度：medium

这个应该很容易想到缩点吧，不过是v-DCC而非e-DCC。

缩完点判强连通分量个数，若为 $1$ 则一定可以。

若大于 $1$ 则看是否为链，如果不为链则一定不可以。

若其为链，则必须两个城市分别为链的两端，且不能为割点。

#include<bits/stdc++.h>
using namespace std;
 
const int MAXN=1e5+5;
const int MAXM=2e5+5;
vector<int>DCC[MAXN];
struct EDGE
{
    int from,to,nxt;
}edge[MAXM*2];
stack<int>s;
int head[MAXN];
int dfn[MAXN],low[MAXN],dcc[MAXN],d[MAXN],siz[MAXN];
int new_id[MAXN];
bool visedge[MAXM*2],cut[MAXN],islink=0;
int tot=1,cnt=0,dccsum=0,root;
int n,m;
void add(int x,int y)
{
    edge[++tot].from=x,edge[tot].to=y,edge[tot].nxt=head[x],head[x]=tot;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++cnt;
    s.push(x);
    if(x==root && head[x]==0)
    {
        dcc[x]=++dccsum;
        ++siz[dccsum];
        DCC[dccsum].push_back(x);
        return;
    }
    int flag=0;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        if(visedge[i]) continue;
        visedge[i]=visedge[i^1]=1;
        int y=edge[i].to;
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x])
            {
                ++flag;
                if(x!=root || flag>1) cut[x]=1;
                ++dccsum;
                int tmp;
                do
                {
                    tmp=s.top(),s.pop();
                    dcc[tmp]=dccsum;
                    ++siz[dccsum];
                    DCC[dccsum].push_back(tmp);
                }while(tmp!=y);
                dcc[x]=dccsum;
                ++siz[dccsum];
                DCC[dccsum].push_back(x);
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
void prework()
{
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            root=i,tarjan(i);
    int oldsum=dccsum;
    for(int i=1;i<=n;++i)
        if(cut[i]) new_id[i]=++dccsum;
    for(int i=1;i<=oldsum;++i)
    {
        for(int j=0;j<DCC[i].size();++j)
        {
            int x=DCC[i][j];
            if(cut[x])
                ++d[i],++d[new_id[x]];
        }
    }
    int sum=0;
    for(int i=1;i<=dccsum;++i) sum+=(d[i]==1);
    if(sum==2) islink=1;
}
int main()
{
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&u,&v);
        add(u,v),add(v,u);
    }
    prework();
    int q;
    cin>>q;
    if(dccsum==1)
        for(int i=1;i<=q;++i) printf("YES\n");
    else if(!islink)
        for(int i=1;i<=q;++i) printf("NO\n");
    else
    {
        while(q--)
        {
            scanf("%d %d",&u,&v);
            if(dcc[u]==dcc[v]) printf("NO\n");
            else if((siz[dcc[u]]>1 && cut[u]) || (siz[dcc[v]]>1 && cut[v])) printf("NO\n");
            else if(d[dcc[u]]==1 && d[dcc[v]]==1) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

G.Geometry

难度：hard

H.Hacker

难度：medium

这道题正解是SAM，但乱搞能过是真的没想到。

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
const int INF=0x3f3f3f3f;
const int MAXN=1e5+10,P=131;
vector<int>v[5000010];
vector<int>g[200010][4];
char a[MAXN],b[MAXN];
int w[MAXN],n,m,k,sum[MAXN];
unsigned long long H[MAXN][2],pw[MAXN];
int num(int l,int r,int k)
{
    int ans=0;
    for(int i=l;i<=min(r,!k?n:m);++i) ans=ans*26+(k?b[i]:a[i])-'a';
    return ans;
}
unsigned long long ask(int l, int r, int op)
{
    return H[r][op]-H[l-1][op]*pw[r-l+1];
}
int solve(int i)
{
    int now=num(i,i+3,1);
    int len=v[now].size();
    if(i+3>m)
    {
        for(int j=3;j>=1;--j)
        {
            if(i+j-1>m) continue;
            int x=num(i,i+j-1,1);
            if(g[x][j].size()) return j;
        }
        return 0;
    }
    else if(!len)
    {
        for(int j=3;j>=1;--j){
            if(i+j-1>m) continue;
            int x=num(i,i+j-1,1);
            if(g[x][j].size()) return j;
        }
        return 0;
    }
    else
    {
        int ans=4;
        for(int p=0;p<len;++p)
        {
            int x=v[now][p];
            int i1=i+3,x1=x;
            while(a[x1]==b[i1] && i1<=m && x1<=n) ++i1,++x1;
            ans=max(ans,i1-i);
        }
        return ans;
    }
}
int get_max(int i, int j)
{
    if(i>j) return 0;
    int ans=0;
    int minx=sum[i-1];
    for(int r=i;r<=j;++r)
    {
        ans=max(ans,sum[r]-minx);
        minx=min(minx,sum[r]);
    }   
    return ans;
}
signed main()
{
    scanf("%lld %lld %lld",&n,&m,&k);
    for(int i=1;i<MAXN;++i) pw[i]=pw[i-1]*P;
    scanf("%s",a+1);
    for(int i=1;i<=n;++i) H[i][0]=H[i-1][0]*P+a[i];
    for(int i=1;i<=m;++i)
    {
        scanf("%lld",&w[i]);
        sum[i]=sum[i-1]+w[i];
    }
    for(int l=1;l+3<=n;++l)
    {
        int r=l+3,x=num(l,r,0);
        v[x].push_back(r);
    }
    for(int len=3;len>=1;--len)
    {
        for(int l=1;l+len-1<=n;++l)
        {
            int r=l+len-1,x=num(l,r,0);
            g[x][len].push_back(r);
        }
    }
    for(int t=1;t<=k;++t)
    {
        scanf("%s",b+1);
        for(int i=1;i<=m;++i) H[i][1]=H[i-1][1]*P+b[i];
        int ans=0;
        for(int i=1;i<=m;++i)
        {
            int len=solve(i);
            ans=max(ans,get_max(i,i+len-1));
            if(len) i=i+(len+1)/2-1;
        }
        printf("%lld\n", ans);
    }  
    return 0;
}

I.Ice Drinking

难度：hard

J.Journey

难度：easy

考虑对边构图，右转边权为 $0$ ，其余情况边权为 $1$ 。

然后跑dijkstra即可。

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pa;
const int MAXN=5e5+5;
vector<pa>G[MAXN<<2];
pa pos[MAXN<<2];
int c[MAXN][5],dis[MAXN<<2];
bool vis[MAXN<<2];
void dijkstra(int s,int t)
{
    priority_queue< pa,vector<pa>,greater<pa> >q;
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0,q.push({dis[s],s});
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        int si=G[x].size();
        for(int i=0;i<si;++i)
        {
            int y=G[x][i].first;
            int w=G[x][i].second;
            if(dis[y]>dis[x]+w)
            {
                dis[y]=dis[x]+w;
                if(y!=t) q.push({dis[y],y});
            }
        }
    }
}
int main()
{
    int n;
    cin>>n;
    int u,v,cnt=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=4;++j)
        {
            scanf("%d",&c[i][j]);
            if(c[i][j]) pos[++cnt]={c[i][j],i};
        }
    }
    sort(pos+1,pos+cnt+1);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=4;++j)
        {
            for(int k=1;k<=4;++k)
            {
                if(!c[i][j] || !c[i][k]) continue;
                int x=lower_bound(pos+1,pos+cnt+1,(pa){c[i][j],i})-pos,y=lower_bound(pos+1,pos+cnt+1,(pa){i,c[i][k]})-pos;
                G[x].push_back({y,k!=(j%4+1)});
            }
        }
    }
    pa a,b;
    scanf("%d %d %d %d",&a.first,&a.second,&b.first,&b.second);
    int s=lower_bound(pos+1,pos+cnt+1,a)-pos,t=lower_bound(pos+1,pos+cnt+1,b)-pos;
    dijkstra(s,t);
    if(dis[t]==0x3f3f3f3f) dis[t]=-1;
    cout<<dis[t];
    return 0;
}