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

这次的 cry 场还可以，只掉了亿点等级分

最近几次的performance都很低，包括我同学，我认为这不应该是我们的问题，因为这么多人普遍较低，肯定有哪一个团伙作弊，或者高rating的开小号来虐菜，哎 CF 的 hack 机制大不如前了，缺少了些许的特色

A. A Gift From Orangutan

题意

猩猩送给你一个长度为 $n$ 的数组 $a$。使用 $a$，你将构造两个数组 $b$ 和 $c$，这两个数组都包含 $n$ 个元素，具体方式如下：

• $b_i=\min (a_1,a_2,...,a_i)$
• $c_i=\max (a_1,a_2,...,a_i)$

定义得分为 ${\sum }_{i=1}^n{c}_i-b_i$。在计算得分之前，你可以随意 打乱 $a$ 的元素。

如果你按最佳方式对 $a$ 的元素进行打乱，找到你可以获得的最大得分。

思路

把最小的放第一个，最大的放第二个，答案直接计算即可

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=2e9;
void solve(){
	int n;
	cin>>n;
	int mx=0,mn=inf;
	for(int i=0;i<n;i++){
        int x;
		cin>>x;
		mx=max(mx,x);
		mn=min(mn,x);
	}
	cout<<(mx-mn)*(n-1)<<endl;
}
signed main(){
    int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

B. Minimise Oneness

思路

对于任意的 $01$ 字符串 $t$，设 $f(t)$ 为只包含 $0$ 的 $t$ 的非空 子序列 的数量，设 $g(t)$ 为至少包含一个 $1$ 的 $t$ 的非空子序列的数量。

定义 $t$ 的 单一性 为 $|f(t)-g(t)\mid$，给定一个 $n$，找到一个长度为 $n$ 的二进制字符串 $s$，使其 单一性 尽可能小。如果存在多个字符串，你可以输出其中的任何一个。

思路

设字符串 $s$ 中 $0$ 的数量为 $k$，则 $f(s)=2^k-1$，$g(s)=(2^n-1)-(2^k-1)$

相减得：$f(s)-g(s)=2^{k+1}-2^n$

可得，当 $k=n-1$ 时，$|f(s)-g(s)|=0$

所以无论顺序，这个字符串应该包含 $n-1$ 个 0 和 $1$ 个 1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
	cin>>t;
	while(t--){
		int n;
        cin>>n;
        n--;
        while(n--){
            cout<<0;
        }
        cout<<1<<endl;
	}
	return 0;
}

C. A TRUE Battle

题意

Alice 和 Bob 正在玩一个游戏。给定一个长度为 $n$ 的 $01$ 字符串，其中包含 $n$ 个布尔值，每个值要么是 true，要么是 false（其中 $1$ 表示 true，$0$ 表示 false）。最开始，布尔值之间没有运算符。

Alice 和 Bob 将轮流在布尔值之间放置 && 或 || 运算符，Alice 先手。因此，游戏将进行 $n-1$ 轮。Alice 旨在让最终表达式的值为 true，而 Bob 旨在让其值为 false。给定布尔值列表，判断如果两位玩家都采取最佳策略，Alice 是否会获胜。

注意，表达式 1||0&&0 被视为 1||(0&&0) = 1||0 = 1。

思路

我们从优先级较低的或运算 || 开始想起：整个式子一定被分为这种类型：(...)||(...)||(...) ..... ，其中 ... 种 一定为 数字或只带 && 运算的表达式

若存在 || ，则只要 ... 处有一个表达式的值为 $1$，最终的值一定为 $1$

当首或尾为 1 时，一定可以分割成 $1||(...)||(...).....$ ，所以一定可以为 $1$

否则，当中间部分存在两个连续的 1 时，一定可以，因为 Alice 先手可以将它变成 ||11，其次：

• Bob 可以把它变成 ||11&&，那么 Alice 再补成 ||1||1&& ，整个式子可以被分割成 $(...)||(...)||1||(...).....$ ，所以一定可以为 $1$
• Bob 也可以选择变成||1&&1 ，此时 Alice 再补成 ||1&&1|| ，整个式子可以被分割成 $(...)||(...)||(1\&\&1)||(...).....$ ，所以一定可以为 $1$

再否则，一定不可以变为 $1$

总而言之，当且仅当 $s$ 首尾为 $1$ 或者 存在两个连续的 $1$ 时，答案为 YES ，否则为 NO

C++ 代码

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n;
    string s;
	cin>>n>>s;
	if(s[0]=='1'||s.back()=='1'){
		YES;
		return;
	}
	for(int i=0;i<n-1;i++){
		if(s[i]=='1'&&s[i+1]=='1'){
			cout<<"YES"<<endl;
			return;
		}
	}
	cout<<"NO"<<endl;
}
int main(){
    int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}