Codeforces Round 875 (Div. 2) A-D

EdGrass / 2023-05-29 / 原文

Codeforces Round 875 (Div. 2)

A. Twin Permutations

int a[N];
void solve(){
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)cout<<n+1-a[i]<<' ';
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

B. Array merging

void solve(){
    int n=read(),last=0,len=0;
    vector<int>cnt1(n*2+5),cnt2(n*2+5);
    for(int i=1;i<=n;i++){
        int x=read();
        if(last==x){
            len++;
        }else {
            cnt1[last]=max(cnt1[last],len);
            len=1;
            last=x;
        }
    }
    cnt1[last]=max(cnt1[last],len);
    last=0,len=0;
    for(int i=1;i<=n;i++){
        int x=read();
        if(last==x){
            len++;
        }else {
            cnt2[last]=max(cnt2[last],len);
            len=1;
            last=x;
        }
    }
    cnt2[last]=max(cnt2[last],len);
    int ans=0;
    for(int i=1;i<=2*n;i++){
        ans=max(cnt1[i]+cnt2[i],ans);
    }
    cout<<ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

C. Copil Copac Draws Trees

int h[N], e[N], ne[N], idx, dep[N], id[N];
bool st[N];
void add(int a, int b,int we){
    e[idx] = b, ne[idx] = h[a], id[idx]=we, h[a] = idx ++ ;
}
void dfs(int u,int we){
    st[u] = true; 
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i],wn=id[i];
        if (!st[j]) {
            if(wn<we)dep[j]=dep[u]+1;
            else dep[j]=dep[u];
            dfs(j,wn);
        }
    }
}
void solve(){
    int n=read(),ans=0;
    idx = 0;
    memset(h, -1, sizeof h);
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y,i);
        add(y,x,i);
    }
    for(int i=1;i<=n;i++)st[i]=false;
    dfs(1,inf);
    for(int i=1;i<=n;i++){
        ans=max(ans,dep[i]);
    }
    cout<<ans<<'\n';
}

D. The BOSS Can Count Pairs

b[i]*b[j]<=2n 利用这一点去压缩时间复杂度

做法就是将pair按照a[i]的sort排序好后，枚举1到sqrt(2n)，按照大小找可匹配的pair

时间复杂度：O(n*sqrt{2n})

int a[N];
PII p[N];
void solve(){
    int n=read(),ans=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=1;i<=n;i++){
        int y=read();
        p[i]={a[i],y};
    }
    sort(p+1,p+1+n);
    for(int i=1;i*i<=n*2;i++){
        vector<int>mp(n+1);
        for(int j=1;j<=n;j++){
            int x=p[j].first,y=p[j].second;
            int need=x*i-y;
            if(need>=1&&need<=n)ans+=mp[need];
            if(x==i)mp[y]++;
        }
    }
    cout<<ans<<'\n';
}