首页 > 其他分享 >【考后总结】8 月 CSP 模拟赛 8

【考后总结】8 月 CSP 模拟赛 8

时间：2023-08-21 17:48:24浏览次数：45  
标签：考后 int void tr id dfn maxn CSP 模拟

8.21 CSP 模拟 27

晴天 - 周杰伦

故事的小黄花 从出生那年就飘着

童年的荡秋千 随记忆一直晃到现在

Re So So Si Do Si La

So La Si Si Si Si La Si La So

吹着前奏 望着天空

我想起花瓣试着掉落

为你翘课的那一天 花落的那一天

教室的那一间 我怎么看不见

消失的下雨天 我好想再淋一遍

没想到 失去的勇气我还留着

好想再问一遍 你会等待还是离开

刮风这天 我试过握着你手

但偏偏 雨渐渐 大到我看你不见

还要多久 我才能在你身边

等到放晴的那天 也许我会比较好一点

从前从前 有个人爱你很久

但偏偏 风渐渐 把距离吹得好远

好不容易 又能再多爱一天

但故事的最后

你好像还是说了 拜拜

为你翘课的那一天 花落的那一天

教室的那一间 我怎么看不见

消失的下雨天 我好想再淋一遍

没想到 失去的勇气我还留着

好想再问一遍 你会等待还是离开

刮风这天 我试过握着你手

但偏偏 雨渐渐 大到我看你不见

还要多久 我才能在你身边

等到放晴的那天 也许我会比较好一点

从前从前 有个人爱你很久

偏偏 风渐渐 把距离吹得好远

好不容易 又能再多爱一天

但故事的最后

你好像还是说了 拜拜

刮风这天 我试过握着你手

但偏偏 雨渐渐 大到我看你不见

还要多久 我才能够在你身边

等到放晴那天 也许我会比较好一点

从前从前 有个人爱你很久

但偏偏 雨渐渐 把距离吹得好远

好不容易 又能再多爱一天

但故事的最后

你好像还是说了拜

\(\text{ZZ\_zuozhe round}\)

T1 道路

原题：CodeForces-1060E Sergey and Subway *2000

答案是：

\[\sum_{u=1}^n\sum_{v=u+1}^n \left\lceil\dfrac{\mathrm{dist}(u,v)}{2}\right\rceil \]

DFS 求就行了。

点击查看代码 
int n;
struct edge{
    int to,nxt;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v){
    e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
    e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
int siz[maxn][2];
ll sum[maxn][2],ans;
void dfs(int u,int f){
    siz[u][0]=1;
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        if(v==f) continue;
        dfs(v,u);
        int siz0=siz[v][1],siz1=siz[v][0];
        ll sum0=sum[v][1],sum1=sum[v][0]+siz[v][0];
        ans=(ans+sum[u][0]*siz0+sum0*siz[u][0]);
        ans=(ans+sum[u][1]*siz0+sum0*siz[u][1]);
        ans=(ans+sum[u][0]*siz1+sum1*siz[u][0]);
        ans=(ans+sum[u][1]*siz1+sum1*siz[u][1]-1ll*siz[u][1]*siz1);
        siz[u][0]+=siz0,siz[u][1]+=siz1;
        sum[u][0]+=sum0,sum[u][1]+=sum1;
    }
}

int main(){
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    n=read();
    for(int i=1,u,v;i<n;++i){
        u=read(),v=read();
        add_edge(u,v);
    }
    dfs(1,0);
    printf("%lld\n",ans);
    return 0;
}

T2 集合

原题：CodeForces-979D Kuro and GCD and XOR and SUM *2200

如果没有第二条限制可以直接建 01-Trie 之后贪心，发现值域不大，因此建 \(w\) 棵 01-Trie，每棵只存储倍数，查询就是在第 \(k\) 棵查询。时间复杂度 \(O(w\sqrt{w}+q\log^2 w)\)。

点击查看代码 
int q;
vector<int> D[maxn];

struct Trie{
    int tot;
    vector<int> tr[2],mn;
    inline void build(int k){
        tr[0].resize(lim/k*20);
        tr[1].resize(lim/k*20);
        mn.resize(lim/k*20);
        mn[0]=inf;
    }
    inline void insert(int x){
        mn[0]=min(mn[0],x);
        int u=0;
        for(int k=16;k>=0;--k){
            if(!tr[(x>>k)&1][u]) tr[(x>>k)&1][u]=++tot,mn[tot]=x;
            u=tr[(x>>k)&1][u];
            mn[u]=min(mn[u],x);
        }
    }
    inline void query(int x,int s){
        int u=0,res=0;
        if(mn[0]>s) return printf("-1\n"),void();
        bool lim=true;
        for(int k=16;k>=0;--k){
            if((x>>k)&1){
                if(tr[0][u]){
                    if(lim&&((s>>k)&1)) lim=false;
                    u=tr[0][u];
                }
                else{
                    u=tr[1][u];
                    res|=(1<<k);
                }
            }
            else{
                if(tr[1][u]&&(!lim||((s>>k)&1))&&mn[tr[1][u]]<=s){
                    u=tr[1][u];
                    res|=(1<<k);
                }
                else{
                    if(lim&&((s>>k)&1)) lim=false;
                    u=tr[0][u];
                }
            }
        }
        printf("%d\n",res);
    }
}T[maxn];

int main(){
    freopen("set.in","r",stdin);
    freopen("set.out","w",stdout);
    q=read();
    for(int i=1;i<=lim;++i){
        for(int j=1;j*j<=i;++j){
            if(i%j) continue;
            D[i].push_back(j);
            if(j*j!=i) D[i].push_back(i/j);
        }
        T[i].build(i);
    }
    for(int i=1,opt,x,k,s;i<=q;++i){
        opt=read();
        if(opt==1){
            x=read();
            for(int d:D[x]) T[d].insert(x);
        }
        else{
            x=read(),k=read(),s=read();
            if(x%k) printf("-1\n");
            else T[k].query(x,s-x);
        }
    }
    return 0;
}

T3 科目五

原题：CodeForces-1101F Trucks and Cities *2400

发现 \(c\) 对答案的影响只是倍数，考虑 \(f_{l,r,k}\) 表示从 \(l\) 到 \(r\)，中间加油 \(k\) 次的最小容量，转移有：

\[f_{l,r,k}=\min_{i=l+1}^{r-1} \{f_{l,i,k-1}+(x_r-x_i)\} \]

具有决策单调性，分治预处理，复杂度 \(O(n^3\log n+m)\)。

点击查看代码 
int n,m;
int x[maxn];
int f[maxn][maxn][maxn];
void solve(int L,int K,int l1,int r1,int l2,int r2){
    if(l1>r1) return;
    int mid1=(l1+r1)>>1;
    int p;
    for(int j=l2;j<=min(mid1-1,r2);++j){
        if(max(f[L][j][K-1],f[j][mid1][0])<f[L][mid1][K]){
            f[L][mid1][K]=max(f[L][j][K-1],f[j][mid1][0]);
            p=j;
        }
    }
    if(l1==r1) return;
    solve(L,K,l1,mid1-1,l2,p),solve(L,K,mid1+1,r1,p,r2);
}
ll ans;
int main(){
    freopen("drive.in","r",stdin);
    freopen("drive.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;++i) x[i]=read();
    memset(f,0x3f,sizeof(f));
    for(int l=1;l<=n;++l){
        for(int r=l+1;r<=n;++r){
            f[l][r][0]=x[r]-x[l];
        }
    }
    for(int k=1;k<=n-2;++k){
        for(int l=1;l+k+1<=n;++l){
            solve(l,k,l+k+1,n,l+k,n);
        }
    }
    for(int i=1,s,t,c,r;i<=m;++i){
        s=read(),t=read(),c=read(),r=read();
        r=min(r,t-s-1);
        ans=max(ans,1ll*f[s][t][r]*c);
    }
    printf("%lld\n",ans);
    return 0;
}

T4 监狱

原题：AtCoder-JOISC2022A 刑務所

考虑一个出发的先后关系，对于路径 \(i\) 和 \(j\)，如果 \(i\) 的起点被 \(j\) 包含，那么 \(i\) 应当在 \(j\) 之前出发；如果 \(i\) 的终点被 \(j\) 包含，那么 \(i\) 应当在 \(j\) 之后出发，建图跑拓扑排序。

考虑线段树优化建图，\(i\) 对应节点向起点 \(u_i\) 的内向树对应叶子连边，同时 \((u_i,v_i)\) 树剖得到的区间在外向树节点连向 \(i\) 对应节点；同理终点 \(v_i\) 的外向树对应对应向 \(i\) 对应节点连边，同时 \(i\) 对应节点连向 \((u_i,v_i)\) 树剖得到的区间在内向树节点。

这样建图可以使得 \(i\) 经过起点 \(u_i\) 在内向树到达包含其的所有区间并到达 \(j\)，终点同理。

但这样连边天然成环，注意一个节点只会作为一条路径的起点，那么外向树连边时漏过起点，可以去掉这个环，终点同理。

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

点击查看代码 
int t;
int n,m;
vector<int> E[maxn];
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) 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==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
struct edge{
    int to,nxt;
}e[maxn*80];
int head[maxn*9],cnt;
int deg[maxn*9];
inline void add_edge(int u,int v){
    ++deg[v];
    e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int pos[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
    void build(int rt,int l,int r){
        if(l==r) return pos[l]=rt,void();
        add_edge(rt,rt<<1),add_edge(rt,rt<<1|1);
        add_edge(4*n+(rt<<1),4*n+rt),add_edge(4*n+(rt<<1|1),4*n+rt);
        build(lson),build(rson);
    }
    void update(int rt,int l,int r,int p,int pl,int pr){
        if(pl<=l&&r<=pr){
            add_edge(p,rt);
            add_edge(4*n+rt,p);
            return;
        }
        if(pl<=mid) update(lson,p,pl,pr);
        if(pr>mid) update(rson,p,pl,pr);
    }
    void update1(int rt,int l,int r,int p,int pl,int pr){
        if(pl>pr) return;
        if(pl<=l&&r<=pr){
            add_edge(p,rt);
            return;
        }
        if(pl<=mid) update1(lson,p,pl,pr);
        if(pr>mid) update1(rson,p,pl,pr);
    }
    void update2(int rt,int l,int r,int p,int pl,int pr){
        if(pl>pr) return;
        if(pl<=l&&r<=pr){
            add_edge(4*n+rt,p);
            return;
        }
        if(pl<=mid) update2(lson,p,pl,pr);
        if(pr>mid) update2(rson,p,pl,pr);
    }
#undef mid
#undef lson
#undef rson
}S;

inline void update(int u,int v,int id){
    add_edge(8*n+id,4*n+pos[dfn[u]]);
    add_edge(pos[dfn[v]],8*n+id);
    int x=u,y=v;
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]]) swap(u,v);
        if(v!=x&&v!=y) S.update(1,1,n,8*n+id,dfn[top[v]],dfn[v]);
        else{
            S.update(1,1,n,8*n+id,dfn[top[v]],dfn[v]-1);
            if(v==x) add_edge(8*n+id,pos[dfn[x]]);
            else add_edge(4*n+pos[dfn[y]],8*n+id);
        }
        v=fa[top[v]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    if(u!=y&&v!=y) S.update1(1,1,n,8*n+id,dfn[u],dfn[v]);
    else if(u!=v){
        if(u==y) S.update1(1,1,n,8*n+id,dfn[u]+1,dfn[v]);
        else S.update1(1,1,n,8*n+id,dfn[u],dfn[v]-1);
    }
    if(u!=x&&v!=x) S.update2(1,1,n,8*n+id,dfn[u],dfn[v]);
    else if(u!=v){
        if(u==x) S.update2(1,1,n,8*n+id,dfn[u]+1,dfn[v]);
        else S.update2(1,1,n,8*n+id,dfn[u],dfn[v]-1);
    }
}
queue<int> q;

int main(){
    freopen("prison.in","r",stdin);
    freopen("prison.out","w",stdout);
    t=read();
    while(t--){
        n=read();
        cnt=0;
        for(int i=1;i<=n;++i){
            fa[i]=dep[i]=siz[i]=son[i]=0;
            top[i]=dfn[i]=0;
            E[i].clear();
        }
        for(int i=1,u,v;i<n;++i){
            u=read(),v=read();
            E[u].push_back(v),E[v].push_back(u);
        }
        dfs1(1,0,0);
        dfs2(1,1);
        m=read();
        for(int i=1;i<=8*n+m;++i) head[i]=0,deg[i]=0;
        dfncnt=0;
        S.build(1,1,n);
        for(int i=1,u,v;i<=m;++i){
            u=read(),v=read();
            update(u,v,i);
        }
        for(int i=1;i<=8*n+m;++i){
            if(!deg[i]) q.push(i);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=head[u],v;i;i=e[i].nxt){
                v=e[i].to;
                --deg[v];
                if(!deg[v]) q.push(v);
            }
        }
        bool chk=true;
        for(int i=1;i<=8*n+m;++i){
            if(deg[i]){
                chk=false;
                break;
            }
        }
        if(chk) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

反思

T2 看到值域很小没有意识到暴力建约数 01-Trie。

T3 暴力二分 \(O(nm\log w)\)，\(mid\) 开 int 喜挂 \(75\)。

T4 想到要线段树优化建图，认为要对路径排序关于路径建线段树，DFS 序的优化做法应当是平凡的。

弱智。

标签：考后,int,void,tr,id,dfn,maxn,CSP,模拟
From： https://www.cnblogs.com/SoyTony/p/Simulation_Problems_of_CSP-S_in_August_8.html

相关文章

  • 2023.8.21 模拟赛
    A多次询问\(l,r\)，求\(\sum_{x=l}^r\sum_{y=x}^ra_x\otimes\gcd(a_x\sima_y)\)，其中$\otimes$是异或。我们先拆解询问，\(Ans=\sum_{x=1}^r\sum_{y=x}^ra_x\otimes\gcd(a_x\sima_y)-\sum_{x=1}^{l-1}\sum_{y=x}^ra_x\otimes\gcd(a_x\sima_y)\)然后离线处理一下......
  • 模拟SSH爆破攻击
    第一步开启靶机的SSH服务开启步骤：打开终端并以root用户身份登录（第二步kali自带SSH服务器的可省略）使用以下命令安装SSH服务器apt-getupdateapt-getinstallopenssh-server安装完成后。SSH服务将自动启动。可使用以下命令检查SSH服务的状态servicesshstatus......
  • 使用JMeter模拟设备通过MQTT发送数据
    需求：需要一个工具能够支持MQTT协议发送各种不同的数据。目的：模拟小型温室设备反馈，搭建一个测试环境，根据测试的数据显示硬件的状态和数值。工具：JMeter环境：需要配置Java运行环境。操作步骤：1.下载JMeter运行包下载地址：https://jmeter.apache.org/download_jmeter.cgi，下载后可以解压......
  • CSP-J2022 复盘
    T1乘方方法\(1\)：使用快速幂，判断答案是否\(\geq10^9\)。方法\(2\)：特判\(1\)的情况，其余的可以直接乘。此处给出方法\(2\)的代码。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;lla,b;intmain(){ cin>>a>>b; if(a==1)cout<<1; else{ ......
  • 模拟集成电路设计系列博客——1.1.6 输出阻抗增强电流镜
    1.1.6输出阻抗增强电流镜另一种常用的Cascode电流镜的变种是输出阻抗增强电流镜，一种简单电路形式如下图所示：其基本思路是利用一个反馈放大器来尽可能地保证\(Q_2\)两端地漏源电压尽可能地稳定，而不需要考虑输出电压。添加了这个放大器后，理想上将Cascode电流镜地输出阻抗增大了1......
  • 《串口篇》实现模拟串口通信（未验证）
    实现串口通信参考链接：https://www.jb51.net/article/279177.htm新建项目出于简单考虑，首先创建一个Winform项目，本文项目名称为portTest。串口通信，至少有两个串口才能通信，所以拖动两个GroupBox，一左一右，里面分别放置一个Combobox、一个按钮，以及两个TextBox用于发送和接收内容，第二......
  • CSP-J 模拟赛 C 题讲解
    前言鸣谢：感谢LHT大佬的推荐、GCK大佬的提醒以及LBJ大佬帮我接龙。原题链接随手给大家扔一份吧。题目大意给你一个\(1\)到\(n\)的数列，当\(a_i<a_{i-1}\)的时候（大于号和小于号其实不用管，因为最后所有方案都会遍历到，对答案没有影响）放置一个红色灯笼，否则放置一个绿......
  • java脚本模拟服务器内存溢出实战&服务器部署java项目
    一、背景：使用javaspringboot,实现linux服务器内存溢出情况。二、方案1、打包成war包，可以直接将war包部署在tomcat容器里2、springboot，打包成jar包。打的jar包，内置了tomcat，所以在服务器上，直接启jar包就行，没有必要放在tomcat容器里部署，在启动jar包时，可以配置线程池等。这......
  • 模拟实现简单的list
    这篇博客主要是关于使用模板实现list的模拟。什么是list：list是一种序列式容器，可以在常数时间内在任意位置进行插入和删除操作，并且支持前后双向迭代。list的底层是双向链表结构，每个元素存储在独立的节点中，节点通过指针指向前一个元素和后一个元素。list与forward_list非常相似，最主......
  • NOIP模拟2总结
    NOIP模拟2总结目录NOIP模拟2总结整体上：个体上第一题：zerosEGOI2021day1t1第二题：lunaEGOI2021day1t2第三题：cowsEGOI2021day2t3第四题：lanternsEGOI整体上：T1非常简单，但是在简单的T2耗费了大量的时间用于证明，导致简单的T3题都没看就跳过，T4暴力没得分个体上第一题：zero......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99