Codeforces Round 905 (Div. 3)

A. Morning

题意

从一开始，每一次操作可以选择当前的数字打印或者是移动到左右相邻的数字，具体排列看上图，给出一个标签四位数，求打印出来的操作次数

思路

求相邻两个数字之间的距离差累加

核心代码

void solve()
{
    string s;
    cin>>s;
    int ans=0;
    if(s[0]=='0')s[0]+=10;
    ans=abs(s[0]-'1');
    for(int i=1;i<4;++i)
    {
        if(s[i]=='0')s[i]+=10;
        ans+=abs(s[i]-s[i-1]);
    }
    ans+=4;
    cout<<ans<<endl;
}

B. Chemistry

题意

给你一个长度为n的字符串以及可以删除的字符个数k，询问删除之后重新排列能否构成回文字符串

思路

要想构成回文字符串所有的字母出现的次数都要是偶数，除了最中间的那一个字母可以是出现奇数次。然后是删除的k次，如果k大于原字符串中出现奇数次数的字母个数，那么后面多余的次数就可以去删除出现偶数次的字母，最后一定能够构成回文字符串，k不够大的话那就不能构成了

核心代码

void solve()
{
    int n,k;
    scanf("%d%d",&n,&k);
    string s;
    cin>>s;
    int len=s.size();
    int arr[26]{};
    for(int i=0;i<len;++i)
    {
        arr[s[i]-'a']++;
    }
    int geshu=0;
    int sum=0;
    for(int i=0;i<26;++i)
    {
        if(arr[i]&1)geshu++;
        sum+=arr[i];
    }
    if(geshu<=k+1)printf("YES\n");
    else printf("NO\n");
}

C. Raspberries

题意

给你一组长度为n的数组，以及一个整数k，每一次可以对数组里面的任意一个数字进行加一操作，问最少执行多少次可以使得这个数组里面所有的数字的乘积是k的倍数

思路

如果k是质数，那么我们只需要满足这个数组里面有一个数字是k的倍数就可以了，可以对每一个数字进行枚举找最小的那一个，但是如果是合数怎么操作呢，本题只有一个合数4，单独进行特判就可以了

核心代码

void solve()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int minzhi=INT_MAX;
    int input;
    int oushu=0;
    int jishu=0;
    for(int i=0;i<n;++i)
    {
        scanf("%d",&input);
        if(input&1)jishu++;
        else oushu++;
        if(input%k==0)minzhi=0;
        else minzhi=min(minzhi,k-input%k);
    }
    if(k!=4)
    {
        printf("%d\n",minzhi);
        return ;
    }
    if(oushu>=2)printf("0\n");
    else if(oushu==1&&jishu>=1)printf("%d\n",min(minzhi,1));
    else if(oushu==1&&jishu==0)printf("%d\n",min(minzhi,2));
    else if(oushu==0&&jishu>=2)printf("%d\n",min(minzhi,2));
    return ;
}

D. In Love

题意

每一次增加一个边或者减少一个边，操作完之后询问是否存在一对不重合的边

思路

如果存在一对不重合的边，那么必然存在一条边的右端点小于一条边的左端点，我们只需要看最小的右端点是否小于最大的左端点即可

核心代码

void solve()
{
    int n;
    cin>>n;
    multiset<int>l,r;
    for(int i=0;i<n;++i)
    {
        char a;
        int x,y;
        cin>>a>>x>>y;
        if(a=='+')
        {
            l.insert(x);
            r.insert(y);
        }
        else
        {
            l.erase(l.find(x));
            r.erase(r.find(y));
        }
        if(l.size() > 1 && *r.begin() < *l.rbegin())printf("YES\n");
        else printf("NO\n");
    }
}

E. Look Back

题意

给你一组长度为n的数组，每一次可以选择一个数组乘以2，最少需要多少次可以使得这个数组变成一个非递减数组

思路

只需要从前往后进行贪心枚举就可以了，但是这个题目数据量有点大，不能直接存储每一个数字变化之后的数字，需要转化一下，比如我们可以通过前后两个数字的大小倍数关系来求

核心代码

void solve()
{
    int n;
    scanf("%d",&n);
    long long a=0,b;
    long long ans=0;
    long long num=0;
    long long bei=0;
    scanf("%lld",&a);
    for(int i=1;i<n;++i)
    {
        scanf("%lld",&b);
        if(b>a)
        {
            int a2=a;
            while(a2<=b&&a2!=0)
            {
                a2<<=1;
                num--;
            }
            num++;
            num=num>0?num:0;
            ans+=num;
            a=b;
            continue;
        }
        else if(a==b)
        {
            ans+=num;
            continue;
        }
        else
        {
            int b2=b;
            while(b2<a)
            {
                num++;
                b2<<=1;
            }
            ans+=num;
            a=b;
        }
    }
    printf("%lld\n",ans);
}