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;
}

原文地址：https://blog.csdn.net/AKDreamer_HeXY/article/details/142440628

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！