# Dashboard – Educational Codeforces Round 105 (Rated for Div. 2) – Codeforces()-dash

## Dashboard – Educational Codeforces Round 105 (Rated for Div. 2) – Codeforces()

### 1.Problem – A – Codeforces

``#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fel(i,x,y) for(int i=x;i<=y;i++)#define fhl(i,x,y) for(int i=x;i>=y;i--)#define inf 0x3fffffff#define ll long long#define pb push_back#define endl "\n"#define int long longstring s;map<char,char>mp;bool judge(string t){    stack<char>st;    for(auto i:t){        if(i=='('){            st.push('(');        }        else{            if(st.empty()){                return false;            }            else{                st.pop();            }        }    }    return st.empty()? true:false;}void slove(){    cin>>s;    int l=s.length();    if(s[l-1]==s[0]){        cout<<"NO"<<endl;        return;    }    mp.clear();//忘记clear吐血    mp[s[0]]='(';    mp[s[l-1]]=')';    string t1="",t2="";    for(int i=0;i<l;i++){        if(!mp.count(s[i])){            t1+='(';            t2+=')';        }        else{            t1+=mp[s[i]];            t2+=mp[s[i]];        }    }    //cout<<t1<<endl;    //cout<<t2<<endl;    int ans=judge(t1)+judge(t2);    if(ans){        cout<<"YES"<<endl;    }    else cout<<"NO"<<endl;}signed main(){    //IOS    int t;    cin>>t;    while(t--) {        slove();    }    return 0;}``

### 2.Problem – B – Codeforces

``#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fel(i,x,y) for(int i=x;i<=y;i++)#define fhl(i,x,y) for(int i=x;i>=y;i--)#define inf 0x3fffffff#define ll long long#define pb push_back#define endl "\n"#define int long long//2-n-2是肯定可以形成的，只用考虑1，n-1，n就可以了int n,a[5];void slove(){    cin>>n;    cin>>a[0]>>a[1]>>a[2]>>a[3];    int t1=0,t2=0,ans=1;    if(a[0]==n) t1++;    if(a[2]==n) t1++;    if(a[0]==n-1) t2++;    if(a[2]==n-1) t2++;    if(a[1]<t1||a[3]<t1) ans=0;    if(a[1]+a[3]<t1*2+t2) ans=0;    t1=0,t2=0;    if(a[1]==n) t1++;    if(a[3]==n) t1++;    if(a[1]==n-1) t2++;    if(a[3]==n-1) t2++;    if(a[0]<t1||a[2]<t1) ans=0;    if(a[0]+a[2]<t1*2+t2) ans=0;    if(ans){        cout<<"YES"<<endl;    }    else{        cout<<"NO"<<endl;    }}signed main(){    //IOS    int t;    cin>>t;    while(t--) {        slove();    }    return 0;}``

### 3.Problem – C – Codeforces

``#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fel(i,x,y) for(int i=x;i<=y;i++)#define fhl(i,x,y) for(int i=x;i>=y;i--)#define inf 0x3fffffff#define ll long long#define pb push_back#define endl "\n"#define int long long//大概意思就是分正负数讨论，情况是一样的//我考考虑枚举移动的箱子视为一连串，将b数组视为结尾，然后看有多少找最大值const int N=2e5+100;int n,m;int a[N],b[N],box[N],q[N];map<int,int>mp;int add(int lena,int lenb){    int count=0,res=0,ans=0;     mp.clear();    fel(i,1,lena) mp[a[i]]=1;    fel(i,1,lenb) if(mp[b[i]]) count++;//记录有多少箱子刚好踩在特殊点上    res=count;    ans=count;    for(int i=1;i<=lenb;i++){//枚举火车头        if(mp[b[i]]){            res--;            continue;        }//当你碰到一个新的火车头你前面求得得那一段的最大值如果在将这个视为火车头，最大值最多也就是ans+1(如果上一个点不变，这个点继续保持原位置也是ans+1),        //所以上一回合求出来的最大值如果把火车以此点作为头话，最大值肯定是会变小的或者不变的        int p=upper_bound(a+1,a+1+lena,b[i])-a-1;//把b[i]作为火车头的火车有多长//upper求得是第一个大的位置，所以还要减去1        int qq=lower_bound(b+1,b+1+lenb,b[i]-p+1)-b;//b[i]-p+1刚好有箱子的第一个位置，大于等于这个位置同时小于i的位置都是有箱子的特殊点。        ans=max(ans,res+i-qq+1);//res是后面匹配的位置，i-q+1是q到i这一段的长度    }    return ans;}void slove(){    cin>>n>>m;    fel(i,1,n) cin>>box[i];    fel(i,1,m) cin>>q[i];        int lena=0,lenb=0;    fel(i,1,n) if(box[i]>=0) a[++lena]=box[i];    fel(i,1,m) if(q[i]>=0) b[++lenb]=q[i];    int ans=add(lena,lenb);        lena=0,lenb=0;//负数的讨论情况直接把他看成正数就可以了    fhl(i,n,1) if(box[i]<0) a[++lena]=-box[i];    fhl(i,m,1) if(q[i]<0) b[++lenb]=-q[i];    ans+=add(lena,lenb);    cout<<ans<<endl;}signed main(){    IOS    int t;    cin>>t;    while(t--) {        slove();    }    return 0;}``
————————

### 1.Problem – A – Codeforces

``#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fel(i,x,y) for(int i=x;i<=y;i++)#define fhl(i,x,y) for(int i=x;i>=y;i--)#define inf 0x3fffffff#define ll long long#define pb push_back#define endl "\n"#define int long longstring s;map<char,char>mp;bool judge(string t){    stack<char>st;    for(auto i:t){        if(i=='('){            st.push('(');        }        else{            if(st.empty()){                return false;            }            else{                st.pop();            }        }    }    return st.empty()? true:false;}void slove(){    cin>>s;    int l=s.length();    if(s[l-1]==s[0]){        cout<<"NO"<<endl;        return;    }    mp.clear();//忘记clear吐血    mp[s[0]]='(';    mp[s[l-1]]=')';    string t1="",t2="";    for(int i=0;i<l;i++){        if(!mp.count(s[i])){            t1+='(';            t2+=')';        }        else{            t1+=mp[s[i]];            t2+=mp[s[i]];        }    }    //cout<<t1<<endl;    //cout<<t2<<endl;    int ans=judge(t1)+judge(t2);    if(ans){        cout<<"YES"<<endl;    }    else cout<<"NO"<<endl;}signed main(){    //IOS    int t;    cin>>t;    while(t--) {        slove();    }    return 0;}``

### 2.Problem – B – Codeforces

``#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fel(i,x,y) for(int i=x;i<=y;i++)#define fhl(i,x,y) for(int i=x;i>=y;i--)#define inf 0x3fffffff#define ll long long#define pb push_back#define endl "\n"#define int long long//2-n-2是肯定可以形成的，只用考虑1，n-1，n就可以了int n,a[5];void slove(){    cin>>n;    cin>>a[0]>>a[1]>>a[2]>>a[3];    int t1=0,t2=0,ans=1;    if(a[0]==n) t1++;    if(a[2]==n) t1++;    if(a[0]==n-1) t2++;    if(a[2]==n-1) t2++;    if(a[1]<t1||a[3]<t1) ans=0;    if(a[1]+a[3]<t1*2+t2) ans=0;    t1=0,t2=0;    if(a[1]==n) t1++;    if(a[3]==n) t1++;    if(a[1]==n-1) t2++;    if(a[3]==n-1) t2++;    if(a[0]<t1||a[2]<t1) ans=0;    if(a[0]+a[2]<t1*2+t2) ans=0;    if(ans){        cout<<"YES"<<endl;    }    else{        cout<<"NO"<<endl;    }}signed main(){    //IOS    int t;    cin>>t;    while(t--) {        slove();    }    return 0;}``

### 3.Problem – C – Codeforces

``#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fel(i,x,y) for(int i=x;i<=y;i++)#define fhl(i,x,y) for(int i=x;i>=y;i--)#define inf 0x3fffffff#define ll long long#define pb push_back#define endl "\n"#define int long long//大概意思就是分正负数讨论，情况是一样的//我考考虑枚举移动的箱子视为一连串，将b数组视为结尾，然后看有多少找最大值const int N=2e5+100;int n,m;int a[N],b[N],box[N],q[N];map<int,int>mp;int add(int lena,int lenb){    int count=0,res=0,ans=0;     mp.clear();    fel(i,1,lena) mp[a[i]]=1;    fel(i,1,lenb) if(mp[b[i]]) count++;//记录有多少箱子刚好踩在特殊点上    res=count;    ans=count;    for(int i=1;i<=lenb;i++){//枚举火车头        if(mp[b[i]]){            res--;            continue;        }//当你碰到一个新的火车头你前面求得得那一段的最大值如果在将这个视为火车头，最大值最多也就是ans+1(如果上一个点不变，这个点继续保持原位置也是ans+1),        //所以上一回合求出来的最大值如果把火车以此点作为头话，最大值肯定是会变小的或者不变的        int p=upper_bound(a+1,a+1+lena,b[i])-a-1;//把b[i]作为火车头的火车有多长//upper求得是第一个大的位置，所以还要减去1        int qq=lower_bound(b+1,b+1+lenb,b[i]-p+1)-b;//b[i]-p+1刚好有箱子的第一个位置，大于等于这个位置同时小于i的位置都是有箱子的特殊点。        ans=max(ans,res+i-qq+1);//res是后面匹配的位置，i-q+1是q到i这一段的长度    }    return ans;}void slove(){    cin>>n>>m;    fel(i,1,n) cin>>box[i];    fel(i,1,m) cin>>q[i];        int lena=0,lenb=0;    fel(i,1,n) if(box[i]>=0) a[++lena]=box[i];    fel(i,1,m) if(q[i]>=0) b[++lenb]=q[i];    int ans=add(lena,lenb);        lena=0,lenb=0;//负数的讨论情况直接把他看成正数就可以了    fhl(i,n,1) if(box[i]<0) a[++lena]=-box[i];    fhl(i,m,1) if(q[i]<0) b[++lenb]=-q[i];    ans+=add(lena,lenb);    cout<<ans<<endl;}signed main(){    IOS    int t;    cin>>t;    while(t--) {        slove();    }    return 0;}``