练习赛42

2024-03-27 18:15:16

练习赛42

Begin:
2019-03-30 18:35

PDD:275rlb

A

Blood Cousins CodeForces - 208E

题目大意：

​ 在一个森林中，如果两个节点a和b向上的第p个祖先相同，就称他们为p代表亲。(跟日常生活中有所不同，p不一定是他们的最近公共祖先)。给出一些询问，问v的p代表亲的数量。

思路：

首先注意题目，这道题是一个森林，而并非一棵树，所以要保存每棵树的根结点。

这道题需要把每个询问存在v的p代祖先上，而并非在v上。其他基本上就是dsu on tree 的模板。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int sz[N],dis[N],f[N][20];
int li[N],ri[N],tot,ID[N];
int cnt[N],ans[N];
bool no[N];
int n,m;
vector<int>e[N];
struct node{int id,d;};
vector<node>q[N];
void dfs(int x){
    sz[x]=1,li[x]=++tot,ID[tot]=x;
    for(int i=0;i<e[x].size();i++){
        int y=e[x][i];
        dis[y]=dis[x]+1;
        f[y][0]=x;
        dfs(y);
        sz[x]+=sz[y];
    }
    ri[x]=tot;
}
void add(int x){for(int i=li[x];i<=ri[x];i++)cnt[dis[ID[i]]]++;}
void del(int x){for(int i=li[x];i<=ri[x];i++)cnt[dis[ID[i]]]--;}
void solve(int x){
    int son=0;
    for(int i=0;i<e[x].size();i++)
        if(!son||sz[son]<sz[e[x][i]])son=e[x][i];//找重儿子
    for(int i=0;i<e[x].size();i++)
        if(e[x][i]!=son)solve(e[x][i]),del(e[x][i]);
    if(son)solve(son);
    for(int i=0;i<e[x].size();i++)
        if(e[x][i]!=son)add(e[x][i]);
    cnt[dis[x]]++;
    for(int i=0;i<q[x].size();i++)
        ans[q[x][i].id]=cnt[dis[x]+q[x][i].d]-1;//不包含自己要-1
}
int UP(int x,int p){
    for(int i=0;i<=17;i++)
        if(p&(1<<i))x=f[x][i];
    return x;
}
int main(){
    scanf("%d",&n);
    for(int i=1,p;i<=n;i++){
        scanf("%d",&p);
        if(p==0)no[i]=1;//是某棵树的根结点
        else e[p].push_back(i);
    }   
    for(int i=1;i<=n;i++)if(no[i])dfs(i);//把每棵树都扫一遍 
    for(int i=1;i<=17;i++)
        for(int j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1];
    scanf("%d",&m);
    for(int i=1,a,b;i<=m;i++){
        scanf("%d%d",&a,&b);
        int fa=UP(a,b);//a往上b个节点：a的b代“祖先”
        q[fa].push_back((node){i,b});//把询问存于祖先上
    }
    for(int i=1;i<=n;i++)
        if(no[i]){
        for(int j=0;j<=n;j++)cnt[j]=0;//注意每棵树都是独立的，最好初始化一下
        solve(i);
        }   
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}

B

Tree Intersection CSU - 1811

题目大意：

​ 给定一棵树，它有n-1条边。如果把第i条边删掉之后，会形成两个联通块。你需要回答有多少种颜色同时出现在这两个联通块中。

思路：

先吐槽一句CSU这个破玩意儿，竟然把WA判成输出超限，de了半天quq

还是树上启发式合并的模板，主要问题在于如何修改。

1.一种暴力的思路就是，把当前遍历到的节点的颜色到存于一个map中，然后每次询问是把这个map里的元素跟总的个数比较，再计算。这样每次询问都要O(N),亲测TLE。

2.那么我们不仅要累积颜色还要直接在修改过程中更改res。

我们注意到，每次新加入一个节点v时，设其颜色为co：

void add(int x){
step1 如果cnt[co]==0时，即当前集合中还没有这个颜色，那么res++;
step2 我们再把cnt[co]++;
step3 如果此时发现cnt[co]==all[co],即集合外没这种颜色了，那么res--.
}

每次从集合中删除一个节点v时，设其颜色为co:

void del(int x){
step1 如果cnt[co]==all[co],我们可以理解为，集合外会第一次加入这个要删除的元素所具有的颜色， 那么res++;
step2 cnt[co]--;
step3 如果此时cnt[co]==0 ,即集合中没有这个颜色了，那么res--.
}

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int all[N],ans[N],res,now[N];
map<int,int>query[N];
vector<int>e[N];
int a[N],li[N],ri[N],ID[N],tot,sz[N];
inline int read(){
    int x=0; char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
void dfs(int x,int fa){
    sz[x]=1,li[x]=++tot,ID[tot]=x;
    for(int i=0;i<e[x].size();i++){
        int y=e[x][i];
        if(y==fa)continue;
        dfs(y,x);
        sz[x]+=sz[y];
    }
    ri[x]=tot;
}
void add(int x){
    for(int i=li[x];i<=ri[x];i++){
        int p=ID[i];    
        if(now[a[p]]==0)res++;
        now[a[p]]++;
        if(now[a[p]]==all[a[p]])res--;
    }
}
void del(int x){
    for(int i=li[x];i<=ri[x];i++){
        int p=ID[i];
        if(now[a[p]]==all[a[p]])res++;
        now[a[p]]--;
        if(now[a[p]]==0)res--;
    }
}
void solve(int x,int fa){
    int son=0;
    for(int i=0;i<e[x].size();i++){
        if(e[x][i]==fa)continue;
        if(!son||sz[e[x][i]]>sz[son])son=e[x][i];
    }
    for(int i=0;i<e[x].size();i++){
        int y=e[x][i];
        if(y!=son&&y!=fa)solve(y,x),del(y);
    }
    if(son)solve(son,x);
    for(int i=0;i<e[x].size();i++){
        int y=e[x][i];
        if(y!=son&&y!=fa)add(y);
    }
    if(now[a[x]]==0)res++;
    now[a[x]]++;
    if(now[a[x]]==all[a[x]])res--;
    if(fa)ans[query[x][fa]]=res;
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        res=0,tot=0;
        for(int i=1;i<=n;i++)now[i]=all[i]=0,query[i].clear(),e[i].clear();
        for(int i=1;i<=n;i++)++all[a[i]=read()];
        for(int i=1,a,b;i<n;i++){
            a=read(),b=read();
            e[a].push_back(b);
            e[b].push_back(a);
            query[a][b]=query[b][a]=i;//注意，因为无法确定谁深度小       
        }
        dfs(1,0);
        solve(1,0); 
        for(int i=1;i<n;i++)printf("%d\n",ans[i]);
    }
}

C

Duff in the Army CodeForces - 587C

题目大意：

​ 有n个城市，由n-1条边连接。两个城市之间的道路是唯一的。
有m个人，住在这n个城市中，现在给出m个人，生活的城市编号。
你需要回答，从一个城市u到另一个城市v的路径中，编号前a小的人的编号是哪些？

思路：

用倍增的方法，把节点v到其所有祖先的路径上居民编号前10大的保存下来，(a<=10)这点很重要，所以每次只保留至多10个元素。路径的合并可以用归并排序解决，因为每段都是从小到大排的，是顺序的。另外注意一些细节.

ps:还有线段树写法。此题最好不用vector，不然跑的很慢,下面代码用了vector,跑的比较慢，但比较好打。

CODE：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1e5+5;
int f[N][20],dep[N];
typedef vector<int> ve;
vector<int> now;
vector<int> a[N][20],city[N],e[N];
vector<int> UP(ve x,ve y){//合并两段路径:归并排序
    int i=0,j=0;
    vector<int> res;
    res.clear();//尤其注意要初始化
    while(i<x.size()&&j<y.size()&&res.size()<10){
        if(x[i]<y[j])res.pb(x[i++]);
        else res.pb(y[j++]);
    }
    while(i<x.size()&&res.size()<10)res.pb(x[i++]);
    while(j<y.size()&&res.size()<10)res.pb(y[j++]);
    return res;
}
void dfs(int x,int fa,int d){
    dep[x]=d,f[x][0]=fa,f[x][1]=f[fa][0];
    //深度    f的意义跟其他题目没区别
    a[x][0]=city[x],a[x][1]=UP(city[x],city[fa]);
    /*a[x][0]=city[x]这里直接复制了city[x],至于前面为什么city不sort(city.begin(),city.end())也能过，我也不太清楚，按理来说如果一个城市有多个居民，应当先要sort一遍，以保证后面归并排序的正确性,可能数据原因吧
    */
    //a[x][0]存的单单是自己，a[x][i]存的是由自己到向上(2^i)-1个节点的路径
    //这与平常的倍增数组不太一样，因为此题还要考虑自己也算在集合中
    for(int i=0;i<e[x].size();i++){
        int y=e[x][i];
        if(y!=fa)dfs(y,x,d+1);
    }
}
void LCA(int u,int v){
//联通u到v路径,其实函数名叫LCA不太恰当，但统计路径的方法跟求LCA是一样的就这么叫着吧
    now.clear();//注意初始化
    if(dep[u]>dep[v])swap(u,v);
    int step=dep[v]-dep[u];
    for(int i=17;i>=0;i--)
        if(step&(1<<i))now=UP(now,a[v][i]),v=f[v][i];
    //与求LCA的步骤一样，先把u，v搞到同一深度去，但别忘了一边合并路径
    if(u==v){
        now=UP(now,a[u][0]);
        return;
    }/*这时候u,v都在一起了，但注意，根据a的定义，上面的累积，并没有考虑最后到的位置，即现在的u,v，所以还要算上自己,但由于u,v一毛一样，所以只累积一次。
    */
    for(int i=17;i>=0;i--){
        if(f[u][i]!=f[v][i]){
            now=UP(now,a[u][i]);
            now=UP(now,a[v][i]);
            u=f[u][i],v=f[v][i];
        }
    }
    now=UP(now,a[u][0]);
    now=UP(now,a[v][1]);
    /*
    注意一点，平时我们求LCA时，最后return的是 fa[u][0];
    也就是说现在这两点还没跳到lca上
    
    
    即此时他们而是分别是lca的两个直系儿子，(为什么呢：因为如果他们能跳到同一个节点上必然其中一个是另一个的祖先，而这种情况上面已经讨论过了)
    那么现在还要累计上lca,nowu,nowv,因为根据a的定义，上面的累积并没有考虑到这三点，所以都要加上，
    即加上a[u][0]+a[v][0]+a[lca][0]
    注意到，a[v][0]+a[lca][0]=a[v][1]
    所以我们直接UP(a[v][1])就好了。。
    */
}
int main(){
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        e[u].pb(v),e[v].pb(u);
    }
    for(int i=1,u;i<=m;i++){
        scanf("%d",&u);
        city[u].pb(i);
    }//i住在城市u
    dfs(1,0,1);
    for(int j=2;j<=17;j++)
    for(int i=1;i<=n;i++){
        f[i][j]=f[f[i][j-1]][j-1]; 
        a[i][j]=UP(a[i][j-1],a[f[i][j-1]][j-1]);
    }//倍增预处理，同时也把a数组处理了
    for(int i=1,u,v,p;i<=q;i++){
        scanf("%d%d%d",&u,&v,&p);
        LCA(u,v);//u到v的路径上求前p小的
        int len=now.size();
        p=min(p,len);
        printf("%d",p);
        for(int j=0;j<p;j++)printf(" %d",now[j]);puts("");
    }
}
上一篇：Codeforces 600E Lomsat gelral（dsu on tree树上启发式合并）


下一篇：每日一题，每日一练.1（压缩字符串）