当前位置 博文首页 > 文章内容

    Codeforces Round #654 (Div. 2) E - Asterism 二分

    作者: 栏目:未分类 时间:2020-07-02 10:14:41

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    E1

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<map>
    using namespace std;
    #define int long long
    const int N=1e6+10;
    int a[N];
    int b[N];
    int n;
    int p;
    int sum[N];
    bool check(int x)
    {
        int ans=1;
        for(int i=1;i<=n;i++)
        {
            ans=(ans*(sum[x]-i+1))%p;
            x++;
            if(ans==0)
                return false;
        }
        return 1;
    }
    void solve()
    {
        
        cin>>n>>p;
        map<int,int>mp;
        for(int i=1;i<=n;i++)
            cin>>a[i],mp[a[i]]++;
        for(int i=1;i<=5000;i++)
            sum[i]=sum[i-1]+mp[i];
        vector<int>v;
        for(int i=1;i<=2020;i++)
            if(check(i))
                v.push_back(i);
        cout<<v.size()<<endl;
        for(auto x:v)
            cout<<x<<" ";
        cout<<endl;
                
    }
    signed main()
    {
        int t=1;
        while(t--)
            solve();
    }

    E2

    #include<map>
    #include<queue>
    #include<time.h>
    #include<limits.h>
    #include<cmath>
    #include<ostream>
    #include<iterator>
    #include<set>
    #include<stack>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define rep_1(i,m,n) for(int i=m;i<=n;i++)
    #define mem(st) memset(st,0,sizeof st)
    inline int read()
    {
        int num=0, w=0;
        char ch=0;
        while (!isdigit(ch))
        {
            w|=ch=='-';
            ch = getchar();
        }
        while (isdigit(ch))
        {
            num = (num<<3) + (num<<1) + (ch^48);
            ch = getchar();
        }
        return w? -num: num;
    }
    typedef long long ll;
    typedef pair<int,int> pii;
    typedef unsigned long long ull;
    typedef pair<double,double> pdd;
    const int inf = 0x3f3f3f3f;
    const int N=2e6+10;
    int n,k;
    int tot;
    int a[N];
    int X[N]; 
    int b[N];
    int pre[N];
    map<int,int>p;
    inline bool jud(int x)
    {
        int tmp=upper_bound(b+1,b+tot+1,x)-b-1;
        int nw=pre[tmp];
        //如果大于等于k,那么往后必定会*k
        //如果是0,那么就说明之前没有人可以战胜,就不行
        if(nw>=k||nw==0)
            return false;
        for(int i=1; i<=n-1; i++)
        {
            nw--;
            x++;
            nw+=p[x];
            //可以选择的个数
            if(nw>=k||nw==0)
                return false;
        }
        return true;
    }
    void solve()
    {
        cin>>n>>k;
        for(int i=1; i<=n; i++)
            a[i]=read(),p[a[i]]++,b[i]=a[i];
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        tot=unique(b+1,b+n+1)-b-1;//离散化之后的个数
        for(int i=1; i<=n; i++)
        {
            int tmp=lower_bound(b+1,b+tot+1,a[i])-b;
            X[tmp]++;//离散化之后的
        }
        for(int i=1; i<=tot; i++)
            pre[i]=pre[i-1]+X[i];
        int l=max(a[1],a[n]-n+1),r=a[n],ans=0;
        for(int i=1; i<=n; i++)
            l=max(l,a[i]-i+1);
        int x=l;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(jud(mid))
                ans=mid,l=mid+1;
            else
                r=mid-1;
        }
        cout<<max(ans-x+1,0)<<endl;
        for(int i=x; i<=ans; i++)
            cout<<i<<" ";
        cout<<endl;
    }
    int main()
    {
        int t=1;
        while(t--)
            solve();
        return 0;
    }