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

2022-10-06 14:33:25

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

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

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

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

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

A. Chunga-Changa

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

#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=;

        printf("%lld %lld\n",(x+y)/z,min(t,t1));

    }

    return ;

}

B. Split a Number

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

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

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<vector>

using namespace std;

typedef long long LL;

const int N=;

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=;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+]=='') return ;

    cnt++;

    len1=max(x,n-x);

    memset(b,,sizeof(b));

    int i=x,j=n;

    for (int u=len1;u>=;u--)

    {

        if (i>=) b[u]=b[u]+ss[i]-'';

        if (j>x) b[u]=b[u]+ss[j]-'';

        i--;j--;

    }

    for (int u=len1;u>=;u--) b[u-]=b[u-]+b[u]/,b[u]%=;

    if (b[]!=)

    {

        len1++;

        for (int u=len1;u>=;u--) b[u]=b[u-];

    }

    if (JD())

    {

        len=len1;tf=true;

        for (int u=;u<=len;u++) a[u]=b[u];

    }

}

int main()

{

    scanf("%d",&n);scanf("%s",ss+);

    cnt=;

    for (int u=n/;u>=;u--)

    {

        check(u);

        if (cnt>=) break;

    }

    cnt=;

    for (int u=n/;u<n;u++)

    {

        check(u);

        if (cnt>=) break;

    }

    for (int u=;u<=len;u++) printf("%d",a[u]);

    return ;

}

C. Flag

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

贡献就是三段R的min

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

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

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

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<vector>

using namespace std;

typedef long long LL;

const int N=;

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=;u<=n;u++) scanf("%s",ss[u]+);

    for (int u=n;u>=;u--)

    {

        for (int i=m;i>=;i--)

        {

            if (ss[u][i]==ss[u][i+]) R[u][i]=R[u][i+]+;

            else R[u][i]=;

        }

    }

    for (int u=;u<=n;u++)

    for (int i=;i<=m;i++)

    {

        mn1[u][i]=R[u][i];

        if (ss[u][i]==ss[u-][i]) mn1[u][i]=min(mn1[u][i],mn1[u-][i]);

    }

    for (int u=n;u>=;u--)

    for (int i=;i<=m;i++)

    {

        mn[u][i]=R[u][i];

        if (ss[u][i]==ss[u+][i])

        {

            mn[u][i]=min(mn[u][i],mn[u+][i]);

            D[u][i]=D[u+][i]+;

        }

        else D[u][i]=;

    }

    int ans=;

    for (int u=;u<=n;u++)

    for (int i=;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]-;

        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 ;

}

D. Irrigation

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

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

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

开个线段树就好了

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<vector>

using namespace std;

typedef long long LL;

const LL N=;

LL n,m,Q;

LL a[N];

struct qt

{

    LL l,r;

    LL c;

    LL s1,s2;

}tr[N*];LL num;

void bt (LL l,LL r)

{

    LL now=++num;

    tr[now].l=l;tr[now].r=r;tr[now].c=;

    if (l==r) return ;

    LL mid=(l+r)>>;

    tr[now].s1=num+;bt(l,mid);

    tr[now].s2=num+;bt(mid+,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)>>;

    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)>>;

    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=;u<=n;u++)    {LL x;scanf("%lld",&x);a[x]++;}

    bt(,m);

    for (LL u=;u<=m;u++) vec[a[u]].push_back(u);

    for (LL u=;u<=Q;u++)    {scanf("%lld",&q[u].x);q[u].x-=n;q[u].id=u;}

    sort(q+,q++Q,cmp);

    LL now=,now1=;//�ٰ��˶�������

    for (LL u=;u<=n;u++)

    {

        while (now1<=Q&&now+tr[].c>=q[now1].x)    {ans[q[now1].id]=query(,q[now1].x-now);now1++;}

        now=now+tr[].c;

        LL siz=vec[u].size();

        for (LL i=;i<siz;i++) add(,vec[u][i]);

    }

    while (now1<=Q)

    {

        LL t=q[now1].x-now;

        t=t%m;if (t==) t=m;

        ans[q[now1].id]=t;

        now1++;

    }

    for (LL u=;u<=Q;u++) printf("%lld\n",ans[u]);

    return ;

}

E1. A Story of One Country (Easy)

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

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

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<vector>

using namespace std;

typedef long long LL;

const int N=;

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==) return true;

    vector<qq> a,b;a.clear();b.clear();

    sort(vec.begin(),vec.end(),cmp);

    for (int u=siz-;u>=;u--) b.push_back(vec[u]);

    int mx=;

    for (int u=;u<siz;u++)

    {

        b.pop_back();a.push_back(vec[u]);mx=max(mx,a[u].x2);

        if (u!=siz-&&mx<=vec[u+].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-;u>=;u--) b.push_back(vec[u]);

    mx=;

    for (int u=;u<siz;u++)

    {

        b.pop_back();a.push_back(vec[u]);mx=max(mx,a[u].y2);

        if (u!=siz-&&mx<=vec[u+].y1)    return solve(a)&solve(b);

    }

    return false;

}

int main()

{

    scanf("%d",&n);

    vector<qq> vec;

    for (int u=;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 ;

}

E2. A Story of One Country (Hard)

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

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

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

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

#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==)

    {

        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=,mxy=,mnx=MAX,mny=MAX;

    for (int u=;u<siz-;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=;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 ;

}
上一篇：Activitys, Threads, & Memory Leaks


下一篇：C#：注册机的实现【提供源代码下载】