Codeforces Round #553 (Div. 2) 题解

昨晚深夜修仙上紫记，虽然不错还是很有遗憾的。

A. Maxim and Biology

看完就会做的题，然而手速跟不上

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const int _=1e2;

const int maxn=;

char ss[]; int a[];

int getdis(int x,int y)

{

    if(x>y)swap(x,y);

    return min(y-x,x+-y);

}

int main()

{

    int n,m;

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

    for(int i=;i<=n;i++)a[i]=ss[i]-'A'+;

    int mn=(<<);

    for(int i=;i<=n-;i++)

    {

        mn=min(mn,getdis(a[i],)+getdis(a[i+],)+getdis(a[i+],)+getdis(a[i+],));

    }

    printf("%d\n",mn);

    return ;

}

A. Maxim and Biology

B. Dima and a Bad XOR

其实先开的是B，但是O(nm*1024)相当不靠谱不是很敢写。。。后来写得还是磕磕绊绊总之相当不爽。就是那种要抢时间这个题又烦的一批的感觉

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const int _=1e2;

const int maxn=;

int a[maxn][maxn];

bool f[maxn][];int d[maxn][],fr[maxn][]; int as[maxn];

int main()

{

    int n,m,mx=;

    scanf("%d%d",&n,&m);

    f[][]=true;

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

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

            scanf("%d",&a[i][j]),mx=max(mx,a[i][j]);

    while(mx!=(mx&-mx))mx-=(mx&-mx);

    mx<<=;

    if(mx==)mx=;

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

        for(int zt=;zt<mx;zt++)

            if(f[i][zt])

            {

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

                    f[i+][zt^a[i+][j]]=true,d[i+][zt^a[i+][j]]=j,fr[i+][zt^a[i+][j]]=zt;

            }

    for(int zt=;zt<mx;zt++)

        if(f[n][zt])

        {

            puts("TAK");

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

            {

                as[i]=d[i][zt],zt=fr[i][zt];

            }

            for(int i=;i<=n;i++)printf("%d ",as[i]);

            puts("");return ;

        }

    puts("NIE");

    return ;

}

B. Dima and a Bad XOR

C. Problem for Nazar

和B一起让我自闭了半个多小时，看错一发题意。其实就是按题意模拟，然后写到45min才过真是！@#￥%……&，也是疯狂调试没什么底的，还好样例比较强。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const LL mod=1e9+;

inline LL ad(LL x,LL y){return (x>=mod-y)?(x-mod+y):x+y;}

inline LL re(LL x,LL y){return (x<y)?(x-y+mod):x-y;}

LL solve(LL n)

{

    if(n==)return ;

    int op=; LL i,step=,ost=,est=,ret=;

    for(i=;i<=n;i<<=)

    {

        if(step+i>=n)break;

        if(op==)

        {

            LL ed=ost+*(i-);

            ret=ad(ret,(ost+ed)%mod*(i%mod)%mod*(mod/+)%mod);

            ost=ed+;

        }

        else

        {

            LL ed=est+*(i-);

            ret=ad(ret,(est+ed)%mod*(i%mod)%mod*(mod/+)%mod);

            est=ed+;

        }

        op^=;

        step+=i;

    }

    if(op==)

    {

        LL ed=ost+*(n-step-);if(ed%==)ed--;

        ret=ad(ret,(ost+ed)%mod*((n-step)%mod)%mod*(mod/+)%mod);

    }

    else

    {

        LL ed=est+*(n-step-);if(ed%==)ed--;

        ret=ad(ret,(est+ed)%mod*((n-step)%mod)%mod*(mod/+)%mod);

    }

    return ret;

}

int main()

{

    LL l,r;

    scanf("%lld%lld",&l,&r);

    printf("%lld\n",re(solve(r),solve(l-)));

    return ;

}

C. Problem for Nazar

D. Stas and the Queue at the Buffet

sb微扰。我觉得比A还sb。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const int _=1e2;

const int maxn=1e5+_;

struct node{int a,b;}p[maxn];

bool cmp(node n1,node n2){return n1.a-n1.b>n2.a-n2.b;}

int main()

{

    int n;

    scanf("%d",&n);

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

        scanf("%d%d",&p[i].a,&p[i].b);

    sort(p+,p+n+,cmp);

    LL ans=;

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

    {

        ans+=(LL)(i-)*p[i].a+(LL)(n-i)*p[i].b;

    }

    printf("%lld\n",ans);

    return ;

}

D. Stas and the Queue at the Buffet

E. Number of Components

这个E岂不是搞笑的？？明明O(n)还放1e5

考虑已经得到前i-1个点的贡献，现在加入i这个点，假如a[i]不在[l,r]里面或a[i],a[i-1]都在[l,r]里面它没有贡献，否则就会产生贡献。

第二天rose_king又给出了一个更直观的做法：因为联通块数=总点数-被删的边数，答案就是=总点数-被删的边数-不在[l,r]的点数

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const int _=1e2;

const int maxn=1e5+_;

int a[maxn];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    LL ans=(LL)(a[]-)*(n-a[])+n; int L,R;

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

    {

        if(a[i]==a[i-])continue;

        if(a[i]>a[i-])

        {

            L=a[i]--a[i-],R=n-a[i];

        }

        else if(a[i]<a[i-])

        {

            L=a[i]-,R=a[i-]--a[i];

        }

        ans+=(LL)L*R+L+R+;

    }

    printf("%lld\n",ans);

    return ;

}

E. Number of Components

F. Sonya and Informatics

这个F也是我有问题，看错了一发题意浪费了半个小时，然后脑子不清醒写了个假的，其实只要设f[i]表示在正确位置的1的个数为i然后明显矩乘优化就完事了

咕了

这几场手速都是极大的劣势

天天又看错题

还很慢热，写完模拟才有点做题的感觉

总之就是菜鸡一个

不过没fail题算是有点安慰吧

巴特西

Codeforces Round #553 (Div. 2) 题解

最新文章

热门文章