Codeforces Round#516 Div.1 翻车记

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

A：开场懵逼。然后发现有人1min过，于是就sort了一下，于是就过了。正经证明的话，考虑回文串两端点一定是相同的，所以最多有Σcnt _i *(cnt _i +1)/2个，cnt _i 为第i种字母出现次数。而sort是可以达到这个最大值的。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

int n;

char s[N];

int main()

{

    n=read();

    scanf("%s",s+);sort(s+,s+n+);

    printf("%s",s+);

    return ;

}

B：注意到由一点到另一点向左和向右移动次数的差是固定的，所以只需要最小化他们的和。直接dij即可。实际上有一种01bfs的trick，用来跑边权只有01的最短路，使用一个deque，每次将0边扩展到的点放在队首，1边扩展到的点放在队尾，容易发现这样保证了队列里的点按距离排序。不过普通队列直接bfs的fst了一片。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 2010

int n,m,r,c,x,y,p[N*N],t,ans=;

int a[N][N],d[N*N];

bool flag[N*N];

struct data{int to,nxt,len;

}edge[N*N<<];

void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}

int trans(int x,int y){return (x-)*m+y;}

struct data2

   {

       int x,d;

      bool operator <(const data2&a) const

        {

            return d>a.d;

        }

    };

    priority_queue<data2> q;

void dijkstra(int start)

{

    while (!q.empty()) q.pop();

    memset(d,,sizeof(d));d[start]=;q.push((data2){start,});

    memset(flag,,sizeof(flag));

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

    {

        while (!q.empty()&&flag[q.top().x]) q.pop();

        if (q.empty()) break;

        data2 v=q.top();q.pop();

        flag[v.x]=;

        for (int j=p[v.x];j;j=edge[j].nxt)

        if (v.d+edge[j].len<d[edge[j].to])

        {

            d[edge[j].to]=v.d+edge[j].len;

            q.push((data2){edge[j].to,d[edge[j].to]});

        }

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif

    n=read(),m=read(),r=read(),c=read(),x=read(),y=read();swap(x,y);

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

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

        {

            char c=getchar();

            while (c!='.'&&c!='*') c=getchar();

            if (c=='.') a[i][j]=;

        }

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

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

        if (a[i][j])

        {

            if (i>&&a[i-][j]) addedge(trans(i,j),trans(i-,j),);

            if (j>&&a[i][j-]) addedge(trans(i,j),trans(i,j-),);

            if (i<n&&a[i+][j]) addedge(trans(i,j),trans(i+,j),);

            if (j<m&&a[i][j+]) addedge(trans(i,j),trans(i,j+),);

        }

    dijkstra(trans(r,c));

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

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

        if (d[trans(i,j)]<=n*m)

        {

            //cout<<i<<' '<<j<<' '<<d[trans(i,j)]<<endl;

            int p=(d[trans(i,j)]+j-c)/,q=d[trans(i,j)]-p;

            if (p<=x&&q<=y)ans++;

        }

        //x+y=d x-y=j-c x right

        //x=(d+j-c)/2 y=d-x

    cout<<ans;

    return ;

}

C：将所有点放在一条线上，黑点划在一边白点划在一边，每次取未确定部分的中点，根据所给颜色继续划分。可能需要把第一个点放在最左或最右，不这么干的话最后可能会有重合点。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 35

int n,l,r;

int main()

{

#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif

    cin>>n;l=,r=;

    cout<<<<' '<<<<endl;

    char ch=getchar();while (ch!='b'&&ch!='w') ch=getchar();

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

    {

        cout<<<<' '<<(l+r)/<<endl;

        fflush(stdout);

        char c=getchar();while (c!='b'&&c!='w') c=getchar();

        if (c==ch) l=(l+r)/;else r=(l+r)/;

        while (c>='a'&&c<='z') c=getchar();

    }

    cout<<<<' '<<l<<' '<<<<' '<<r<<endl;

    fflush(stdout);

    return ;

}