Educational Codeforces Round 58 (Rated for Div. 2)（ABCE）

た入场券 2023-06-03 13:52 26阅读 0赞

A. Minimum Integer

题意：找到一个x，使得x不在\[l,r\]内，且最小能够整除d的数；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=3e5+10;
     
     
     
    int main(){
        int T;
        cin>>T;
        while(T--){
            ll l,r,d;
            cin>>l>>r>>d;
            if(d>r||d<l)cout<<d<<endl;
            else {
                int ans=r;
                int x=ans%d;
                ans-=x;
                while(ans<=r){
                    ans+=d;
                }
                cout<<ans<<endl;
            }
        }
     
     
     
        return 0;
    }

B. Accordion

题意：给定串中找到\[::\]，冒号里面可以是|，的最大长度；

模拟一下就行了；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=3e5+10;
     
     
     
    int main(){
        string s;
        int len;
        cin>>s;
        len=s.size();
        int i=0,j=len-1;
        while(s[i]!='['&&i<len)i++;
        if(i>=len-3){
            cout<<"-1"<<endl;
            return 0;
        }
        while(s[j]!=']'&&j>=0)j--;
        if(i>=j||j<=2){
            cout<<"-1"<<endl;
            return 0;
        }
        while(s[i]!=':'&&i<j)i++;
        while(s[j]!=':'&&i<j)j--;
        if(i>=j){
            cout<<"-1"<<endl;;
            return 0;
        }
        //cout<<i<<' '<<j<<endl;
        int ans=4;
        for(int k=i+1;k<j;k++){
            if(s[k]=='|')ans++;
        }
        cout<<ans<<endl;
     
     
        return 0;
    }

C. Division and Union

题意：把能相交的区间放在一个集合里，其他放在另外一个集合；

解：排序，然后从区间1开始扩张，直到遇到不能扩展的情况；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    struct node{
        int l,r;
        int id;
    }Q[maxn];
    int ans[maxn];
    bool cmp(node a,node b){
        if(a.l==b.l)return a.r<b.r;
        return a.l<b.l;
    }
    int main(){
        int T;
        cin>>T;
        while(T--){
            int n;
            cin>>n;
            for(int i=1;i<=n;i++){
                cin>>Q[i].l>>Q[i].r;
                Q[i].id=i;
            }
            sort(Q+1,Q+1+n,cmp);
            ans[Q[1].id]=1;
            int flag=0;
            int y=Q[1].r;
            for(int i=2;i<=n;i++){
                if(flag==1){
                    ans[Q[i].id]=2;
                    continue;
                }
                if(Q[i].l<=y){
                    ans[Q[i].id]=1;
                    y=max(y,Q[i].r);
                }
                else {
                    flag=1;
                    ans[Q[i].id]=2;
                }
            }
            if(flag==0)cout<<"-1"<<endl;
            else{
                for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
                cout<<endl;
            }
     
        }
     
     
        return 0;
    }

E. Polycarp's New Job

题意：给你两个操作，+代表增加一个订单，‘？’表示询问是否满足所有订单都能装下

解：每次询问都把两个数排序，然后每次增加一个订单，都扩展一下当前最小能装下的长宽；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    int ans[maxn];
    int main(){
        ios::sync_with_stdio(false);
        int n,flagx=0,flagy=0,x,y;
        char ch;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>ch>>x>>y;
            if(x>y)swap(x,y);
            if(ch=='+'){
                flagx=max(flagx,x);
                flagy=max(flagy,y);
            }
            else {
                if(flagx<=x&&flagy<=y)cout<<"YES"<<endl;
                else cout<<"NO"<<endl;
            }
        }
     
     
     
        return 0;
    }

转载于:https://www.cnblogs.com/lin1874/p/11398746.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/5e32a5b7e16b46c4822f1fd705722462.png