牛客周赛 Round 70 个人题解 (A~G)

牛客周赛 Round 70

A. 小苯晨跑

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void solve(){
	int a,b,c,d;cin>>a>>b>>c>>d;
	if(a==b && b==c && c==d){
		cout<<"NO"<<endl;
	}
	else cout<<"YES"<<endl;

}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}

B. 小苯过马路

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void solve(){
	int x,y,k,t;
	char c;
	cin>>x>>y>>k>>t>>c;
	if(c=='G'){
		int ans=0;
		if(k>=t) ans=t;
		else ans=t+k+x;
		cout<<ans<<endl;
	}
	else if(c=='R'){
		int ans=k+t;
		cout<<ans<<endl;
	}

}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T=1;
	while(T--) solve();
	return 0;
}

C. 小苯的字符串染色

题目分析

• 因为操作次数不大于n，所以直接对每个黑块染色即可

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void solve(){
	int n;cin>>n;
	string s;cin>>s;
	s=" "+s;
	int tot=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='1') tot++;
	}
	cout<<tot<<endl;
	for(int i=1;i<=n;i++){
		if(s[i]=='1'){
			cout<<i<<" "<<i<<endl;
		}
	}
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}

D. 小苯的能量项链

题目分析

• 维护前缀max 与后缀max，O(n)查询即可

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=5e5+10;
int a[N],pre[N],suf[N];
void solve(){
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(n==1){
		cout<<a[1]<<endl;
		return;
	}
	else if(n==2){
		cout<<a[1]+a[2]<<endl;
		return;
	}
	pre[0]=0,suf[n+1]=0;
	for(int i=1;i<=n;i++){
		pre[i]=max(a[i],pre[i-1]);
	}
	for(int i=n;i>=1;i--){
		suf[i]=max(a[i],suf[i+1]);
	}
	int ans=0;
	for(int i=1;i<=min(n-1,k+1);i++){
		int l=i;
		int r=max(i+1,n-k+i-1);
		int c1=pre[l],c2=suf[r];
		ans=max(ans,c1+c2);
	}
	cout<<ans<<endl;
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}

E. 小苯的最短路

题目分析

• 考察异或性质的一道题，和之前 cf一道题类似codeforces.com/contest/2036/problem/F

• f[l,r]表示l xor l+1 xor ... xor r

  • 当r%4==0时,f[0,r]=n
  • 当r%4==1时,f[0,r]=1
  • 当r%4==2时,f[0,r]=n+1
  • 当r%4==3时,f[0,r]=0

• 由于是完全图，所以点1到每个点的最短路就是两点的边，所以经过化简后可得，ans=f[1,n] xor n个1的xor和

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
void solve(){
	int n;cin>>n;
	int t=0;
	if(n%4==0) t=n;
	else if(n%4==1) t=1;
	else if(n%4==2) t=n+1;
	else if(n%4==3) t=0;
	if(n%2==0){
		cout<<t<<endl;
	}
	else{
		int ans=1^t;
		cout<<ans<<endl;
	}
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}

F. 小苯的优雅好序列

题目分析

• 题解的证明很好，这里引用一下
• 首先不难发现，如果要满足这个数组的所有连续子数组都优秀，那么相邻两个数一定要满足条件，即a[i]|a[i+1]或者a[i+1]|a[i]
• 
• 推出该式子后，只需找到相邻两项最大的d，然后枚举他的因数，再暴力check即可

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=5e4+10;
int a[N];
void solve(){
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int maxn=1e18,idx=0;
	for(int i=2;i<=n;i++){
		int tmp=abs(a[i]-a[i-1]);
		if(tmp && tmp<maxn){
			maxn=tmp;
			idx=i;
		}
	}
	if(maxn==1e18){
		cout<<k<<" "<<k*(k+1)/2<<endl;
		return;
	}
	int num=min(a[idx],a[idx-1]);
	vector<int> v;
	for(int i=1;i*i<=maxn;i++){
		if(maxn%i!=0) continue;
		int x=i-num;
		if(x>0 && x<=k) v.push_back(x);
		if(maxn/i!=i){
			int t=maxn/i;
			int _x=t-num;
			if(_x>0 && _x<=k) v.push_back(_x);
		}	
	}
	int cnt=0,ans=0;
	for(auto x:v){
		bool flag=1;
		for(int i=2;i<=n;i++){
			int t1=a[i-1]+x;
			int t2=a[i]+x;
			if(t1%t2 && t2%t1){
				flag=0;
				break;
			}
		}
		if(flag){
			cnt++;
			ans+=x;
		}
	}
	cout<<cnt<<" "<<ans<<endl;
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}