Codeforces Deltix Round Summer 2021 [Div.1 + Div.2]个人题解
比赛链接：Codeforces Deltix Round Summer 2021 [Div.1 + Div.2]
A题 A Variety of Operations
题目大意：
给你两个数 \(a\) ，\(b\) ，初始值都为 \(0\)，你有三种操作：\(1.(a+k，b+k)\) \(2.(a+k，b-k)\) \(3.(a-k，b+k)\)
给出 \(c，d\) 问最少的操作次数使 \(a=c\) ，\(b=d\)
思路解析：
我们可以直观地发现三种操作是不会改变 \(a-b\) 的奇偶性的，所以如果 \(c-d\) 为奇数的话就一定不可能有可行方案的。
如果 \(a-b\) 为偶数的话，我们可以发现我们可以用不超过 \(2\) 次操作使它由 \(a,b\) 到 \(c,d\) ，第一步 \((a+(a+b)/2,b+(a+b)/2)\) ,第二步 \((a+(a-b)/2,b-(a-b)/2)\) 或 \((a-(a-b)/2,b+(a-b)/2)\) 。
特别的有两种特殊情况需要考虑，如果 \(c，d\) 都为 \(0\) 的时候，不需要进行任何操作，如果 \(c=d\) 的时候，我们只需进行一次操作一即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
if(n==0&&m==0){
cout<<0<<endl;
continue;
}
if((abs(n-m))%2==1)cout<<-1<<endl;
else if(n==m)cout<<1<<endl;
else cout<<2<<endl;
}
}
B题 Take Your Places!
题目大意：
给出一数组，你可以每次交换相邻的两个元素，问最少多少次能够把数组变成奇偶相间，如果不能输出 \(-1\) 。
思路解析：
首先我们考虑不能的情况：很显然，如果 \(abs(奇数数量-偶数数量)> 1\) 一定不能
如果可行的话，怎样使次数最少呢?
我们可以把交换次数理解为当前元素与它目标位置的距离，因为我们可以通过他们之间距离次交换来交换任意两个元素的位置，所以我们只要把应该交换的元素移到他最近的目标位置即可。
我们可以这样考虑，什么情况下满足最终的要求，只有两种情况：奇偶奇偶奇偶... 或者 偶奇偶奇偶奇...
所以我们就可以单独存储奇数和偶数，按下标大小从小到大，一一对应目标位置的奇偶，答案就只需累加他与目标位置之间的距离即可，当然还需要取 \(min\)
其实，如果 \(abs(奇数数量-偶数数量) = 1\) 的话，可以发现他的目标位置是唯一的
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
ll a[maxn],pos[maxn],top;
ll pos2[maxn];
ll sum,tot;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
tot=0;
sum=0;
ll n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]%2==0)pos[++sum]=i;
else pos2[++tot]=i;
}
if(abs(tot-sum)>1)cout<<-1<<endl;
else {
ll ans=0,ans2=0;
ll now=1;
for(int i=1;i<=sum;i++){
if(pos[i]!=now)ans+=abs(now-pos[i]);
now+=2;
}
now=1;
for(int i=1;i<=tot;i++){
if(pos2[i]!=now)ans2+=abs(now-pos2[i]);
now+=2;
}
if(sum==tot)cout<<min(ans,ans2)<<endl;
else if(sum>tot)cout<<ans<<endl;
else cout<<ans2<<endl;
}
}
}
C题 Compressed Bracket Sequence
题目大意：
给你一个括号字符串的映射数组 \(a\) ，奇数位表示左括号的数量，偶数位表示右括号的数量，这样形成了一个长度为 \(\sum a_i\) 的括号字符串，问有多少合法括号序列子串
思路解析：
AC代码：