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");
}