首页 > 其他分享 >2024杭电多校第九场

2024杭电多校第九场

时间：2024-08-17 13:26:25浏览次数：9  
标签：rt 杭电多校 ch return int pos 2024 第九 mx

1007

简单博弈，队友做的

#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
int n,a[N+5],b[N+5],A,B;
bool vis[N+5];
inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
void Kafka()
{
    n=read();
    for(int i=1;i<=n;++i) vis[i]=0;
    A=0;for(int i=1;i<=n;++i) A+=(vis[a[i]=read()]),vis[a[i]]=1;
    for(int i=1;i<=n;++i) vis[i]=0;
    B=0;for(int i=1;i<=n;++i) B+=(vis[b[i]=read()]),vis[b[i]]=1;
    if(A==0&&B==0) puts("sha7dow");
    else puts(A>=B?"shuishui":"sha7dow");
}
signed main()
{
    for(int T=read();T--;) Kafka();
    return 0;
}

 

1003 

诈骗题，合并顺序根本不会影响答案（之前见过类似的），模拟一遍就好

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int mod = 998244353;
const int N = 1e6+5;
int w[N];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    int ans=0;
    
    for(int r=n,i=1;i<=n-1;i++,r--){
        if(r==1) break;
        ans+=w[1]*w[r]%mod*((w[r]+w[1])%mod)%mod ;
        ans%=mod;
        w[1]+=w[r];
        w[1]%=mod;
    }
    cout<<ans<<"\n";
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
    return 0;
}

 

1005

没想得很明白，赛时乱搞没过，最后俩队友一起做的

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
int k,x,y,t;
bool all(){
    if (k<=x) return false;
    if(y>=2*x) return true;
    return t*x-k+(t-1)*(y%x)>=x;
}
void Kafka()
{
    cin>>k>>x>>y;
    if(x>y) swap(x,y);
    t=(k+x-1)/x;
    if (all()) cout << "Yes\nYes\n";
    else{
        if (t&1) cout << "Yes\nNo\n";
            else cout << "No\nYes\n";
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--) Kafka();
    return 0;
}

 

1001 

一个显然的结论是k不重要，每位都是独立的

接下来一个显然的想法是构造，尽可能让每个子树内01数量均等

如果不均等的话把奇数数目的子树个数算一下，抽一半出来强制为1，另一半强制为0

最后01可以翻转，答案再*2

#include<bits/stdc++.h>
using namespace std;
const int N=2e5,mod=998244353;
inline int add(int x,int y){return (x+=y)>=mod?x-mod:x;}
inline int sub(int x,int y){return (x-=y)<0?x+mod:x;}
inline int mul(int x,int y){return 1LL*x*y%mod;}
inline int qpow(int x,int y){int res=1;for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);return res;}
int fac[N+5],inv[N+5];
inline int C(int x,int y){return x>y?0:mul(fac[y],mul(inv[x],inv[y-x]));}
int n,k,f[N+5],Siz[N+5];
vector<int> ver[N+5];
inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
void dfs(int x,int fa)
{
    Siz[x]=1,f[x]=1;
    int sum=1;
    for(auto y:ver[x])
    {
        if(y==fa) continue;
        dfs(y,x);
        Siz[x]+=Siz[y];
        f[x]=mul(f[x],f[y]);
        sum+=Siz[y]&1;
    }
    f[x]=mul(f[x],C(sum>>1,sum));
}
void Kafka()
{
    n=read(),k=read();
    for(int i=1;i<=n;++i) ver[i].clear();
    for(int i=2;i<=n;++i) ver[read()].push_back(i);
    dfs(1,0);
//    for(int i=1;i<=n;++i) printf("f[%d]=%d\n",i,f[i]);
    printf("%d\n",qpow(mul((Siz[1]&1)?2:1,f[1]),k));
}
signed main()
{
    fac[0]=1;for(int i=1;i<=N;++i) fac[i]=mul(i,fac[i-1]);
    inv[N]=qpow(fac[N],mod-2);for(int i=N-1;~i;--i) inv[i]=mul(i+1,inv[i+1]);
    for(int T=read();T--;) Kafka();
    return 0;
}
/*
1
5 1
1 1 1 2



18
*/

 

　

1002

数据假了，纯暴力做法才跑了时限一半，比正解还快

#include<bits/stdc++.h>
using namespace std;
const int N = 100001;
int p[N];
int cnt;
int l,r;
vector<int> G[N];
int w2v[N];
bool S[N];
void dfs(int now){
    cnt--;
    S[now]=1;
    bool flag=0;
    for(int child:G[now]){
        if(!S[child]){
            if(p[child]<=r&&p[child]>=l){
                dfs(child);
                flag=1;
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i=1;i<=n;i++){
            cin>>p[i];
            w2v[p[i]]=i;
        }
        int x,y;
        for(int i=0;i<n-1;i++){
            cin>>x>>y;
            G[x].push_back(y);
            G[y].push_back(x);
        }
        int m;cin>>m;
        int oprt;
        for(int i=0;i<m;i++){
            cin>>oprt>>x>>y;
            if(oprt==1){
                int t=p[x];
                p[x]=p[y];
                p[y]=t;
                w2v[p[x]]=x;
                w2v[p[y]]=y;
            }
            else {
                memset(S,0,n+1);
                l=x;
                r=y;
                cnt=r-l+1;
                dfs(w2v[l]);
                if(cnt==0){
                    cout<<"Yes"<<"\n";
                }
                else cout<<"No"<<"\n";
            }
        }
    }
}

但是我们要追求正解是不~

考虑区间[l,r]内所有点中深度最深的点，一定是路径端点，另一个路径端点可能是次深点，也可能是最深点的祖先

可以把求最深点和次深点放在线段树区间合并时维护，具体细节看线段树内的merge( )

确定了端点后要判断的就是路径长度是否=r-l+1以及路径最小值是否=l，最大值是否等于r，这些可以用树链剖分做

所以做法就是：

以点权为下标维护一颗线段树，线段树的节点信息有当前区间内最深点、次深点、次深点如果为-1的话另外一个端点（也就是lca）

再树剖维护路径最大值和最小值

注意：区间合并时求lca要用st表法，用倍增法会多一个log

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define ls (rt<<1)
#define rs (rt<<1|1)
int n ;
const int N = 1e5+5;
vector<int>e[N];
int lg[N],p[N],invp[N],invdfn[N],siz[N],fa[N],dep[N],cnt,id[N],top[N],lcaf[N][20],son[N],mx[N<<2],mi[N<<2];
int get(int x, int y) {return id[x] < id[y] ? x : y;}
int LCA(int u,int v){
    if(u == v) return u;
    if((u = id[u]) > (v = id[v])) swap(u, v);
    int d = __lg(v - u++);
    return get(lcaf[u][d], lcaf[v - (1 << d) + 1][d]);
}
void dfs1(int u,int f){
    cnt++;// dfs order
    id[u]=cnt;// id:dfn
    lcaf[id[u]][0] = f; 
    siz[u]=1;
    fa[u]=f;
    dep[u]=dep[f]+1;
    int maxson=-1;
    for(auto to:e[u]){
        if(to==f) continue;
        dfs1(to,u);
        siz[u]+=siz[to];
        if(siz[to]>maxson) son[u]=to,maxson=siz[to];
    }
}
void dfs2(int u,int topf){
    invdfn[id[u]]=u;
    top[u]=topf;
    if(!son[u]) return;
    dfs2(son[u],topf);
    for(auto to:e[u]){
        if(to==son[u]||to==fa[u]) continue;
        dfs2(to,to);
    }
}
void up_link(int rt){
    mx[rt]=max(mx[ls],mx[rs]);
    mi[rt]=min(mi[ls],mi[rs]);
}
void build(int rt,int l,int r){
    if(l==r) {
        mi[rt]=mx[rt]=p[invdfn[l]];
        return;
    }
    build(ls,l,mid);build(rs,mid+1,r);
    up_link(rt);
}
int query(int op,int ql,int qr,int rt=1,int l=1,int r=n){
    if(ql<=l&&r<=qr){
        if(op==1) return mx[rt];
        else return mi[rt];
    }
    int ans;
    if(op==1) ans=0;
    else ans=2e9;
    if(mid>=ql) {
        if(op==1) ans=max(ans,query(op,ql,qr,ls,l,mid));
        else ans=min(ans,query(op,ql,qr,ls,l,mid));
    }
    if(mid<qr) {
        if(op==1) ans=max(ans,query(op,ql,qr,rs,mid+1,r));
        else ans=min(ans,query(op,ql,qr,rs,mid+1,r));
    }
    up_link(rt);
    return ans;
}
void change(int ql,int qr,int k,int rt=1,int l=1,int r=n){
    if(ql<=l&&r<=qr){
        mx[rt]=mi[rt]=k;
        return;
    }
    if(ql<=mid) change(ql,qr,k,ls,l,mid);
    if(qr>mid) change(ql,qr,k,rs,mid+1,r);
    up_link(rt);
}
void change_path(int x,int y,int val){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        change(id[top[x]],id[x],val);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    change(id[x],id[y],val);
}
int qpath(int x,int y,int op){
    int ans;
    //1 max, 0 min
    if(op==1) ans=0;
    else ans=2e9;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        if(op==1)    ans=max(ans,query(op,id[top[x]],id[x]));
        else    ans=min(ans,query(op,id[top[x]],id[x]));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    if(op==1)    ans=max(ans,query(op,id[x],id[y]));    
    else    ans=min(ans,query(op,id[x],id[y]));
    return ans;
}
struct seg_tree{
    int mx_pos[N<<2],se_pos[N<<2],lca[N<<2];
    pair<int,int>merge(int a,int b,int c,int d){
        int mx=-1,mxpos=-1;
        int w[5]={0};
        w[1]=a;w[2]=b;w[3]=c;w[4]=d;
        for(int i=1;i<=4;i++){
            if(w[i]==-1) continue;
            if(dep[w[i]]>mx){
                mx=dep[w[i]];
                mxpos=w[i];
            }
        }
        int sepos=-1;
        for(int i=1;i<=4;i++){
            if(w[i]==-1) continue;
            if(mxpos==w[i]) continue;
            if(LCA(mxpos,w[i])!=w[i]){
                if(sepos==-1) {
                    sepos=w[i];
                }
                else if(dep[w[i]]>dep[sepos]){
                    sepos=w[i];
                } 
            }
        }
        return {mxpos,sepos};
    }
    void up(int rt){
        pair<int,int>out;
        out=merge(mx_pos[ls],se_pos[ls],mx_pos[rs],se_pos[rs]);
        mx_pos[rt]=out.first;
        se_pos[rt]=out.second;
        lca[rt]=LCA(lca[ls],lca[rs]);
    }
    void build(int rt=1,int l=1,int r=n){
        if(l==r){
            mx_pos[rt]=invp[l];
            se_pos[rt]=-1;
            lca[rt]=invp[l];
            return;
        }
        build(ls,l,mid);build(rs,mid+1,r);
        up(rt);
    }
    void update(int val,int pos,int rt=1,int l=1,int r=n){
        if(l==r){
            lca[rt]=pos;
            mx_pos[rt]=pos;
            se_pos[rt]=-1;
            return;
        }
        if(val<=mid) update(val,pos,ls,l,mid);
        else update(val,pos,rs,mid+1,r);
        up(rt);
    }
    pair<int,int> query(int ql,int qr,int rt=1,int l=1,int r=n){
        if(ql<=l&&r<=qr) {
            pair<int,int>q;
            q.first=mx_pos[rt];q.second=se_pos[rt];
            return q;
        }
        pair<int,int>lq,rq;
        lq={-1,-1};rq={-1,-1};
        if(mid>=ql) lq=query(ql,qr,ls,l,mid);
        if(mid<qr) rq=query(ql,qr,rs,mid+1,r);
        return merge(lq.first,lq.second,rq.first,rq.second);
    }
    int qlca(int ql,int qr,int rt=1,int l=1,int r=n){
        if(ql<=l&&r<=qr) {
            return lca[rt];
        }
        int Llca=0,Rlca=0;
        if(mid>=ql) Llca=qlca(ql,qr,ls,l,mid);
        if(mid<qr) Rlca=qlca(ql,qr,rs,mid+1,r);
        if(Llca&&Rlca) return LCA(Llca,Rlca);
        else if(Llca) return Llca;
        else if(Rlca) return Rlca;
    }
}t;
void solve(){    
    cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++) e[i].clear(),son[i]=0;
    for(int i=1;i<=n;i++) cin>>p[i],invp[p[i]]=i;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    for(int i = 1; i <= __lg(n); i++)
        for(int j = 1; j + (1 << i) - 1 <= n; j++)
            lcaf[j][i] = get(lcaf[j][i-1], lcaf[j + (1 << i - 1)][i-1]);
    t.build();
    int m;cin>>m;
    while(m--){
        int op;cin>>op;
        if(op==1) {
            int x,y;cin>>x>>y;
            int wx=p[x],wy=p[y];
            change_path(x,x,wy),change_path(y,y,wx);
            t.update(wy,x),t.update(wx,y);
            p[x]=wy,p[y]=wx;
        }
        else {
            int l,r;
            cin>>l>>r;
            pair<int,int>tmp=t.query(l,r);
            int mx=tmp.first;
            int se=tmp.second;
            if(se==-1) se=t.qlca(l,r);
            int len_path=dep[mx]+dep[se]-2*dep[LCA(mx,se)]+1;
            if(qpath(mx,se,1)==r&&qpath(mx,se,0)==l&&r-l+1==len_path) cout<<"Yes"<<"\n";
            else cout<<"No"<<"\n";
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
    return 0;
}

 

标签：rt,杭电多校,ch,return,int,pos,2024,第九,mx
From： https://www.cnblogs.com/liyishui2003/p/18364278

相关文章

  • 2024.8.16随笔（补）
    前言本来准备熬夜补的，结果因为前一天熬了夜加上家长压力被迫正常睡觉。讲课上午是whx给我们讲莫反和筛法。前半部分我全部听懂了，后面我听懂了但是印象不深刻，遇到题自己也推不出来。总的来说听懂了80%以上。重点聊筛法吧，就前面的简单的筛法之前讲数论讲过很简单，然后杜教筛当时......
  • 2024新型数字政府综合解决方案（一）
    新型数字政府综合解决方案通过整合先进的数字技术和智能化系统，构建了一个高效、透明且响应迅速的政府服务平台，能够实现跨部门数据共享和实时信息更新。该解决方案包括智能数据分析、大数据平台和云计算服务，旨在提升政府决策的科学性和行政管理的效能。通过在线服务和自动化流程......
  • 2024闪存峰会(FMS)回顾：行业趋势与创新
    一年一度的存储专业人士盛会——闪存峰会（FMS），如期在圣克拉拉会议中心举行。今年的活动吸引了约75家参展商，参会人数突破3000人，虽然这个数字仍低于新冠疫情之前的水平，但整体上仍然是一次成功的活动。会议的主题“未来记忆与存储”得到了与会者的广泛认可。参展商概览尽管参展商......
  • 2024.8.16 总结（集训）
    今天是[whx]（？）巨佬来给我们讲数论，大概是狄利克雷卷积、莫比乌斯反演、杜教筛、PN筛这条线路。虽然我很喜欢莫反，之前写了一些莫反题，但今天还是很有收获。对整除分块、杜教筛的理解更深刻了（关于整除分块为什么是\(O(\sqrtn)\)的、杜教筛的本质）。明白了\(\mu\)适合容斥。见到......
  • 2024.8.16
    DATE#:20240816ITEM#:DOCWEEK#:FRIDAYDAIL#:捌月拾叁TAGS<BGM=["Autism--闫东炜"](https://music.163.com/song?id=1321871852&userid=8847964125)><theme=oi-mathlinearmath><[空]><[空]>&l......
  • 2024年第四届网络通信与信息安全国际学术会议（ICNCIS 2024） 2024 4th International Con
    文章目录一、会议详情二、投稿信息三、大会简介四、主讲嘉宾五、征稿主题六、咨询一、会议详情二、投稿信息大会官网：https://ais.cn/u/vEbMBz会议时间：2024年8月23-25日大会地点：中国--杭州终轮截稿：2024年8月19日接受/拒稿通知：投稿后1周内收录检索：EICom......
  • 第三届机械、航天技术与材料应用国际学术会议 (MATMA 2024) 2024 3rd International C
    文章目录一、会议详情二、重要信息三、大会简介四、主讲嘉宾五、征稿主题六、咨询一、会议详情二、重要信息末轮征稿：2024年8月26日23:59，不再延期！收录检索：EI(核心)，Scopus均稳定检索会议官网：https://ais.cn/u/vEbMBz会议地点：内蒙古工业大学新城校区三、......
  • 2024 Read Paper
    202408161.PhD,SearchingforpulsarsintheGalacticcentreandthetimingofamassivepulsar2.TheHighTimeResolutionUniversePulsarsurvey-XVIII.ThereprocessingoftheHTRU-SLowLatsurveyaroundtheGalacticCentreusingaFastFoldingAlgo......
  • 2024 暑假平邑一中集训整合(下)
    Day10考试T3形式化题意，给定\(n,m\)，求\(\sum^n_{i=1}\sum^m_{j=1}\displaystyle\begin{pmatrix}n\\i\\\end{pmatrix}\displaystyle\begin{pmatrix}i\\j\\\end{pmatrix}\)推式子:\[\sum^n_{i=1}\sum^m_{j=1}\displaystyle\begin{pmatrix}n\\i......
  • mathtype7永久激活码秘钥2024最新分享
    mathtype7永久激活码秘钥2024最新分享：4VN8B-C86SQ-Z9R0C-27M97-15HUA打开MathType插件，选择“激活”，输入该激活码，点击“验证”即可激活使用。......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99