2021暑期cf加训1

本文主要是介绍2021暑期cf加训1，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

比赛链接：https://codeforces.com/group/2g1PZcsgml/contest/337661

A，D，K，3/12，第11名，还好。

A他们挺快写出来了。D我感觉可以用上一场A一样的做法，成功。G用AC自动机把K过了；字符串的板子我还都老生疏了，真惭愧。其他题看来看去都没有成熟的思路，直到比赛结束。G最后十五分钟用分治猛改J题，可惜太匆忙，WA了；后来改改就A了。

话说那个教室空调好冷啊。

C：Cover the Paths

题意：

给定一颗树和树上的若干条路径（的两个端点），求最小的点集，使得每条路径至少有一个点在此点集中。\( 1 \leq n , m \leq 10^5 \) 。

分析：

树上的路径比较特殊，一般要关注LCA，这题也是。一个很好的发现是两条路径如果相交，那么较低路径上的LCA一定是交点之一。所以答案一定从LCA中选。就可以贪心，从低往高找LCA，用找到的LCA覆盖尽量多的路径。

但怎么实现还是个问题；这里可以用set，用法好妙啊。给每个点开一个set，一开始存的是以这个点为端点的路径的编号。然后dfs，把子节点的set启发式合并到父节点的set里；如果合并过程中发现有相同的元素，说明这个父节点是个LCA（两端点在此会师），那么答案++，set全清空，意思是这些路径都被覆盖了。可以想到，如果一条路径在其某一侧被覆盖了，两端点中那一侧的那个的set里一开始存的路径编号就被清空了，那么在LCA处也不会会师，也就不再算答案了。复杂度是 \( O(nlog^2(n)) \) 的。

代码如下：

#include<iostream>
#include<set>
using namespace std;
int const N=1e5+5;
int n,m,hd[N],to[N<<1],nxt[N<<1],cnt,id[N],ans;
bool is[N];
set<int>st[N];
int rd()
{
    int ret=0,f=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9')ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret*f;
}
void add(int x,int y){nxt[++cnt]=hd[x]; hd[x]=cnt; to[cnt]=y;}
int mer(int x,int y)
{
    if(st[x].size()<st[y].size())swap(x,y);
    for(int it:st[y])
    {
        if(st[x].find(it)!=st[x].end())return -1;
        st[x].insert(it);
    }
    return x;
}
void dfs(int u,int fa)
{
    if(is[u])ans++,st[id[u]].clear();//
    for(int i=hd[u],v;i;i=nxt[i])
    {
        if((v=to[i])==fa)continue;
        dfs(v,u);
        if(is[u]){st[v].clear(); continue;}//前面已经决定选u了
        int k=mer(id[u],id[v]);
        if(k==-1)st[id[u]].clear(),st[id[v]].clear(),is[u]=1,ans++;
        else id[u]=k;
    }
}
int main()
{
    n=rd();
    for(int i=1,x,y;i<n;i++)
        x=rd(),y=rd(),add(x,y),add(y,x);
    for(int i=1;i<=n;i++)id[i]=i;
    m=rd();
    for(int i=1,x,y;i<=m;i++)
    {
        x=rd(); y=rd();
        if(x==y)is[x]=1;
        else st[x].insert(i),st[y].insert(i);
    }
    dfs(1,0);
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
        if(is[i])printf("%d ",i);
    printf("\n");
    return 0;
}

L：Increasing Costs

题意：

给定一张图，可求1号点到每个点的最短路，问单独增大每条边，有多少点的最短路会受到影响？\( 2 \leq n \leq 2*10^5 , n-1 \leq m \leq 2*10^5 \) 。

分析：

支配树？

先dijkstra求出最短路；过程中每个点用vector存下相同的最短路，存最后那条边即可。然后这些最短路就形成了一个拓扑图。

这时我们需要从这个图中提取出一棵树，使得一条边下的子树的所有点都会被这条边影响。想想可以发现，对于一个点，所有最短路上的前一个点（下称前驱点）在图中的拓扑序比它靠前；如果我们按照拓扑序构造那棵树，那么那些前驱点会在当前点之前加入树中。而对于这个点，可以影响到它最短路的边就是这些路共有的部分，也就是树上LCA往上的部分。

所以我们找到所有前驱点在已有的树上的LCA，然后把当前点直接连在LCA下面，这个树就还满足我们的需求。

这样做完以后得到一棵树，然后dfs求子树大小就可以得到边影响的点数了。这还需要我们在造树的过程中时刻记录边的编号。

代码如下：

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#define ll long long
using namespace std;
int const N=2e5+5;
int n,m,hd[N],to[N<<1],fr[N<<1],nxt[N<<1],cnt=1;//cnt=1
int du[N],f[N][25],dep[N],tag[N],ans[N],siz[N];
ll D[N],w[N<<1];//ll!
bool vis[N];
vector<int>ve[N],E[N],tr[N];
struct Nd{
    ll dis,id;
    bool operator < (const Nd &a) const
    {return dis>a.dis;}
};
priority_queue<Nd>q;
queue<int>tq;
void add(int x,int y,int s){nxt[++cnt]=hd[x]; hd[x]=cnt; to[cnt]=y; fr[cnt]=x; w[cnt]=s;}
void dij()
{
    q.push((Nd){0,1});
    memset(D,0x3f3f,sizeof D); D[1]=0;
    while(q.size())
    {
        int u=q.top().id; q.pop();
        if(vis[u])continue; vis[u]=1;
        for(int i=hd[u],v;i;i=nxt[i])
        {
            if(vis[v=to[i]])continue;
            if(D[v]>D[u]+w[i])
            {
                ve[v].clear(); ve[v].push_back(i); du[v]=1;//ve:拓扑图上指来的边
                D[v]=D[u]+w[i];
                q.push((Nd){D[v],v});
            }
            else if(D[v]==D[u]+w[i])ve[v].push_back(i),du[v]++;
        }
    }
    for(int i=1;i<=n;i++)
        for(int it:ve[i])E[fr[it]].push_back(it);//E:拓扑图上指出的边
    //for(int i=1;i<=n;i++)printf("du[%d]=%d\n",i,du[i]);
}
int getlca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--)
        if(f[x][i]&&dep[f[x][i]]>=dep[y])x=f[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
void topo()
{
    tq.push(1);
    while(tq.size())
    {
        int u=tq.front(); tq.pop();
        for(int e:E[u])
        {
            int v=to[e]; du[v]--;
            //printf("%d-%d\n",u,v);
            if(!du[v])tq.push(v);
            else continue;
            if(ve[v].size()==1)
            {
                f[v][0]=u; dep[v]=dep[u]+1;
                tag[v]=e/2;//边的编号/2
                //printf("u=%d tag[%d]=%d\n",u,v,tag[v]);
                tr[u].push_back(v);//tr:最短路树上指向的点
            }
            else
            {
                int lca=fr[ve[v][0]],sz=ve[v].size();
                for(int i=1;i<sz;i++)
                    lca=getlca(lca,fr[ve[v][i]]);//所有最短路的lca
                f[v][0]=lca; dep[v]=dep[lca]+1;
                tr[lca].push_back(v);
            }
            for(int i=1;i<=20;i++)
                f[v][i]=f[f[v][i-1]][i-1];
        }
    }
}
void dfs(int u)
{
    siz[u]=1;
    for(int v:tr[u]){dfs(v); siz[u]+=siz[v];}
    if(tag[u])ans[tag[u]]=siz[u];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,s;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&s);
        add(x,y,s); add(y,x,s);
    }
    dij(); topo(); dfs(1);
    //for(int i=1;i<=n;i++)printf("tag[%d]=%d\n",i,tag[i]);
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

这篇关于2021暑期cf加训1的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！