首页 > 其他分享 >CodeChef Starters 83 Division 1 解题报告

CodeChef Starters 83 Division 1 解题报告

时间：2023-04-15 16:22:27浏览次数：74  
标签：Division le int max texttt Starters MAXN 83 out

CodeChef Starters 83 Division 1 题解

\(\newcommand \v \mathrm\)

\(\text{By DaiRuiChen007}\)

Contest Link

A. Construct String

Problem Link

题目大意

给定长度为 \(n\) 的字符串 \(S\)，每次操作可以把三个相同的字符变成一个同样的字符（\(\texttt {ccc}\to\texttt c\)）

求若干次操作后可以得到最短的 \(S\)

数据范围：\(n\le 10^6\)

思路分析

容易证明贪心地把 \(S\) 中每三个连续的相同字符都操作直到不能操作位置的策略是最优的

用一个栈模拟这个过程即可

时间复杂度 \(\mathcal O(n)\)

代码呈现

#include<bits/stdc++.h>
using namespace std;
inline void solve() {
    int n; string s,t;
    cin>>n>>s;
    for(int i=0;i<n;++i) {
        int x=t.length();
        if(x<2) t+=s[i];
        else if(t[x-1]==s[i]&&t[x-2]==s[i]) t.pop_back();
        else t+=s[i];
    }
    cout<<t<<"\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}


B. Order by XOR

Problem Link

题目大意

给三个不同的非负整数数 \(a,b,c\in[0,V]\)，求出某个 \(x\in [0,V]\) 使得 \(a\oplus x<b\oplus x<c\oplus x\)，无解输出 \(-1\)

数据范围：\(V=2^{30}-1\)

思路分析

从高位到低位逐位考虑，对于当前位 \(k\)：

  • \(a_k=b_k=c_k\)：\(x_k=0/1\) 均无影响
  • \(a_k=b_k\ne c_k\)：贪心可以证明取 \(x_k=b_k\) 更优
  • \(a_k\ne b_k=c_k\)：贪心可以证明取 \(x_k=a_k\) 更优
  • \(a_k\ne b_k\ne c_k,a_k=c_k\)：
    • 若之前所有位 \(a\oplus x,b\oplus x,c\oplus x\) 都相等，则无解
    • 若 \(a\oplus x<b\oplus x\) 已被满足，取 \(x_k=b_k\) 即可得到答案
    • 若 \(b\oplus x<c\oplus x\) 已被满足，去 \(x_k=a_k\) 即可得到答案

根据上述分类讨论模拟即可

时间复杂度 \(\mathcal O(\log V)\)

代码呈现

#include<bits/stdc++.h>
using namespace std;
inline void solve() {
    int a,b,c,ans=0;
    scanf("%d%d%d",&a,&b,&c);
    auto dig=[&](int x,int k) { return (x>>k)&1; };
    int opt=0;
    for(int k=30;k>=0;--k) {
        int x=dig(a,k),y=dig(b,k),z=dig(c,k);
        if(x==y&&y==z) continue;
        if(x==y) ans|=y<<k,opt|=1;
        if(y==z) ans|=x<<k,opt|=2;
        if(x==z) {
            if(opt==0) { puts("-1"); return ; }
            if(opt==1) ans|=x<<k,opt|=2;
            if(opt==2) ans|=y<<k,opt|=1;
        }
        if(opt==3) { printf("%d\n",ans); return ; }
    }
    puts("-1");
}
signed main() {
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}


C. Rotate to Minimum

Problem Link

题目大意

对于一个长度为 \(n\) 的字符串 \(S\) 可以进行如下两种操作：

  1. 对于某个 \(S_i\) 使 \(S_i\gets S_i+1\)（\(\texttt c\to \texttt d,\texttt z\to \texttt a\)）
  2. 对于某个 \(S_i\) 是 \(S_i\gets S_i-1\)（\(\texttt d\to \texttt c,\texttt a\to \texttt z\)）

操作 1 不超过 \(p\) 次，操作 2 不超过 \(q\) 次，求最终 \(S\) 最小可能的字典序

数据范围：\(n\le 2\times 10^5\)

思路分析

显然先将 \(S\) 的一段前缀中尽可能多的字符复原成 \(\texttt a\)

再求出最长全 \(\texttt a\) 前缀后的步骤是 trivial 的：全 \(\texttt a\) 前缀的下一个字符用 2 操作最小化字典序，剩下的能用操作 1 变成 \(\texttt a\) 就用，否则不用

考虑二分最大的 \(\texttt a\) 的前缀长度 \(len\)，对于前 \(len\) 个位置，我们需要确定用哪种操作复原，并使得两种操作的总次数分别不超过 \(p,q\)

注意到，当 \(S_i\ne \texttt a\) 时，操作 1 的花费越大，操作 2 的花费越小，反之亦然，因此可以证明最优策略一定是取用操作 1 复原代价最小的若干位置，剩下的选用操作 2，因此一遍排序即可完成判定

然后还有一个细节需要简单贪心处理，因为我们要尽可能最小化 \(S_{len+1}\)，因此在 \(S[1\dots len]\) 的复原中，应尽可能多选用操作 1，剩下按上述过程贪心即可

时间复杂度 \(\mathcal O(n\log^2n)\)

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
char str[MAXN];
inline void solve() {
    int n,u,d;
    scanf("%d%d%d%s",&n,&u,&d,str+1);
    int l=1,r=n,res=0;
    while(l<=r) {
        auto check=[&](int x) -> bool {
            vector <pair<int,int>> v;
            for(int i=1;i<=x;++i) v.push_back(make_pair((26-(str[i]-'a'))%26,str[i]-'a'));
            int p=0,q=0;
            sort(v.begin(),v.end());
            for(auto t:v) {
                if(t.first+p<=u) p+=t.first;
                else q+=t.second;
            }
            return p<=u&&q<=d;
        };
        int mid=(l+r)>>1;
        if(check(mid)) res=mid,l=mid+1;
        else r=mid-1;
    }
    vector <pair<int,int>> v;
    for(int i=1;i<=res;++i) {
        v.push_back(make_pair((26-(str[i]-'a'))%26,str[i]-'a'));
        str[i]='a';
    }
    sort(v.begin(),v.end());
    for(auto t:v) {
        if(t.first<=u) u-=t.first;
        else d-=t.second;
    }
    if(res<n) str[res+1]-=d;
    for(int i=res+2;i<=n;++i) {
        int x=(26-(str[i]-'a'))%26;
        if(u>=x) str[i]='a',u-=x;
    }
    printf("%s\n",str+1);
}
signed main() {
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}


D. Saber Slays

Problem Link

题目大意

你需要进行若干次“挑战”，设你的能力值为 \(u\)，对手的能力值为 \(v\)，那么每次“挑战”会发生如下 \(3\) 种结果之一：

  • \(u<v\)：你失败
  • \(u=v\)：你胜利，且 \(u\gets u-1\)
  • \(u>v\)：你胜利

给定 \(n\) 个对手，第 \(i\) 个对手的能力值为 \(s_i\)，\(q\) 次询问 \(l,r\)，你需要回答如果你想依次战胜编号为 \(l,l+1,\dots ,r\) 的对手，你的初始能力值至少是多少

数据范围：\(n,q\le 5\times 10^5\)

思路分析

考虑用线段树维护每个区间对应的信息 \((\v{in},\v{out})\)，表示想要战胜这个区间中的所有人，初始能力值至少是 \(\v{in}\)，且最终你的能力值会变成 \(\v{out}\)，一个显然的观察是对于某个区间 \([l,r]\)，其 \(\v{in}\in\{\max[s_l\sim s_r],\max[s_l\sim s_r]+1\}\)

考虑合并左右区间信息 \((L_\v{in},L_\v{out}),(R_\v{in},R_\v{out})\) 的过程

  • 若 \(L_\v{out}>R_\v{in}\)：此时直接从 \(L_\v{in}\) 进入，得到 \(L_\v{out}\) 后在右区间一定有 \(L_\v{out}>R_\max\)，因此最终的结果是 \((L_\v{in},L_\v{out})\)
  • 若 \(L_{\v out}=R_\v{in}\)：此时直接从 \(L_\v{in}\) 进入，得到 \(L_\v{out}=R_\v{in}\) 恰好可以通过右区间并得到 \(R_\v{out}\)，因此最终的结果是 \((L_\v{in},R_\v{out})\)
  • 若 \(L_\v{out}<R_\v{in}\)：
    • 若 \(R_\v{in}>L_\v{in}\)，此时直接用 \(R_\v{in}\) 进入，在左区间一定有 \(L_\max<R_\v{in}\)，可以直接到右区间，因此最终的结果是 \((R_\v{in},R_\v{out})\)
    • 否则说明 \(L_\v{in}=L_\max=(L+R)_{\max}\)，此时 \(L_\v{in}\) 无法通过，选择用 \(L_\v{in}+1\) 进入，最终的结果是 \((L_\v{in}+1,L_\v{in}+1)\)

用线段树维护上述信息的合并即可

时间复杂度 \(\mathcal O((n+q)\log n)\)

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1,INF=2e9;
struct Data {
    int in,out;
    Data(): in(INF),out(INF) {}
    Data(int x): in(x),out(x-1) {}
    Data(int _i,int _o): in(_i),out(_o) {}
    inline friend Data operator +(const Data &L,const Data &R) {
        if(L.out>R.in) return Data(L.in,L.out);
        else if(L.out==R.in) return Data(L.in,R.out);
        else {
            if(L.in<R.in) return Data(R.in,R.out);
            else return Data(L.in+1,L.in+1);
        }
    }
};
int n,q,a[MAXN];
class SegmentTree {
    private:
        struct Node {
            Data data;
        } tree[MAXN<<2];
        inline int left(int x) { return x<<1; }
        inline int right(int x) { return x<<1|1; }
        inline void pushup(int pos) {
            tree[pos].data=tree[left(pos)].data+tree[right(pos)].data;
        }
    public:
        inline void Build(int l=1,int r=n,int pos=1) {
            if(l==r) { tree[pos].data=Data(a[l]); return ; }
            int mid=(l+r)>>1;
            Build(l,mid,left(pos));
            Build(mid+1,r,right(pos));
            pushup(pos);
        }
        inline Data Query(int ul,int ur,int l=1,int r=n,int pos=1) {
            if(ul<=l&&r<=ur) return tree[pos].data;
            int mid=(l+r)>>1;
            if(ur<=mid) return Query(ul,ur,l,mid,left(pos));
            if(mid<ul) return Query(ul,ur,mid+1,r,right(pos));
            return Query(ul,ur,l,mid,left(pos))+Query(ul,ur,mid+1,r,right(pos));
        }
}    S;
inline void solve() {
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    S.Build();
    while(q--) {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",S.Query(l,r).in);
    }
}
signed main() {
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}


E. Restoration

Problem Link

题目大意

交互器有一个大小为 \(n\) 的排列 \(p_i\)，每次交互你可以询问一个大小为 \(n\) 的排列，交互器会返回排列 \(r_i=p_{q_i}\) 中所有Local Max（前缀最大值）的位置（即所有满足 \(\forall 1\le j<i\) 均有 \(r_j<r_i\) 的 \(i\)）

你需要在 \(n-1\) 次询问内还原排列 \(p_i\)

数据范围：\(n\le 500\)

思路分析

考虑从排列的 Local Max 入手，注意到最后一个 Local Max 一定是 \(n\)，因此不管我们第一次询问的 \(q\) 是什么，我们总能确定 \(n\) 的位置

接下来考虑 \(n-1\) 的位置，用类似的方法找倒数二个 Local Max，为了保证 \(n-1\) 不被 \(n\) 挡住，我们可以通过选择合适的 \(q\) 使得 \(r_n=n\)，然后找倒数第二个 Local Max 即可，同理可以以一次询问的代价分别确定 \(n-2,n-3,\dots ,1\) 的对应位置

注意到当已经确定 \(2\sim n\) 的位置时，\(1\) 的位置也可以求出，因此可以做到 \(n-1\) 次询问还原 \(p_i\)

时间复杂度 \(\mathcal O(n^2)\)

代码呈现

#include<bits/stdc++.h>
using namespace std;
inline void solve() {
    int n;
    cin>>n;
    vector <int> p(n+1),idx(n+1);
    for(int i=n;i>1;--i) {
        vector <int> q(n+1,0),vis(n+1,0);
        for(int j=i+1;j<=n;++j) q[j]=idx[j],vis[q[j]]=1;
        for(int j=1;j<=i;++j) {
            for(int k=q[j-1]+1;k<=n;++k) if(!vis[k]) { q[j]=k,vis[k]=true; break; }
        }
        cout<<"? ";
        for(int j=1;j<=n;++j) cout<<q[j]<<" ";
        cout<<endl;
        int s; cin>>s; vector <int> v(s);
        for(int j=0;j<s;++j) cin>>v[j];
        for(int j=0;j<s;++j) {
            if(v[j]<=i) idx[i]=q[v[j]];
        }
        p[idx[i]]=i;
    }
    for(int i=1;i<=n;++i) if(!p[i]) p[i]=1;
    cout<<"! ";
    for(int i=1;i<=n;++i) cout<<p[i]<<" ";
    cout<<endl;
    int ans; cin>>ans; 
}
signed main() {
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}


F. Mex Segments

Problem Link

题目大意

给定一个 \(0\sim n-1\) 的排列 \(a_i\)，\(q\) 次询问，每次询问给定 \(l,r,s,t\)，你需要回答有多少 \(1\le x\le y\le n\) 使得 \(l\le y-x+1\le r\) 且 \(s\le\v{mex}(a_x,a_{x+1},\dots,a_y)\le t\)

数据范围：\(n,q\le 10^6\)

思路分析

考虑当我们强制选择了 \(0\sim k-1\) 号元素，此时对 \(x,y\) 的限制形如 \(x\le u\le v\le y\)，那么我们可以得到有多少区间 \([x,y]\) 满足 \(\v{mex}(a_x,a_{x+1},\dots,a_y)\ge k\)，因此考虑用后缀和把答案拆成 \(\v{mex}(a_x,a_{x+1},\dots,a_y)\ge s\) 和 \(\v{mex}(a_x,a_{x+1},\dots,a_y)\ge t+1\) 两个询问

离线后我们每次加入 \(k\) 所在的位置，更新对应的 \([u,v]\)，然后再对区间长度用前缀和拆分，长度 \(\le x\) 的区间共有 \(\sum_{i=v-u+1}^x \min(u,n-x+1)-\max(v-x+1,1)+1\) 个，分别分类讨论拆开 \(\min\) 和 \(\max\) 即可

时间复杂度 \(\mathcal O(n+q)\)

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Query {
    int l,r,id,c;
    Query(int _l=0,int _r=0,int _id=0,int _c=0): l(_l),r(_r),id(_id),c(_c) {}
};
inline void solve() {
    int n,q;
    scanf("%lld%lld",&n,&q);
    vector <int> a(n+1),pos(n+1),ans(q+1);
    vector <vector<Query>> Q(n+1);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]),pos[a[i]]=i;
    auto sum=[&](int l,int r) { return (l+r)*(r-l+1)/2; };
    for(int i=1;i<=q;++i) {
        int l,r,lo,hi;
        scanf("%lld%lld%lld%lld",&l,&r,&lo,&hi);
        if(lo>0) Q[lo-1].push_back(Query(l,r,i,1));
        else ans[i]+=sum(n-r+1,n-l+1);
        if(hi<n) Q[hi].push_back(Query(l,r,i,-1));
    }
    int lb=pos[0],rb=pos[0];
    for(int i=0;i<n;++i) {
        lb=min(lb,pos[i]),rb=max(rb,pos[i]);
        int len=rb-lb+1;
        auto calc=[&](int x) -> int {
            if(x<rb-lb+1) return 0;
            int ans=x-len+1;
            if(x<=n-lb+1) ans+=lb*(x-len+1);
            else ans+=lb*(n-rb+1)+sum(n-x+1,lb-1);
            if(x<=rb) ans-=sum(rb-x+1,lb);
            else ans-=sum(1,lb)+(x-rb);
            return ans;
        };
        for(auto x:Q[i]) {
            ans[x.id]+=x.c*(calc(x.r)-calc(x.l-1));
        }
    }
    for(int i=1;i<=q;++i) printf("%lld\n",ans[i]);
}
signed main() {
    int T;
    scanf("%lld",&T);
    while(T--) solve();
    return 0;
}


G. Beauty Sum

Problem Link

题目大意

给定一棵大小为 \(n\) 的树，点有点权 \(a_i\)，记 \(\v{path}(u,v)\) 为树上 \(u\to v\) 的简单路径所经过的节点集合

求 \(\sum_{1\le u<v\le n}\min\{a_i\mid i\in\v{path}(u,v\}\times\max\{a_i\mid i\in\v{path}(u,v)\}\)，即所有路径 \(u\to v\) 上最大值与最小值乘积的和

数据范围：\(n\le 2\times 10^5\)

思路分析

考虑点分治，设 \(x_i,y_i\) 分别表示节点 \(i\) 到当前分支中心 \(\v{root}\) 路径上的最小值和最大值，那么此时经过 \(\v{root}\) 的路径对答案的贡献就是 \(\sum_{u,v}[\v{subtree}(u)\ne \v{subtree}(v)]\times \min(x_u,x_v)\times\max(y_u,y_v)\)（\(\v{subtree}(u)\) 表示 \(u\) 在 \(\v{root}\) 的哪棵子树中）

但是这个式子实际上是在对三元组 \((\v{subtree}(u),x_u,y_u)\) 求三维偏序，直接求是 \(\mathcal O(n\log^2n)\) 的，加上点分治后复杂度达到 \(\mathcal O(n\log^3n)\)，无法通过此题

考虑我们在点分树统计答案时所用的容斥技巧，将 \(\v{root}\) 对答案的贡献重新表示成 \(\sum_{u,v}\min(x_u,x_v)\times\max(y_u,y_v)-\sum_{u,v}[\v{subtree}(u)= \v{subtree}(v)]\times \min(x_u,x_v)\times\max(y_u,y_v)\)

注意到第二个式子只需要对每个子树中分别求出 \(\sum_{u,v}\min(x_u,x_v)\times\max(y_u,y_v)\) 即可，而这个式子可以看成 \((x_u,y_u)\) 的二维偏序问题，用 CDQ 分治套双指针即可在 \(\mathcal O(n\log n)\) 的时间复杂度内解决（也可以使用平衡树或树状数组维护点的坐标，复杂度相同）

时间复杂度 \(\mathcal O(n\log^2n)\)

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+1,MOD=1e9+7;
vector <int> G[MAXN];
int ans=0;
int a[MAXN],siz[MAXN],cur[MAXN];
int mindis[MAXN],maxdis[MAXN];
bool vis[MAXN];
struct Point {
    int x,y;
    Point(int _x=0,int _y=0): x(_x),y(_y) {}
}    P[MAXN];
int pre[MAXN],suf[MAXN];
inline void calc(int p) {
    auto solve=[&](const vector <int> &ver) -> int {
        int n=ver.size(),ans=0;
        for(int i=1;i<=n;++i) P[i]=Point(mindis[ver[i-1]],maxdis[ver[i-1]]);
        sort(P+1,P+n+1,[](Point u,Point v){ return u.x<v.x; });
        auto CDQ=[&](auto self,int l,int r) -> void {
            if(l==r) return ;
            int mid=(l+r)>>1;
            self(self,l,mid),self(self,mid+1,r);
            pre[l]=P[l].x%MOD; //prefix-sum of x
            for(int i=l+1;i<=mid;++i) pre[i]=(pre[i-1]+P[i].x)%MOD; 
            suf[mid]=P[mid].x*P[mid].y%MOD; //suffix-sum of x*y
            for(int i=mid-1;i>=l;--i) suf[i]=(suf[i+1]+P[i].x*P[i].y%MOD)%MOD;
            
            pre[mid+1]=1; //prefix-sum of 1
            for(int i=mid+2;i<=r;++i) pre[i]=(pre[i-1]+1)%MOD;
            suf[r]=P[r].y; //suffix-sum of y
            for(int i=r-1;i>=mid+1;--i) suf[i]=(suf[i+1]+P[i].y)%MOD;
            
            for(int lp=l,rp=mid;lp<=mid;++lp) {
                while(rp<r&&P[rp+1].y<=P[lp].y)  ++rp;
                if(mid+1<=rp) ans=(ans+P[lp].x*P[lp].y%MOD*pre[rp]%MOD)%MOD;
                if(rp+1<=r) ans=(ans+P[lp].x*suf[rp+1]%MOD)%MOD;
            }
            for(int rp=mid+1,lp=l-1;rp<=r;++rp) {
                while(lp<mid&&P[lp+1].y<=P[rp].y) ++lp;
                if(l<=lp) ans=(ans+P[rp].y*pre[lp]%MOD)%MOD;
                if(lp+1<=mid) ans=(ans+suf[lp+1])%MOD;
            }
            inplace_merge(P+l,P+mid+1,P+r+1,[](Point u,Point v){ return u.y<v.y; });
        };
        CDQ(CDQ,1,n);
        return ans;
    };
    mindis[p]=maxdis[p]=a[p];
    vector <int> ver{p};
    for(int v:G[p]) {
        if(vis[v]) continue;
        vector <int> subt;
        auto dfs=[&](auto self,int p,int fa) -> void {
            ver.push_back(p),subt.push_back(p);
            mindis[p]=min(mindis[fa],a[p]);
            maxdis[p]=max(maxdis[fa],a[p]);
            for(int v:G[p]) {
                if(vis[v]||v==fa) continue;
                self(self,v,p);
            }
        };
        dfs(dfs,v,p);
        ans=(ans+MOD-solve(subt))%MOD;
    }
    ans=(ans+solve(ver))%MOD;
}
inline void dfs(int p) {
    calc(p); vis[p]=true;
    for(int v:G[p]) {
        if(vis[v]) continue;
        int tot=siz[v],rt=0;
        auto get=[&](auto self,int p,int fa) -> void {
            cur[p]=0,siz[p]=1;
            for(int v:G[p]) {
                if(vis[v]||v==fa) continue;
                self(self,v,p);
                cur[p]=max(cur[p],siz[v]);
                siz[p]+=siz[v];
            }
            cur[p]=max(cur[p],tot-siz[p]);
            if(!rt||cur[p]<cur[rt]) rt=p;
        };
        get(get,v,p);
        dfs(rt);
    }
}
inline void solve() {
    int n;
    scanf("%lld",&n);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]),vis[i]=false,G[i].clear();
    ans=0;
    for(int i=1;i<n;++i) {
        int u,v;
        scanf("%lld%lld",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int tot=n,rt=0;
    auto get=[&](auto self,int p,int fa) -> void {
        cur[p]=0,siz[p]=1;
        for(int v:G[p]) {
            if(vis[v]||v==fa) continue;
            self(self,v,p);
            cur[p]=max(cur[p],siz[v]);
            siz[p]+=siz[v];
        }
        cur[p]=max(cur[p],tot-siz[p]);
        if(!rt||cur[p]<cur[rt]) rt=p;
    };
    get(get,1,0);
    dfs(rt);
    printf("%lld\n",(MOD+1)/2*ans%MOD);
}
signed main() {
    int T;
    scanf("%lld",&T);
    while(T--) solve();
    return 0;
}


H. The Faulty Tree

Problem Link

题目大意

给 \(n\) 个权值 \(w_1,w_2,\dots,w_n\)，A 和 B 分别构造一棵二叉树，以 \(1\sim n\) 为叶子并最小化 \(\sum_{i=1}^n w_i\times dep_i\)

其中 A 的二叉树上的每个节点都有 \(\ge 1\) 个儿子是叶子，现在 B 想要使他构造的二叉树的权值严格小于 A 构造的二叉树的权值，求出 A 至少要修改几个 \(w_i\) 的值，并给出方案（无 解输出 \(-1\)）

数据范围： \(n\le 10^6\)

思路分析

注意到 \(n\le 3\) 时两个人构造的树一定同构，因此直接输出

显然 A 会把叶子按权值从小到大，从深到浅排序

考虑在 A 构造的二叉树的基础上进行某种调整操作使得新树的权值更小

显然考虑对二叉树进行 zig-zag 操作，如下图：

p9pebxU.png

注意 \(A,B\) 是节点的权值，\(C\) 是子树的权值和，那么此时树的权值会加上 \(A-C\)

考虑回到序列上，假设 \(w_i\) 按升序排列，其前缀和记为 \(sum_i\)，那么序列 \(w\) 可以使 B 获胜当且仅当存在一个 \(3< i\le n\) 使得 \(w_i<sum_{i-2}\)，若这样的 \(i\) 已经存在，答案为 \(0\)，可以直接输出，而劣的做法一定是使得 \(w_i=w_{i-1}=w_{i-2}\)，此时 \(sum_{i-2}=sum_{i-3}+w_{i-2}=w_{i}+sum_{i-3}>w_i\)，因此答案至多为 \(2\)

考虑答案为 \(1\) 的情况，显然只有可能最小化 \(w_i\) 或最大化 \(sum_{i-2}\)，第一种情况尝试令 \(w_i\gets w_{i-1}\)，第二种情况尝试另 \(w_1\gets w_{i-1}\)，分别判断即可

容易证明不存在其他的策略

时间复杂度 \(\mathcal O(n\log n)\)

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+1;
int a[MAXN],sum[MAXN],p[MAXN],q[MAXN];
inline void solve() {
    int n;
    scanf("%lld",&n);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]),p[i]=i;
    sort(p+1,p+n+1,[&](int x,int y){ return a[x]<a[y]; });
    for(int i=1;i<=n;++i) q[p[i]]=i;
    sort(a+1,a+n+1);
    if(n<=3) { puts("NO"); return ; }
    puts("YES");
    for(int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
    auto print=[&]() { for(int i=1;i<=n;++i) printf("%lld ",a[q[i]]); puts(""); };
    for(int i=3;i<=n;++i) if(sum[i-2]>a[i]) { print(); return ; }
    for(int i=3;i<=n;++i) if(sum[i-2]>a[i-1]) { a[i]=a[i-1],print(); return ; }
    for(int i=3;i<=n;++i) if(sum[i-2]-a[1]+a[i-1]>a[i]) { a[1]=a[i-1],print(); return ; }
    a[n]=a[n-1]=a[n-2],print();
}
signed main() {
    int T;
    scanf("%lld",&T);
    while(T--) solve();
    return 0;
}

标签：Division,le,int,max,texttt,Starters,MAXN,83,out
From： https://www.cnblogs.com/DaiRuiChen007/p/17321333.html

相关文章

  • 1683. 无效的推文
    【题目】表：Tweets+----------------+---------+|ColumnName   |Type   |+----------------+---------+|tweet_id      |int    ||content       |varchar|+----------------+---------+tweet_id是这个表的主键。这个表包含某社交媒体App......
  • 华为认证H12-831题库解析
    1、（单选）某工程师利用2台路由器进行IPv6业务测试,通过运行BGP4+模拟总部与分支的互联互通。如图所示,某工程师抓包查看R1发出的update报文。关于该报文信息的描述,以下哪个说法是正确的?A、该报文描述的路由的下一跳地址为:2001:db8::2345:1::1B、该报文描述的是当前撤销的IPv6路由C......
  • leetcode-830-easy
    PositionsofLargeGroupsInastringsoflowercaseletters,theselettersformconsecutivegroupsofthesamecharacter.Forexample,astringlikes="abbxxxxzyy"hasthegroups"a","bb","xxxx","z"......
  • POJ 1830 开关问题 (高斯消元)
    题目地址：POJ1830高斯消元第一发。一个地方逻辑判断出现了失误，调了一下午啊。。。通过高斯消元来找矩阵的秩，然后2^(自由元的数量)就是答案。因为对于每个自由元，都有0和1两种状态可选。代码如下：#include<iostream>#include<string.h>#include<math.h>#include<queue>#includ......
  • 1835. 所有数对按位与结果的异或和
    题目描述给了列表异或和的定义现在的列表是arr1和arr2构造出来的，元素对是arr[i]andarr[j]问以上列表的异或和？f1-依次确定答案的每一位基本分析为什么考虑计算答案的每一位？表达式只包含位运算（按位与和按位异或）具体怎么计算？要知道答案的第k为是1还是0->分别计算arr1和arr......
  • ASEMI代理AD9833BRMZ-REEL7原装ADI车规级AD9833BRMZ-REEL7
    编辑：llASEMI代理AD9833BRMZ-REEL7原装ADI车规级AD9833BRMZ-REEL7型号：AD9833BRMZ-REEL7品牌：ADI/亚德诺封装：MSOP-10批号：2023+安装类型：表面贴装型引脚数量：10类型：车规级芯片工作温度：−40°C至+105°CAD9833BRMZ-REEL7特性AD9833BRMZ-REEL7是一种低功耗可编程波形能够产生......
  • 383.赎金信——学习笔记
    题目：给你两个字符串：ransomNote和magazine，判断ransomNote能不能由magazine里面的字符构成。如果可以，返回true；否则返回false。magazine中的每个字符只能在ransomNote中使用一次。示例1：输入：ransomNote="a",magazine="b"输出：false示例2：输入：ransomNote="a......
  • LeetCode #283 移动零（双指针版本，效率高）
    基本思路思路————双指针初始状态左右指针都指向数组首位元素，然后right指针开始迭代数组，当碰到非0元素则与左指针left所在位置的元素交换。交换完毕后，左指针left则向前移动到下一位置，做好准备迎接下一个非0元素的交换。这种算法效率比之前撰写的“伪双指针”......
  • UVa 11498 Division of Nlogonia (water ver.)
    11498-DivisionofNlogoniaTimelimit:1.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2493TheProblemAftercenturiesofhostilitiesandskirmishesbetweenthefour......
  • UVa 10783 Odd Sum (water ver.)
    10783-OddSumTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1724Givenarange [a, b],youaretofindthesummationofalltheoddintegersinthisran......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99