Codeforces Round 862 (Div. 2) （4.2）

Codeforces Round 862 (Div. 2)

A - We Need the Zero

思路:某个数被异或两次相当于没变，即判断n的奇偶性；n为偶数时判断所有数异或后的数是否为0，若为0，输出任意数；n为奇数时答案为所有数异或后的值

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=5e3+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int t,n,x;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        int ans=0;
        for(int i=0;i<n;++i){
            cin>>x;
            ans^=x;
        }
        if(n%2)cout<<ans<<'\n';
        else{
            if(ans==0)cout<<0<<'\n';
            else cout<<"-1\n";
        }
    }
    return 0;
}

B - The String Has a Target

思路：对1~n-1中的最后一个大于等于s[0]的s[i]进行操作

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=5e3+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int t,n;
string s;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>s;
        char mi=s[0];
        int p=0;
        for(int i=s.size()-1;i>0;--i){
            if(s[i]<mi||(s[i]==mi&&p==0)){p=i,mi=s[i];}
        }
        cout<<s[p];
        for(int i=0;i<s.size();++i)
            if(i!=p)cout<<s[i];
        cout<<'\n';
    }
    return 0;
}

C - Place for a Selfie

思路：判断ax²+（b-k）x+c=0是否有解，即（b-k）²-4ac<0，将所有k排列，二分出距离b最近的k，看不等式是否成立

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int t,n,m;
double k[N];
struct E{
    double a,b,c;
}g[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=0;i<n;++i)cin>>k[i];
        sort(k,k+n);
        for(int i=0;i<m;++i){
            bool ok=false;
            cin>>g[i].a>>g[i].b>>g[i].c;
            double b=g[i].b,a=g[i].a,c=g[i].c;
            int p= upper_bound(k,k+n,b)-k;
            if(p!=0){
                double s=b-2*sqrt(a*c);
                if(k[p-1]>s){
                    cout<<"YES\n";
                    cout<<(int)k[p-1]<<'\n';
                    ok=true;
                }
            }
            if(!ok&&p<n){
                double s=b+2*sqrt(a*c);
                if(k[p]<s){
                    cout<<"YES\n";
                    cout<<(int)k[p]<<'\n';
                    ok=true;
                }
            }
            if(!ok)cout<<"NO\n";
        }
    }
    return 0;
}

D - A Wide, Wide Graph

思路:找出直径的两端点，从两端点bfs求每个点到端点的最大距离；对于每个k，若点到端点的距离大于等于k就可以连通，求出Gk的所有连通块

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int t,n,m;
double k[N];
struct E{
    double a,b,c;
}g[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=0;i<n;++i)cin>>k[i];
        sort(k,k+n);
        for(int i=0;i<m;++i){
            bool ok=false;
            cin>>g[i].a>>g[i].b>>g[i].c;
            double b=g[i].b,a=g[i].a,c=g[i].c;
            int p= upper_bound(k,k+n,b)-k;
            if(p!=0){
                double s=b-2*sqrt(a*c);
                if(k[p-1]>s){
                    cout<<"YES\n";
                    cout<<(int)k[p-1]<<'\n';
                    ok=true;
                }
            }
            if(!ok&&p<n){
                double s=b+2*sqrt(a*c);
                if(k[p]<s){
                    cout<<"YES\n";
                    cout<<(int)k[p]<<'\n';
                    ok=true;
                }
            }
            if(!ok)cout<<"NO\n";
        }
    }
    return 0;
}