题解 | 牛客周赛 Round 110

A

如果 和 互质，这最大不能表示的数为 。

这时，， 最大不能表示的数就为 。

#include<bits/stdc++.h>
using namespace std;
int n;
signed main(){
    //HAPPY!
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    cout<<(n==1?"NO\n":"YES\n"); 
    return 0;
}

B

贪心将最小放两边即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n;
signed main(){
	//HAPPY!
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int tcase;
	cin>>tcase;
	while(tcase--){
		cin>>n;
		int mn1=1e9,mn2=1e9;
		ll sum=0;
		for(int i=1;i<=n;i++){
			int x;
			cin>>x;
			if(mn1>x){
				mn2=mn1,mn1=x;
			}
			else if(mn2>x){
				mn2=x;
			}
			sum+=x;
		}
		cout<<sum*2-mn1-mn2<<"\n"; 
	}
	return 0;
}

C

找最大值，看左右两边不为 ，之后分类讨论即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=3e5+5;
int n;
int a[N];
signed main(){
	//HAPPY!
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int tcase;
	cin>>tcase;
	while(tcase--){
		cin>>n;
        int mx=0;
		for(int i=1;i<=n;i++){
            cin>>a[i];
            mx=max(mx,a[i]);
		}
        bool f=0;
        for(int i=1;i<=n;i++){
            if(mx==a[i]){
                if(i>1 && a[i-1]){
                    f|=1;
                }
                if(i<n && a[i+1]){
                    f|=1;
                }
            }
        }
        if(f){
            cout<<mx<<"\n";
        }
		else if(mx<=1){
            cout<<"-1\n";
        }
        else{
            cout<<mx-1<<"\n";
        }
	}
	return 0;
}

D

贪心删最小或最大。

枚举发现，若删最小，则 为数组 的 ；若删最大，则 为数组 的 。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+5;
int n;
int a[N];
signed main(){
	//HAPPY!
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int tcase;
	cin>>tcase;
	while(tcase--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
        sort(a+1,a+n+1);
        ll ans=0;
        for(int i=1;i<n;i++){
            ans+=abs(a[i]-a[(n+1)/2]);
        }
        ll res=0;
        for(int i=2;i<=n;i++){
            res+=abs(a[i]-a[(n+1)/2+1]);
        }
        cout<<min(ans,res)<<"\n";
	}
	return 0;
}

E

每进一次位，数字和就要减九，因此可以模九。

但判断连续的字串差值为 的情况。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+5;
string s;
int sum[N],f[N],g[N];
signed main(){
	//HAPPY!
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int tcase;
	cin>>tcase;
	while(tcase--){
		cin>>s;
		int n=s.size();
		for(int i=0;i<n;i++){
			sum[i+1]=(sum[i]+s[i]-'0')%9;
		}
		for(int i=0;i<9;i++){
			f[i]=g[i]=0;
		}
		for(int i=0;i<=n;i++){
			f[sum[i]]++;
		}
		ll z=0;
		for(int i=0;i<9;i++){
			z+=f[i]*(f[i]-1ll)/2;
		}
//		cout<<z<<" ";
		ll rz=0;
		for(int i=0;i<n;){
			if(s[i]=='0'){
				int j=i;
				while(j<n && s[j]=='0'){
					j++;
				} 
				int delta=j-i;
				rz+=delta*(delta+1ll)/2;
				i=j;
			}
			else{
				i++;
			}
		}
//		cout<<rz<<" "; 
		ll res=0;
		for(int i=0;i<=n;i++){
			for(int j=0;j<9;j++){
				int diff=(sum[i]-j+9)%9;
				res+=1ll*diff*g[j];
			}
			g[sum[i]]++;
		}
		ll ans=res+9*(z-rz);
		cout<<ans<<"\n"; 
	}
	return 0;
}

F

考虑只有连续段为 或 。

因为连续段为大于等于 ，则可以将两个段连续段合并起来。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n;
int a[N],sum[N];
signed main(){
	//HAPPY!
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int tcase;
	cin>>tcase;
	while(tcase--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
            sum[i]=sum[i-1]^a[i];
		}
        int ans=sum[n],res=0;
        for(int i=n;i>=0;i--){
            res^=a[i];
            ans=max(ans,sum[i-1]&res);
        }
		cout<<ans<<"\n";
	}
	return 0;
}