526互联

wzOI 202311.8-9 模拟赛题解

发布时间 2023-11-09 21:46:25作者: NBest

2023.11.9 competion

复盘

时间安排不太好，然后就是太纠结于一个想法了导致第二题不知道在想什么鬼东西，心态还是要放平啊。

A

明显大模拟，我想逃避一下，所以就skip了半个小时，发现后面三道一点思路都没有，然后就回来打 T1 大模拟。这个大模拟非常考验对工具的使用，幸好我造的数据比较多，而且搞过一些这种东西，就复制粘贴然后输入到代码里把变成程序语言，打了我一个半小时。打完的时候已经是两个小时过去了。

大致思路:复制信息到代码里，让代码将其加工成可以使用的代码语言，然后暴力乱搞即可。

B

我题目看错了（一开始看对了后来第二次回来看的时候看错了），以为必须选最前面连续的 \(k\) 个，然后就想着暴力枚举然后跑一个玄学的状压贪心加暴力，当然我赛时想了 \(1\) 小时的状压分类讨论无果就 skip 了。

正解 \(dp\) 啊，如果想到维护差值的话就肯定会写了。状态不用说了，暴力打就行了，复杂度 \(O(n^3p)\)。

对于每个数，只有五种抉择：

  • 不放
  • 放进 \(S\)
  • 乘 \(2\) 放进 \(S\)
  • 放进 \(T\)
  • 乘 \(2\) 放进 \(S\)

所以我们可以记一维表示 \(S-T\) 差值，一维表示选了几个数乘 \(2\)，最后一维枚举 \(i\) 的可以滚掉，因为这一维信息用不到。虽然不滚好像也能过？

\(Code\)

const int N=102,d=2662;
int n,m,p[N],v[N];
ll f[2][N][5500],ans=-1e18;
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        v[i]=read(),p[i]=read();
    memset(f,-0x3f,sizeof(f));
    f[0][0][d]=0;
    for(int i=1,o=1;i<=n;i++,o^=1)
        for(int k=0;k<=m;k++)
            for(int w=52;w<=2*d-52;w++)
                f[o][k][w]=max(f[o^1][k][w],max(max(f[o^1][k][w-2*p[i]],f[o^1][k][w+2*p[i]]),(k?max(f[o^1][k-1][w-4*p[i]],f[o^1][k-1][w+4*p[i]]):-(ll)1e18))+v[i]);
    for(int k=0;k<=m;k++)
        ans=max(ans,f[n&1][k][d]);
    printf("%lld\n",ans);
    return 0;
}

C

T3 贪心没特判两个点都挂（为什么会有人在 5000 的点里面放一个 2 专门卡特判啊）。

正解就贪心，我一开始以为是什么神奇的数据结构。

我们肯定有一个上限（一个正排一个反排求差），我们每次交换如果都是交换最大的那最后结果也一定是最大的。

我们令 \(a_1>b_1\)，\(a_2>b_2\)，那么换之前为 \(|a_1-b_1|+|a_2-b_2|=a_1+a_2-b_1-b_2\)。

  • 假设此时的 \(b_1>a_2\)，那么交换后有 \(|a_1-b_2|+|a_2-b_1|=a_1-b_2+b_1-a_2=a_1+b_1-a_2-b_2\)，对答案的贡献为 \(2b_1 - 2a_2=2\times(\min(a_1,b_1)-\max(a_2,b_2))\)。
  • 如果 \(b_1\le a_2\)，那么有 \(|a_1-b_2|+|a_2-b_1|=a_1-b_2+a_2-b_1=a_1+a_2-b_1-b_2\)，对答案贡献为 \(0\)。为无意义交换。

所以我们对每个 \(\min(a_i,b_i),\max(a_i,b_i)\) 排个序然后把最大贡献都拿来，最后如果最优了就做无意义交换即可，不过一定要注意特判 \(n=2\) 的情况，此时无意义交换也会对答案造成贡献。

\(Code\)

const int N=1e5+5;
int n,k,a[N],b[N];
priority_queue<int>Q1;
priority_queue<int,vector<int>,greater<int> >Q2;
int main(){
    for(int T=read();T--;){
        n=read(),k=read();
        ll ans=0;
        while(Q1.size())Q1.pop();
        while(Q2.size())Q2.pop();
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=n;i++){
            b[i]=read();
            ans+=abs(a[i]-b[i]);
            if(a[i]>b[i])Q1.push(b[i]),Q2.push(a[i]);
            else Q1.push(a[i]),Q2.push(b[i]);
        }
        if(n==2){
            if(k&1)swap(a[1],a[2]);
            printf("%lld\n",1ll*abs(a[1]-b[1])+abs(a[2]-b[2]));
            continue;
        }
        while(Q1.size()&&Q1.top()>Q2.top()&&(k--)){
            ans+=1ll*Q1.top()-Q2.top()<<1;
            Q1.pop(),Q2.pop();
        }
        printf("%lld\n",ans);
    }
    return 0;
}

D

题面打错了，导致我特殊性质看了好久看不出错，但是和样例不一样。最后以样例为准拿下暴力的 \(50\) 分。

暴力思路就是每个时间跑一遍。

特殊分 \(l\) 相同或者 \(r\) 相同可以把动的那边遍历然后跑并查集，最后在哪里不行就在哪里结束。

正解就是线段树分治板子，不在这里讲了。

\(Code\)

const int N=1e5+5;
struct edge{
    int u,v,l,r;
}e[N<<1];
int n,m,T,fa[N<<1];
inline int find(int x){return (x==fa[x]?x:fa[x]=find(fa[x]));}
namespace subtask_l{
    inline bool cmp(const edge a,const edge b){return a.r>b.r;}
    int R;
    bool work(int L){
        for(int i=0;i<=L-1;i++)
            puts("Yes");
        sort(e+1,e+1+m,cmp);
        for(int t=R=e[1].r,i=1;t>=L;t--){
            bool flag=1;
            while(i<=m&&e[i].r==t){
                if(find(e[i].u)==find(e[i].v)){flag=0;break;}
                fa[find(e[i].u+n)]=find(e[i].v);
                fa[find(e[i].v+n)]=find(e[i].u);
                i++;
            }
            if(!flag){R=t-1;break;}
            if(t==L)R=L-1;
        }
        for(int i=L;i<=R;i++)puts("No");
        for(int i=R+1;i<T;i++)puts("Yes");
        return 0;
    }
}
namespace subtask_r{
    inline bool cmp(const edge a,const edge b){return a.l<b.l;}
    int L;
    bool work(int R){
        sort(e+1,e+1+m,cmp);
        for(int t=L=e[1].l,i=1;t<R;t++){
            bool flag=1;
            while(i<=m&&e[i].l==t){
                if(find(e[i].u)==find(e[i].v)){flag=0;break;}
                fa[find(e[i].u+n)]=find(e[i].v);
                fa[find(e[i].v+n)]=find(e[i].u);
                i++;
            }
            if(!flag){L=t-1;break;}
            if(t==R-1)L=R-1;
        }
        for(int i=0;i<=L;i++)puts("Yes");
        for(int i=L+1;i<R;i++)puts("No");
        for(int i=R;i<T;i++)puts("Yes");
        return 0;
    }
}
namespace subtask_v{
    int c[N],t;
    vector<edge>f[N];
    bool dfs(int x){
        for(edge PI:f[x])if(PI.l<=t&&t<PI.r){
            int y=PI.v;
            if(!c[y]){
                c[y]=-c[x];
                if(!dfs(y))return 0;
            }
            else if(c[y]==c[x])return 0;
        }
        return 1;
    }
    bool work(){
        for(int i=1;i<=m;i++){
            f[e[i].u].push_back(e[i]);
            f[e[i].v].push_back({e[i].v,e[i].u,e[i].l,e[i].r});
        }
        for(t=0;t<T;t++){
            for(int i=1;i<=n;i++)c[i]=0;
            bool flag=1;
            for(int i=1;i<=n;i++)
                if(!c[i])c[i]=1,flag&=dfs(i);
            puts(flag?"Yes":"No");
        }
        return 0;
    }
}
int samL,samR;
int main(){
    n=read(),m=read(),T=read();
    for(int i=1;i<=(n<<1);i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),l=read(),r=read();
        if(i>1&&l!=samL)samL=0;
        else if(i==1)samL=l;
        if(i>1&&r!=samR)samR=0;
        else if(i==1)samR=r;
        e[i]={u,v,l,r};
    }
    if(samL)return subtask_l::work(samL),0;
    else if(samR)return subtask_r::work(samR),0;
    subtask_v::work();
    return 0;
}

2023.11.8 competition

前言

因为这场我就写了两题就不单独发一个了。

A

显然可以状压然后直接暴力，不过需要一点点贪心优化吧，半个小时打完。

代码很丑。

\(Code\)

int n,m,a[100005],s[25],ans;
void dfs(int res){
    bool flag=0;
    for(int i=2;i<(1<<m)-1;i++){
        if(!s[i])continue;
        for(int j=1;j<i;j++){
            if(!s[j])continue;
            if(i+j!=(i|j))continue;
            int minn=min(s[i],s[j]);
            s[i]-=minn;
            s[j]-=minn;
            s[i|j]+=minn;
            flag=1;
            dfs(res-minn);
            s[i|j]-=minn;
            s[i]+=minn;
            s[j]+=minn;
        }
    }
    if(!flag)ans=min(ans,res);
}
int main(){
    n=read(),m=read();
    for(int i=0;i<m;i++){
        int k=read();
        for(int j=1;j<=k;j++){
            int w=read();
            a[w]|=(1<<i);
        }
    }
    for(int i=1;i<=n;i++)s[a[i]]++;
    int res=n-s[0];s[0]=0;
    for(int i=(1<<m)-2;~i;--i){
        if(s[i]&&s[((1<<m)-1)^i]){
            int minn=min(s[i],s[((1<<m)-1)^i]);
            s[i]-=minn;
            s[((1<<m)-1)^i]-=minn;
            s[(1<<m)-1]+=minn;
            res-=minn;
        }
    }
    for(int i=0;i<m;i++){
        for(int j=3;s[1<<i]&&j<(1<<m)-1;j++){
            if(__builtin_popcount(j)==1)continue;
            if((1<<i)+j!=((1<<i)|j))continue;
            if(!s[j])continue;
            int minn=min(s[1<<i],s[j]);
            s[1<<i]-=minn;
            s[j]-=minn;
            s[(1<<i)|j]+=minn;
            res-=minn;
        }
    }
    ans=res;
    dfs(res);
    cout<<ans;
    return 0;
}

B

树形dp。

至多有一个不好求，先想想怎么让他就不超过，即在同一层选不超过k个子树吧，这个只需要跑个优先队列什么的找最大贡献，如果还要被选需要少选一个，到k的话可以直接记入答案之类的。

那有一个呢？

我们发现 \(w\) 是个非负整数，也就是我们在找那个超过 \(k\) 的时也可以直接贪心，因为不劣我们可以选择从子树里面找一个没有限制的（排序找最大值），也可以把自己变成没有限制的，但是会对之后产生影响，所以这里要多记一维，如果自己没有限制那肯定是全部加进来。

其实自己是不需要记的，因为用不到这一维。

令 \(f_{0/1,u}\) 表示 \(u\) 这棵包含自己的子树有没有选无限制的的最大贡献，那么有:

\[\text{自己无限：} f_{1,u}=\sum f_{0,v}+w_{u,v}\\\text{都有限:}f_{0,u}=\max\sum^{k-1}_{i=1}f_{0,v}+w_{u,v}\\\text{儿子无限:}f_{1,u}=\max f_{1,v'}+w_{u,v'}+\max\sum_{v\ne v'}^{k-2}f_{0,v}+w_{u,v} \]

为什么这里取 \(k-1\) 呢，因为还要连父亲啊，但是统计答案时要多统计一个。

为什么不用换根呢？因为父亲子树如果选了自己的话就已经算了包括自己的答案了，如果没加说明自己不够优，总之所有情况都被考虑到了。

看不懂的话可以看代码。

\(Code\)

int n,m;
ll f[2][N],ans;
vector<PII>F[N];
void dfs(int x,int fa){
    ll my=0;
    int id=0;
    priority_queue<ll>Q;
    for(PII PI:F[x]){
        int y=PI.first,w=PI.second;
        if(y==fa)continue;
        dfs(y,x);
        my+=f[0][y]+w;
        Q.push(f[0][y]+w);
        if(f[1][y]+w>f[1][x])f[1][x]=f[1][y]+w,id=y;
    }
    if(Q.size()<m)f[0][x]=my,my=0;
    else{
        for(int T=m-1;T--;)f[0][x]+=Q.top(),Q.pop();
        ans=max(ans,f[0][x]+Q.top());
    }
    while(!Q.empty())Q.pop();
    for(PII PI:F[x]){
        int y=PI.first,w=PI.second;
        if(y==fa)continue;
        if(y!=id)Q.push(f[0][y]+w);
    }
    if(Q.size()<m-1)
        while(!Q.empty())f[1][x]+=Q.top(),Q.pop();
    else{
        for(int T=m-2;T--;)f[1][x]+=Q.top(),Q.pop();
        ans=max(ans,f[1][x]+Q.top());
    }
    while(!Q.empty())Q.pop();
    f[1][x]=max(f[1][x],my);
    ans=max(ans,f[1][x]);
    ans=max(ans,f[0][x]);
    return;
}
int main(){
    n=read(),m=read();
    if(!m)return puts("0"),0;
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        F[u].push_back({v,w}),F[v].push_back({u,w});
    }
    if(m==1){
        for(int x=1;x<=n;x++){
            ll res=0;
            for(PII PI:F[x])res+=PI.second;
            if(res>ans)ans=res;
        }
        printf("%lld",ans);
        return 0;
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}