Codeforces Round 870 (Div. 2)

Codeforces Round 870 (Div. 2)

A - Trust Nobody

思路：枚举每一种说谎人数x，若a[i]大于x则说谎人数加一，判断最后说谎总人数是否为x，若是则输出x，结束枚举；若没有满足的x则-1

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

const double eps=1e-6;
typedef long long ll;

int t,n,a[N];
bool cmp(int x,int y){
    return x>y;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;++i)cin>>a[i];
        bool ok=false;
        for(int i=0;i<=n;++i){
            int c=0;
            for(int j=0;j<n;++j){
                if(a[j]>i)c++;
            }
            if(c==i){
                cout<<i<<'\n';
                ok=true;
                break;
            }
        }
        if(!ok)cout<<-1<<'\n';
    }
    return 0;
}

 B - Lunatic Never Content

思路：若两数分别对x求余后的值相等，则该两数相减后的值一定是x的倍数，对所有对称的数相减后的值求最大公因数即可

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

const double eps=1e-6;
typedef long long ll;

int t,n,a[N];


int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        int res=0;
        for(int i=0;i<n;++i)cin>>a[i];
        if(n!=1){
            for(int i=0;i<n/2;++i){
                if(i==0)res=abs(a[i]-a[n-i-1]);
                else res=__gcd(res,abs(a[i]-a[n-i-1]));
            }
        }
        cout<<res<<'\n';
    }
    return 0;
}

C - Dreaming of Freedom

思路：每种选择的个数相同则是NO，那么就判断是否能让每种选择的个数相同；那就求x的最小的非1因子，若y大于等于该因子则NO；x的范围1e6，可以先处理出所有范围内的数的最小因子

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

const double eps=1e-6;
typedef long long ll;

int t,x,y;
bool st[N];
int primes[N],idx;
void P(){
    st[1]=true;
    for(int i=2;i<=N-5;++i){
        if(!st[i])primes[idx++]=i;
        for(int j=0;primes[j]*i<=N-5;++j){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    P();
    while(t--){
        cin>>x>>y;
        bool ok=true;
        if(!st[x]&&y>=x)ok=false;
        if(st[x]){
            for(int i=2;i<=x;++i){
                if(x%i==0){
                    if(y>=i)ok=false;break;
                }
            }
        }
        if(ok)cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

D - Running Miles

思路：由于a，b，c是[l，r]中最大的三个数，要使a+b+c-(r-l)最大，对于固定的abc，（r-l）就要最小，假设abc按下标顺序排，那么r对应的是c的下标，l对应的是a的下标；a+b+c-(r-l) = (a+l)+b+(c-r)，求出ai+i的最大前缀值和ci-i的最大后缀值，枚举b即可

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

const double eps=1e-6;
typedef long long ll;

ll t,n,b[N],l[N],r[N];

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;++i){
            cin>>b[i];
            l[i]=max(l[i-1],i+b[i]);
        }
        for(int i=n;i>=1;--i){
            if(i==n)r[i]=b[i]-i;
            else r[i]=max(r[i+1],b[i]-i);
        }
        ll res=-INF;
        for(int i=2;i<=n-1;++i){
            res=max(res,b[i]+l[i-1]+r[i+1]);
        }
        cout<<res<<'\n';
    }
    return 0;
}