首页 > 其他分享 >【考后总结】9 月 CSP-S 模拟赛 4

【考后总结】9 月 CSP-S 模拟赛 4

时间：2023-09-14 20:55:07浏览次数：40  
标签：cnt 考后 lcol int 1ll pw CSP 模拟 mod

9.14 CSP 模拟 38

T1 我是 A 题

每个点坐标都至少有一维卡上界。

那么按照哪一维卡上界分成 \((A,v,w),(u,B,w),(u,v,C)\) 三类，对于点 \((x,y,z)\)，如果会被第一类点删去，那么第一维就不需要考虑了，只需要满足 \(y\) 不大于所有 \(w\) 大于等于 \(z\) 的第一类点中 \(v\) 的最大值。这样实际是构造了关于 \(v,w\) 的二维平面，在上面取后缀 \(\max\)。对第二类点同理，这样对 \(z\) 分类，得到区间 \([1,x_z],[1,y_z]\)，表示如果第三维为 \(z\) 且第一维或第二维在这个区间，那么就会被前两类点删去。

那么只需要考虑 \((x_z,A],(y_z,B]\) 部分，注意到对第三类点来说，无论 \(z\) 取何值，构造出关于 \(u,v\) 的二维平面取出的 \(\max\) 相同，那么只需要枚举 \(z\) 求出即可。

点击查看代码 
int n,A,B,C,lim;
int u[maxn],v[maxn],w[maxn];

inline ull rand(ull &k1,ull &k2){
    ull k3=k1,k4=k2;
    k1=k4;
    k3^=(k3<<23);
    k2=k3^k4^(k3>>17)^(k4>>26);
    return k2+k4;
}
inline void GetData(){
    ull x,y;
    cin>>n>>A>>B>>C>>x>>y;
    lim=max({A,B,C});
    for(int i=1;i<=n;++i){
        u[i]=rand(x,y)%A+1;
        v[i]=rand(x,y)%B+1;
        w[i]=rand(x,y)%C+1;
        if(rand(x,y)%3==0) u[i]=A;
        if(rand(x,y)%3==0) v[i]=B;
        if((u[i]!=A)&&(v[i]!=B)) w[i]=C;
    }
}

int X[maxn],Y[maxn];
ll sumx[maxn];
int mxy[maxn];
__int128_t ans;

void write(__int128_t x){
    if(!x) return;
    write(x/10);
    printf("%d",(int)(x%10));
}

int main(){
    GetData();
    for(int i=1;i<=n;++i){
        if(u[i]==A) Y[w[i]]=max(Y[w[i]],v[i]);
        if(v[i]==B) X[w[i]]=max(X[w[i]],u[i]);
    }
    for(int i=lim;i>=1;--i){
        X[i]=max(X[i],X[i+1]);
        Y[i]=max(Y[i],Y[i+1]);
    }
    for(int i=1;i<=n;++i){
        if(w[i]==C){
            sumx[u[i]]=max(sumx[u[i]],(ll)v[i]);
            mxy[v[i]]=max(mxy[v[i]],u[i]);
        }
    }
    for(int i=lim;i>=1;--i){
        sumx[i]=max(sumx[i],sumx[i+1]);
        mxy[i]=max(mxy[i],mxy[i+1]);
    }
    for(int i=1;i<=lim;++i) sumx[i]+=sumx[i-1];
    for(int i=1;i<=C;++i){
        ans+=1ll*A*Y[i]+1ll*B*X[i]-1ll*X[i]*Y[i];
        if(X[i]==A||Y[i]==B) continue;
        int mxX=sumx[X[i]+1]-sumx[X[i]],mxY=mxy[Y[i]+1];
        if(Y[i]<=mxX&&X[i]<=mxY){
            ans+=(sumx[mxY]-sumx[X[i]])-1ll*Y[i]*(mxY-X[i]);
        }
    }
    if(!ans) printf("0\n");
    else{
        write(ans);
        printf("\n");
    }
    return 0;
}

T2 我是 B 题

最终一定会只剩一个数，枚举其为 \(x\)。

设 \(f_{i,j,k}\) 为删去了 \(i\) 个数，其中 \(x\) 前面还剩 \(j\) 个，\(x\) 后面还剩 \(k\) 个。转移是一个 \(\sum p_i(1-p_i)^l\) 形式。

注意到 \(j+k=n-i-1\)，那么实际状态就是 \(f_{i,j}\)，时间复杂度 \(O(n^3)\)。

点击查看代码 
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;
int p[maxn],inv[maxn],pw[maxn][maxn];
int f[maxn][maxn];
int ans;

int main(){
    n=read();
    for(int i=1;i<n;++i) p[i]=read();
    for(int i=1;i<=n;++i){
        inv[i]=q_pow(p[i],mod-2,mod);
        pw[i][0]=1;
        for(int j=1;j<=n;++j){
            pw[i][j]=1ll*pw[i][j-1]*(mod+1-p[i])%mod;
        }
    }
    for(int x=1;x<=n;++x){
        for(int i=0;i<=n;++i){
            for(int j=0;j<=n;++j){
                f[i][j]=0;
            }
        }
        f[0][x-1]=1;
        for(int i=0;i<n;++i){
            for(int j=0,k=n-i-1;j<=n-i-1;++j,--k){
                if(j>x-1||k>n-x) continue;
                if(!f[i][j]) continue;
                if(j){
                    f[i+1][j-1]=(f[i+1][j-1]+1ll*(mod+1-pw[i+1][j])*f[i][j]%mod)%mod;
                }
                if(k){
                    f[i+1][j]=(f[i+1][j]+1ll*pw[i+1][j+1]*f[i][j]%mod)%mod;
                }
            }
        }
        for(int i=0;i<=n;++i){
            for(int j=0;j<=n;++j){
                int k=n-i-j;
                if(k<0) continue;
            }
        }
        ans=(ans+1ll*x*f[n-1][0]%mod)%mod;
    }
    printf("%d\n",ans);
    return 0;
}

T3 我是 C 题

\(b\) 序列单调不升，因此更小的区间的要求是更“严苛”的。

如果一个区间 \([l,r]\) 中有位置 \(p\) 不满足条件，那么跨过 \(p\) 的所有子区间一定不满足条件，可以分治。

分治是找到这样的一个 \(p\) 后递归，但复杂度没有保证。

借助启发式合并的思想，从两侧向中间遍历找到第一个 \(p\)，同时要维护一个桶，先删去小区间内元素，递归大区间，在递归过程中就删去了大区间内元素，再加入小区间内元素，最后递归小区间。这样的流程保证了在当前层没有遍历大区间，时间复杂度 \(O(n\log n)\)。

点击查看代码 
int n;
int a[maxn],b[maxn];
int cnt[maxn];
int ans;
void solve(int l,int r){
    int p=-1;
    for(int i=l,j=r;i<=j;++i,--j){
        if(cnt[a[i]]<b[r-l+1]){
            p=i;
            break;
        }
        if(cnt[a[j]]<b[r-l+1]){
            p=j;
            break;
        }
    }
    if(p==-1){
        ans=max(ans,r-l+1);
        for(int i=l;i<=r;++i) --cnt[a[i]];
        return;
    }
    if(l==r) return --cnt[a[l]],void();
    if(p==r) --p;
    int L1=l,R1=p,L2=p+1,R2=r;
    if(R1-L1>R2-L2) swap(L1,L2),swap(R1,R2);
    for(int i=L1;i<=R1;++i) --cnt[a[i]];
    solve(L2,R2);
    for(int i=L1;i<=R1;++i) ++cnt[a[i]];
    solve(L1,R1);
}

int main(){
    n=read();
    for(int i=1;i<=n;++i) a[i]=read(),++cnt[a[i]];
    for(int i=1;i<=n;++i) b[i]=read(); 
    solve(1,n);
    printf("%d\n",ans);
    return 0;
}

T4 我是 D 题

关键转化是 \(n^2=2\binom{n}{2}+\binom{n}{1}\)，后者每次询问都是 \(r-l+1\)，那么只考虑 \(\dbinom{n}{2}\)，这相当于每个连续子段都有 \(1\) 的贡献，根据期望线性性，问题核心是求 \([l,r]\) 内所有区间作为一个连续段的概率之和。

设 \(cnt_{l,r}\) 表示区间 \([l,r]\) 内 \(0\) 的个数，概率形如：

  • \([l,r]\) 内全部为 \(0\)，概率为 \(\frac{1}{m^{cnt_{l,r}-1}}\)

  • \([l,r]\) 内只包含 \(0\) 和某种数字，概率为 \(\frac{1}{m^{cnt_{l,r}}}\)

  • \([l,r]\) 内含两种以及上数字，概率 \(0\)

考虑如何线段树维护，注意到合并两个区间时，只有左区间后缀和右区间前缀是有贡献的，且要有这部分是只包含 \(0\) 和某种数字。

那么维护这个前缀或后缀的 \(\sum \frac{1}{m^{cnt}}\)，合并时相乘即可。但合并可能存在全部为 \(0\) 的区间，因此还要额外统计全部为 \(0\) 的极长前缀或后缀，减去他们产生的贡献，再将真正的概率加上。

点击查看代码 
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,q;
int a[maxn];
int inv_pw[maxn],sum_inv_pw[maxn];

struct Data{
    int L,R,len,cnt;
    bool cov;
    int lcol,lsum1,lsum2;
    int rcol,rsum1,rsum2;
    int sump;
    void merge(Data A,Data B){
        L=A.L,R=B.R,len=A.len+B.len,cnt=A.cnt+B.cnt;
        cov=A.cov&&B.cov&&(!A.lcol||!B.lcol||A.lcol==B.lcol);
        if(!A.lcol){
            lcol=B.lcol;
            lsum1=(sum_inv_pw[A.len]+1ll*inv_pw[A.cnt]*B.lsum1%mod)%mod;
            lsum2=(sum_inv_pw[A.len]+1ll*inv_pw[A.cnt]*B.lsum2%mod)%mod;
        }
        else{
            lcol=A.lcol;
            lsum1=A.lsum1;
            if(A.cov){
                if(!B.lcol||A.lcol==B.lcol) lsum2=(A.lsum2+1ll*inv_pw[A.cnt]*B.lsum2%mod)%mod;
                else lsum2=(A.lsum2+1ll*inv_pw[A.cnt]*B.lsum1%mod)%mod;
            }
            else lsum2=A.lsum2;
        }
        if(!B.lcol){
            rcol=A.rcol;
            rsum1=(sum_inv_pw[B.len]+1ll*inv_pw[B.cnt]*A.rsum1%mod)%mod;
            rsum2=(sum_inv_pw[B.len]+1ll*inv_pw[B.cnt]*A.rsum2%mod)%mod;
        }
        else{
            rcol=B.rcol;
            rsum1=B.rsum1;
            if(B.cov){
                if(!A.lcol||A.rcol==B.lcol) rsum2=(B.rsum2+1ll*inv_pw[B.cnt]*A.rsum2%mod)%mod;
                else rsum2=(B.rsum2+1ll*inv_pw[B.cnt]*A.rsum1%mod)%mod;
            }
            else rsum2=B.rsum2;
        }
        sump=(A.sump+B.sump)%mod;
        sump=(sump+1ll*A.rsum1*B.lsum1%mod*m%mod)%mod;
        if(!A.lcol||!B.lcol||A.rcol==B.lcol) sump=(sump+1ll*A.rsum2*B.lsum2%mod-1ll*A.rsum1*B.lsum1%mod+mod)%mod;
        else sump=(sump+1ll*(A.rsum2-A.rsum1+mod)*B.lsum1%mod+1ll*(B.lsum2-B.lsum1+mod)*A.rsum1%mod)%mod;
    }
};

struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
    Data D[maxn<<2];
    inline void push_up(int rt){
        D[rt].merge(D[rt<<1],D[rt<<1|1]);
    }
    void build(int rt,int l,int r){
        if(l==r){
            if(a[l]){
                D[rt].L=D[rt].R=l,D[rt].len=1,D[rt].cnt=0,D[rt].cov=true;
                D[rt].lcol=D[rt].rcol=a[l],D[rt].lsum1=D[rt].rsum1=0,D[rt].lsum2=D[rt].rsum2=1;
                D[rt].sump=1;
            }
            else{
                D[rt].L=D[rt].R=l,D[rt].len=1,D[rt].cnt=1,D[rt].cov=true;
                D[rt].lcol=D[rt].rcol=0,D[rt].lsum1=D[rt].rsum1=inv_pw[1],D[rt].lsum2=D[rt].rsum2=inv_pw[1];
                D[rt].sump=1;
            }
            return;
        }
        build(lson),build(rson);
        push_up(rt);
    }
    void update(int rt,int l,int r,int p){
        if(l==r){
            if(a[l]){
                D[rt].L=D[rt].R=l,D[rt].len=1,D[rt].cnt=0,D[rt].cov=true;
                D[rt].lcol=D[rt].rcol=a[l],D[rt].lsum1=D[rt].rsum1=0,D[rt].lsum2=D[rt].rsum2=1;
                D[rt].sump=1;
            }
            else{
                D[rt].L=D[rt].R=l,D[rt].len=1,D[rt].cnt=1,D[rt].cov=true;
                D[rt].lcol=D[rt].rcol=0,D[rt].lsum1=D[rt].rsum1=inv_pw[1],D[rt].lsum2=D[rt].rsum2=inv_pw[1];
                D[rt].sump=1;
            }
            return;
        }
        if(p<=mid) update(lson,p);
        else update(rson,p);
        push_up(rt);
    }
    Data query(int rt,int l,int r,int pl,int pr){
        if(pl<=l&&r<=pr) return D[rt];
        if(pr<=mid) return query(lson,pl,pr);
        else if(pl>mid) return query(rson,pl,pr);
        else{
            Data res;
            res.merge(query(lson,pl,pr),query(rson,pl,pr));
            return res;
        }
    }
#undef mid
#undef lson
#undef rson
}S;

int main(){
    n=read(),m=read(),q=read();
    inv_pw[0]=1,inv_pw[1]=q_pow(m,mod-2,mod);
    for(int i=2;i<=n;++i) inv_pw[i]=1ll*inv_pw[i-1]*inv_pw[1]%mod;
    for(int i=1;i<=n;++i) sum_inv_pw[i]=(sum_inv_pw[i-1]+inv_pw[i])%mod;
    for(int i=1;i<=n;++i) a[i]=read();
    S.build(1,1,n);
    while(q--){
        int opt=read();
        if(opt==1){
            int x=read(),k=read();
            a[x]=k;
            S.update(1,1,n,x);
        }
        else{
            int l=read(),r=read();
            Data now=S.query(1,1,n,l,r);
            int ans=now.sump;
            ans=(2ll*ans-(r-l+1)+mod)%mod;
            printf("%d\n",ans);
        }
    }
    return 0;
}

标签：cnt,考后,lcol,int,1ll,pw,CSP,模拟,mod
From： https://www.cnblogs.com/SoyTony/p/Simulation_Problems_of_CSP-S_in_September_4.html

相关文章

  • CSP 2023 游记
    有人已经开始催我写游记了？？？DAY-1凌乱……作业写完了，然后就开始再度刷复赛卷……明天的课只能咕了，相比OI，数学算什么！（doge，我今天数学考试还炸了阅读程序噩梦啊啊啊，完善程序要命啊啊啊，一整个疯狂的状态无可奈何啊，初赛前垂死挣扎一下吧QAQ晚上重刷CSP-J2019的卷子吧，不知结果会......
  • 模拟企业环境
               ......
  • 系统架构设计师 - 模拟题 - 案例题（二）
    试题二(25分)阅读以下关于软件系统建模的叙述，在答题纸上回答问题1至问题3。[说明]某软件公司计划开发一套教学管理系统，用于为高校提供教学管理服务。该教学管理系统基本的需求包括:(1)系统用户必须成功登录到系统后才能使用系统的各项功能服务。(2)管理员(Registrar)使用该系统管......
  • 2023年9月CSPM-3国标项目管理中级认证报名到这就对了
    CSPM-3中级项目管理专业人员评价，是中国标准化协会（全国项目管理标准化技术委员会秘书处），面向社会开展项目管理专业人员能力的等级证书。旨在构建多层次从业人员培养培训体系，建立健全人才职业能力评价和激励机制的要求，培养我国项目管理领域复合型人才。  【证书含金量】 ·竞聘优先......
  • CSP 202109-2 非零段划分
    题目C++代码//202109-2非零段划分#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=500010;constintM=10010;inta[N],d[M];//d[i]为差分数组boolc[N];intn,ans,sum;intmain(){scanf(&q......
  • Android后台模拟点击探索（附源码）攻略
    ​本攻略将详细介绍如何在Android应用中使用后台模拟点击的技术。通过模拟点击，我们可以在后台执行一些用户交互操作，例如点击按钮、输入文本等。这对于自动化测试、批量操作等场景非常有用。步骤一：添加权限首先，在AndroidManifest.xml文件中添加以下权限：<uses-permissionandro......
  • 【气动学】基于龙格库塔法模拟单机无穷大系统功角稳定仿真matlab实现
    ✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进，matlab项目合作可私信。......
  • 常用电子电路模块---模拟电路及数模集成电路模块
    模拟电路及数模集成电路模块从功能上进行分类模拟集成电路可以被分为通用类模拟集成电路和专用类模拟集成电路。这种分类比较宽泛，其实这两大类还可以再细分。例如，通用类模拟集成电路还可以分为运放类、电源类、接口类和时钟类集成电路等；而专用模拟集成电路则更加广泛，有时候可能......
  • P5664 [CSP-S2019] Emiya 家今天的饭
    原题之前做过，后来忘了，回顾&复习首先这题容易想到是容斥，因为保证所有他要求每种主要食材至多在\(\lfloor\frac{k}{2}\rfloor\)道菜中被使用(注意，这里是主要食材，不是菜的个数，别问我为什么强调这个)，这说明不满足这个条件的情况最多只有一列会出现\(>\lfloor\frac{k}{2}\rfloor......
  • 【考后总结】9 月 CSP-S 模拟赛 3
    9.12CSP模拟36T1博弈如果路径上最小值数量为奇数，那么先手第一个取最小值必胜。如果是偶数，那么双方都尽量避免第一个取最小值，变成了删去最小值不能操作的必败，就是子问题，归纳发现先手必败当且仅当所有值的出现次数都是偶数。关于偶数的统计想到异或哈希，由于重复路径异或后贡......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99