【考试总结】2022-05-01

2022/5/2 23:17:41

编程Tag： return int push 01 lim 05 opt 2022 rson

本文主要是介绍【考试总结】2022-05-01，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

a

观察能构成合法区间的条件就是奇数成对，同时每对奇数之间没有 \(0\)

使用一类线段树维护历史信息的手段来解决本题，为了规避麻烦的标记下放，可以将每个 “偶数个奇数” 的出现区间左右端点刻画出来并使用 \(r-l+1\) 来计算

同时在每个节点要支持 \(01\) 翻转的部分维护 “对未翻转时奇数/偶数” 的权值增加量方便下方

Code Display 
const int N=5e5+10;
int n,Q,a[N],his[N],ans[N];
vector<pair<int,int> > qu[N];
bool ban[N],od[N];
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
bool rev[N<<2];
int num[N<<2][2],delt[N<<2][2],sum[N<<2];
inline void push_up(int p){
    sum[p]=sum[ls]+sum[rs];
    num[p][0]=num[ls][0]+num[rs][0];
    num[p][1]=num[ls][1]+num[rs][1];
    return ;
}
inline void push_rev(int p){rev[p]^=1; swap(num[p][0],num[p][1]);}
inline void push_add(int p,int v,int fl){
    delt[p][rev[p]^fl]+=v;
    sum[p]+=num[p][fl]*v;
    return ;
}
inline void push_down(int p){
    for(int i=0;i<2;++i) if(delt[p][i]){
        push_add(ls,delt[p][i],i);
        push_add(rs,delt[p][i],i);
        delt[p][i]=0;
    }
    if(rev[p]){
        push_rev(ls); push_rev(rs);
        rev[p]=0;
    }
    return ;
}
inline void upd(int R,int v,int fl,int p=1,int l=1,int r=n){
    if(r<=R) return push_add(p,v,fl),void();
    int mid=(l+r)>>1; push_down(p);
    if(R>mid) upd(R,v,fl,rson);
    upd(R,v,fl,lson);
    return push_up(p);
}
inline int query(int st,int ed,int p=1,int l=1,int r=n){
    if(st<=l&&r<=ed) return sum[p];
    int mid=(l+r)>>1,res=0; push_down(p);
    if(ed>mid) res+=query(st,ed,rson);
    if(st<=mid) res+=query(st,ed,lson);
    return res;
}
inline void dfs(int p,int l,int r){
    if(!num[p][1]) return ;
    if(l==r){
        delt[p][0]=delt[p][1]=0;
        num[p][0]=num[p][1]=0;
        return ;
    }
    int mid=(l+r)>>1; push_down(p);
    dfs(lson); dfs(rson);
    return push_up(p);
}
inline void Reverse(int R,int p=1,int l=1,int r=n){
    if(r<=R) return push_rev(p);
    int mid=(l+r)>>1; push_down(p);
    if(R>mid) Reverse(R,rson);
    Reverse(R,lson);
    return push_up(p);
}
inline void build(int p,int l,int r){
    if(l==r){
        num[p][0]=1;
        sum[p]=-l;
        return ;
    }
    int mid=(l+r)>>1;
    build(lson); build(rson);
    return push_up(p);
}
inline void output(int p,int l,int r){
    if(l==r) return cout<<sum[p]<<" ",void();
    int mid=(l+r)>>1; push_down(p);
    output(lson); output(rson);
    return ;
}
#undef ls
#undef rs
#undef lson
#undef rson
signed main(){
    freopen("a.in","r",stdin); freopen("a.out","w",stdout);
    n=read(); Q=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=Q;++i){
        int l=read(),r=read();
        qu[r].emplace_back(l,i);
    }
    build(1,1,n);
    for(int i=1;i<=n;++i){
        if(!a[i]&&i) dfs(1,1,n);
        if(a[i]&1){
            upd(i,i,0);
            upd(i,-i,1);
            Reverse(i);
        }
        for(auto t:qu[i]){
            upd(i,i+1,0);
            ans[t.sec]+=query(t.fir,i);
            upd(i,-1-i,0);
        }
    }
    rep(i,1,Q) print(ans[i]);
    return 0;
}

b

对于 \(Q\) 个属于 \([1,m]\) 的 随机区间，将左端点排序后，对应的右端点最长上升子序列长度是 \(\Theta(\sqrt Q)\) 级别的

那么将所有询问分成 \(\dfrac{Q}{\sqrt Q}\) 组，每组中询问形成嵌套关系，使用势能线段树暴力扩展即可

但是据说会被卡常，所以代码写了个能过的暴力

Code Display 
const int N=15010;
int n,m,Q,sum[N<<2];
struct operation{
    int l,r,v,id;
}opt[N<<1];
inline void upd(int p,int l,int r,int st,int ed){
    if(sum[p]==r-l+1) return ;
    if(st<=l&&r<=ed) return sum[p]=r-l+1,void();
    int mid=(l+r)>>1;
    if(st<=mid) upd(p<<1,l,mid,st,ed);
    if(ed>mid) upd(p<<1|1,mid+1,r,st,ed);
    sum[p]=sum[p<<1]+sum[p<<1|1];
    return ;
}
inline void build(int p,int l,int r){
    sum[p]=0; if(l==r) return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid); build(p<<1|1,mid+1,r);
}
signed main(){
    freopen("b.in","r",stdin); freopen("b.out","w",stdout);
    n=read(); m=read(); Q=read();
    for(int i=1;i<=n;++i) opt[i]={i,i,read(),0};
    int cnt=n;
    for(int i=1;i<=m;++i){
        int l=read(),r=read(),v=read();
        opt[++cnt]={l,r,v,i};
    }
    sort(opt+1,opt+cnt+1,[&](const operation A,const operation B){return A.v<B.v;});
    while(Q--){
        int l1=read(),r1=read(),l2=read(),r2=read();
        int lst=0;
        int ans=0;
        int siz=r2-l2+1;
        build(1,1,siz);
        for(int i=1;i<=cnt;++i){
            if(opt[i].id&&(opt[i].id<l1||opt[i].id>r1)) continue;
            if(opt[i].r<l2||opt[i].l>r2) continue;
            upd(1,1,siz,max(opt[i].l,l2)-l2+1,min(opt[i].r,r2)-l2+1);
            ans+=(sum[1]-lst)*opt[i].v;
            if(sum[1]==siz) break;   
            lst=sum[1];
        }
        print(ans);
    }
    return 0;
}

c

发现本质上要完成的工作是对 \(n\times K\) 个点值做背包，但是每个元素的值域只有 \(\pm1\) ，也就是在 \(n\) 个数字里面找到 \(m\) 个并将它们乘起来再对所有选择方案的权值求和

设有 \(x\) 个元素贡献 \(1\) 而 \(n-x\) 个元素贡献 \(-1\)，对于所有 \(x\) 求出来 \([z^m](1-z)^{n-x}(1+z)^{x}\)

而这通过分配幂次变成 \(\displaystyle \sum_{i=0}^m(-1)^{m-i}\binom{n-x}{m-i}\binom{x}i\)

再拆成阶乘逆元可以通过一次卷积进行计算

在对 \(a_i\) 形成的桶做 \(\rm FWT\) 后得到的点值解方程可以得到上面所写的 \(x\)，那么直接代换成背包后的结果再做逆变换得到答案

Code Display 
const int N=2e5+10;
int n,m,K;
inline void FWT(vector<int> &f,int lim){
    for(int p=2;p<=lim;p<<=1){
        int len=p>>1;
        for(int k=0;k<lim;k+=p) for(int l=k;l<k+len;++l){
            int x=f[l],y=f[l+len];
            f[l+len]=x-y;
            f[l]=x+y;
        }
    }
    return ;
}
inline void iFWT(vector<int> &f,int lim){
    for(int p=2;p<=lim;p<<=1){
        int len=p>>1;
        for(int k=0;k<lim;k+=p) for(int l=k;l<k+len;++l){
            int x=f[l],y=f[l+len];
            f[l+len]=del(x,y);
            f[l]=add(x,y);
        }
    }
    for(int tmp=ksm(lim,mod-2),i=0;i<lim;++i) ckmul(f[i],tmp);
    return ;
}
int W[1<<20],r[1<<20];
inline void NTT(vector<int> &f,int lim,int opt){
    f.resize(lim);
    for(int i=0;i<lim;++i){
        r[i]=r[i>>1]>>1|((i&1)?(lim>>1):0);
        if(i<r[i]) swap(f[i],f[r[i]]);
    }
    for(int p=2;p<=lim;p<<=1){
        int len=p>>1; W[0]=1; 
        W[1]=ksm(3,(mod-1)/p);
        if(opt==-1) W[1]=ksm(W[1],mod-2);
        for(int j=2;j<len;++j) W[j]=mul(W[j-1],W[1]);
        for(int k=0;k<lim;k+=p){
            for(int l=k;l<k+len;++l){
                int tt=mul(f[l+len],W[l-k]);
                f[l+len]=del(f[l],tt);
                ckadd(f[l],tt);
            }
        }        
    }
    if(opt==-1) for(int tmp=ksm(lim,mod-2),i=0;i<lim;++i) ckmul(f[i],tmp);
}
int ifac[N],fac[N];
signed main(){
    freopen("c.in","r",stdin); freopen("c.out","w",stdout);
    n=read(); m=read(); K=read();
    vector<int> f,g,a(K);
    for(int i=1;i<=n;++i) a[read()]++;
    if(m==1){
        rep(i,0,K-1) print(a[i]);
        putchar('\n');
        exit(0);
    }
    fac[0]=1;
    for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
    ifac[n]=ksm(fac[n],mod-2);
    for(int i=n;i>=1;--i) ifac[i-1]=mul(ifac[i],i);
    
    FWT(a,K);
    int lim=1;
    while(lim<=n) lim<<=1;
    f.resize(m+1);
    g.resize(n-m+1);
    for(int i=0;i<=m;++i){
        f[i]=mul(ifac[i],ifac[m-i]);
        if((m-i)&1) f[i]=del(0,f[i]);
    }
    for(int i=0;i<=n-m;++i) g[i]=mul(ifac[i],ifac[n-m-i]);
    NTT(f,lim,1); NTT(g,lim,1);
    for(int i=0;i<lim;++i) ckmul(f[i],g[i]);
    NTT(f,lim,-1);
    for(int i=0;i<=n;++i) ckmul(f[i],mul(fac[i],fac[n-i]));
    for(int i=0;i<K;++i) a[i]=f[(n-a[i])/2];
    iFWT(a,K);
    for(int i=0;i<K;++i) print(a[i]); putchar('\n');
    return 0;
}



这篇关于【考试总结】2022-05-01的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程