Educational Codeforces Round 132 (Rated for Div. 2)【比赛记录】

A Three Doors

连续打开两扇门，如果未出现0的情况，即是YES，否则NO

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define rep2(i,a,b) for(int i=a;i>=b;i--)
///* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=1e6+5;
const ll INF=1e15+5;
int sum[10],mp[10];
int main(){
    int t;sc(t);
    while(t--){
        int a,b,c;
        int pre;sc(pre);
        sc(a);sc(b);sc(c);
        mp[1]=a;
        mp[2]=b;
        mp[3]=c;
        if(mp[pre]==0) printf("NO\n");
        else{
            pre=mp[pre];
            // cout<<pre<<"---\n";
            if(mp[pre]==0) printf("NO\n");
            else{
                pre=mp[pre];
                // cout<<pre<<"--\n";
                if(pre==0) printf("NO\n");
                else printf("YES\n");
            }
        }
    }
}

B Also Try Minecraft

如果是奇数情况，从左到右枚举高度即可；

如果是偶数情况，会发现可以有一次机会可以连续跳跃两个跳台，现预处理前缀和和后缀和，然后从左到右枚举连续跳跃的两个跳台，进而求出最小值即可。

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define rep2(i,a,b) for(int i=a;i>=b;i--)
///* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=1e6+5;
const ll INF=1e15+5;
int a[Max];
ll sum[Max],pre[Max];
int main(){
    // int t;sc(t);
    // while(t--){
        int n;
        sc(n);
        int q;sc(q);
        for(int i=1;i<=n;i++) sum[i]=0,pre[i]=0;
        for(int i=1;i<=n;i++){
            sc(a[i]);
            if(i>=2){
                if(a[i]<=a[i-1]) sum[i]=a[i-1]-a[i];
                sum[i]+=sum[i-1];
            }
        }
        for(int i=n-1;i>=1;i--){
            if(a[i+1]>=a[i]) pre[i]=a[i+1]-a[i];
            pre[i]+=pre[i+1];
            // cout<<pre[i]<<' ';
        }
        while(q--){
            int l,r;sc(l);sc(r);
            if(r>=l) printf("%lld\n",sum[r]-sum[l]);
            else printf("%lld\n",pre[r]-pre[l]);
        }
    // }
}

C Recover an RBS

        题目所给的字符串一定满足正则表达式，'?'在缺少'('的情况下，尽可能'?'填'('，剩余'?'全填')'，这种情况一定满足正则表达式，然后找出中间一组？分别为'('和')'，两者交换位置判断整个是否继续满足，如果满足即答案为NO，否则为YES！！！

例如：？？？？-＞（（）），然后考虑影响最小的情况，必然是最后一个（和第一个）换位置，？？？？-＞（）（），成立，固有多组解，否则只要一组解

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define rep2(i,a,b) for(int i=a;i>=b;i--)
///* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=1e6+5;
const ll INF=1e15+5;
stack<char>s;
int main(){
    int t;sc(t);
    while(t--){
        string str;
        cin>>str;
        int num1=0,num2=0;
        for(int i=0;i<str.size();i++){
            if(str[i]=='(') num1++;
            else if(str[i]==')') num2++;
        }
        int len=str.size();int tmp=num2,temp=num1;
        for(int i=0;i<str.size();i++){
            if(str[i]=='?'){
                if(len/2-num1>0){
                    num1++;
                    if(num1==len/2&&num2!=len/2) str[i]=')';
                    else str[i]='(';
                }
                else if(len/2-num2>0){
                    num2++;
                    if(tmp==num2-1&&temp!=len/2) str[i]='(';
                    else str[i]=')';
                }
            }
        }
        for(int i=0;i<str.size();i++){
            // cout<<str[i];
            if(str[i]=='(') s.push(str[i]);
            else{
                if(s.empty()) s.push(str[i]);
                else{
                    char ch=s.top();
                    if(ch=='(') s.pop();
                    else s.push(str[i]);
                }
            }
        }
        if(!s.empty()||tmp==len/2||temp==len/2) printf("YES\n");
        else printf("NO\n");
        while(!s.empty()) s.pop();
    }
}

D Rorororobot

ST板子题，线段树也可维护区间最大值，例如下图： 从(5,3)到(11,5)，需要同时到达同一高度（大于之间最高障碍高度），然后判断(xs-xf)%k!=0&&(ys-yf)%k!=0

比赛时一直w5，当时没考虑边界（刚好与最高障碍同一高度的情况）！！！ 

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define rep2(i,a,b) for(int i=a;i>=b;i--)
///* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=2e5+200;
const ll INF=1e15+5;
int a[Max];
int num[Max];
int m,n;
ll tree[10000005];
void buildtree(int node,int start,int end){
	if(start==end){
		tree[node]=num[start];
		return ;
	}
	int mid=(start+end)/2;
	int Lchild=node*2;
	int Rchild=node*2+1;
	buildtree(Lchild,start,mid);
	buildtree(Rchild,mid+1,end);
	tree[node]=max(tree[Lchild],tree[Rchild]);
}
 
long long int add(int node,int start,int end,int L,int R){
//	cout<<start<<' '<<end<<' '<<L<<' '<<R<<endl;
	if(end<L||start>R) return 0;
	if(start>=L&&end<=R){
		return tree[node];
	}
	//cout<<start<<' '<<end<<' '<<L<<' '<<R<<endl;
	int mid=(start+end)/2;
	ll ret=0;
	ret=max(ret,add(node*2,start,mid,L,R));
	ret=max(ret,add(node*2+1,mid+1,end,L,R));
	return ret;
}
int main(){
    sc(n);sc(m);
    for(int i=1;i<=m;i++) sc(num[i]);
    buildtree(1,1,m);
    // cout<<add(1,1,m,9,9)<<"---\n";
    int q;sc(q);
    while(q--){
        ll x,y,x1,y1;
        sl(x),sl(y);
        sl(x1);sl(y1);ll k;sl(k);
        if(y>y1) swap(x,x1),swap(y,y1);
        ll maxa=add(1,1,m,y,y1);
        // cout<<maxa<<"----\n";
        bool flag=true;
        if(abs(y1-y)%k!=0||abs(x1-x)%k!=0) flag=false;
        if(x<=maxa&&x1<=maxa){
            if(x==maxa) x=maxa+k;
            else{
                if((maxa-x+1)%k==0) x=maxa+1;
                else{
                    x=x+(maxa-x+1)/k*k+k;
                }
            }
            if(x>n) flag=false;
            if(x1==maxa) x1=maxa+k;
            else{
                if((maxa-x1+1)%k==0) x1=maxa+1;
                else{
                    x1=x1+(maxa-x1+1)/k*k+k;
                }
            }
            if(x1>n) flag=false;
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
}