For XeniaF

(☆▽☆)

8.12考试总结

published 2021-09-07 | category in 考试总结 | 19 minutes | 3733 words

考试总结。

watchdogwatchdog

给定一颗有 nn 个节点的树，有边权，求 ∑i=1n23333N−iAnsi\sum_{i=1}^n23333^{N-i}Ans_i。

具体的，对于每一个节点 ii ，有 li,ril_i,r_i 。求经过 ii 的、不经过 ii 的祖先的、路径条数在 lil_i 到 rir_i 之间的、路径、的长度、的最大值，记作 AnsiAns_i 。

对于 100%100\% 的数据,满足：N≤1000000N≤1000000 , 0≤ci≤1090≤c_i≤10^9 , 1≤li≤ri≤N−11≤l_i≤r_i≤N-1 。

10610^6 ，树上问题，o(nlogn)o(nlogn) 内解决，比较容易想到 dsu on tree。

考虑对于每一个点 xx ，只处理这个点的轻儿子，这就是 dsu on tree 的思想了。

更加具体点，维护一个线段树，下标 ii 所在位置的值表示在深度 ii 的位置的所有子结点中到 11 （ rootroot ）节点的最大值。值得注意的是，这个最大值一定是在当前处理的节点 xx 的子树内。至于为什么在递归完轻儿子之后要清空 dep[x]dep[x] 到 maxdep[x]maxdep[x] （子树内的最大深度）的值，因为要避免子树之间的互相影响，即 aa 儿子的子树的答案影响了 bb 儿子的子树的答案，其实他们是互不相关的。

for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==son[x])  continue;
        solve(to);
        t.clean(1,mx,1,dep[x],mdep[x]);
}
复制代码

处理完轻儿子之后，直接递归处理重儿子即可，此时不用再清零了，因为后面处理整个大子树是包含重儿子这一段的值的。

if(son[x])      solve(son[x]);
复制代码

更新 xx 节点本身所在 dep[x]dep[x] 的值

t.add(1,mx,1,dep[x],d[x]);
复制代码

重儿子的所有子树已经被记录在线段树里面了，直接查询计算即可。

至于为什么直接查询 depx+lxdep_x+l_x 到 depx+rxdep_x+r_x 中的最大值，因为此时计算的路径是以 xx 开头的路径。

if(son[x])
	ans[x]=d[x]+qy(1,mx,1,dep[x]+l[x],dep[x]+r[x]);
复制代码

将轻儿子的值依次加入线段树，并更新 xx 的答案。

for(register int i=hd[x];i;i=e[i].nx){
	ll to=e[i].to;
	if(to==son[x])  continue;
	search(to,x);
	rechange(to);
}
复制代码

这里的 searchsearch 为不断更新 ansxans_x 的答案，计算式是这样来的： depx∗2+lx−depch=depx+lx−(depch−depx)dep_x*2+l_x-dep_{ch} = dep_x+l_x-(dep_{ch}-dep_x) 。注意这里计算的是不以 xx 开头的路径。

每次在线段树中搜索这样一段长度，使得两个子树节点的深度加起来不超过特定的值。

inline void search(ll x,ll rt){
    ans[rt]=max(ans[rt],d[x]+qy(1,mx,1,dep[rt]*2+l[rt]-dep[x],dep[rt]*2+r[rt]-dep[x]));
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        search(to,rt);
    }
}
复制代码

rechangerechange ，更新线段树的值，在计算结果之后更新以避免出现同一个子儿子的子树下的节点互相计算的情况。

inline void rechange(ll x){
    t.add(1,mx,1,dep[x],d[x]);
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        rechange(to);
    }
}
复制代码

最后记得减去 lcalca ，即 xx。

for(register int i=1;i<=n;++i)
	if(ans[i]!=-1)
		ans[i]-=d[i]*2;
复制代码

下面来看看线段树的 lazytaglazytag ，这里是一个难点。

  • 如果 lazytag=1lazytag=1 ，说明这个点的值在本次更新的时候更新了，在 cleanclean 的时候要将最大值打回为 00
  • 如果 lazytag=0lazytag=0 ，说明这个点在本次并没有更新，不要改动
  • 如果此时的范围并不是完全在要 cleanclean 的范围内，标记下传
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define maxn 1000001
using namespace std;
ll n,l[maxn],r[maxn],u,v,w,d[maxn];
ll cnt,hd[maxn],dep[maxn],mdep[maxn],mx;
ll fa[maxn],son[maxn],siz[maxn];
ll lans,ans[maxn];
struct Node{
    ll nx,to,dis;
}e[maxn<<1];
struct Segment_tree{
    ll tree[maxn<<2],lazytag[maxn<<2];

    inline void pushup(ll f){
        tree[f]=max(tree[f<<1],tree[f<<1|1]);
    }

    inline void pushdown(ll f){
        if(!lazytag[f]) return;
        lazytag[f<<1]=lazytag[f<<1|1]=1;
        lazytag[f]=0;
        tree[f<<1]=tree[f<<1|1]=0;
    }

    inline void clean(ll l,ll r,ll f,ll cl,ll cr){
        if(lazytag[f]||cl<=l&&cr>=r){
            lazytag[f]=1;
            tree[f]=0;
            return;
        }
        ll mid=(l+r)>>1;
        if(cl<=mid)     clean(l,mid,f<<1,cl,cr);
        if(mid<cr)      clean(mid+1,r,f<<1|1,cl,cr);
        pushup(f);
    }

    inline void add(ll l,ll r,ll f,ll x,ll val){
        if(l==r){
            tree[f]=max(tree[f],val);
            return;
        }
        pushdown(f);
        ll mid=(l+r)>>1;
        if(x<=mid)      add(l,mid,f<<1,x,val);
        else            add(mid+1,r,f<<1|1,x,val);
        pushup(f);
    }

    inline ll query(ll l,ll r,ll f,ll cl,ll cr){
        if(cl<=l&&cr>=r)
            return tree[f];
        ll mid=(l+r)>>1;
        ll maxx=0;
        pushdown(f);
        if(cl<=mid)     maxx=max(maxx,query(l,mid,f<<1,cl,cr));
        if(mid<cr)      maxx=max(maxx,query(mid+1,r,f<<1|1,cl,cr));
        return maxx;
    }
}t;

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline void add(ll x,ll y,ll z){
    e[++cnt].to=y;
    e[cnt].dis=z;
    e[cnt].nx=hd[x];
    hd[x]=cnt;
}

inline void dfs1(ll x){
    dep[x]=dep[fa[x]]+1;
    mx=max(mx,dep[x]);
    mdep[x]=dep[x];
    siz[x]=1;
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==fa[x])   continue;
        fa[to]=x;
        d[to]=d[x]+e[i].dis;
        dfs1(to);
        siz[x]+=siz[to];
        
        mdep[x]=max(mdep[x],mdep[to]);
        if(siz[son[x]]<siz[to]||!son[x])
            son[x]=to;
    }
}

inline ll qy(ll l,ll r,ll f,ll cl,ll cr){
    if(cl>cr||cl>mx||cr<1)   return -1;
    else                     return t.query(l,r,f,max(1LL,cl),min(cr,mx));
}

inline void search(ll x,ll rt){
    ans[rt]=max(ans[rt],d[x]+qy(1,mx,1,dep[rt]*2+l[rt]-dep[x],dep[rt]*2+r[rt]-dep[x]));
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        search(to,rt);
    }
}

inline void rechange(ll x){
    t.add(1,mx,1,dep[x],d[x]);
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        rechange(to);
    }

}

inline void solve(ll x){
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==son[x])  continue;
        solve(to);
        t.clean(1,mx,1,dep[x],mdep[x]);
    }
    
    if(son[x])      solve(son[x]);
    t.add(1,mx,1,dep[x],d[x]);
    if(son[x])
        ans[x]=d[x]+qy(1,mx,1,dep[x]+l[x],dep[x]+r[x]);
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==son[x])  continue;
        search(to,x);
        rechange(to);
    }
}

inline ll qpow(ll a,ll b){
    ll base=1;
    while(b){
        if(b&1)     base*=a,base%=mod;
        a*=a,a%=mod;
        b>>=1;
    }
    return base;
}

int main(){
    memset(ans,-1,sizeof(ans));
    n=read();
    for(register int i=1;i<=n;++i)
        l[i]=read(),r[i]=read();
    for(register int i=2;i<=n;++i){
        u=read();v=i;
        w=read();
        add(u,v,w);
    }
    dep[1]=1;
    dfs1(1);
    solve(1);
    for(register int i=1;i<=n;++i)
        if(ans[i]!=-1)
            ans[i]-=d[i]*2;
    lans=0;
    for(register int i=1;i<=n;++i)
        lans+=ans[i]%mod*qpow(23333,n-i),lans%=mod;
    lans<0?lans=(lans+mod)%mod:lans%mod;
    printf("%lld\n",lans);
    return 0;
}
复制代码

bb

n∗mn*m 的格子，某些位置有障碍物，障碍物不能走。

选择一个位置放置第一枚棋，接下来由敌方先手，每次可以向周围四个方向移动一步，有障碍或走过的格子不能再走。

询问在哪些格子放第一枚棋子有必胜策略。

对于 100%100\% 的数据：1<=n,m<=1001<=n,m<=100。

100100 ，网格图，染色，二分图（网络流）。考虑黑白（奇偶）染色，黑向周围的白连边，跑二分图最大匹配。如果一个点在一次最大匹配中可以不出现，那这个点就一定有必胜策略。先跑一遍匈牙利算法，找到一种匹配，再尝试不断换匹配，如果可以成功换，就说明不一定要在最大匹配中出现。记录一下有几个这样的格子即可。

代码：

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000000
#define maxn 200*200
using namespace std;
ll n,m,ans,vit[maxn],s,t,d[maxn];
ll td[8][3]={{1,0},{0,1},{-1,0},{0,-1}};
ll cnt=1,hd[maxn],q[maxn],as[201][201];
ll mch[maxn],tot;
ll vis[maxn];
char a[101][101];
char cc;
struct Node{
    ll nx,to,dis;
}e[maxn<<1];

inline ll sm(ll x,ll y){
    return (x-1)*m+y;
}

inline void add(ll x,ll y,ll z){
    e[++cnt].to=y;
    e[cnt].nx=hd[x];
    e[cnt].dis=z;
    hd[x]=cnt;
}

inline int match(ll x){
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(vis[to]) continue;
        vis[to]=1;
        if(!mch[to]||match(mch[to])){
            mch[to]=x;
            return 1;
        }
    }
    return 0;
}

inline void dfss(ll x){
    ++tot;
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(!mch[to])    continue;
        if(!vit[mch[to]]){
            vit[mch[to]]=1;
            dfss(mch[to]);
        }
    }
}

int main(){
    cin>>n>>m;
    for(register int i=1;i<=n;++i)    cin>>a[i];
    for(register int i=1;i<=n;++i)
        for(register int j=0;j<m;++j)
            if((i+j+1)&1&&a[i][j]!='#')
                for(register int k=0;k<=3;++k){
                    ll dx=i+td[k][0];
                    ll dy=j+td[k][1];
                    if(dx>=1&&dx<=n&&dy+1>=1&&dy+1<=m&&a[dx][dy]!='#'){
                        add(sm(i,j+1),sm(dx,dy+1),1);
                        add(sm(dx,dy+1),sm(i,j+1),0);
                    }   
                }
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            if(a[i][j-1]!='#'&&(i+j)&1){
                memset(vis,0,sizeof(vis));
                match(sm(i,j));
            }
                
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            if(mch[sm(i,j)]&&a[i][j-1]!='#')
                mch[mch[sm(i,j)]]=sm(i,j);
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            if(a[i][j-1]!='#'&&!mch[sm(i,j)]){
                vit[sm(i,j)]=1;
                dfss(sm(i,j));
            }
    printf("%lld\n",tot);
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            if(vit[sm(i,j)]&&a[i][j-1]!='#')
                printf("%d %d\n",i,j);
    return 0;
}
复制代码

cc

求满足路径价值是 pp 的倍数的路径条数，路径均为简单路径。

点有点权，路径价值为路径上的点权和−- 路径上的点权最大值。

对于所有数据,n<=100000,P<=107,vi<=109n<=100000,P<=10^7,v_i<=10^9。

点分治板子题。代码有亿点点难写。处理也有亿点点麻烦。

首先是熟悉的 workwork 和熟悉的去重。

这里的去重还是值得讲一下的。先跳到 getdeepgetdeep 的 dd 数组，在循环中依然是要老老实实的统计，在循环之后就要去除本次循环的所有影响。理由还是很简单，防止干扰其他的子树。因此在每一次循环完之后，理论上 dd 数组是 00 的状态。不会少统计吗？不会，过 xx 节点的点在 getdeepgetdeep 里面全部已经被统计了。

回到去重的问题。

getdeepgetdeep 给出的范围确实很泛，整颗还没有被遍历的子树，也没有说互相影响的事情。对于一条链，maxmax 后面有可能确实被更新了，那么会出现在一条链上计算错误的情况。具体点，对于从 xx 出发的一条链上的两个点 uu 和 vv ，在计算 uu 的时候其实是无法判断他是否也和 vv 匹配了，而实际上这并不是一条合法的边。

于是就需要在计算完 xx 之后，再次计算各个子树。值得注意的是，因为循环的出现，子树与子树之间并不是互通的，uu 子树在 vv 子树前面，那么 vv 时 vit[u]vit[u] 已经为 11 了。对于单颗子树继续计算，但再计算的时候就要加上 val[x]val[x] 的值了，最大值也要和 val[x]val[x] 相关，相当于全真模拟前面那些不合法的边了。

图示参考这个博客，这里是原图链接。

inline void work(ll x){
    ans+=dfs1(x,val[x],0);
    vit[x]=1;
    for(register int i=hd[x];i;i=e[i].nx)
        if(!vit[e[i].to]){
            ans-=dfs1(e[i].to,val[x],val[x]); 
            sum=f[0]=siz[e[i].to];
            root=0;
            getroot(e[i].to,0);
            work(root); 
        }
}
复制代码

这道题的 dfs1dfs1 很奇怪。首先 getrootgetroot ，一定只能这样写，要不然会 WA 。具体原因暂不明。

inline void getdeep(ll x,ll fa,ll hmx,ll hsm){
    t[++tnw].mx=hmx;
    t[tnw].sm=hsm;
    for(register int i=hd[x];i;i=e[i].nx)
        if(e[i].to!=fa&&!vit[e[i].to])
            getdeep(e[i].to,x,max(hmx,val[e[i].to]),hsm+val[e[i].to]);
}
复制代码

排序的时候是按照 maxmax ，从小到大排的，方便更新。在每一次计算的时候，注意统计当前的最大值是什么。具体来说，在加入 tt 数组的时候先把 xx 作为最大值，在搜索的时候不断更新最大值，一定不要取模。 在计算的时候，直接用 tit_i 的 sum−maxsum-max 计算就好了。

inline ll dfs1(ll x,ll fm,ll pre){
    tnw=0;
    getdeep(x,0,max(val[x],pre),pre+val[x]);
    sort(t+1,t+tnw+1,cmp);
    ll nsm=0;
    for(register int i=1;i<=tnw;++i){
        nsm+=d[((t[i].sm-t[i].mx)%mod+mod)%mod];
        ++d[(mod-(t[i].sm-fm)%mod+mod)%mod];
    }
    for(register int i=1;i<=tnw;++i)
        --d[(mod-(t[i].sm-fm)%mod+mod)%mod];
    return nsm;
}
复制代码

总结

出现了以下错误：

AA

线段树永远都不记得开的四倍空间；

i=e[i].nxi=e[i].nx 和 to=e[i].toto=e[i].to ，不要打反；

线段树注意 pushdownpushdown；

区间询问 queryquery 记得判断 i<=ji<=j 和 i>=1i>=1 和 j<=nj<=n；

记得即使清空数组避免不必要的干扰！

BB

每一次匹配之后 visvis 数组记得清零；

网络流最大流可以比较方便的求出最大匹配的数量，但是不能记录每个点被匹配到了对面的那个点，在需要记录的题目中不适用；

数据范围在 100∗100100*100 以内考虑二分图网络流DP；

网格图黑白染色考虑二分图网络流DP。

CC

最大值在传递过程中不要取模；

取模公式一定是 (a%mod+mod)%mod(a\%mod+mod)\%mod ，不要直接 %\% ；

递归的时候记得考虑初始点是否被加入计算数组；

计算的时候记得计算在根节点会被算在子结点又会被算的重复部分；

数组不要开小了！ tt 数组看的不是数据的数量，而是数据的大小。

有以下失误：

时间安排过于不合理，在一道题上面耽误过多时间；

没有想清算法就盲目下笔，耽误大量时间；

打的时候不够细致，思考不够完善，导致了很多的 bugbug；

没有完整的浏览和思考整套试卷，出现了先做难题后做容易题的情况；

心态崩溃的过于快，没有调整好心态。

# 考试总结
LCT 上一篇
CF1530 部分考试记录 下一篇
浏览数 1765 次 | 访客数 1289 人
Powered by Gridea ©2019 | Theme By HsxyHao
Powered by ？
0%