Codeforces Round 983 (Div. 2) 题解

Codeforces Round 983 (Div. 2)

Problem - A - Codeforces

解题思路

• 考虑贪心，每个灯连两个开关，即两个开的灯可以关闭一盏灯，则灯数最多则尽可能让两个开关都开的灯尽量少，灯数最少则反之

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int a[110];
void solve(){
	int n;cin>>n;
	int cnt0=0,cnt1=0;
	for(int i=1;i<=2*n;i++){
		int x;cin>>x;
		if(x==1) cnt1++;
		else cnt0++;
	}
	int ans1=0,ans2=0;
	if(cnt1<=n) ans1=cnt1;
	else ans1=n-(cnt1-n);
	ans2=cnt1%2;
	cout<<ans2<<" "<<ans1<<endl;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}

Problem - B - Codeforces

解题思路

• 构造，我们可以考虑这样一个构造，将数组分成三段，第k个数为中间一段，并且令k为中位数，这样的话，加上前后的数组则满足题目意思
• 注意特判n=1时直接输出1，k=1或k=n时输出-1
• k要分奇偶讨论，如果k为偶数则[1,k-1],[k,k],[k+1,n];如果k为奇数则[1,k-2],[k-1,k+1],[k+2,n]

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=2e5+10;
int a[N];
void solve(){
	int n,k;cin>>n>>k;
	if(n==1){
		cout<<1<<endl;
		cout<<1<<endl;
		return;
	}
	if(k==1 || k==n){
		cout<<-1<<endl;
		return;
	}
	if(k%2==0){
		cout<<3<<endl;
		cout<<1<<" "<<k<<" "<<k+1<<endl;
	}
	else{
		cout<<3<<endl;
		cout<<1<<" "<<k-1<<" "<<k+2<<endl;
		return;
	}
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}

Problem - C - Codeforces

解题思路

• 要满足a[i]+a[j]>a[k],那么假如我们让最小的两个值相加能大于数组里的最大值，则一定可以满足，不妨排序一下，我们二分第一个大于a[1]+a[2]的位置id,则我们只需更改n-id+1个数则可以满足题意
• 但上述不一定是最少的操作次数，因为我们也可以通过更改a[1]或者a[2]使得满足题意思，如果我们更改a[1],a[2]的值，我们一定能让其中一个数与其他数的和都能满足题意
• 所以我们可以将题意简化成，我们每次删除一个数字，使得所有的a[i]+a[j]>a[k]，(因为我们最多对一个数操作一次赋值，并且他与其他数的和一定满足题意)
• 所以枚举a[i],二分第一个大于a[i]+a[i+1]的位置id,ans即为(i-1)+(n-id+1)
• 时间复杂度为O(nlogn)

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	int ans=1e9;
	for(int i=1;i<=n-1;i++){
		int x=a[i]+a[i+1];
		int id=lower_bound(a+1,a+n+1,x)-a;
		int tmp=n-id+1+i-1;
	//	cout<<x<<" "<<id<<" "<<tmp<<endl;
		ans=min(ans,tmp);
	}
	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;
}

Problem - D - Codeforces

解题思路

• 感觉难点在于读题，题目的三条性质其实表示这是一颗层序遍历的树，除0点外每一个节点只有一个孩子
• 我们可以通过一个队列进行模拟询问，只要找出节点1的孩子之后剩下的就依次询问即可
• 详情见代码部分

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int fa[N];
int ask(int x,int y){
	cout<<"? "<<x<<" "<<y<<endl;
	int tmp;cin>>tmp;
	return tmp;
}
void solve(){
	int n;cin>>n;
	fa[1]=0;
	queue<int> q;
	q.push(1);
	int now=2;
	while(now<n){
		int tmp=ask(1,now);
		if(tmp==1){
			fa[now]=0;
			q.push(now);
			now++;
		}
		else if(tmp==0){
			fa[now]=1;
			q.pop();//1出队
			q.push(now);
			now++;
			break;
		}
	}
	while(now<n){
		int t=q.front();
		q.pop();
		int tmp=ask(t,now);
		if(tmp==0){
			fa[now]=t;
			q.push(now);
			now++;
		}
	}
	cout<<"! ";
	for(int i=1;i<n;i++) cout<<fa[i]<<" ";
	cout<<endl;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}