CF Round 879(Div. 2) 题解

2023/6/21 C++ 算法竞赛 Div. 2 题解 CodeForce

A-D题解

A. Unit Array

题解

只用看一下有多少个1和-1

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
int a[N];
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[i]==-1)
                cnt++;
        }
        if(cnt<=n/2&&cnt%2==0)
            cout<<0<<'\n';
        else
        {
            if(cnt>n/2)
            {
                if(n/2%2==0)
                    cout<<cnt-n/2<<'\n';
                else
                    cout<<cnt-n/2+1<<'\n';
            }
            else
            {
                cout<<1<<'\n';
            }
        }
    }
    return 0;
}

B. Maximum Strength

题解

如果 和 的位数不一样，那么可以将 除最左边一位保持不变，其余全置为0，将 的右边全置为9

例如88和1914就变成999和1000

显然这样是最大的

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
signed main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        string L,R;
        cin>>L>>R;
        reverse(L.begin(),L.end());
        for(int i=L.length();i<R.length();i++)
            L+='0';
        reverse(L.begin(),L.end());
        bool flag=false;
        int k=R.length();
        for(int i=0;i<R.length();i++)
        {
            if(L[i]!=R[i])
            {
                k=i;
                flag=true;
                break;
            }
        }
        if(!flag)
            cout<<0<<'\n';
        else
            cout<<abs(R[k]-L[k])+9*(R.length()-1-k)<<'\n';
    }
    return 0;
}

C. Game with Reversing

题解

可以发现翻转对结果是没什么用的，只用算一下两个字符串的距离以及其中一个翻转之后的距离

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int d[2];
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        memset(d,0,sizeof(d));
        string s1,s2;
        cin>>s1>>s2;
        for(int i=0;i<n;i++)
        {
            if(s1[i]!=s2[i])
                d[0]++;
        }
        string temp=s2;
        reverse(temp.begin(),temp.end());
        for(int i=0;i<n;i++)
        {
            if(s1[i]!=temp[i])
                d[1]++;
        }
        if(d[0]==0)
            cout<<0<<'\n';
        else if(d[1]==0)
            cout<<2<<'\n';
        else
            cout<<min(max(0,d[0]%2==1?(2*d[0]-1):2*d[0]),d[1]%2==1?2*d[1]:2*d[1]-1)<<'\n';
    }
    return 0;
}

D. Survey in Class

题解

相当于计算每两个学生的区间的差的最大值

对于每两个区间a和b，a被b交之后有三种情况，一种是留下左边，一种是留下右边，另一种是一个在另一个的中间

对于所有的第一种情况，可以通过先算出maxl简化运算

对于所有的第二种情况，可以通过先算出minr简化运算

对于第三种情况，最大的值只能是最长区间长度减最短区间长度

对于区间完全不相交的情况，其实也是可以遍历到的

最后遍历一遍取最大值就行，复杂度O(n)

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int l[N],r[N],len[N];
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>l[i]>>r[i];
            len[i]=r[i]-l[i]+1;
        }
        int maxl=*max_element(l+1,l+1+n);
        int minr=*min_element(r+1,r+1+n);
        int ans=*max_element(len+1,len+1+n)-*min_element(len+1,len+1+n);
        for(int i=1;i<=n;i++)
        {
            ans=max(ans,min(r[i]-minr,len[i]));
            ans=max(ans,min(len[i],maxl-l[i]));
        }
        cout<<ans*2<<'\n';
    }
    return 0;
}
img_show