JZTXT

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

发布时间 2023-07-14 18:03:40作者: SoyTony

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;
}