Codeforces Round 862 (Div. 2)

A. We Need the Zero　

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

B. The String Has a Target

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

C. Place for a Selfie

int a[N];
bool check(double ranl,double ranr , int x) {
       if(ranl<a[x] && a[x]<ranr){
        return true;
       }else return false;
 }
int bs1(double ranl,double ranr, int l, int r){ //左偏二分
    while (l < r){
        int mid = l + r >> 1;
        if (ranl<a[mid]&&a[mid]<ranr) return mid; 
        else if(ranr<=a[mid])r=mid;  
        else l = mid + 1;
    }
    return l;
}
void solve(){
    int n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    sort(a+1,a+1+n);
    for(int i=1;i<=m;i++){
        int aa=read(),b=read(),c=read();
        double ranl=b-sqrt(4*aa*c);
        double ranr=b+sqrt(4*aa*c);
        // cout<<ran<<'\n';
        int poi=bs1(ranl,ranr,1,n);
        if(ranl<a[poi] && a[poi]<ranr){
            cout<<"YES\n";
            cout<<a[poi]<<'\n';
        }else cout<<"NO\n";
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

D. A Wide, Wide Graph

首先直径的两个端点是最容易连起来的一条边如果k大于等于直径必然答案为n

如果k的值小于直径那么只要判断每个点接入直径的的端点的长度是否大于k

确实比较简单(*1800) 树上直径就没什么内容了但是我的树真的是yi‘tuo

vector<int>g[N];
void dfs(int v,int par,int h,vector<int> &d){
    d[v]=h;
    for(int i:g[v]){
        if(i!=par){
            dfs(i,v,h+1,d);
        }
    }
}
void solve(){
    int n=read();
    for(int i=1;i<n;i++){
        int x=read()-1,y=read()-1;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vector<int>d1(n),d2(n);
    dfs(0,-1,0,d1);
    int a=max_element(d1.begin(),d1.end())-d1.begin();  //得到深度最大的点a
    dfs(a,-1,0,d1);
    int b=max_element(d1.begin(),d1.end())-d1.begin();  //计算每个点到a点的距离 记录距离a点最远的b点
    dfs(b,-1,0,d2);                              //计算每个点到b点的距离
    for(int i=0;i<n;i++){                       
        d2[i]=max(d2[i],d1[i]);                    //计算每个点到直径端点的最长路径
    }
    sort(d2.begin(),d2.end());
    int ans=0;
    for(int i=1;i<=n;i++){
        while(ans<n&&d2[ans]<i){
            ans++;
        }
        cout<<min(n,ans+1)<<" ";
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}