Codeforces Round 973 (Div. 2) A-C 题解

C 提交 MLE 了一次，原因是找到答案没加感叹号

A. Zhan’s Blender

题意

原题描述还是不太清楚

你有 $n$ 个水果，每秒可以放入搅拌机 $y$ 个水果，搅拌机每秒可以搅拌 $x$ 个水果，问最终至少需要多少秒能搅完？

注意，可以同步进行，如第一秒时候，我们可以放如 $3$ 个，搅拌机搅了 $1$ 个

思路

$$工作时间=\frac{工作总量}{工作效率}$$

当 $x\ge y$ 时，工作效率取决于 $y$

否则取决于 $x$

则工作效率为 $\min (x,y)$

所以最终答案为 $\lceil \frac{n}{\min (x,y)}\rceil$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int inf=2e9;
const int MOD=998244353;
const int maxn=200005;
void solve(){
	int n,x,y;
	cin>>n>>x>>y;
	int p=min(x,y);
	cout<<(n+p-1)/p<<endl;
}
int main(){
    int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

B. Battle for Survive

题意

$n$ 个战士，第 $i$ 个评分 $a_i$，共 $n-1$ 场比赛，每次比赛你可以选择 $i,j(1\le i<j\le n)$，此时 $i$ 战败消失，$j$ 的评分需要减去 $a_i$，问最终剩下的那个战士的评分的 最大值

输入的 $a_i$ 是正整数，但每次比赛结束后 $a_j$ 可以变为负数

思路

因为 $i<j$ 可得，最终剩下的战士一定是最右边的

那么贪心思路如下：

要使得最右边的大，它减去的值就要尽可能小，所以左边 $n-1$ 个的最终值尽可能小；

因为 $a_i$ 为正整数，所以左边 $n-1$ 个最小为 $a_{n-1}-a_{n-2}-...-a_1$

那么最终答案为 $a_n-(a_{n-1}-a_{n-2}-...-a_1)$

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
	int n;
	cin>>n;
	vector<int> v(n);
	for(int i=0;i<n;i++){
		cin>>v[i];
	}
	int ans=v[n-2];
	for(int i=n-3;i>=0;i--){
		ans-=v[i];
	}
	cout<<v[n-1]-ans<<endl;
}
signed main(){
    int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

C. Password Cracking

题意

本题为 交互题

有一个长度为 $n$ 的 01字符串，每次你可以询问任意一个 01字符串 是不是这个串的子串，若是回应 1，否则回应 0

询问最多 $2n$ 次，每次格式为 ? t

思路

不管位置，只要存在就一直往下问。

每次分别询问当前串 + 0 和 + 1 ，哪个是加哪个。若都不是，说明到最后了，开始往前找

最后输出即可

C++ 代码

#include<bits/stdc++.h>
using namespace std;

bool query(string t){
	cout<<"? "<<t<<endl;
	bool res;
	cin>>res;
	return res;
}

void solve(){
	int n;
	string s="0";
	cin>>n;
	bool flag=true; //flag 表示当前串是否已经到了结尾，到了为false，往前找；没到为true，往后找
	bool tmp=query("0");
    
    //特殊情况判断
	if(!tmp){
		s="";
		while(n--){
			s+="1";
		}
		cout<<"! "<<s<<endl;
		return;
	}
    
	for(int i=2;i<=n;i++){
		if(flag){
			bool f1=query(s+"0");
			bool f2=query(s+"1");
			if(f1){
				s+="0";
			}else if(f2){
				s+="1";
			}else{
				flag=false;
				bool p=query("0"+s);
				if(!p){
					s="1"+s;
				}else{
					s="0"+s;
				}
			}
		}else{
			bool fl=query("0"+s);
			if(fl){
				s="0"+s;
			}else{
				s="1"+s;
			}
		}
	}
	cout<<"! "<<s<<endl;
}

int main(){
    int tt;
	cin>>tt;
	while(tt--){
		solve();
	}
	return 0;
}