Codeforces Round #567 (Div. 2)自闭记

我就是我 2021-11-26 15:26 209阅读 0赞

嘿嘿嘿，第一篇文章，感觉代码可以缩起来简直不要太爽

打个div2发挥都这么差...

平均一题fail一次，还调不出错，自闭了

又一次跳A开B，又一次B傻逼错误调不出来

罚时上天，E还傻逼了..本来这场应该很前的，最后只苟在rated的人里面50

A. Chunga-Changa

随便做就行了，因为CF似乎不可以print("%d",0);于是WA了一个样例

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

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<vector>
    using namespace std;
    typedef long long LL;
    
    int main()
    {
        LL x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        if (x/z+y/z==(x+y)/z) printf("%lld 0\n",(x+y)/z);
        else 
        {
            LL t=(z-y%z)%z;
            LL t1=(z-x%z)%z;
            LL ans=0;
            printf("%lld %lld\n",(x+y)/z,min(t,t1));
        }
        return 0;
    }

B. Split a Number

显然取中间最优，但可能中间有0，那就往两边找

然后一开始有一个大于号写成小于号WA了一发，然后看了半天看不出，最后使得A和B都是30min过

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

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<vector>
    using namespace std;
    typedef long long LL;
    const int N=100005;
    char ss[N];
    int n;
    int cnt;
    bool tf=false;
    int len,a[N];
    int b[N],len1;
    bool JD ()
    {
        if (tf==false) return true;
        if (len<len1) return false;
        if (len>len1) return true;
        for (int u=1;u<=len;u++) 
        {
            if (a[u]<b[u]) return false;
            if (a[u]>b[u]) return true;
        }
        return true;
    }
    void check (int x)
    {
        if (ss[x+1]=='0') return ;
        cnt++;
        len1=max(x,n-x);
        memset(b,0,sizeof(b));
        int i=x,j=n;
        for (int u=len1;u>=1;u--)
        {
            if (i>=1) b[u]=b[u]+ss[i]-'0';
            if (j>x) b[u]=b[u]+ss[j]-'0';
            i--;j--;
        }
        for (int u=len1;u>=1;u--) b[u-1]=b[u-1]+b[u]/10,b[u]%=10;
        if (b[0]!=0)
        {
            len1++;
            for (int u=len1;u>=1;u--) b[u]=b[u-1];
        }
        if (JD())
        {
            len=len1;tf=true;
            for (int u=1;u<=len;u++) a[u]=b[u];
        }
    }
    int main()
    {
        scanf("%d",&n);scanf("%s",ss+1);
        cnt=0;
        for (int u=n/2;u>=1;u--)
        {
            check(u);
            if (cnt>=50) break;
        }
        cnt=0;
        for (int u=n/2;u<n;u++)
        {
            check(u);
            if (cnt>=50) break;
        }
        for (int u=1;u<=len;u++) printf("%d",a[u]);
        return 0;
    }

C. Flag

考虑枚举左上角，那么我们要知道的就是每个点往下多少个就不同D以及在这一段里面往右多少个就不同R

贡献就是三段R的min

前两段的D要一样，问题是第三段他只要比前两段的D大就好了

于是再倒着维护一个U，然后第三段跳到左下角查询，复杂度O(nm)

然后一个变量打错了，WA了两发

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

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<vector>
    using namespace std;
    typedef long long LL;
    const int N=1005;
    char ss[N][N];
    int n,m;
    int R[N][N];
    int mn[N][N];
    int D[N][N];
    int mn1[N][N];
    int main()
    {
        scanf("%d%d",&n,&m);
        for (int u=1;u<=n;u++) scanf("%s",ss[u]+1);
        for (int u=n;u>=1;u--)
        {
            for (int i=m;i>=1;i--)
            {
                if (ss[u][i]==ss[u][i+1]) R[u][i]=R[u][i+1]+1;
                else R[u][i]=1;
            }
        }
        for (int u=1;u<=n;u++)
        for (int i=1;i<=m;i++)
        {
            mn1[u][i]=R[u][i];
            if (ss[u][i]==ss[u-1][i]) mn1[u][i]=min(mn1[u][i],mn1[u-1][i]);
        }
        for (int u=n;u>=1;u--)
        for (int i=1;i<=m;i++)
        {
            mn[u][i]=R[u][i];
            if (ss[u][i]==ss[u+1][i]) 
            {
                mn[u][i]=min(mn[u][i],mn[u+1][i]);
                D[u][i]=D[u+1][i]+1;
            }
            else D[u][i]=1;
        }
        int ans=0;
        for (int u=1;u<=n;u++)
        for (int i=1;i<=m;i++)
        {
            int x1,x2,x3;
            x1=u;
            x2=x1+D[x1][i];
            x3=x2+D[x2][i];
            if (D[x1][i]!=D[x2][i]) continue;
            if (D[x3][i]<D[x2][i]) continue;
            x3=x3+D[x2][i]-1;
            if (x3>n) continue;
            ans=ans+min(min(mn[x1][i],mn[x2][i]),mn1[x3][i]);
            //printf("%d %d %d %d %d\n",u,i,x1,x2,x3);
        }
        printf("%d\n",ans);
        return 0;
    }

D. Irrigation

模拟这个过程使得所有人一样

每一次把所有i的人变为i+1

发现要维护现在又多少人，以及第k大

开个线段树就好了

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

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<vector>
    using namespace std;
    typedef long long LL;
    const LL N=500005;
    LL n,m,Q;
    LL a[N];
    struct qt
    {
        LL l,r;
        LL c;
        LL s1,s2;
    }tr[N*2];LL num;
    void bt (LL l,LL r)
    {
        LL now=++num;
        tr[now].l=l;tr[now].r=r;tr[now].c=0;
        if (l==r) return ;
        LL mid=(l+r)>>1;
        tr[now].s1=num+1;bt(l,mid);
        tr[now].s2=num+1;bt(mid+1,r);
    }
    LL query (LL now,LL x)
    {
        if (tr[now].l==tr[now].r) return tr[now].l;
        LL mid=(tr[now].l+tr[now].r)>>1;
        LL s1=tr[now].s1,s2=tr[now].s2;
        if (tr[s1].c>=x) return query(s1,x);
        else return query(s2,x-tr[s1].c);
    }
    void add (LL now,LL c)
    {
        tr[now].c++;
        if (tr[now].l==tr[now].r) return ;
        LL mid=(tr[now].l+tr[now].r)>>1;
        LL s1=tr[now].s1,s2=tr[now].s2;
        if (c<=mid) add(s1,c);
        else add(s2,c);
    }
    vector<LL> vec[N];
    LL ans[N];
    struct qq
    {
        LL x,id;
    }q[N];
    bool cmp (qq x,qq y) {
         return x.x<y.x;}
    int main()
    {
        scanf("%lld%lld%lld",&n,&m,&Q);
        for (LL u=1;u<=n;u++)    {LL x;scanf("%lld",&x);a[x]++;}
        bt(1,m);
        for (LL u=1;u<=m;u++) vec[a[u]].push_back(u);
        for (LL u=1;u<=Q;u++)    {scanf("%lld",&q[u].x);q[u].x-=n;q[u].id=u;}
        sort(q+1,q+1+Q,cmp);
        LL now=0,now1=1;//�ٰ��˶�������
        for (LL u=0;u<=n;u++)
        {
            while (now1<=Q&&now+tr[1].c>=q[now1].x)    {ans[q[now1].id]=query(1,q[now1].x-now);now1++;}
            now=now+tr[1].c;
            LL siz=vec[u].size();
            for (LL i=0;i<siz;i++) add(1,vec[u][i]);
        }
        while (now1<=Q)
        {
            LL t=q[now1].x-now;
            t=t%m;if (t==0) t=m;
            ans[q[now1].id]=t;
            now1++;
        }
        for (LL u=1;u<=Q;u++) printf("%lld\n",ans[u]);
        return 0;
    }

E1. A Story of One Country (Easy)

打的时候有点崩，不好意思说自己写了个什么傻吊玩意了

就是暴力枚举一个能切的地方就好了，递归处理，复杂度是O(n^2)的

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

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<vector>
    using namespace std;
    typedef long long LL;
    const int N=1005;
    const int MAX=1e9;
    struct qq
    {
        int x1,y1,x2,y2;
        qq () {}
        qq (int a,int b,int c,int d)    {x1=a;y1=b;x2=c;y2=d;}
    };
    bool cmp (qq x,qq y)    {
         return x.x1<y.x1;}
    bool cmp1 (qq x,qq y)    {
         return x.y1<y.y1;}
    int n;
    bool solve (vector<qq> vec)
    {
        int siz=vec.size();    
        if (siz==1) return true;
        vector<qq> a,b;a.clear();b.clear();
        sort(vec.begin(),vec.end(),cmp);
        for (int u=siz-1;u>=0;u--) b.push_back(vec[u]);
        int mx=0;
        for (int u=0;u<siz;u++)
        {
            b.pop_back();a.push_back(vec[u]);mx=max(mx,a[u].x2);
            if (u!=siz-1&&mx<=vec[u+1].x1)    
            {
                //printf("%d %d\n",siz,u);
                return solve(a)&solve(b);
            }
        }
        sort(vec.begin(),vec.end(),cmp1);
        a.clear();b.clear();
        for (int u=siz-1;u>=0;u--) b.push_back(vec[u]);
        mx=0;
        for (int u=0;u<siz;u++)
        {
            b.pop_back();a.push_back(vec[u]);mx=max(mx,a[u].y2);
            if (u!=siz-1&&mx<=vec[u+1].y1)    return solve(a)&solve(b);
        }
        return false;
    }
    int main()
    {
        scanf("%d",&n);
        vector<qq> vec;
        for (int u=1;u<=n;u++)
        {
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            vec.push_back(qq(a,b,c,d));
        }
        if (solve(vec)) printf("YES\n");
        else printf("NO\n");
        return 0;
    }

E2. A Story of One Country (Hard)

考虑优化上面这个过程，其实只需要四个方向一起枚举就可以了

枚举到最小的一个就递归下去，复杂度是启发式分裂，也就是和启发式合并一样的复杂度nlogn

但是实现有点小技巧，因为你不可以扫全部元素，否则复杂度就退化了

那么就是要维护一个有序序列，还要支持删除，显然维护4个set就行了

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

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<vector>
    #include<set>
    using namespace std;
    typedef long long LL;
    const int MAX=1e9;
    struct qq
    {
        int x1,y1,x2,y2;
        qq () {}
        qq (int a,int b,int c,int d)    {x1=a;y1=b;x2=c;y2=d;}
    };
    struct cmp1
    {
        inline bool operator () (qq a,qq b)    {
         return a.x1==b.x1?a.y1<b.y1:a.x1<b.x1;}
    };
    struct cmp2
    {
        inline bool operator () (qq a,qq b)    {
         return a.y1==b.y1?a.x1<b.x1:a.y1<b.y1;}
    };
    struct cmp3
    {
        inline bool operator () (qq a,qq b)    {
         return a.x2==b.x2?a.y2<b.y2:a.x2>b.x2;}
    };
    struct cmp4
    {
        inline bool operator () (qq a,qq b)    {
         return a.y2==b.y2?a.x2<b.x2:a.y2>b.y2;}
    };
    int n;
    bool solve (set<qq,cmp1> &s1,set<qq,cmp2> &s2,set<qq,cmp3> &s3,set<qq,cmp4> &s4)
    {
        int siz=s1.size();    
        if (siz==1) 
        {
            s1.clear();s2.clear();s3.clear();s4.clear();
            return true;
        }
    
        set<qq,cmp1> g1;g1.clear();set<qq,cmp1> :: iterator it1=s1.begin();
        set<qq,cmp2> g2;g2.clear();set<qq,cmp2> :: iterator it2=s2.begin();
        set<qq,cmp3> g3;g3.clear();set<qq,cmp3> :: iterator it3=s3.begin();
        set<qq,cmp4> g4;g4.clear();set<qq,cmp4> :: iterator it4=s4.begin();
        
        int mxx=0,mxy=0,mnx=MAX,mny=MAX;
        for (int u=0;u<siz-1;u++)
        {
            mxx=max(mxx,(*it1).x2);it1++;
            if (mxx<=(*it1).x1)
            {
                set<qq,cmp1> :: iterator now=s1.begin();
                while (now!=it1)
                {
                    qq xx=(*now);now++;
                    s1.erase(xx);g1.insert(xx);
                    s2.erase(xx);g2.insert(xx);
                    s3.erase(xx);g3.insert(xx);
                    s4.erase(xx);g4.insert(xx);
                }
                return solve(g1,g2,g3,g4)&solve(s1,s2,s3,s4);
            }
            mxy=max(mxy,(*it2).y2);it2++;
            
            if (mxy<=(*it2).y1)
            {
                set<qq,cmp2> :: iterator now=s2.begin();
                while (now!=it2)
                {
                    qq xx=(*now);now++;
                    s1.erase(xx);g1.insert(xx);
                    s2.erase(xx);g2.insert(xx);
                    s3.erase(xx);g3.insert(xx);
                    s4.erase(xx);g4.insert(xx);
                }
                return solve(g1,g2,g3,g4)&solve(s1,s2,s3,s4);
            }
            mnx=min(mnx,(*it3).x1);it3++;
            if (mnx>=(*it3).x2)
            {
                set<qq,cmp3> :: iterator now=s3.begin();
                while (now!=it3)
                {
                    qq xx=(*now);now++;
                    s1.erase(xx);g1.insert(xx);
                    s2.erase(xx);g2.insert(xx);
                    s3.erase(xx);g3.insert(xx);
                    s4.erase(xx);g4.insert(xx);
                }
                return solve(g1,g2,g3,g4)&solve(s1,s2,s3,s4);
            }
            mny=min(mny,(*it4).y1);it4++;
            if (mny>=(*it4).y2)
            {
                set<qq,cmp4> :: iterator now=s4.begin();
                while (now!=it4)
                {
                    qq xx=(*now);now++;
                    s1.erase(xx);g1.insert(xx);
                    s2.erase(xx);g2.insert(xx);
                    s3.erase(xx);g3.insert(xx);
                    s4.erase(xx);g4.insert(xx);
                }
                return solve(g1,g2,g3,g4)&solve(s1,s2,s3,s4);
            }
        }
        return false;
    }
    int main()
    {
        scanf("%d",&n);
        set<qq,cmp1> s1;
        set<qq,cmp2> s2;
        set<qq,cmp3> s3;
        set<qq,cmp4> s4;
        for (int u=1;u<=n;u++)
        {
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            s1.insert(qq(a,b,c,d));
            s2.insert(qq(a,b,c,d));
            s3.insert(qq(a,b,c,d));
            s4.insert(qq(a,b,c,d));
        }
        if (solve(s1,s2,s3,s4)) printf("YES\n");
        else printf("NO\n");
        return 0;
    }

转载于:https://www.cnblogs.com/Als123/p/11037265.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211126/bde4cfb77c5c4505bf270f0b756c8988.png