Codeforces Round #228 (Div. 1)

今天学长给我们挂了一套Div.1的题，难受，好难啊。

Problem A:

题目大意：给你n个数字，让你叠成n堆，每个数字上面的数的个数不能超过这个数，如 3 上面最多放三个数字

问你，最少能放几堆。

刚开始看错题意，以为只要比这个数字小的数都能放上去，后来看清了题意，一直想的是怎么从下往上放，感觉

二分加贪心可以做，但是太麻烦了，后来想如果从上往下放就好做多了，每次从小的开取，这样到取下一个数的

时候就知道上面有多少，能不能取这个数，这样的话也能保证这一堆是最优的。

#include<bits/stdc++.h>

using namespace std;

int a[],n;

bool vis[];

int main()

{

    scanf("%d",&n);

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

    sort(a,a+n);

    int sum=n;

    int ans=;

    int now=;

    while(sum)

    {

        //cout<<sum<<endl;

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

        {

            if(!vis[i])

            {

                if(a[i]>=now)

                {

                    now++;

                    vis[i]=;

                    sum--;

                }

            }

        }

        ans++;

        now=;

    }

    cout<<ans<<endl;

    return ;

}

Problem B:

题目大意：让你给出一幅图，让这幅图从1节点到2节点的最短路的条数为k，且节点个数不能超过1000个。

思路：如果没有节点个数的限制那么这题就非常好些，但有了限制的话其实我们可以这么想，我们可以把

k用2进制表示，这样就能将条数表示成2*2*2...+2*2...的方式。刚写的时候每条单链都是新的，取极限值的

时候会超过1000个节点，于是我就先预处理处一条长度为100的单链重复利用。

#include<bits/stdc++.h>

using namespace std;

int k;

int a[],pos;

bool vis[][];

int len[];//len[i]表示还需要增加i长度的链需要接在那个节点上

int main()

{

    vis[][]=vis[][]=;

    len[]=;

    len[]=;

    int ct=;

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

    {

        vis[i][i-]=vis[i-][i]=;

        len[++ct]=i-;

    }

    cin>>k;

    pos=;

    while(k)

    {

        a[pos++]=k&;

        k=k>>;

    }

    pos--;

    int cnt=;

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

    {

        if(a[i])

        {

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

            {

                if(j==)

                {

                    cnt++;

                    vis[cnt][]=;

                    vis[][cnt]=;

                    cnt++;

                    vis[cnt][]=;

                    vis[][cnt]=;

                }

                else

                {

                    cnt++;

                    vis[cnt][cnt-]=vis[cnt-][cnt]=;

                    vis[cnt][cnt-]=vis[cnt-][cnt]=;

                    cnt++;

                    vis[cnt][cnt-]=vis[cnt-][cnt]=;

                    vis[cnt][cnt-]=vis[cnt-][cnt]=;

                }

            }

            if(i==pos)

            {

                vis[cnt][]=vis[][cnt]=;

                vis[cnt-][]=vis[][cnt-]=;

            }

            else

            {

                if(!i) vis[][len[pos+]]=vis[len[pos+]][]=;

                else

                {

                    vis[cnt][len[pos-i+]]=vis[len[pos-i+]][cnt]=;

                    vis[cnt-][len[pos-i+]]=vis[len[pos-i+]][cnt-]=;

                }

            }

        }

    }

    cout<<""<<endl;

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

    {

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

        {

            if(vis[i][j] && i!=j) printf("Y");

            else printf("N");

        }

        puts("");

    }

    return ;

}

Problem C:

题目大意：有n堆牌，A只能从顶部取牌，B只能从底部取牌，A先取，如果每个人都希望自己的点数总和

最大，且每个人的操作都最优，问你最后两个人的点数分别是什么。

思路：这个题还是比较简单的贪心，我们可以这么想，我们把每堆牌都分成上堆和下堆，如果是奇数则

把中间的牌取出来放到一个数组里。如果对A来说下堆有对他有利的大牌，他会想去拿，但是B也是最优

操作，B不会让A拿到，对B来说也是同理，所以最后肯定上堆都是A的下堆都是B的，奇数堆取出来的一

个一个分。

#include<bits/stdc++.h>

using namespace std;

vector<int> zhong;

bool cmp(int a,int b)

{

    return a>b;

}

int main()

{

    int n;

    cin>>n;

    int sum1=,sum2=;

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

    {

        int m;

        scanf("%d",&m);

        if(m%==)

        {

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

            {

                int g;scanf("%d",&g);

                if(i<=m/) sum1+=g;

                else sum2+=g;

            }

        }

        else

        {

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

            {

                int g;scanf("%d",&g);

                if(i<=m/) sum1+=g;

                else if(i==m/+) zhong.push_back(g);

                else sum2+=g;

            }

        }

    }

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

    for(int i=;i<zhong.size();i++)

    {

        if(i%==) sum1+=zhong[i];

        else sum2+=zhong[i];

    }

    printf("%d %d\n",sum1,sum2);

    return ;

}

巴特西

Codeforces Round #228 (Div. 1)

最新文章

热门文章