标签：校国赛考后 int res void maxn siz 模拟 mod

7.14 冲刺国赛模拟 36

T1 染色题

关键性质是奇数偶数位上可以放置的只有两种，若 \(i\) 和 \(i-2\) 选的颜色不同，那么在 \(i\) 位置放一个球，\([l,r]\) 的限制等价于 \([l+2,r]\) 中奇数位和偶数位不同时有球。

设 \(f_i\) 为 \(i\) 放置一个球的合法方案数，这样直接枚举上一个球所在位置，注意到奇偶性相同的没有限制，不同的只能转移一个前缀，前缀和优化 DP。

点击查看代码

int n,m;
pii p[maxn];
int cnt=0;
int lpos[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
    int tag[maxn<<2];
    inline void push_down(int rt){
        if(tag[rt]){
            tag[rt<<1]=tag[rt],tag[rt<<1|1]=tag[rt];
            tag[rt]=0;
        }
    }
    void update(int rt,int l,int r,int pl,int pr,int k){
        if(pl<=l&&r<=pr) return tag[rt]=k,void();
        push_down(rt);
        if(pl<=mid) update(lson,pl,pr,k);
        if(pr>mid) update(rson,pl,pr,k);
    }
    void dfs(int rt,int l,int r){
        if(l==r) return lpos[l]=tag[rt]?tag[rt]:l,void();
        push_down(rt);
        dfs(lson),dfs(rson);
    }
#undef mid
#undef lson
#undef rson
}S;
int f[maxn];
int sum[maxn][2];

int main(){
    freopen("colour.in","r",stdin);
    freopen("colour.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;++i){
        int l=read()+2,r=read();
        if(l<r) p[++cnt]=make_pair(l,r);
    }
    sort(p+1,p+1+cnt,[&](pii A,pii B){
        return A.fir>B.fir;
    });
    for(int i=1;i<=cnt;++i){
        S.update(1,1,n,p[i].fir,p[i].sec,p[i].fir);
    }
    S.dfs(1,1,n);
    f[1]=4,sum[1][1]=4;
    for(int i=2;i<=n;++i){
        f[i]=(sum[i-2][i&1]+sum[lpos[i]-1][i&1^1])%mod;
        sum[i][i&1^1]=sum[i-1][i&1^1],sum[i][i&1]=(sum[i-1][i&1]+f[i])%mod;
    }
    printf("%d\n",(sum[n][0]+sum[n][1])%mod);
    return 0;
}

T2 石头剪刀布

朴素规则可以倍增处理某个类型胜出的概率，在此基础上研究。

\(l=r\) 的特殊性质也可以倍增处理，具体是合并时讨论 \(u\) 出现在哪一侧。

\(L=l,R=r\) 的特殊性质注意到这个合并是满足分配律的，也就是可以批量处理某个区间全部作为 \(u\) 和某个区间全部不作为 \(u\) 合并。

正解就呼之欲出了，类似线段树去求解，如果 \([l,r]\) 与一个子区间有交，那么递归求 \(u\) 在这个子区间的情况并与 \(u\) 不在另一子区间的情况合并。

点击查看代码

inline int q_pow(int A,int B,int P){
    int res=1;
    while(B){
        if(B&1) res=1ll*res*A%P;
        A=1ll*A*A%P;
        B>>=1;
    }
    return res;
}

int n,m;
char s[maxn];
struct Data{
    ll R,P,S;
    Data()=default;
    Data(ll R_,ll P_,ll S_):R(R_),P(P_),S(S_){}
    Data operator+(const Data &rhs)const{
        Data res;
        res.R=(R+rhs.R)%mod,res.P=(P+rhs.P)%mod,res.S=(S+rhs.S)%mod;
        return res;
    }
};
inline Data merge(Data A,Data B){
    Data res;
    res.R=(A.R*B.R%mod+(A.R*B.P%mod+A.P*B.R%mod)%mod*inv3%mod+(A.R*B.S%mod+A.S*B.R%mod)%mod*inv3*2%mod)%mod;
    res.P=(A.P*B.P%mod+(A.R*B.P%mod+A.P*B.R%mod)%mod*inv3*2%mod+(A.P*B.S%mod+A.S*B.P%mod)%mod*inv3%mod)%mod;
    res.S=(A.S*B.S%mod+(A.R*B.S%mod+A.S*B.R%mod)%mod*inv3%mod+(A.P*B.S%mod+A.S*B.P%mod)%mod*inv3*2%mod)%mod;
    return res;
}
Data f[maxn][19],g[maxn][19];
Data solve(int l,int r,int pl,int pr,int k){
    if(pl<=l&&r<=pr) return g[l][k];
    Data res=Data(0,0,0);
    if(pl<=l+(1<<k-1)-2) res=res+merge(solve(l,l+(1<<k-1)-2,pl,pr,k-1),f[r-(1<<k-1)+1][k-1]);    
    if(pr>=r-(1<<k-1)+2) res=res+merge(f[l][k-1],solve(r-(1<<k-1)+2,r,pl,pr,k-1)); 
    return res;
}

int main(){
    freopen("rps.in","r",stdin);
    freopen("rps.out","w",stdout);
    n=read(),m=read();
    scanf("%s",s+1);
    for(int i=1;i<=n;++i){
        if(s[i]=='R') f[i][0]=g[i][1]=Data(1,0,0);
        else if(s[i]=='P') f[i][0]=g[i][1]=Data(0,1,0);
        else f[i][0]=g[i][1]=Data(0,0,1);
    }
    for(int k=1;k<=18;++k){
        for(int i=1;i+(1<<k)-1<=n;++i){
            f[i][k]=merge(f[i][k-1],f[i+(1<<k-1)][k-1]);
        }
    }
    for(int k=2;k<=18;++k){
        for(int i=1;i+(1<<k)-2<=n;++i){
            g[i][k]=merge(g[i][k-1],f[i+(1<<k-1)-1][k-1])+merge(f[i][k-1],g[i+(1<<k-1)][k-1]);
        }
    }
    while(m--){
        int L=read(),R=read(),l=read(),r=read();
        Data ans=solve(L,R,l,r,__lg(R-L+2));
        printf("%lld\n",ans.R*q_pow((l-L)&1?(r-l+1)/2:(r-l+2)/2,mod-2,mod)%mod);
    }
    return 0;
}

T3 树状数组

两个关键性质：

低 \(p\) 位均为 \(0\) 的所有数在进行同样后缀的操作后低 \(p\) 位相同。
运算过程中，两个低 \(p\) 位均为 \(0\) 的时刻之间的 \(-1\) 操作不会影响到比 \(p\) 位更高的，也就是可以直接异或和。

考虑预处理 \(f_{p,i}\) 表示在 \(i\) 操作之后低 \(p\) 为均为 \(0\) 的数下一次低 \(p\) 为均为 \(0\) 的位置，\(g_{p,i,0/1}\) 表示在 \(i\) 操作之后低 \(p-1\) 位均为 \(0\) 且第 \(p\) 位为 \(0/1\) 的数下一次低 \(p\) 位均为 \(0\) 的位置。

预处理过程是倒序枚举，如果已经处理了 \(p-1\)，那么 \(p\) 的只需讨论当前操作并在 \(g_{p,f_{p-1,i},0/1}\) 转移过来。

之后预处理 \(ans_i\) 表示 \(i\) 位置输入 \(0\) 后进行操作最终的结果。这个过程找到最大的 \(p\) 使得 \(f_{p,i}\) 存在，那么 \(ans_{f_{p,i}+1}\) 与 \(ans_i\) 相比，低 \(p\) 位都相同，剩下的不会被 \(-1\) 影响，直接异或和。

最后求答案考虑依次消去 \(\mathrm{lowbit}\)，每次跳到 \(g_{p,i,1}\) 的位置，这个过程依旧是低位不变，高位异或和。最终到达的位置也是和 \(ans_i\) 处理即可。

点击查看代码

#define lowbit(x) (x&-x)

int n,m,k,A,B;
int a[maxn];
int xorsum[maxn];
int f[31][maxn],g[31][maxn][2];
int ans[maxn];
int lastans;

int main(){
    freopen("fenwick.in","r",stdin);
    freopen("fenwick.out","w",stdout);
    n=read(),m=read(),k=read(),A=read(),B=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        xorsum[i]=xorsum[i-1]^(a[i]==-1?0:a[i]);
    }
    f[0][n]=n+1,g[0][n][0]=n,g[0][n][1]=n+1,g[0][n+1][0]=n+1,g[0][n+1][1]=n+1;
    for(int i=n-1,last=(a[n]==-1||a[n]&1)?n:n+1;i>=0;--i){
        if(a[i+1]==-1||!(a[i+1]&1)) f[0][i]=i+1;
        else f[0][i]=g[0][i+1][1];
        g[0][i][0]=i,g[0][i][1]=last;
        if(a[i]==-1||a[i]&1) last=i;
    }
    for(int p=1;p<k;++p){
        f[p][n]=n+1,g[p][n][0]=n,g[p][n][1]=n+1,g[p][n+1][0]=n+1,g[p][n+1][1]=n+1;
        for(int i=n-1;i>=0;--i){
            if(a[i+1]==-1||lowbit(a[i+1])>(1<<p)) f[p][i]=i+1;
            else f[p][i]=g[p][f[p-1][i]][((xorsum[f[p-1][i]]^xorsum[i])>>p)&1];
            g[p][i][0]=i;
            if(a[i+1]==-1) g[p][i][1]=i+1;
            else g[p][i][1]=g[p][f[p-1][i]][((xorsum[f[p-1][i]]^xorsum[i])>>p)&1^1];
        }
    }
    for(int i=n;i>=1;--i){
        int high=-1;
        for(int p=k-1;p>=0;--p){
            if(f[p][i-1]!=n+1){
                high=p;
                break;
            }
        }
        if(high==-1) ans[i]=xorsum[n]^xorsum[i-1];
        else ans[i]=ans[f[high][i-1]+1]^(((xorsum[f[high][i-1]]^xorsum[i-1])>>high+1)<<high+1);
    }
    while(m--){
        int l=read(),x=read();
        l^=(1ll*A*lastans+B)%n,x^=(1ll*A*lastans+B)%(1<<k);
        --l;
        while(x){
            int low=__lg(lowbit(x));
            if(g[low][l][1]==n+1) break;
            x=((x>>low+1)<<low+1)^(((xorsum[g[low][l][1]]^xorsum[l])>>low+1)<<low+1);
            l=g[low][l][1];
        }
        if(!x) lastans=ans[l+1];
        else{
            int low=__lg(lowbit(x));
            lastans=(x>>low<<low)^ans[l+1];
        }
        printf("%d\n",lastans);
    }
    return 0;
}

7.17 冲刺国赛模拟 37

T1 数叶子

赛时写的式子三个求和号，只能 \(O(m\log m)\) 卷积，中间一个枚举选中的边数完全没必要啊！

注意到一个节点产生贡献就是只选一条边，就可以写出：

\[\sum_{l=1}^m(m-l+1)\sum_{i=1}^{n} deg_i\times l\times (m-l)^{\underline{deg_i-1}}\times (m-deg_i)^{\underline{n-1-deg_i}} \]

整理之后是：

\[\sum_{i=1}^n deg_i \times (m-deg_i)^{\underline{n-1-deg_i}} \sum_{l=1}^m l(m-l+1)^{\underline{deg_i}} \]

第二个求和号之前的预处理 \(n\) 次下降幂就能求了。观察后面是关于 \(m\) 的多项式，次数考虑差分后是 \(deg_i+1\) 次，因此是 \(deg_i+2\) 次多项式。

考虑拉插过程中，小于 \(deg_i\) 的下降幂都是 \(0\)，只有 \(deg_i,deg_i+1,deg_i+2\) 位置点值不为零，所以单次拉插复杂度 \(O(deg_i)\)，总复杂度就是 \(O(n)\)。

据说也有吸收的做法。

点击查看代码

inline int q_pow(int A,int B,int P){
    int res=1;
    while(B){
        if(B&1) res=1ll*res*A%P;
        A=1ll*A*A%P;
        B>>=1;
    }    
    return res;
}

int n,m;
int deg[maxn],cnt[maxn];
int fact[maxn<<1],inv_fact[maxn<<1];
int prod[maxn<<1],inv_prod[maxn<<1];

int Y[maxn],pre[maxn],suf[maxn];
inline int Lagrange(int D,int X){
    for(int i=0;i<D;++i) Y[i]=0;
    Y[D]=fact[D],Y[D+1]=(fact[D+1]+2ll*fact[D]%mod)%mod,Y[D+2]=((1ll*fact[D+2]*inv_fact[2]%mod+2ll*fact[D+1])%mod+3ll*fact[D]%mod)%mod;
    pre[0]=1,suf[D+2]=1;
    for(int i=1;i<=D+2;++i) pre[i]=1ll*pre[i-1]*(X-(i-1)+mod)%mod;
    for(int i=D+1;i>=0;--i) suf[i]=1ll*suf[i+1]*(X-(i+1)+mod)%mod;
    int res=0;
    for(int i=0;i<=D+2;++i){
        int now=1ll*Y[i]*pre[i]%mod*suf[i]%mod*inv_fact[i]%mod*inv_fact[D+2-i]%mod;
        if((D+2-i)&1) res=(res-now+mod)%mod;
        else res=(res+now)%mod;
    }
    return res;
}

int ans;

int main(){
    freopen("leaf.in","r",stdin);
    freopen("leaf.out","w",stdout);
    n=read(),m=read();
    for(int i=1,u,v;i<n;++i){
        u=read(),v=read();
        ++deg[u],++deg[v];
    }
    for(int i=1;i<=n;++i) ++cnt[deg[i]];
    fact[0]=1,inv_fact[0]=1;
    for(int i=1;i<=n+2;++i) fact[i]=1ll*fact[i-1]*i%mod;
    inv_fact[n+2]=q_pow(fact[n+2],mod-2,mod);
    for(int i=n+1;i>=1;--i) inv_fact[i]=1ll*inv_fact[i+1]*(i+1)%mod;
    prod[0]=1,inv_prod[0]=1;
    for(int i=1;i<n;++i) prod[i]=1ll*prod[i-1]*(m-i+1)%mod;
    inv_prod[n-1]=q_pow(prod[n-1],mod-2,mod);
    for(int i=n-2;i>=1;--i) inv_prod[i]=1ll*inv_prod[i+1]*(m-i)%mod;
    for(int i=1;i<n;++i){
        if(!cnt[i]) continue;
        int now=1ll*cnt[i]*i%mod*prod[n-1]%mod*inv_prod[i]%mod;
        now=1ll*now*Lagrange(i,m)%mod;
        ans=(ans+now)%mod;
    }
    printf("%d\n",ans);
    return 0;
}

T3 数论

莫比乌斯反演之后得到：

\[\sum_{T=1}^{n}\sum_{k\mid t}\mu\left(\dfrac{T}{k}\right)\dfrac{k}{\varphi(k)}\sum_{i=1}^{\left\lfloor n/T\right\rfloor}\sum_{j=1}^{\left\lfloor n/T\right\rfloor}\varphi(iT)\varphi(jT)\mathrm{dist}^k(iT,jT) \]

前面可以直接 \(O(n\log n)\) 卷出来，但是后面带着距离不好求。

枚举 \(T\)，对倍数建虚树，总点数是 \(O(n\log n)\)。

考虑斯特林数把普通幂转成组合数得到（\(\mathrm{dist}(iT,jT)\) 简写成 \(d\)）：

\[d^k=\sum_{i=0}^k\dbinom{d}{i}\sum_{j=0}^i(-1)^{i-j}\dbinom{i}{j}j^k \]

之后 \(\varphi(i)\varphi(j)d^k\) 就可以写进去变成求 \(\sum \varphi(i)\varphi(j)\dbinom{d}{k}\)，后面的预处理出来就行。这个过程可以树上 DP，维护到根路径上选 \(k\) 条边的方案数成点权之和，转移类似背包。复杂度是 \(O(n\log^2 n+nk^2\log n)\)。

点击查看代码

inline int q_pow(int A,int B,int P){
    int res=1;
    while(B){
        if(B&1) res=1ll*res*A%P;
        A=1ll*A*A%P;
        B>>=1;
    }
    return res;
}
int pr[maxn],phi[maxn],mu[maxn];
bool vis[maxn];
int inv[maxn];
int fact[maxn],inv_fact[maxn],pw[11][11];
inline void linear_sieve(){
    phi[1]=1,mu[1]=1;
    for(int i=2;i<=lim;++i){
        if(!vis[i]) pr[++pr[0]]=i,phi[i]=i-1,mu[i]=-1;
        for(int j=1;i*pr[j]<=lim&&j<=pr[0];++j){
            vis[i*pr[j]]=1;
            phi[i*pr[j]]=phi[i]*phi[pr[j]],mu[i*pr[j]]=-mu[i];
            if(i%pr[j]==0){
                phi[i*pr[j]]=phi[i]*pr[j],mu[i*pr[j]]=0;
                break;
            }
        }
    }
    inv[1]=1;
    for(int i=2;i<=lim;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    fact[0]=1,inv_fact[0]=1;
    for(int i=1;i<=lim;++i) fact[i]=1ll*fact[i-1]*i%mod;
    inv_fact[lim]=q_pow(fact[lim],mod-2,mod);
    for(int i=lim-1;i>=1;--i) inv_fact[i]=1ll*inv_fact[i+1]*(i+1)%mod;
    for(int i=0;i<=10;++i){
        pw[i][0]=1;
        for(int j=1;j<=10;++j){
            pw[i][j]=1ll*pw[i][j-1]*i%mod;
        }
    }
}
inline int C(int N,int M){
    if(N<M) return 0;
    return 1ll*fact[N]*inv_fact[M]%mod*inv_fact[N-M]%mod;
}

int n,K;
vector<int> E[maxn];
struct edge{
    int to,nxt,w;
}e[maxn];
int head[maxn],cnt;
inline void add_edge(int u,int v,int w){
    e[++cnt].to=v,e[cnt].nxt=head[u],e[cnt].w=w,head[u]=cnt;
}
int fa[maxn],dep[maxn],siz[maxn],son[maxn];
int top[maxn],dfn[maxn],dfncnt;
void dfs1(int u,int f,int d){
    fa[u]=f,dep[u]=d,siz[u]=1;
    int maxson=-1;
    for(int v:E[u]){
        if(v==f) continue;
        dfs1(v,u,d+1);
        siz[u]+=siz[v];
        if(siz[v]>maxson) maxson=siz[v],son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t,dfn[u]=++dfncnt;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(int v:E[u]){
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
inline int get_LCA(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]]) swap(u,v);
        v=fa[top[v]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    return u;
}

int rt,id[maxn];
int st[maxn],tp;
inline void build(){
    sort(id+1,id+id[0]+1,[&](int A,int B){
        return dfn[A]<dfn[B];
    });
    rt=id[1];
    for(int i=2;i<=id[0];++i) rt=get_LCA(rt,id[i]);
    tp=0,cnt=0;
    head[rt]=0,st[++tp]=rt;
    if(rt!=id[1]) head[id[1]]=0,st[++tp]=id[1];
    for(int i=2;i<=id[0];++i){
        int u=id[i],lca=get_LCA(st[tp],u);
        if(lca==st[tp]){
            head[u]=0,st[++tp]=u;
            continue;
        }
        while(tp>1&&dep[get_LCA(st[tp],u)]<dep[st[tp-1]]){
            add_edge(st[tp-1],st[tp],dep[st[tp]]-dep[st[tp-1]]);
            --tp;
        }
        lca=get_LCA(st[tp],u);
        if(lca==st[tp-1]){
            add_edge(st[tp-1],st[tp],dep[st[tp]]-dep[st[tp-1]]);
            head[u]=0,st[tp]=u;
        }
        else{
            head[lca]=0;
            add_edge(lca,st[tp],dep[st[tp]]-dep[lca]);
            st[tp]=lca;
            head[u]=0,st[++tp]=u;
        }
    }
    for(int i=tp;i>1;--i) add_edge(st[i-1],st[i],dep[st[i]]-dep[st[i-1]]); 
}
int res[11];
int sumC[maxn][11],tmp[11];
inline void dfs3(int u,int D){
    for(int j=0;j<=K;++j) sumC[u][j]=0;
    sumC[u][0]=(u%D)?0:phi[u];
    res[0]=(res[0]+((u%D)?0:1ll*phi[u]*phi[u]%mod))%mod;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].w;
        dfs3(v,D);
        for(int j=0;j<=K;++j) tmp[j]=0;
        for(int j=0;j<=w;++j){
            for(int k=0;k+j<=K;++k){
                tmp[j+k]=(tmp[j+k]+1ll*C(w,j)*sumC[v][k]%mod)%mod;
            }
        }
        for(int j=0;j<=K;++j){
            for(int k=0;k<=j;++k){
                res[j]=(res[j]+2ll*sumC[u][k]*tmp[j-k]%mod)%mod;
            }
        }
        for(int j=0;j<=K;++j) sumC[u][j]=(sumC[u][j]+tmp[j])%mod;
    }
}

int f[maxn],g[11][11],ans[11];

int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    linear_sieve();
    n=read(),K=read();
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        E[u].push_back(v),E[v].push_back(u);
    }
    for(int i=1;i<=n;++i){
        for(int j=1;i*j<=n;++j){
            f[i*j]=(f[i*j]+1ll*(mu[i]+mod)%mod*j%mod*inv[phi[j]]%mod)%mod;
        };
    }
    dfs1(1,0,0);
    dfs2(1,1);
    for(int k=0;k<=K;++k){
        for(int i=0;i<=k;++i){
            for(int j=0;j<=i;++j){
                int now=1ll*C(i,j)*pw[j][k]%mod;
                if((i-j)&1) g[k][i]=(g[k][i]-now+mod)%mod;
                else g[k][i]=(g[k][i]+now)%mod;
            }
        }
    }
    for(int i=1;i<=n;++i){
        id[0]=0;
        for(int j=1;i*j<=n;++j) id[++id[0]]=i*j;
        build();
        for(int j=0;j<=K;++j) res[j]=0;
        dfs3(rt,i);
        for(int k=0;k<=K;++k){
            for(int j=0;j<=k;++j){
                ans[k]=(ans[k]+1ll*f[i]*res[j]%mod*g[k][j]%mod)%mod;
            }
        }
    }
    for(int k=0;k<=K;++k) printf("%d\n",ans[k]);
    return 0;
}

7.18 冲刺国赛模拟 38

T1 智力游戏

普及 BFS。

点击查看代码

int n;
char dr[4]={'L','R','U','D'};
struct opt{
    int id,d,k;
    opt()=default;
    opt(int id_,int d_,int k_):id(id_),d(d_),k(k_){}
};
struct node{
    int mp[7][7];
    vector<opt> O;
}S;
inline puu get_h(node u){
    ull h1=0,h2=0;
    for(int i=1;i<=6;++i){
        for(int j=1;j<=6;++j){
            h1=h1*base1+u.mp[i][j];
            h2=h2*base2+u.mp[i][j];
        }
    }
    return make_pair(h1,h2);
}
map<puu,int> MP;
queue<node> q;
bool vis[40];

int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    for(int i=1;i<=6;++i){
        for(int j=1;j<=6;++j){
            S.mp[i][j]=read();
            n=max(n,S.mp[i][j]);
        }
    } 
    q.push(S);
    while(!q.empty()){
        node now=q.front();
        q.pop();
        if(now.mp[3][6]==1){
            printf("%ld\n",now.O.size());
            for(opt i:now.O){
                printf("%d %c %d\n",i.id,dr[i.d],i.k);
            }
            break;
        }
        for(int i=1;i<=n;++i) vis[i]=0;
        for(int i=1;i<=6;++i){
            for(int j=1;j<=6;++j){
                if(!now.mp[i][j]||vis[now.mp[i][j]]) continue;
                vis[now.mp[i][j]]=1;
                if(now.mp[i][j+1]==now.mp[i][j]){
                    int len=1;
                    while(len<=6&&now.mp[i][j+len]==now.mp[i][j]) ++len;
                    for(int k=1;k<=6;++k){
                        if(j-k>=1&&!now.mp[i][j-k]){
                            node nxt=now;
                            for(int p=j;p<j+len;++p) nxt.mp[i][p]=0;
                            for(int p=j-k;p<j+len-k;++p) nxt.mp[i][p]=now.mp[i][j];
                            puu h=get_h(nxt);
                            if(!MP.count(h)){
                                MP[h]=1;
                                nxt.O.push_back(opt(now.mp[i][j],0,k));
                                q.push(nxt);
                            } 
                        }
                        else break;
                    }
                    for(int k=1;k<=6;++k){
                        if(j+len-1+k<=6&&!now.mp[i][j+len-1+k]){
                            node nxt=now;
                            for(int p=j;p<j+len;++p) nxt.mp[i][p]=0;
                            for(int p=j+k;p<j+len+k;++p) nxt.mp[i][p]=now.mp[i][j];
                            puu h=get_h(nxt);
                            if(!MP.count(h)){
                                MP[h]=1;
                                nxt.O.push_back(opt(now.mp[i][j],1,k));
                                q.push(nxt);
                            } 
                        }
                        else break;
                    }
                }
                else{
                    int len=1;
                    while(len<=6&&now.mp[i+len][j]==now.mp[i][j]) ++len;
                    for(int k=1;k<=6;++k){
                        if(i-k>=1&&!now.mp[i-k][j]){
                            node nxt=now;
                            for(int p=i;p<i+len;++p) nxt.mp[p][j]=0;
                            for(int p=i-k;p<i+len-k;++p) nxt.mp[p][j]=now.mp[i][j];
                            puu h=get_h(nxt);
                            if(!MP.count(h)){
                                MP[h]=1;
                                nxt.O.push_back(opt(now.mp[i][j],2,k));
                                q.push(nxt);
                            } 
                        }
                        else break;
                    }
                    for(int k=1;k<=6;++k){
                        if(i+len-1+k<=6&&!now.mp[i+len-1+k][j]){
                            node nxt=now;
                            for(int p=i;p<i+len;++p) nxt.mp[p][j]=0;
                            for(int p=i+k;p<i+len+k;++p) nxt.mp[p][j]=now.mp[i][j];
                            puu h=get_h(nxt);
                            if(!MP.count(h)){
                                MP[h]=1;
                                nxt.O.push_back(opt(now.mp[i][j],3,k));
                                q.push(nxt);
                            } 
                        }
                        else break;
                    }
                }
            }
        }
    }
    return 0;
}

T2 区域划分

构造题，先特判掉一定不合法的情况。

用 \(0\) 分割成若干段，每段都是 \(12\) 相间，最终状态是形如 \(0121212121\)，那么就与间隔为 \(1\) 的位置连边依次删去。

如果 \(0\) 两侧不相同，就可以左右连边直接删。

反之形如 \(1202\)，可以先与 \(1\) 连边删去 \(2\)，之后左右连边删去 \(0\)。

注意到可能存在 \(01010101010\) 的连续段，这个不会影响到，因为开头必定存在上面的形式来依次删每个 \(0\)。（但是如果是删右侧的就不对了，原因是枚举顺序相反）

用链表维护。

点击查看代码

int n;
int a[maxn];
int pre[maxn],nxt[maxn];
int cnt[3];

inline void erase(int x){
    pre[nxt[x]]=pre[x],nxt[pre[x]]=nxt[x];
}

int main(){
    freopen("divide.in","r",stdin);
    freopen("divide.out","w",stdout);
    n=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        ++cnt[a[i]];
        pre[i]=i-1,nxt[i]=i+1;
        if(i>1&&a[i-1]==a[i]) return printf("No\n"),0;
    } 
    pre[1]=n,nxt[n]=1;
    if(a[1]==a[n]) return printf("No\n"),0;
    if(!cnt[0]||!cnt[1]||!cnt[2]) return printf("No\n"),0;
    printf("Yes\n");
    for(int i=1;i<=n;++i){
        if(a[i]) continue;
        if(cnt[0]==1){
            while(pre[pre[pre[i]]]!=i){
                printf("%d %d\n",pre[pre[i]],i);
                erase(pre[i]);
            }
            break;
        }
        else{
            if(a[pre[i]]!=a[nxt[i]]){
                printf("%d %d\n",pre[i],nxt[i]);
                erase(i);
            }
            else{
                if(a[pre[pre[i]]]+a[nxt[i]]==3){
                    printf("%d %d\n",pre[pre[i]],i);
                    erase(pre[i]);
                    printf("%d %d\n",pre[i],nxt[i]);
                    erase(i);
                }
            }
            --cnt[0];
        }
    }
    return 0;
}

T3 基因识别

不考虑修改就是建出广义 SAM，类似严格子树内编号集合并的操作。

考虑对修改的串根号分治，大于根号的个数少，可以把所有大于根号的拿来线段树合并，查询时 DFS 线段树。

小于根号的考虑枚举每个节点，这样会有算重，按 DFS 序排序后两两 \(\mathrm{LCA}\) 位置减去重复，就是单点查询子树求和。注意到每次询问只查询一次但修改串长次，所以不用树状数组而使用分块，可以平衡到严格 \(O(n\sqrt{n})\)。

点击查看代码

int n,m,B=170;
ll val[maxn];
int cnt,mp[maxn],imp[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
    int ch[maxn*40][2],tot;
    int siz[maxn*40];
    inline void push_up(int pos){
        siz[pos]=siz[ch[pos][0]]+siz[ch[pos][1]];
    }
    void insert(int &pos,int l,int r,int p,int k){
        if(!pos) pos=++tot;
        if(l==r) return siz[pos]=1,void();
        if(p<=mid) insert(ch[pos][0],l,mid,p,k);
        else insert(ch[pos][1],mid+1,r,p,k);
        push_up(pos);
    }
    int merge(int x,int y,int l,int r){
        if(!x||!y) return x+y;
        int pos=++tot;
        if(l==r){
            siz[pos]=siz[x];
            return pos;
        }
        ch[pos][0]=merge(ch[x][0],ch[y][0],l,mid);
        ch[pos][1]=merge(ch[x][1],ch[y][1],mid+1,r);
        push_up(pos);
        return pos;
    }
    ll dfs(int pos,int l,int r){
        if(l==r) return val[imp[l]];
        ll res=0;
        if(ch[pos][0]) res+=dfs(ch[pos][0],l,mid);
        if(ch[pos][1]) res+=dfs(ch[pos][1],mid+1,r);
        return res;
    }
#undef mid
}S;
struct Block{
    int bel[maxn<<1];
    int lpos[maxn<<1],rpos[maxn<<1];
    int cntB;
    ll sum[maxn<<1],sumB[maxn<<1];
    inline void init(int siz){
        for(int i=1;i<=siz;++i) bel[i]=(i-1)/B+1;
        cntB=(siz-1)/B+1;
        for(int i=1;i<=cntB;++i) lpos[i]=(i-1)*B+1,rpos[i]=min(i*B,siz);
    }
    inline void update(int x,int k){
        sum[x]+=k,sumB[bel[x]]+=k;
    }
    inline ll query(int l,int r){
        ll res=0;
        if(bel[l]==bel[r]){
            for(int i=l;i<=r;++i) res+=sum[i];
        }
        else{
            for(int i=l;i<=rpos[bel[l]];++i) res+=sum[i];
            for(int i=bel[l]+1;i<bel[r];++i) res+=sumB[i];
            for(int i=lpos[bel[r]];i<=r;++i) res+=sum[i];
        }
        return res;
    }
}BL;
struct Query{
    int opt,id,k;
    Query()=default;
    Query(int opt_,int id_,int k_):opt(opt_),id(id_),k(k_){}
}Q[maxn];
string s[maxn];
int mark[maxn];
struct SuffixAutomaton{
    int ch[maxn<<1][26],tot;
    int len[maxn<<1],link[maxn<<1];
    SuffixAutomaton(){
        tot=0;
        len[0]=0,link[0]=-1;
    }
    int rt[maxn<<1];
    inline int extend(int last,int c,vector<int> ID){
        int cur=++tot;
        len[cur]=len[last]+1;
        for(int i:ID){
            if(mp[i]) S.insert(rt[cur],1,mp[0],mp[i],val[i]);
        }
        int p=last;
        while(p!=-1&&!ch[p][c]){
            ch[p][c]=cur;
            p=link[p];
        }
        if(p==-1) link[cur]=0;
        else{
            int q=ch[p][c];
            if(len[p]+1==len[q]) link[cur]=q;
            else{
                int clone=++tot;
                len[clone]=len[p]+1,link[clone]=link[q];
                for(int i=0;i<26;++i) ch[clone][i]=ch[q][i];
                while(p!=-1&&ch[p][c]==q){
                    ch[p][c]=clone;
                    p=link[p];
                }
                link[cur]=link[q]=clone;
            }
        }
        return cur;
    }
    vector<int> E[maxn<<1];
    inline void build(){
        for(int i=1;i<=tot;++i) E[link[i]].push_back(i);
        // for(int u=0;u<=tot;++u){
        //     printf("u:%d link:%d\n",u,link[u]);
        //     for(int i=0;i<26;++i){
        //         if(ch[u][i]) printf("%c:%d ",i+'a',ch[u][i]);
        //     }
        //     printf("\n");
        // }
    }
    int dep[maxn<<1],siz[maxn<<1],son[maxn<<1];
    int top[maxn<<1],dfn[maxn<<1],dfncnt;
    inline int get_LCA(int u,int v){
        while(top[u]!=top[v]){
            if(dep[top[u]]>dep[top[v]]) swap(u,v);
            v=link[top[v]];
        }
        if(dep[u]>dep[v]) swap(u,v);
        return u;
    }
    void dfs1(int u,int d){
        dep[u]=d,siz[u]=1;
        int maxson=-1;
        for(int v:E[u]){
            dfs1(v,d+1);
            if(mp[0]) rt[u]=S.merge(rt[u],rt[v],1,mp[0]);
            siz[u]+=siz[v];
            if(siz[v]>maxson) son[u]=v,maxson=siz[v];
        }
    }
    void dfs2(int u,int t){
        top[u]=t,dfn[u]=++dfncnt;
        if(!son[u]) return;
        dfs2(son[u],t);
        for(int v:E[u]){
            if(v==son[u]) continue;
            dfs2(v,v);
        }
    }
    int p[maxn<<1];
    inline void update(int id,int k){
        int u=0,len=s[id].size();
        p[0]=0;
        for(int i=0;i<len;++i){
            int c=s[id][i]-'a';
            u=ch[u][c];
            p[++p[0]]=u;
        }
        sort(p+1,p+p[0]+1,[&](int A,int B){
            return dfn[A]<dfn[B];
        });
        // for(int i=1;i<=p[0];++i) cerr<<p[i]<<" ";
        // cerr<<endl;
        for(int i=1;i<=p[0];++i){
            BL.update(dfn[p[i]],k);
            if(i>1){
                int lca=get_LCA(p[i-1],p[i]);
                BL.update(dfn[lca],-k);
            }
        }
    }
    inline void query(int u){
        printf("%lld\n",S.dfs(rt[u],1,mp[0])+BL.query(dfn[u],dfn[u]+siz[u]-1));
    }
}SAM;
struct Trie{
    int tr[maxn][26],tot;
    int fa[maxn],last[maxn],C[maxn];
    vector<int> ID[maxn];
    inline void insert(int id){
        int u=0,len=s[id].size();
        if(len>=B) mp[id]=++mp[0],imp[mp[0]]=id;
        for(int i=0;i<len;++i){
            int c=s[id][i]-'a';
            if(!tr[u][c]) tr[u][c]=++tot;
            fa[tr[u][c]]=u,C[tr[u][c]]=c;
            u=tr[u][c];
            if(id<=n) ID[u].push_back(id);
        }
        mark[id]=u;
    }
    inline void build(){
        queue<int> q;
        for(int i=0;i<26;++i){
            if(tr[0][i]) q.push(tr[0][i]);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            last[u]=SAM.extend(last[fa[u]],C[u],ID[u]);
            for(int i=0;i<26;++i){
                if(tr[u][i]) q.push(tr[u][i]);
            }
        }
        for(int i=1;i<=cnt;++i) mark[i]=last[mark[i]];
    }
}T;

int main(){
    freopen("dna.in","r",stdin);
    freopen("dna.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;++i){
        val[i]=read();
        cin>>s[i];
        T.insert(i);
    }
    cnt=n;
    for(int i=1;i<=m;++i){
        int opt=read();
        if(opt==1){
            ++cnt;
            cin>>s[cnt];
            T.insert(cnt);
            Q[i]=Query(opt,cnt,0);
        }
        else{
            int id=read(),k=read();
            Q[i]=Query(opt,id,k);
        }
    }
    T.build();
    SAM.build();
    SAM.dfs1(0,0);
    SAM.dfs2(0,0);
    BL.init(SAM.dfncnt);
    for(int i=1;i<=n;++i){
        if(!mp[i]) SAM.update(i,val[i]);
    }
    for(int i=1;i<=m;++i){
        if(Q[i].opt==1){
            //大于根号线段树合并，暴力 DFS 一遍
            //小于根号单点加，子树求和，需要类似建虚树防止算重，即在 LCA 位置减 1
            SAM.query(mark[Q[i].id]);
        }
        else{
            if(mp[Q[i].id]) val[Q[i].id]+=Q[i].k;
            else SAM.update(Q[i].id,Q[i].k);
        }
    }
    return 0;
}

标签：校国赛,考后,int,res,void,maxn,siz,模拟,mod
From： https://www.cnblogs.com/SoyTony/p/Multiple_School_Simulation_Problems_of_NOI_in_July_3.htm

【考后总结】7 月多校国赛模拟赛 3

7.14 冲刺国赛模拟 36

T1 染色题

T2 石头剪刀布

T3 树状数组

7.17 冲刺国赛模拟 37

T1 数叶子

T3 数论

7.18 冲刺国赛模拟 38

T1 智力游戏

T2 区域划分

T3 基因识别

相关文章

赞助商

阅读排行