Educational Codeforces Round 132 (Rated for Div. 2)(A-D)

A. Three Doors

  Ideas : Judge whether the door corresponding to the key behind the current door and the key behind the current door has a key .

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int n,a[4];
    cin>>n;
    cin>>a[1]>>a[2]>>a[3];
    if(a[n]==0)
    {
        cout<<"NO\n";
        return ;
    }
    if(a[a[n]]==0)
    {
        cout<<"NO\n";
        return ;
    }
    cout<<"YES\n";
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

B. Also Try Minecraft

Ideas : Run back and forth twice , Judge whether it will contribute , Find the prefix sum ( Different pros and cons make different contributions )

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
int shun[100005],ni[100005];
int h[100005];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
        if(i!=1)
            if(h[i]<h[i-1])
                shun[i]=shun[i-1]+(h[i-1]-h[i]);
            else
                shun[i]=shun[i-1];
    }
    for(int i=n;i>=1;i--)
        if(i!=n)
            if(h[i]<h[i+1])
                ni[i]=ni[i+1]+(h[i]-h[i+1]);
            else
                ni[i]=ni[i+1];
    int l,r;
    while(m--)
    {
        cin>>l>>r;
        if(l<=r)
        {
            cout<<shun[r]-shun[l]<<"\n";
        }
        else
        {
            cout<<ni[l]-ni[r]<<"\n";
        }
    }
    return ;
}
signed main()
{
    solve();
    return 0;
}

C. Recover an RBS

Ideas : First, determine whether the left and right parentheses are equal to n/2 individual (n Is the length of a string ), If equal to, then the bracket direction of the question mark is also determined .

And then for this sequence , Talk to think , We want to minimize the impact on the string , therefore , Let's assign the left and right brackets greedily to the position of the question mark , Try to allocate the left bracket first and insert the right bracket . At this time, according to the greedy thought , We need to satisfy RBS The definition of , When traversing the string , The number of left parentheses in each position should be greater than or equal to the number of right parentheses , In order to find the second kind of bracket arrangement sequence as a minimum , We need to change the leftmost question mark into ')' And the rightmost one changed from a question mark '(' Exchange positions , Exchange the latter two in this way for RBS The influence of composition is minimal . In accordance with the above rules , Directly traverse the number of left and right parentheses of the record . When the number of right parentheses is greater than the number of left parentheses, it indicates that it is inappropriate , Even the love mine that has the smallest impact on the greed of the original sequence is illegal , It shows that there is only one arrangement method .

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    string s;
    cin>>s;
    int zuo=0,you=0,wen=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='(')
            zuo++;
        else if(s[i]==')')
            you++;
        else if(s[i]=='?')
            wen++;       
    }   
    if(zuo==s.size()/2||you==s.size()/2)
    {
        cout<<"YES\n";
        return ;
    }
    int l=1e8,r=-1;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='?')
            if(zuo<s.size()/2)
            {
                s[i]='(';
                r=max(r,i);
                zuo++;
            }
            else
            {
                s[i]=')';
                l=min(l,i);
            }
    }
    swap(s[l],s[r]);
    zuo=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='(')
            zuo++;
        else if(s[i]==')')
            zuo--;
        if(zuo<0)
        {
            cout<<"YES\n";
            return ;
        }
    }
    cout<<"NO\n";
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

D. Rorororobot

Ideas : We must first judge whether the difference between the horizontal and vertical coordinates is k Multiple , If not, it means you can't go . Be careful , We don't need the minimum number of steps , So we can adopt a strategy , Walk from the current point to the top you can reach , Then go right to the top of the destination , Go down to the destination , This is the most greedy way to go , If you can't even get to this , Then there is no way to go . Then this method requires us to preprocess the interval maximum , When we can go up to get the maximum height greater than the maximum obstacle in the interval , You can definitely walk to .

Then the segment tree ( Personal testing will not t) and st All tables are OK .

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int l,r,minn;
}tr[4*200010];
int a[200010];
void build(int l,int r,int node)
{
    tr[node].l=l;
    tr[node].r=r;
    if(l==r)
    {
        tr[node].minn=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,node<<1);
    build(mid+1,r,node<<1|1);
    tr[node].minn=max(tr[node<<1].minn,tr[node<<1|1].minn);
    return ;
}
int query(int l,int r,int node)
{
    if(l<=tr[node].l&&tr[node].r<=r)
        return tr[node].minn;
    int mid=(tr[node].l+tr[node].r)>>1;
    int minn=-1;
    if(l<=mid)
        minn=max(query(l,r,node<<1),minn);
    if(r>mid)
        minn=max(query(l,r,node<<1|1),minn);
    return minn;

}
void solve()
{
    int n,m,q;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i];
    build(1,m,1);
    cin>>q;
    while(q--)
    {
        int sx,sy,ex,ey,k;
        cin>>sx>>sy>>ex>>ey>>k;
        if(abs(sx-ex)%k||abs(sy-ey)%k)
        {
            cout<<"NO\n";
            continue;
        }
        int maxx=max(ex,sx);
        maxx=(n-maxx)/k*k+maxx;
        if(maxx>query(min(sy,ey),max(sy,ey),1))
        {
            cout<<"YES\n";
        }
        else
        {
            cout<<"NO\n";
        }
    }
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    solve();
    return 0;
}