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

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

时间:2023-08-24 16:35:16浏览次数:49  
标签:考后 int siz free break maxn want CSP 模拟

8.24 CSP 模拟 29

I Want to Break Free - Queen

I want to break free

I want to break free

I want to break free from your lies

You're so self satisfied I don't need you

I've got to break free

God knows, God knows I want to break free

I've fallen in love

I've fallen in love for the first time

And this time I know it's for real

I've fallen in love yeah

God knows God knows I've fallen in love

It's strange but it's true

I can't get over the way you love me like you do

But I have to be sure

When I walk out that door

Oh how I want to be free baby

Oh how I want to be free

Oh how I want to break free

But life still goes on

I can't get used to living without living without

Living without you by my side

I don't want to live alone hey

God knows got to make it on my own

So baby can't you see

I've got to break free

I've got to break free

I want to break free yeah

I want, I want, I want, I want to break free

\(\text{ZZ_zuozhe round}\)

T1 树篱之途

原题:CodeForces-685B Kay and Snowflake *1900

判定重心方法是 \(ct=\operatorname{argmin}_{u\in \mathrm{subtree}(rt)} \{\max(\max_{v\in \mathrm{son}(u)}\{siz_v\},siz_{rt}-siz_u)\}\)。

对于节点 \(u\),若已知其儿子 \(v\) 的重心 \(ct\),那么 \(u\) 的重心 \(ct'\) 如果在 \(v\) 子树中则一定在 \((u,ct)\) 路径上,因此可以暴力与 \(ct\) 的父亲比较谁更优,若父亲更优向上跳,否则停止。这样找到每棵子树最优的,再取最优即可。

注意比较过程应当与父亲比较而不是与当前重心比较。

点击查看代码
int n;
struct edge{
    int to,nxt;
}e[maxn];
int head[maxn],cnt;
inline void add_edge(int u,int v){
    e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}
int fa[maxn],siz[maxn],mxsiz[maxn],ct[maxn];
void dfs(int u,int f){
    fa[u]=f,siz[u]=1,mxsiz[u]=0;
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        dfs(v,u);
        siz[u]+=siz[v],mxsiz[u]=max(mxsiz[u],siz[v]);
    }
    ct[u]=u;
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        int x=ct[v];
        while(x!=u){
            if(max(mxsiz[fa[x]],siz[u]-siz[fa[x]])<max(mxsiz[x],siz[u]-siz[x])) x=fa[x];
            else break;
        }
        if(max(mxsiz[x],siz[u]-siz[x])<max(mxsiz[ct[u]],siz[u]-siz[ct[u]])) ct[u]=x;
    }
}

int main(){
    freopen("cent.in","r",stdin);
    freopen("cent.out","w",stdout);
    n=read();
    for(int u,v=2;v<=n;++v){
        u=read();
        add_edge(u,v);
    }
    dfs(1,0);
    for(int i=1;i<=n;++i) printf("%d\n",ct[i]);
    return 0;
}

T2 坍缩

原题:CodeForces-1080E Sonya and Matrix Beauty *2400

考虑固定列 \([l,r]\),那么一行可以重排成回文当且仅当其出现次数为奇数的
字符不超过一种,可以使用 \(\bigoplus 2^c\) 异或哈希判断。

之后要求两行重排相等,也就是字符可重集完全相同,这部分可以使用 \(\sum base^c\) 哈希判断。之后求回文使用 Manacher,时间复杂度 \(O(n^3)\)。

点击查看代码
int n,m;
int pw[26];
char s[255][255];
int sum[255][255],xorsum[255][255];
int ch[255],now[505],D[505];
int ans;
inline void check(int u,int d){
    if(u>d) return;
    int len=2*(d-u+1)+1;
    now[1]=mod+1;
    for(int i=u;i<=d;++i) now[2*(i-u+1)]=ch[i],now[2*(i-u+1)+1]=mod+1;
    for(int i=1,l,r=-1;i<=len;++i){
        int j=(l+r)-i,k;
        if(i>r) k=0;
        else k=min(D[j],r-i+1);
        while(i+k<=len&&i-k>=1&&now[i-k]==now[i+k]) ++k;
        D[i]=k;
        ans+=D[i]/2;
        if(i+k-1>r) l=i-k+1,r=i+k-1;
    }
}

int main(){
    freopen("pal.in","r",stdin);
    freopen("pal.out","w",stdout);
    pw[0]=1;
    for(int i=1;i<26;++i) pw[i]=1ll*pw[i-1]*base%mod;
    n=read(),m=read();
    for(int i=1;i<=n;++i){
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;++j){
            sum[i][j]=(sum[i][j-1]+pw[s[i][j]-'a'])%mod;
            xorsum[i][j]=xorsum[i][j-1]^(1<<(s[i][j]-'a'));
        }
    }
    for(int l=1;l<=m;++l){
        for(int r=l;r<=m;++r){
            int last=0;
            for(int i=1;i<=n;++i){
                int range_sum=(sum[i][r]-sum[i][l-1]+mod)%mod,range_xor=xorsum[i][r]^xorsum[i][l-1];
                if(__builtin_popcount(range_xor)>1){
                    check(last+1,i-1);
                    last=i;
                    continue;
                }
                ch[i]=range_sum;
            }
            check(last+1,n);
        }
    }
    printf("%d\n",ans);
    return 0;
}

T3 诡意行商

原题:CodeForces-1023F Mobile Phone Network *2600

把 \(k\) 条边边权设为 \(0\),求出最小生成树,非树边 \((u,v)\) 会使得树上 \((u,v)\) 路径上所有边边权不得超过非树边边权,因此树剖区间取 \(\min\),从大到小排序变为区间覆盖。

点击查看代码
int n,k,m;
struct edge{
    int u,v,w;
    bool mark;
    edge()=default;
    edge(int u_,int v_,int w_,bool mark_):u(u_),v(v_),w(w_),mark(mark_){}
    bool operator<(const edge &rhs)const{
        return w<rhs.w;
    }
}e[maxn<<1];

int bel[maxn];
int find(int x){
    if(x==bel[x]) return x;
    else return bel[x]=find(bel[x]);
}
vector<int> E[maxn];
inline void Kruskal(){
    for(int i=1;i<=n;++i) bel[i]=i;
    sort(e+1,e+k+m+1);
    for(int i=1,u,v;i<=k+m;++i){
        u=e[i].u,v=e[i].v;
        int fu=find(u),fv=find(v);
        if(fu==fv) continue;
        bel[fv]=fu;
        E[u].push_back(v),E[v].push_back(u);
        e[i].mark=true;
    }

}

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

int val[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];
    void build(int rt,int l,int r){
        if(l==r) return tag[rt]=inf,void();
        build(lson),build(rson);
    }
    inline void push_down(int rt){
        if(tag[rt]){
            tag[rt<<1]=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 val[l]=tag[rt],void();
        push_down(rt);
        dfs(lson),dfs(rson);
    }
#undef mid
#undef lson
#undef rson
}S;

inline void update(int u,int v,int w){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]]) swap(u,v);
        S.update(1,1,n,dfn[top[v]],dfn[v],w);
        v=fa[top[v]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    if(u!=v) S.update(1,1,n,dfn[u]+1,dfn[v],w);
}

ll ans;

int main(){
    freopen("trade.in","r",stdin);
    freopen("trade.out","w",stdout);
    n=read(),k=read(),m=read();
    for(int i=1,u,v;i<=k;++i){
        u=read(),v=read();
        e[i]=edge(u,v,0,false);
    }
    for(int i=1,u,v,w;i<=m;++i){
        u=read(),v=read(),w=read();
        e[k+i]=edge(u,v,w,false);
    }
    Kruskal();
    dfs1(1,0,0);
    dfs2(1,1);
    S.build(1,1,n);
    for(int i=k+m;i>k;--i){
        if(e[i].mark) continue;
        update(e[i].u,e[i].v,e[i].w);
    }
    S.dfs(1,1,n);
    for(int i=1;i<=k;++i){
        int now=max(dfn[e[i].u],dfn[e[i].v]);
        if(val[now]==inf) return printf("-1\n"),0;
        ans+=val[now];
    }
    printf("%lld\n",ans);
    return 0;
}

T4 越过群山

原题:AtCoder-JOISC2022B 京都観光

考虑行 \(x<y<z\),列 \(l<r\),那么有三种移动方式:

  • \((x,l)\to (x,r)\to (z,r)\),代价 \((r-l)a_x+(z-x)b_r\)。

  • \((x,l)\to (z,l)\to (z,r)\),代价 \((r-l)a_z+(z-x)b_l\)。

  • \((x,l)\to (y,l)\to (y,z)\to (z,r)\),代价 \((r-l)a_y+(y-x)b_l+(z-y)b_r\)。

经过 \(y\) 的条件时后者小于前面两个式子,移项整理得到:

\[\dfrac{a_y-a_x}{y-x}<\dfrac{b_r-b_l}{r-l}<\dfrac{a_z-a_y}{z-y} \]

因此对 \(a\) 维护一下下凸壳,\(b\) 同理。

现在就只考虑是向下或向右了,把前两个式子比较,有:

\[(r-l)a_x+(z-x)b_r<(r-l)a_z+(z-x)b_l\Rightarrow \dfrac{b_r-b_l}{r-l}<\dfrac{a_z-a_x}{z-x} \]

因此每次会选择沿斜率较小的方向移动,维护两个指针分别在两个凸包上移动即可。

点击查看代码
int n,m;
int a[maxn],b[maxn];

inline bool check_slope_a(int x,int y,int z){
    ll lhs=1ll*(a[y]-a[x])*(z-y),rhs=1ll*(a[z]-a[y])*(y-x);
    return lhs>=rhs;
}
inline bool check_slope_b(int x,int y,int z){
    ll lhs=1ll*(b[y]-b[x])*(z-y),rhs=1ll*(b[z]-b[y])*(y-x);
    return lhs>=rhs;
}
inline bool check_slope_ab(int x,int y,int l,int r){
    ll lhs=1ll*(a[y]-a[x])*(r-l),rhs=1ll*(b[r]-b[l])*(y-x);
    return lhs<rhs;
}

int sta[maxn],topa;
int stb[maxn],topb;

ll ans;

int main(){
    freopen("grid.in","r",stdin);
    freopen("grid.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=m;++i) b[i]=read();
    sta[++topa]=1;
    for(int i=2;i<=n;++i){
        while(topa>1&&check_slope_a(sta[topa-1],sta[topa],i)) --topa;
        sta[++topa]=i;
    }
    stb[++topb]=1;
    for(int i=2;i<=m;++i){
        while(topb>1&&check_slope_b(stb[topb-1],stb[topb],i)) --topb;
        stb[++topb]=i;
    }
    int i=1,j=1;
    while(i<topa||j<topb){
        if(i==topa){
            ans+=1ll*(stb[j+1]-stb[j])*a[sta[i]];
            ++j;
        }
        else if(j==topb){
            ans+=1ll*(sta[i+1]-sta[i])*b[stb[j]];
            ++i;
        }
        else{
            if(check_slope_ab(sta[i],sta[i+1],stb[j],stb[j+1])){
                ans+=1ll*(sta[i+1]-sta[i])*b[stb[j]];
                ++i;
            }
            else{
                ans+=1ll*(stb[j+1]-stb[j])*a[sta[i]];
                ++j;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

反思

T1 想到一个 \(O(n\log n)\) 的做法,经过卡常喜提 \(0\) 分。

T4 应当尝试去列式思考什么情况下会走一段路径。

开题顺序还行。

标签:考后,int,siz,free,break,maxn,want,CSP,模拟
From: https://www.cnblogs.com/SoyTony/p/Simulation_Problems_of_CSP-S_in_August_9.html

相关文章

  • 模拟气泡样式
    .bubble{right:0;top:45px;position:absolute;padding:012px;font-size:14px;he......
  • 8.23 模拟赛小记
    A.还是单调队列优化dp的板子,类似昨天C。B.洛谷原题指路:P1758[NOI2009]管道取珠感觉是比较有难度的dp。题目概述:给你两个只有两种字符组成的序列,每次从一个序列末尾取走一位放入新序列的末尾,最后得到k种不同的新序列形态。每种形态有a[i]种不同的操作,求\(\sum_{i......
  • 模拟退火算法代码
    当参加数学建模竞赛时,模拟退火算法是一个常用的解题方法之一。以下是一个简单的模拟退火算法的代码示例,用于解决旅行商问题(TSP):点击查看代码importmathimportrandomdefdistance(point1,point2):#计算两个点之间的欧几里德距离returnmath.sqrt((point1[0]-poi......
  • CSP模拟28
    考废了,无语[CF1681E]LabyrinthAdventures题目链接有点神奇的题;首先可以想到简单dp,设$dp_{i,0|1}$表示在第\(i\)层,从上or右门出的最短路径,显然:\[\begin{cases}dp_{i,0}=\min(dp_{i-1,0}+dis_{0,0},dp_{i-1,1}+dis_{1,0})\\dp_{i,1}=\min(dp_{i-1......
  • 2023.8.23 模拟赛
    A一条蛇,有\(K(K\le6)\)个格子,格子必须连续且不能重叠。在\(n\timesm(n,m\le3000)\)的矩阵中放置,有一些格子是不能放的,问方案数。B一棵树\((n\le50000)\).每次询问\([l1,r1],[l2,r2]\)在\(rt\)为根下两两lca的异或和。先处理以\(rt\)为根的问题,发现\(lca_{......
  • 使用条件变量模拟消费者和生产者
    题目简介生产者和消费者问题是一个经典的多线程同步问题,涉及到一个共享的缓冲区,生产者将数据放入缓冲区,消费者从缓冲区中取出数据。问题的关键是要确保生产者和消费者之间的正确交互,避免生产者在缓冲区满时继续生产,消费者在缓冲区空时继续消费。解决方案使用条件变量是一种常见的解......
  • 题解 P8816 [CSP-J 2022] 上升点列
    P8816[CSP-J2022]上升点列题目大意给定\(n\)个点,你可以任意添加\(k\)个点,从中选择若干点使得序列中任意相邻两点间的欧几里得距离恰好为\(1\)而且横坐标、纵坐标值均单调不减。换言之,求二维最长上升子序列。solution:很容易想到动态规划,根据最长上升子序列的套路,可以......
  • 持有PMP®证书,增持CSPM-2或直接考CSPM-3,哪个好?
    在项目管理领域,PMP®证书和CSPM证书都是非常重要的认证,对于已经持有PMP®证书的项目管理专业人员,接下来是增持CSPM-2还是直接考CSPM-3,需要根据个人的职业发展和需求来决定。 如果您现在是做项目经理不久的话建议先转换CSPM-2,然后再考CSPM-3提升;如果您目前已经是资深项目经理或者......
  • m基于FPGA的高斯白噪声信道模拟系统verilog实现,包含testbench,可以配置不同的SNR和频
    1.算法仿真效果vivado2019.2仿真结果如下:SNR=0db,无频偏SNR=5db,无频偏SNR=25db,无频偏SNR=45db,带频偏2.算法涉及理论知识概要高斯白噪声信道在通信系统中具有重要意义,模拟此类信道有助于评估系统性能。本文提出的FPGA实现系统可以灵活地模拟不同信道条件,为通信系统的设计......
  • m基于FPGA的高斯白噪声信道模拟系统verilog实现,包含testbench,可以配置不同的SNR和频
    1.算法仿真效果vivado2019.2仿真结果如下:   SNR=0db,无频偏   SNR=5db,无频偏   SNR=25db,无频偏   SNR=45db,带频偏   2.算法涉及理论知识概要       高斯白噪声信道在通信系统中具有重要意义,模拟此类信道有助于评估系统性能。本......