Educational Codeforces Round 36 (Rated for Div. 2)

A. 签到题不解释

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n,k,i,j;
    //cin>>n;
    vector<int>v;
    cin>>n>>k;
    for(i=1;i<=n;i++){
        scanf("%d",&j);
        if(k%j==0)v.push_back(j);
    }
    sort(v.begin(),v.end(),cmp);
    cout<<k/v[0]<<endl;

    return 0;
}

B. 总共只有两种情况:先关左边再关右边,或者反过来,讨论一下特殊边界情形即可,签到*2

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
    int n,pos,l,r,i,j,k;
    cin>>n>>pos>>l>>r;
    if(l==1&&r==n){
        cout<<0<<endl;return 0;
    }
    else if(l==1&&r!=n){
        cout<<abs(pos-r)+1<<endl;
    }
    else if(l!=1&&r==n){
        cout<<abs(pos-l)+1<<endl;
    }
    else{
        int a=abs(pos-l)+1+abs(r-l)+1;
        int b=abs(pos-r)+1+abs(l-r)+1;
        cout<<min(a,b)<<endl;
    }

    return 0;
}

C. 显然我们是想求一个满足条件的字典序最大的排列,那么对于每一位,我们从可放置的最大数出发,找出在当前状况下后续能排出的最小序列,跟b剩下的位数比较,如果最小序列比b小,那么这一位就可以放最大的数。否则这一位就必须放比较小的数。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int cnt[15];
string build(void)
{
    string res;
    for(int i=0;i<10;i++){
        for(int j=1;j<=cnt[i];j++)
            res+=char(i+'0');
    }
    return res;
}
int main()
{
    string a,b;int i,j,k;
    cin>>a>>b;
    int num[25];
    for(i=0;i<b.size();i++)
        num[i]=b[i]-'0';//每位数字,便于比较
    for(i=0;i<a.size();i++)//统计每种数字的个数
        cnt[a[i]-'0']++;
    if(a.size()<b.size()){//如果位数少直接输出最大排列
        for(i=9;~i;i--){
            for(j=cnt[i];j;j--)
                cout<<i;
        }
        cout<<endl;return 0;
    }
    string ans;bool ismall=false;
    for(i=0;i<a.size();i++){
        if(ismall)break;
        for(j=num[i];~j;j--){//寻找这一位最大的可能
            if(cnt[j]){
                cnt[j]--;
                if(j<num[i]){//如果这一位已经比b小了,直接输出后续最大排列即可
                    ismall=true;ans+=char(j+'0');break;
                }
                string minn=build();string bnow=b.substr(i+1);//寻找在当前情况下后续能排出的最小排列
                if(minn<=bnow){
                    ans+=char(j+'0');

                    break;
                }
                cnt[j]++;
            }
        }
    }
    cout<<ans;
    for(i=9;~i;i--){
        for(j=cnt[i];j;j--)
            cout<<i;
    }
    cout<<endl;

    return 0;
}

D.

给定一幅有向图,问是否可以最多去掉一条边使得该有向图无环?

题目的做法比较神奇。一开始的想法是先求一波强连通分量,然后特判一下强连通分量为1的情况,然而test56 GG了。 看到一种做法,即从1~n,每次以不同的起点开始dfs找环,判断图中是否可能存在只去掉一条边就无环的情况(当然要是本来就没环那就是废话)。 为什么从不同的点开始dfs结果会不一样?因为这道题中会有一种比较奇特的情形,有可能有多个环都依赖于一条有向边而存在,比如样例1(如图) 在这里会发现2->3的边是一条关键边,从3开始搜索时因为先到2,再开始搜索1,因此vis[2]=1而不会被1搜索到,于是cnt只有1.因此这就是“YES”。 看起来似乎还是挺奇妙的233

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
vector<int>G[505];
int cnt;
int vis[505];
void dfs(int x)
{
    vis[x]=2;//正在当前搜索序列中的标记为2
    for(auto a:G[x]){
        if(vis[a]==2)
            cnt++;//每找到一个环cnt++
        else if(!vis[a])
            dfs(a);
    }
    vis[x]=1;//已经访问过但不是当前搜索序列中的标记为1
}
int main()
{
    int n,m,i,j,k;
    cin>>n>>m;
    for(i=1;i<=m;i++){
        int a,b;scanf("%d%d",&a,&b);
        G[a].push_back(b);
    }
    for(i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));cnt=0;
        dfs(i);
        for(j=1;j<=n&&cnt<=1;j++)
            if(!vis[j])
                dfs(j);
        if(cnt<=1){//如果从这个点出发只找到一个环(关建边)
            cout<<"YES"<<endl;return 0;
        }
    }
    cout<<"NO"<<endl;

    return 0;
}

E.

给定一个初始全为1的序列,不停地给出一个比较短的序列(l,r),将(l,r)范围内数全部变为1或0(根据k的值决定)。序列范围较大。

一眼看下去感觉线段树能搞,一看范围1e9…事实上这道题又是一个用map维护区间信息的典例…我们将连续的工作日区间按右端点为关键值插入map中,map的第二个键值就是区间的左端点。那么初始时有range[n]=1 对于每次询问,我们找出大于l的的最小的在map中的工作区间,把它与这次询问的区间相交的部分全部删去,然后依次类推直至map中的区间不与询问区间相交。如果k=2,那么答案加上r-l+1即可。为什么不讨论k=1?因为即使是k=1,询问的空间也可能是支离破碎的,并不容易统计,不如把他们全部删掉重置。

#include<cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
    map<int,int>range;//标记周期
    int n,i,j,k,q;
    cin>>n>>q;
    range[n]=1;int ans=n;
    for(i=1;i<=q;i++){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        auto a=range.lower_bound(l);//找出大于等于询问区间的第一个map的右端点
        while(a!=range.end()){
            int cl=a->second,cr=a->first;
            if(cl>r)break;//如果区间的左端点已经大于询问区间的右端点,显然没有交集了
            ans-=(min(cr,r)-max(cl,l)+1);//除去询问区间的所有工作日
            range.erase(a++);//删去重叠区间
            if(cr>r)range[cr]=r+1;//如果大区间被询问区间肢解了,加入小的未涉及区间
            if(cl<l)range[l-1]=cl;
        }
        if(k==2){
            range[r]=l;ans+=r-l+1;//k=2时加入询问区间
        }
        printf("%d\n",ans);
    }

    return 0;
}