ZR 集训 Day12 – 模拟赛

ooliver 发布于 12 小时前 72 次阅读 OI

AI 摘要

T1也能因为没加 long long 挂掉，简直唐飞了！离散化被卡常，改成最长不下降子序列才过。还有让人毫无欲望的神中神题……集训一天，坑与惊喜齐飞。

2026 暑假 C 班 Day2 之学废离去

二进制与一 IV

想不到吧，T1也能挂，还是没加 long long，简直唐飞了。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=45;
int T,x,idx,ans;
bool a[N];

signed main(){
    cin>>T;
    while(T--){
        cin>>x;
        ans=idx=0;
        while(x) a[++idx]=x&1,x>>=1;
        for(int i=idx,j=1;i>(idx>>1);i--,j++) ans+=((a[i]^a[j])<<(j-1));
        cout<<ans<<"\n";
    }
    return 0;
}

小 L 涂色

糖糖题，还好没挂。

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e6+5;
int n,m,ans;
int a[N],fa[N],mn[N],vis[N],eg[N],tag[N],siz[N];

int find(int x){
    if(x==fa[x]) return x;
    else return fa[x]=find(fa[x]);
}

signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld=",&a[i]);
        fa[i]=i,mn[i]=a[i],vis[i]=a[i],siz[i]=1;
        ans+=a[i];
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        int x=find(u),y=find(v);
        if(x==y){
            eg[x]++;
            continue;
        }
        if(siz[x]>siz[y]) swap(x,y);
        fa[x]=y,siz[y]+=siz[x];
        vis[y]+=vis[x],mn[y]=min(mn[y],mn[x]),eg[y]+=eg[x]+1;
    }
    for(int i=1;i<=n;i++){
        int x=find(fa[i]);
        if(tag[x]) continue;
        tag[x]=1;
        if(eg[x]>=siz[x]) ans-=vis[x];
        else ans-=(vis[x]-mn[x]);
    }
    printf("%lld",ans);
    return 0;
}

删除滚木

巨糖之题，想到了二位偏序，于是直接用上树状数组了，复杂度对但需要离散化啥的被卡常了。

赛后重构写了个最长不下降子序列就过了。。。

C++
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int n,k;
int a[N];
long double d[N];
struct node{
    long double x,y;
    bool operator<(const node b)const{
        if(x!=b.x) return x>b.x;
        return y<b.y;
    }
}b[N];

bool check(long double x){
    for(int i=1;i<=n;i++) b[i]={a[i]-i*x,a[i]+i*x};
    sort(b+1,b+1+n);
    int len=0;
    for(int i=1;i<=n;i++){
        if(!len||b[i].y>=d[len]) d[++len]=b[i].y;
        else *lower_bound(d+1,d+1+len,b[i].y)=b[i].y;
    }
    return len>=n-k;
}

signed main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    long double l=0,r=2e9,ans;
    for(int i=1;i<=70;i++){
        long double mid=(l+r)/2.0;
        if(check(mid)) r=ans=mid;
        else l=mid;
    }
    printf("%0.10Lf",ans);
    return 0;
}

午安。

神中神中神中神之题，毫无想写的欲望，把官方题解放这了：