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

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

时间：2023-09-12 18:44:18浏览次数：36  
标签：ch 考后 int siz mx maxn pmn CSP 模拟

9.12 CSP 模拟 36

T1 博弈

如果路径上最小值数量为奇数，那么先手第一个取最小值必胜。如果是偶数，那么双方都尽量避免第一个取最小值，变成了删去最小值不能操作的必败，就是子问题，归纳发现先手必败当且仅当所有值的出现次数都是偶数。

关于偶数的统计想到异或哈希，由于重复路径异或后贡献消失，直接 DFS 而不是点分治。

哈希可以重编号后双哈希，使用哈希表代替 map 可以卡点分治的常数。

点击查看代码（正解） 
int t;
int n;
struct edge{
    int to,nxt,w;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v,int w){
    e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt,e[cnt].w=w;
    e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt,e[cnt].w=w;
}
vector<int> V;
map<int,int> W;
int pw1[maxn],pw2[maxn];
int dis1[maxn],dis2[maxn];
map<pii,int> mp;
ll ans;
void dfs(int u,int fa){
    ans-=mp[make_pair(dis1[u],dis2[u])];
    ++mp[make_pair(dis1[u],dis2[u])];
    for(int i=head[u],v,w;i;i=e[i].nxt){
        v=e[i].to,w=e[i].w;
        if(v==fa) continue;
        dis1[v]=dis1[u]^pw1[w],dis2[v]=dis2[u]^pw2[w];
        dfs(v,u);
    }
}

int main(){
    srand((unsigned long long)&seed);
    t=read();
    while(t--){
        n=read();
        cnt=0;
        for(int i=1;i<=n;++i) head[i]=0,dis1[i]=0,dis2[i]=0;
        V.clear(),W.clear();
        for(int i=1,u,v,w;i<n;++i){
            u=read(),v=read(),w=read();
            add_edge(u,v,w);
            V.push_back(w);
        }
        sort(V.begin(),V.end());
        V.erase(unique(V.begin(),V.end()),V.end());
        random_shuffle(V.begin(),V.end());
        pw1[0]=pw2[0]=1;
        for(int i=0;i<V.size();++i){
            W[V[i]]=i+1;
            pw1[i+1]=1ll*pw1[i]*base1%mod,pw2[i+1]=1ll*pw2[i]*base2%mod;
        }
        for(int u=1;u<=n;++u){
            for(int i=head[u];i;i=e[i].nxt){
                e[i].w=W[e[i].w];
            }
        }
        ans=1ll*n*(n-1)/2;
        mp.clear();
        dfs(1,0);
        printf("%lld\n",ans);
    }
    return 0;
}
点击查看代码（卡常后点分治） 
const int MOD=5e6+11;

int t;
int n;
struct edge{
    int to,nxt,w;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v,int w){
    e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt,e[cnt].w=w;
    e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt,e[cnt].w=w;
}
int cntW;
unordered_map<int,int> W;
int pw1[maxn],pw2[maxn];
ll ans;

int ct;
bool vis[maxn];
int siz[maxn],mxsiz[maxn],sumsiz;
void dfs_siz(int u,int fa){
    siz[u]=1;
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        if(vis[v]||v==fa) continue;
        dfs_siz(v,u);
        siz[u]+=siz[v];
    }
}
inline void init(int u){
    ct=0,sumsiz=siz[u];
}
void dfs_ct(int u,int fa){
    mxsiz[u]=0;
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        if(vis[v]||v==fa) continue;
        dfs_ct(v,u);
        mxsiz[u]=max(mxsiz[u],siz[v]);
    }
    mxsiz[u]=max(mxsiz[u],sumsiz-siz[u]);
    if(!ct||mxsiz[u]<mxsiz[ct]) ct=u;
}

int dis1[maxn],dis2[maxn];
int hd[MOD+5],nxt[maxn];
ll Key[maxn];
int Val[maxn],tot;
int mark[MOD+5];
int NOW;
inline void insert(ll k){
    int p=k%MOD+1;
    hd[p]=(mark[p]==NOW)?hd[p]:0;
    mark[p]=NOW;
    for(int i=hd[p];i;i=nxt[i]){
        if(Key[i]==k){
            ++Val[i];
            return;
        }
    }
    Key[++tot]=k,Val[tot]=1;
    nxt[tot]=hd[p],hd[p]=tot;
}
inline int query(ll k){
    int p=k%MOD+1;
    hd[p]=(mark[p]==NOW)?hd[p]:0;
    mark[p]=NOW;
    for(int i=hd[p];i;i=nxt[i]){
        if(Key[i]==k) return Val[i];
    }
    return 0;
}
ll st[maxn];
int top;

void calc(int u,int fa){
    ans-=query(1ll*dis1[u]*mod+dis2[u]);
    st[++top]=1ll*dis1[u]*mod+dis2[u];
    for(int i=head[u],v,w;i;i=e[i].nxt){
        v=e[i].to,w=e[i].w;
        if(vis[v]||v==fa) continue;
        dis1[v]=dis1[u]^pw1[w],dis2[v]=dis2[u]^pw2[w];
        calc(v,u);
    }
}
void solve(int u){
    vis[u]=true;
    tot=0,++NOW;
    insert(0);
    for(int i=head[u],v,w;i;i=e[i].nxt){
        v=e[i].to,w=e[i].w;
        if(vis[v]) continue;
        dis1[v]=pw1[w],dis2[v]=pw2[w];
        calc(v,0);
        while(top){
            insert(st[top]);
            --top;
        }
    }
    dfs_siz(u,0);
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        if(vis[v]) continue;
        init(v);
        dfs_ct(v,0);
        solve(ct);
    }
}

int main(){
    pw1[0]=pw2[0]=1;
    for(int i=1;i<=500000;++i) pw1[i]=1ll*pw1[i-1]*base1%mod,pw2[i]=1ll*pw2[i-1]*base2%mod;
    t=read();
    while(t--){
        n=read();
        ans=1ll*n*(n-1)/2;
        cnt=0;
        for(int i=1;i<=n;++i){
            head[i]=0,vis[i]=false;
        } 
        W.clear();
        for(int i=1,u,v,w;i<n;++i){
            u=read(),v=read(),w=read();
            if(W[w]) w=W[w];
            else{
                ++cntW;
                W[w]=cntW,w=cntW;
            }
            add_edge(u,v,w);
        }
        dfs_siz(1,0);
        init(1);
        dfs_ct(1,0);
        solve(ct);
        printf("%lld\n",ans);
        if(!t) exit(0);
    }
    return 0;
}

T2 跳跃

容易发现最后一定是在一个子段反复横跳，但可能无法一次到达这个子段，需要在前面一个子段反复横跳积累权值，以此类推，到达前面这个子段可能也需要在更前面反复横跳……

注意到上面这个操作的前提是每次横跳的子段和单调递增，那么只需要枚举最后一个子段就可以了，而固定了右端点，一定选择权值和最大的子段。

考虑一个 DP，设 \(f_i\) 为从 \(1\) 经过一系列操作到达 \(i\) 需要的最少次数，\(g_i\) 为在此基础上可以积累的最大权值和，注意由于每次横跳的子段和单调递增，因此越早到达后面的子段一定是更优的。

转移即枚举上一个子段右端点 \(j\)，设 \(s\) 为 \(j\) 作为右端点的最大子段和，设横跳了 \(p\) 次，\(sum\) 为从 \(j\) 对应子段的左端点移动到 \(i\) 的权值，那么要求 \(g_j+ps+sum\ge 0\)，可以解出 \(p\) 的最小值，同时要求 \(f_j+p\) 是偶数才可以下一次跳到 \(i\)。

有一些细节需要处理。

点击查看代码 
int t;
int n,k;
int a[maxn],sum[maxn],mnid[maxn];
int f[maxn];
ll g[maxn];
ll ans;

int main(){
    t=read();
    while(t--){
        n=read(),k=read();
        for(int i=0;i<=n;++i) sum[i]=0,mnid[i]=0,f[i]=0,g[i]=0;
        for(int i=1;i<=n;++i){
            a[i]=read();
            sum[i]=sum[i-1]+a[i];
            if(sum[i]<=sum[mnid[i-1]]) mnid[i]=i;
            else mnid[i]=mnid[i-1];
        }
        ans=0;
        f[1]=0,g[1]=0;
        for(int i=2;i<=n;++i){
            if(sum[i]>=0) f[i]=1,g[i]=sum[i];
            else{
                f[i]=k+1,g[i]=0;
                for(int j=1;j<mnid[i];++j){
                    if(f[j]==k+1) continue;
                    int now=sum[j]-sum[mnid[j]];
                    if(now<=0) continue;
                    if((f[j]&1)&&g[j]+now+sum[i]-sum[mnid[j]]>=0){
                        if(f[j]+2<f[i]) f[i]=f[j]+2,g[i]=g[j]+now+(sum[i]-sum[mnid[j]]);
                        else if(f[j]+2==f[i]) g[i]=max(g[i],g[j]+now+(sum[i]-sum[mnid[j]])); 
                    }
                    else{
                        int p=(-(sum[i]-sum[mnid[j]])-g[j]-1)/now+1;
                        if((f[j]+p)&1) ++p;
                        if(f[j]+p+1<f[i]) f[i]=f[j]+p+1,g[i]=g[j]+1ll*p*now+(sum[i]-sum[mnid[j]]);
                        else if(f[j]+p+1==f[i]) g[i]=max(g[i],g[j]+1ll*p*now+(sum[i]-sum[mnid[j]]));
                    } 
                }
            }
        }
        for(int i=1;i<=n;++i){
            if(f[i]==k+1) continue;
            ans=max(ans,g[i]+1ll*(k-f[i])*(sum[i]-sum[mnid[i]]));
        }
        printf("%lld\n",ans);
    }
    return 0;
}

T3 大陆

原题：Luogu-P2325 SCOI2005 王室联邦

对每个节点 \(u\) 维护一个集合 \(S_u\) 表示还未分块的部分，每次枚举儿子 \(v\)，将 \(S_v\) 合并在一起，当合并后集合超过 \(B\) 后，将这部分划为一个块，首府设为 \(u\)，剩下的节点算上 \(u\) 上传到 \(u\) 的父亲。

这样每次上传的集合大小不超过 \(B\)，那么每个块大小不超过 \(2B\)。

最后根位置可能还剩余一些节点，也放入上一个首府为根的块，其大小不超过 \(3B\)。

点击查看代码 
int n,B;
vector<int> E[maxn];
vector<int> S[maxn];
int a[maxn],b[maxn],tot;
void dfs(int u,int fa){
    for(int v:E[u]){
        if(v==fa) continue;
        dfs(v,u);
        for(int i:S[v]){
            S[u].push_back(i);
        }
        S[v].clear();
        S[v].shrink_to_fit();
        if((int)S[u].size()>=B){
            b[++tot]=u;
            for(int i:S[u]) a[i]=tot;
            S[u].clear();
            S[u].shrink_to_fit();
        }
    }
    S[u].push_back(u);
}

int main(){
    n=read(),B=read();
    for(int i=1,u,v;i<n;++i){
        u=read(),v=read();
        E[u].push_back(v),E[v].push_back(u);
    }
    dfs(1,0);
    if(!tot) b[++tot]=1;
    for(int i:S[1]) a[i]=tot;
    printf("%d\n",tot);
    for(int i=1;i<=n;++i) printf("%d ",a[i]);
    printf("\n");
    for(int i=1;i<=tot;++i) printf("%d ",b[i]);
    printf("\n");
    return 0;
}

T4 排列

循环移位操作等价于用 fhq-Treap 将两个区间拆出来交换顺序再合并进去。

那么就需要考虑如何维护子树信息。

思考一个更简单的问题：如何维护二元上升子序列？只需要维护每个子树的最小值 \(mn\) 和最大值 \(mx\)，合并时跨过子树产生的贡献就是左子树 \(mn\) 与根的较小值小于右子树 \(mx\) 与根的较大值。

那么维护三元上升子序列，就可能存在一侧子树贡献两个位置的情况，维护 \(pmn\) 表示子树内二元上升子序列中较大值的最小值，\(pmx\) 表示子树内二元上升子序列中较小值的最大值。

这样合并时跨过子树产生的贡献就是左子树的 \(pmn\) 小于右子树 \(mx\) 与根的较大值或是右子树的 \(pmx\) 大于左子树 \(mn\) 与根的较小值。

现在问题是如何维护 \(pmn\) 与 \(pmx\)，再继承两子树信息的基础上，需要考虑两子树各贡献一个的情况，注意到 \(pmn\) 一定是左子树 \(mn\) 与根的较小值贡献二元上升子序列中左侧的值，\(pmx\) 一定是是右子树 \(mx\) 与根的较大值贡献二元上升子序列中右侧的值，似乎是无法快速查找出另一个值的。

发现维护这两个信息的前提是子树内没有三元上升子序列，因此左子树中小于右子树 \(mx\) 与根的较大值的部分不存在二元上升子序列，同理，右子树中大于左子树 \(mn\) 与根的较小值的部分不存在二元上升子序列。换句话说，就是左子树中小于右子树 \(mx\) 与根的较大值的部分单调不升，右子树中大于左子树 \(mn\) 与根的较小值的部分也单调不升。

那么就可以直接进子树平衡树上二分了，对于 \(pmn\) 就是找右子树最右侧的大于的，\(pmx\) 就是找左子树最左侧的小于的。

时间复杂度 \(O(n\log^2 n)\)。

点击查看代码 
int n,q;

struct fhq_Treap{
    int rt,ch[maxn][2];
    int val[maxn],pri[maxn];
    int siz[maxn],mn[maxn],mx[maxn];
    int pmn[maxn],pmx[maxn];
    bool tag[maxn];
    int st[maxn],top;
    inline void input(){
        val[1]=inf,val[n+2]=-inf;
        for(int i=2;i<=n+1;++i) val[i]=read();
        for(int i=1;i<=n+2;++i){
            pri[i]=rand(1,1000000000);
            siz[i]=1,mn[i]=mx[i]=val[i];
            pmn[i]=inf,pmx[i]=-inf;
            tag[i]=false;
        }
    }
    inline int query_max(int x,int k){
        while(1){
            if(ch[x][0]&&mn[ch[x][0]]<k) x=ch[x][0];
            else if(val[x]<k) return val[x];
            else x=ch[x][1];
        }
    }
    inline int query_min(int x,int k){
        while(1){
            if(ch[x][1]&&mx[ch[x][1]]>k) x=ch[x][1];
            else if(val[x]>k) return val[x];
            else x=ch[x][0];
        }
    }
    inline void push_up(int x){
        if(!ch[x][0]&&!ch[x][1]){
            siz[x]=1,mn[x]=mx[x]=val[x];
            pmn[x]=inf,pmx[x]=-inf;
            tag[x]=false;
        }
        else if(!ch[x][1]){
            siz[x]=siz[ch[x][0]]+1,mn[x]=min(mn[ch[x][0]],val[x]),mx[x]=max(mx[ch[x][0]],val[x]);
            pmn[x]=pmn[ch[x][0]],pmx[x]=pmx[ch[x][0]];
            tag[x]=tag[ch[x][0]]|(pmn[ch[x][0]]<val[x]);
            if(!tag[x]){
                if(mn[ch[x][0]]<val[x]){
                    pmn[x]=min(pmn[x],val[x]);
                    pmx[x]=max(pmx[x],query_max(ch[x][0],val[x]));
                }
            }
        }
        else if(!ch[x][0]){
            siz[x]=siz[ch[x][1]]+1,mn[x]=min(mn[ch[x][1]],val[x]),mx[x]=max(mx[ch[x][1]],val[x]);
            pmn[x]=pmn[ch[x][1]],pmx[x]=pmx[ch[x][1]];
            tag[x]=tag[ch[x][1]]|(val[x]<pmx[ch[x][1]]);
            if(!tag[x]){
                if(val[x]<mx[ch[x][1]]){
                    pmn[x]=min(pmn[x],query_min(ch[x][1],val[x]));
                    pmx[x]=max(pmx[x],val[x]);
                }
            }
        }
        else{
            siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1,mn[x]=min({mn[ch[x][0]],mn[ch[x][1]],val[x]}),mx[x]=max({mx[ch[x][0]],mx[ch[x][1]],val[x]});
            pmn[x]=min(pmn[ch[x][0]],pmn[ch[x][1]]),pmx[x]=max(pmx[ch[x][0]],pmx[ch[x][1]]);
            tag[x]=tag[ch[x][0]]|tag[ch[x][1]]|(pmn[ch[x][0]]<max(mx[ch[x][1]],val[x]))|(min(mn[ch[x][0]],val[x])<pmx[ch[x][1]]);
            if(!tag[x]){
                if(mn[ch[x][0]]<val[x]) pmn[x]=min(pmn[x],val[x]);
                if(val[x]<mx[ch[x][1]]) pmx[x]=max(pmx[x],val[x]);
                if(mn[ch[x][0]]<max(mx[ch[x][1]],val[x])){
                    pmx[x]=max(pmx[x],query_max(ch[x][0],max(mx[ch[x][1]],val[x])));
                }
                if(min(mn[ch[x][0]],val[x])<mx[ch[x][1]]){
                    pmn[x]=min(pmn[x],query_min(ch[x][1],min(mn[ch[x][0]],val[x])));
                }
            }
        }
    }
    void dfs(int x){
        if(!ch[x][0]&&!ch[x][1]) return;
        if(ch[x][0]) dfs(ch[x][0]);
        if(ch[x][1]) dfs(ch[x][1]);
        push_up(x);
    }
    inline void build(){
        top=0;
        for(int i=1;i<=n+2;++i){
            int now=top;
            while(now&&pri[st[now]]>pri[i]) --now;
            if(now) ch[st[now]][1]=i;
            if(now!=top) ch[i][0]=st[now+1];
            top=now;
            st[++top]=i;
        }
        rt=st[1];
        dfs(rt);
    }
    int merge(int x,int y){
        if(!x||!y) return x+y;
        if(pri[x]<pri[y]){
            ch[x][1]=merge(ch[x][1],y);
            push_up(x);
            return x;
        }
        else{
            ch[y][0]=merge(x,ch[y][0]);
            push_up(y);
            return y;
        }
    }
    void split(int p,int k,int &x,int &y){
        if(!p) x=0,y=0;
        else{
            if(siz[ch[p][0]]+1<=k) x=p,split(ch[p][1],k-(siz[ch[p][0]]+1),ch[x][1],y);
            else y=p,split(ch[p][0],k,x,ch[y][0]);
            push_up(p); 
        }
    }
    inline void solve(int l,int r,int k){
        int a,b,c,d;
        split(rt,r+1,c,d);
        split(c,l,a,c);
        split(c,r-l+1-k,b,c);
        rt=merge(merge(merge(a,c),b),d);
        if(tag[rt]) printf("YES\n");
        else printf("NO\n");
    }
}T;

int main(){
    n=read();
    T.input();
    T.build();
    q=read();
    while(q--){
        int l=read(),r=read(),k=read();
        T.solve(l,r,k);
    }
    return 0;
}

标签：ch,考后,int,siz,mx,maxn,pmn,CSP,模拟
From： https://www.cnblogs.com/SoyTony/p/Simulation_Problems_of_CSP-S_in_September_3.html

相关文章

  • 模拟赛记录
    打摆不知道干什么的时候来写写吧，毕竟高二了。教练让我们不要在网上写题解，那我觉得流水账应该没啥问题。毕竟复盘自己的模拟赛状态应该还是蛮重要的吧...？9.9zzfls联考搬题搬一整套是吧/qd但是题目质量还是可以的。虽然有T3这样的要不然不会要不然会100的不是很OI风的......
  • 接口未通时，模拟接口返回数据
    调用接口未接通时，可以用Promise.resolve()或者Promise.reject()模拟成功和失败的返回eg：正常写法exportfunctiongetData(){returnrequest({method:'get',url:'xxx'})}模拟成功exportfunctiongetData(){returnresolve({cod......
  • 校内模拟赛赛后总结
    前记（开始写于\(2023.9.9\)）（本来是不想写的，但是看到学长以及身边人都写，思考了一下，感觉有点用，于是也写了）（里面也写了一些闲话）（以前的比赛我就记个排名得了，懒得补了）7.20~7.22CSP模拟1~3没考7.24CSP模拟4(rk6)7.25CSP模拟5(rk3)7.26CSP模拟6(rk23)7.27......
  • 【230911-3】☆反炮兵听声辨位之三点定敌炮(鼠标左键点击模拟敌发炮)位置
    【说明】使用鼠标点击左键模拟敌炮发射，两条双曲线交汇位置即敌炮所在位置。【图示】【代码】<!DOCTYPEhtml><htmllang="utf-8"><metahttp-equiv="Content-Type"content="text/html;charset=utf-8"/><head><title>反炮兵听声辨位之三点定敌炮(鼠标左键点击模拟敌发炮)......
  • 国内项目管理中级证书CSPM-3正在报名！
    CSPM-3中级项目管理专业人员认证，是中国标准化协会（全国项目管理标准化技术委员会秘书处），面向社会开展项目管理专业人员能力的等级证书。旨在构建多层次从业人员培养培训体系，建立健全人才职业能力评价和激励机制的要求，培养我国项目管理领域复合型人才。  2023年9月6日，中国标准化协会......
  • 安卓模拟器第二弹（补充说明）
    ❝关于模拟器的问题其实之前已经发了一篇文章了，这里主要是再进行补充说明❞目前我常用的有两个分别是雷电模拟器和网易MUMU模拟器这两个模拟器各有千秋，都不错！网易MUMU模拟器说起网易MUMU模拟器，就不得不说一说一件事了，那就是adb会不会自动连接的问题这可能是我的错觉，我以前用雷电模......
  • 230909 NOIP 模拟赛 T1 cake 题解
    原题题意有一块\(n\timesm\)\((1\len,m\le14)\)的蛋糕，每个位置上有一个权值\(a_{i,j}\)\((1\lea_{i,j}\le1000)\)，现在你要把它切开。每次你可以平行与某一边界把蛋糕切开，所以共有\(n-1\)个可以竖着切的位置，以及\(m-1\)个可以横着切的位置。对于每一组\(i,j\)\(......
  • 2023年9月CSPM-3国标项目管理中级认证报名，哪有？
    CSPM-3中级项目管理专业人员评价，是中国标准化协会（全国项目管理标准化技术委员会秘书处），面向社会开展项目管理专业人员能力的等级证书。旨在构建多层次从业人员培养培训体系，建立健全人才职业能力评价和激励机制的要求，培养我国项目管理领域复合型人才。  【证书含金量】 ·竞聘优先......
  • Edge浏览器没有让我失望! 今天终于可以在win10中模拟IE内核进行前端测试了,以后就用它
    ......
  • CSP-S2022初赛易错题解析
    一.2.错误原因：不会解析：real代表实际运行时间，user代表用户态运行时间，sys表示内核态运行时间，故选A 5.错误原因：不会解析：基数排序的思路类似于桶排序，故选A 9.错误原因：不会解析：这个问题可以转化成圆排列问题，公式为A(n-1,n-1)，即(n-1)!,要考虑从两个方向看的图，所以要除......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99