Codeforces Round ＃807 (Div. 2) A-D

Codeforces Round #807 (Div. 2)

A. Mark the Photographer
Given integer n, The length of the array 2*n, Ask if it can be split into two lengths n Array of , The second of two arrays i Xiang you a[i]>=b[i]+x

Ideas ： violence

DIFF ： 800

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+100;
int a[N];
int main()
{
    
    int t;
    for(cin>>t;t;t--)
    {
    
        int n,x;
        cin>>n>>x;
        for(int i=1;i<=n*2;i++)
        {
    
            cin>>a[i];
        }
        sort(a+1,a+2*n+1);
        bool falg=true;
        for(int i=1;i<=n;i++)
        {
    
            if(a[i+n]-a[i]<x)
            {
    
                falg=false;
            }
        }
        if(falg)
        {
    
             cout<<"YES"<<endl;
        }
        else
        {
    
           cout<<"NO"<<endl;
        }
    }
    return 0;
}

B. Mark the Dust Sweeper
Give an array , Each time you can choose from 1 To n-1 Any segment of is continuous and the value is greater than 0 The range of [l,r], bring a[l]–,a[r]++
, How many times do you need to choose such a range to get from 1 To n-1 The intervals of all become 0

Ideas ： violence , Find the non-zero interval that needs to be selected , So take the first non 0 Count until n-1 term , encounter 0 Add one... To the answer , When you encounter a non-zero number, add this number to the answer .

#include <iostream>
#define int long long
using namespace std;
const int N = 2e5+100;
int a[N];
signed main()
{
    
    int t;
    for(cin>>t;t;t--)
    {
    
        int n,sum=0,st=1;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
    
            cin>>a[i];
        }
        for(int i=1;i<=n-1;i++)
        {
    
            if(a[i]==0)
            {
    
                st=i+1;
            }
            else
            {
    
                break;
            }
        }
        for(int i=st;i<=n-1;i++)
        {
    
            if(a[i]==0)
            {
    
                sum++;
            }
            else
            {
    
                sum+=a[i];
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

C. Mark and His Unfinished Essay
This question is a little interesting , We give an initial string s, Select an interval for many times, copy and splice it to s The rear forms a new s, It is worth noting that , After each replication, our next replication operation is based on the new string s On going . When the copy operation is complete , We output number k Characters

Ideas ： violence , Each time, find the subscript of the copied object corresponding to this subscript . The first string I've been looking for .（ I hope a master can write a recursive method. Let me see ）

#include <iostream>
#define int long long
using namespace std;
const int N = 2e5+100;
int l[N];
int sum[N];
signed main()
{
    
    int t;
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    for(cin>>t;t;t--)
    {
    
        string s;
        int n,c,q;
        cin>>n>>c>>q;
        cin>>s;
        sum[0]=n;
        for(int i=1,r;i<=c;i++)
        {
    
            cin>>l[i]>>r;
            sum[i]=sum[i-1]+r-l[i]+1;
        }
        for(int i=1;i<=q;i++)
        {
    
            int num;
            cin>>num;
            while(num>n)
            {
    
                for(int j=1;j<=c;j++)
                {
    
                    if(sum[j]>=num)
                    {
    
                        num-=sum[j-1];
                        num+=l[j]-1;
                        break;
                    }
                }
            }
            cout<<s[num-1]<<'\n';
        }
    }
    return 0;
}

D. Mark and Lightbulbs
The question ： Give one or two 01 strand , Pick the elements in the middle , If the elements on both sides are different , Then you can change this element （ from 0 To 1 Or vice versa ）
Ideas ： Because change requires unequal left and right , So die directly , We compress the string ,001100 become 010 such , If the two strings can be changed after compression , And the answer is the sum of the absolute values of the lower standard deviations at the left end of different blocks . There is no solution if it is different .

#include <iostream>
#define int long long
using namespace std;
const int N = 2e5+100;
int a[N],b[N];
signed main()
{
    
    int t;
    for(cin>>t;t;t--)
    {
    
        string s,ss;
        int n,con1=0,con2=0;
        cin>>n;
        cin>>s>>ss;
        string s1="",ss1="";
        s1+=s[0];
        ss1+=ss[0];
        a[++con1]=0;
        b[++con2]=0;
        for(int i=1;i<n;i++)
        {
    
            if(s[i]!=s[i-1])
            {
    
                s1+=s[i];
                a[++con1]=i;
            }
            if(ss[i]!=ss[i-1])
            {
    
                ss1+=ss[i];
                b[++con2]=i;
            }
        }
        if(s1!=ss1)
        {
    
            cout<<-1<<endl;
            continue;
        }
        int ans=0;
        for(int i=1;i<=con1;i++)
        {
    
            ans+=abs(a[i]-b[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}