10.13

Third_Mag · 2021-10-15 15:24:00 · 个人记录

10.13题解

1.打地鼠：

一道妥妥的水蓝，完全暴力加上一点一点优化就能够AC。我们可以发现在锤子规格，确定的情况下，怎么敲都是一样的，但决策不具备单调性且属于二维，二分不可行，那么就考虑去枚举锤子规格去更新答案。更新答案就直接用贪心解决。但关键在于枚举规格就已经是n^2级别了，求答案又是n^2枚举位置，再n^2锤，总计n^6肯定不行，我们加亿点小优化（雾）。

1.我们可以累加出总和，如果总和取模锤子面积不等于0那么就肯定没法，直接跳过。

其实加了第一个优化就已经能过了，但优化永远不嫌少。

2.可以从面积大的，如果某个面积大的可以满足，那么小的就没必要了。

3.可以用差分优化掉每次锤的时候的更新，优化掉一个n。

搞定。

2.消防：

本题要求我们选择一条路径，要其他每个点到这个这条路径上的距离最大值最小。本题最为困难的地方 在于确定路径位置，肯定不能够暴力处理出每条路径，在去求距离，有没有分都不清楚。那么我们先来感性感知一下，路径应该在哪个位置。猜测：直径之上。why?树上特殊的地方除了直径还有哪里啊。考树，要么考树剖，要么LCA，要么考树上DP，要么树上差分，要么就是树的直径。什么虚树啊什么的都很少考。那么我们现在来证明一下。说是要证明，但其实关键是不断利用直径是树上最长的一条路径这个性质，然后假设不在直径上的情况反证，因为要画图，本人对插入图片很头痛，所以就不在这里严谨证明了。

但是即使知道了这一点后，代码依然难以实现。我们先预处理出直径，然后用尺度法去直径上乱搞。但我们肯定不能尺度每找到一个区间就跑一次n的遍历更新答案。我们可以尝试分析树的性质，离当前最远的点要么在直径两端，要么在直径连得点的子树上，还有很多细节直接看代码吧，说不清楚。

#include<bits/stdc++.h>
using namespace std;
template<typename W>inline void rd(W &x){
    W ch=getchar(),tx=1;x=0;
    while(!isdigit(ch)) tx=ch=='-'?-1:tx,ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    x=tx*x;
}
const int N=300010;
int n,s,cnt,d[N];
int head[N],net[N<<1],to[N<<1],val[N<<1];
int deter[N],fa[N],x,y,m,f[N],ans,temp;
bool vis[N];

inline void add(int u,int v,int w){
    net[++cnt]=head[u],head[u]=cnt;
    to[cnt]=v,val[cnt]=w;
}

void Dfs(int x){
    for(int i=head[x];i;i=net[i]){
        if(to[i]!=fa[x]){
            fa[to[i]]=x;
            d[to[i]]=d[x]+val[i];
            Dfs(to[i]);
        }
    }
}

void treedp(int x){
    vis[x]=true;
    for(int i=head[x];i;i=net[i]){
        if(!vis[to[i]]){
            treedp(to[i]);
            f[x]=max(f[x],f[to[i]]+val[i]);
        }
    }
}

int main(){
    int u,v,w;
    rd(n),rd(s);
    for(int i=1;i<n;++i){
        rd(u),rd(v),rd(w);
        add(u,v,w),add(v,u,w);
    }
    Dfs(1);
    memset(fa,0,sizeof(fa));
    for(int i=1;i<=n;++i)
        if(d[i]>d[x]) x=i;
    d[x]=0;
    Dfs(x);
    for(int i=1;i<=n;++i)
        if(d[i]>d[y]) y=i;
    while(y!=x){
        vis[y]=true;
        deter[++m]=y;
        y=fa[y];
    }
    vis[x]=true;
    deter[++m]=x;
    for(int i=1;i<=m;++i) treedp(deter[i]);
    int j=m;
    ans=0x7fffffff;
    for(int i=1;i<=m;i++)temp=max(temp,f[deter[i]]);
    for(int i=m;i>=1;i--){
        while(j>=1&&d[deter[j]]-d[deter[i]]<=s)j--;
        ans=min(ans,max(temp,max(d[deter[i]],d[deter[1]]-d[deter[j+1]])));
    }
    printf("%d\n",ans);
}

3.染色：

关键在于线段树区间合并的时候要记上左区间的颜色与右区间的颜色，合并是方便计算答案。

#include<bits/stdc++.h>
#define lc (x<<1)
#define rc (x<<1|1)
using namespace std;
const int N=100009;
struct node{
    int l,r,lcol,rcol,sum,lz;
}tr[N<<2];
int n,m,tot,cnt,L,R;
int head[N],to[N<<1],nxt[N<<1];
int col[N];
int dep[N],siz[N],fa[N],son[N],top[N],seg[N],rev[N];
template<typename T>inline void read(T &a){
    T ch=getchar(),f=1;
    for(a=0;!isdigit(ch);ch=getchar()) f=ch=='-' ? -1 : f;
    for(;isdigit(ch);ch=getchar()) a=(a<<3)+(a<<1)+ch - '0';
    a *=f;
}
template<typename T>inline void print(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x / 10);
    putchar(x % 10+'0');
}
inline int add(int u,int v){
    to[++cnt]=v,nxt[cnt]=head[u],head[u]=cnt;
}
inline void dfs(int x,int f){
    dep[x]=dep[f]+1;
    siz[x]=1;
    fa[x]=f;
    for(int i=head[x];i;i=nxt[i]){
        int v=to[i];
        if(v==f) continue;
        if(!dep[v]){
            dfs(v,x);
            siz[x]+=siz[v];
            if(siz[v]>siz[son[x]])
                son[x]=v;
        }
    }
}
inline void dfs2(int x,int f){
    if(son[x]){
        seg[son[x]]=++tot;
        rev[tot]=son[x];
        top[son[x]]=top[x];
        dfs2(son[x],x);
    }
    for(int i=head[x];i;i=nxt[i]){
        int v=to[i];
        if(!top[v]){
            top[v]=v;
            seg[v]=++tot;
            rev[tot]=v;
            dfs2(v,x);
        }
    }
}
inline void build(int x,int l,int r){
    tr[x].l=l,tr[x].r=r;
    tr[x].lz=-1;
    if(l==r){
        tr[x].lcol=tr[x].rcol=col[rev[l]];
        tr[x].sum=1;
        return;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[x].sum=tr[lc].sum+tr[rc].sum;
    if(tr[lc].rcol==tr[rc].lcol) tr[x].sum--;
    tr[x].lcol=tr[lc].lcol;
    tr[x].rcol=tr[rc].rcol;
}
inline void pushdown(int x){
    if(tr[x].lz==-1)return;
    tr[lc].lz=tr[rc].lz=tr[x].lz;
    tr[lc].lcol=tr[lc].rcol=tr[x].lz;
    tr[rc].lcol=tr[rc].rcol=tr[x].lz;
    tr[lc].sum=tr[rc].sum=1;
    tr[x].lz=-1;
}
inline void update(int x,int l,int r,int val){
    if(tr[x].l>r || tr[x].r<l)  return;
    if(tr[x].l>=l && tr[x].r<=r){
        tr[x].lz=tr[x].lcol=tr[x].rcol=val;
        tr[x].sum=1;
        return;
    }
    pushdown(x);
    update(lc,l,r,val);
    update(rc,l,r,val);
    tr[x].sum=tr[lc].sum+tr[rc].sum;
    if(tr[lc].rcol==tr[rc].lcol) tr[x].sum--;
    tr[x].lcol=tr[lc].lcol;
    tr[x].rcol=tr[rc].rcol;
}
inline void change(int x,int y,int z){
    if(dep[x]<dep[y])swap(x,y);
    int fx=top[x],fy=top[y];
    while(fx !=fy){
        if(dep[fx]<dep[fy])
            swap(x,y),swap(fx,fy);
        update(1,seg[fx],seg[x],z);
        x=fa[top[x]],fx=top[x];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    update(1,seg[x],seg[y],z);
}
inline int query(int x,int l,int r){
    if(tr[x].l>r || tr[x].r<l) return 0;
    if(tr[x].l==l)
        L=tr[x].lcol;
    if(tr[x].r==r)
        R=tr[x].rcol;
    if(tr[x].l>=l && tr[x].r<=r) 
        return tr[x].sum;
    pushdown(x);
    int ans=query(lc,l,r)+query(rc,l,r);
    if(tr[lc].l>r || tr[lc].r<l || tr[rc].l>r || tr[rc].r<l) return ans;
    if(tr[lc].rcol==tr[rc].lcol) ans--;
    return ans;
}
inline int ask(int x,int y){
    int ans=0,lca,tmpx=x,tmpy=y,pre=-1;
    int fx=top[x],fy=top[y];
    while(fx!=fy){
        if(dep[fx]<dep[fy])
            swap(x,y),swap(fx,fy);
        x=fa[top[x]],fx=top[x];
    }
    lca=dep[x]>dep[y] ? y : x;
    x=tmpx,y=tmpy;
    while(top[x]!=top[lca]){
        ans+=query(1,seg[top[x]],seg[x]);
        if(R==pre) ans--;
        pre=L;
        x=fa[top[x]];
    }
    ans+=query(1,seg[lca],seg[x]);
    if(R==pre) ans--;
    pre=-1;
    while(top[y]!=top[lca]){
        ans+=query(1,seg[top[y]],seg[y]);
        if(R==pre) ans--;
        pre=L;
        y=fa[top[y]];
    }
    ans+=query(1,seg[lca],seg[y]);
    if(R==pre) ans--;
    return ans-1;
}
int a,b,c;
char opt[2];
int main(){
    read(n),read(m);
    for(int i=1;i<=n;i++) read(col[i]);
    for(int i=1;i<n;i++){
        read(a),read(b);
        add(a,b),add(b,a);
    }
    dfs(1,0);
    seg[1]=rev[1]=top[1]=tot=1;
    dfs2(1,0);
    build(1,1,n);
    while(m--){
        scanf("%s",opt);
        read(a),read(b);
        if(opt[0]=='C')
            read(c),change(a,b,c);
        else
            print(ask(a,b)),putchar('\n');
    }
    return 0;
}