Codeforces Round 879 (Div. 2) A-D题解
第一次写题解，请见谅O3O
a题代码是完整的，后面的只显示主要内容的代码
A. Unit Array
题目解释
他会给你一个只包含1或者-1的数字串，每次操作可以把1变成-1或者把-1变成1，要求操作之后的串满足每一位累加>=0,每一位累乘=1，求最小的操作次数
思路分析
累加>=0说明1的个数要大于等于-1的个数，累乘=1说明-1的个数是偶数,所以只需要比较小于等于n的一半的最大偶数和-1的个数
代码
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define endl '\n'
#define int long long
typedef long long ll;
typedef unsigned long long ull;
const ll N=5e5+7;
constexpr ll mod = 1e9+7;
const ll inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
void solve()
{
int n,num=0;
cin>>n;
for(int i=0;i<n;i++)
{
int t;
cin>>t;
if(t==-1) num++;
}
if(num%2==0&&num<=n/2)
{
cout<<0<<"\n";
}
else if(num<=n/2)
{
cout<<"1\n";
}
else
{
int t=n/2;
if(t%2==1) cout<<num-t+1<<"\n";
else cout<<num-t<<"\n";
}
}
signed main()
{
IOS;
int _=1;
cin>>_;
while(_--)
{
solve();
}
return 0;
}
B. Maximum Strength
题目解释
告诉你两个数字，你可以在两个之间选择任意两个数（包括端点），要求找到每一位上数字差值的和的最大值
思路分析
最优的解法就是找到形如100000和99999 如果位数不相同就是第一个数加上后面位数*9，如果位数相同，就是找到第一个不相同的，答案是第一个不相同的差值加上后面位数 *9
代码
void solve()
{
string a,b;
cin>>a>>b;
if(a.length()<b.length())
swap(a,b);
int sum=0,l=a.length()-b.length();
for(int i=0;i<l;i++)
{
b="0"+b;
}
int g=0;
for(int i=0;i<a.length();i++)
{
if(g==0&&a[i]!=b[i])
{
g=1;
sum+=abs(a[i]-b[i]);
}
else if(g==1)
{
sum+=9;
}
}
cout<<sum<<"\n";
}
C. Game with Reversing
题目解释
给你两个字符串，A可以选择一个字符串中的一个字符将他变成另一个字符，B可以选择一个字符串将他对称翻转，A是先手，操作顺序是ABABABAB·····要求你找到使两个字符串完全相同的最小的操作次数。
思路分析
B的操作，就相当于正方向匹配和反向匹配，并且操作两次就相当于没有操作（有点类似a的-1），那我们只要找到正向匹配不同字符的个数和最小的偶数次反转操作，还有逆向匹配不同的字符个数和最小奇数次翻转操作。这两个的最小值就是答案
代码
void solve()
{
int n,num1=0,num2=0;
string a,b;
cin>>n>>a>>b;
for(int i=0;i<n;i++)
{
if(a[i]!=b[i]) num1++;
if(a[i]!=b[n-1-i]) num2++;
}
if(num1==0) cout<<0<<"\n";
else if(num2==0) cout<<2<<"\n";
else cout<<min(num1+num1-1+(num1-1)%2,num2+num2-(num2-1)%2)<<"\n";
}
D. Survey in Class
题目解释
给你n个区间，要求找到一个区间里面数的个数减去和另一个区间重叠的数的个数的最大值
思路分析
两个区间的情况只有三种，分别是没有任何部分重叠，部分重叠，还有就是一个区间完全被包含。
没有任何部分重叠就是最大的左边界不在区间里面，或者最小的右边界不在区间里面，那就考虑这一区间的本身长度。
部分重叠情况几乎就是上面情况的反面，如果最大的左边界在区间里面，就考虑最大的左边界减去区间左边界；如果最小的右边界在区间里面，就考虑区间右边界减去最小有边界。
第三种情况可能会被非法统计在上面，但是我们只需要考虑最长和最短之间的差，因为如果有多组重叠，并且这个也重叠，那这个肯定是最大的；如果两个是相交的那答案肯定出现在上一种情况；如果不相交，那就会出现在第一种。简单的来说就是如果重叠的情况是答案，那就只可能是最大和最小的重叠。
答案是所有情况的最大值
代码
pair<int,int> p[N];
void solve()
{
int n,m;
cin>>n>>m;
int l1=-1,l2=inf,l=-inf,r=inf;
for(int i=0;i<n;i++)
{
cin>>p[i].first>>p[i].second;
l1=max(l1,p[i].second-p[i].first);
l2=min(l2,p[i].second-p[i].first);
l=max(l,p[i].first);
r=min(r,p[i].second);
}
int ans=l1-l2;
for(int i=0;i<n;i++)
{
if(l>=p[i].first&&l<=p[i].second)
ans=max(ans,l-p[i].first);
else ans=max(ans,p[i].second-p[i].first+1);
if(r>=p[i].first&&r<=p[i].second)
ans=max(ans,p[i].second-r);
else ans=max(ans,p[i].second-p[i].first+1);
}
cout<<ans*2<<"\n";
}