Codeforces Deltix Round Summer 2021 [Div.1 + Div.2]个人题解
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
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< B题 Take Your Places!
题目大意：
给出一数组，你可以每次交换相邻的两个元素，问最少多少次能够把数组变成奇偶相间，如果不能输出 \(-1\) 。
思路解析：
首先我们考虑不能的情况：很显然，如果 \(abs(奇数数量-偶数数量)> 1\) 一定不能
如果可行的话，怎样使次数最少呢?
我们可以把交换次数理解为当前元素与它目标位置的距离，因为我们可以通过他们之间距离次交换来交换任意两个元素的位置，所以我们只要把应该交换的元素移到他最近的目标位置即可。
我们可以这样考虑，什么情况下满足最终的要求，只有两种情况：奇偶奇偶奇偶... 或者 偶奇偶奇偶奇...
所以我们就可以单独存储奇数和偶数，按下标大小从小到大，一一对应目标位置的奇偶，答案就只需累加他与目标位置之间的距离即可，当然还需要取 \(min\)
其实，如果 \(abs(奇数数量-偶数数量) = 1\) 的话，可以发现他的目标位置是唯一的
AC代码：
#include
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<tot)cout< C题 Compressed Bracket Sequence
题目大意：
给你一个括号字符串的映射数组 \(a\) ，奇数位表示左括号的数量，偶数位表示右括号的数量，这样形成了一个长度为 \(\sum a_i\) 的括号字符串，问有多少合法括号序列子串
思路解析：
我们可以从前往后枚举左括号，来计算每种左括号对应的情况数，毕竟每个合法子序列都是以左括号开头的。
那么我们该如何计算呢？
我们对于每组左括号，向右遍历，如果是左括号，我们就把他加到额外的左括号里（注意这个额外的并非是我们枚举的那个左括号），对于右括号，我们优先把他与额外的左括号匹配，不加入答案，因为在后面我们还会枚举到这个右括号的上一个左括号，避免重复计算，如果匹配完后右括号还有剩余，就和枚举的左括号匹配，加入答案，当右括号此时还有剩余，那么就退出当前左括号遍历，否则继续向下匹配知道把左括号全部匹配掉。
另外，对于每种情况，我们还需要加上好几个合法已匹配的括号序列并排的情况，判断一下就好
AC代码：
#include
using namespace std;
typedef pair pii;
typedef long long ll;
const int maxn=1e5+5;
ll a[maxn],ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i+=2){
ll top=a[i],m=0;
for(int j=i+1;j<=n;j++){
if(j%2==1){
m+=a[j];
}
else {
ll sum=a[j];
ll p=min(sum,m);
sum-=p;m-=p;
if(m==0){
p=min(top,sum);
ans+=p+(j>i+1);
top-=p;sum-=p;
if(sum)break;
}
}
}
}
cout<