Codeforces Round #228 div1前三题

A题:

A. Fox and Box Accumulation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Fox Ciel has n boxes in her room. They have the same size and weight, but they might have different strength. The i-th box can hold at most xi boxes on its top (we‘ll call xi the strength of the box).

Since all the boxes have the same size, Ciel cannot put more than one box directly on the top of some box. For example, imagine Ciel has three boxes: the first has strength 2, the second has strength 1 and the third has strength 1. She cannot put the second and the third box simultaneously directly on the top of the first one. But she can put the second box directly on the top of the first one, and then the third box directly on the top of the second one. We will call such a construction of boxes a pile.

Codeforces Round #228 div1前三题

Fox Ciel wants to construct piles from all the boxes. Each pile will contain some boxes from top to bottom, and there cannot be more thanxi boxes on the top of i-th box. What is the minimal number of piles she needs to construct?

Input

The first line contains an integer n (1?≤?n?≤?100). The next line contains n integers x1,?x2,?...,?xn (0?≤?xi?≤?100).

Output

Output a single integer — the minimal possible number of piles.

Sample test(s)
input
3
0 0 10
output
2
input
5
0 1 2 3 4
output
1
input
4
0 0 0 0
output
4
input
9
0 1 0 2 0 1 1 2 10
output
3
Note

In example 1, one optimal way is to build 2 piles: the first pile contains boxes 1 and 3 (from top to bottom), the second pile contains only box 2.

Codeforces Round #228 div1前三题

In example 2, we can build only 1 pile that contains boxes 1, 2, 3, 4, 5 (from top to bottom).

Codeforces Round #228 div1前三题


题目大意:给你一些物品给出每件物品上面最多放多少箱子,然后求解最少放多少堆。

解题思路:可以采取贪心的策略。这题相对来说比较简单,每次都从可以放最少的箱子数量从上往下放,这样贪心可以求解。


AC代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

int a[102];

int main()
{
    int n,i,x;
    while(cin>>n)
    {
        memset(a,0,sizeof(a));
        for(i=0;i<n;i++)
        {
            cin>>x;
            a[x]++;
        }

        int res=0;
        while(1)
        {
            int flag=0;
            for(i=0;i<=100;i++)
            {
                if(a[i])
                {
                    flag=1;
                    break;
                }
            }

            if(flag==0) break;

            int step=0;
            for(i=0;i<=100;i++)
            {
                if((a[i]>=1&&i==step)||(a[i]==1&&step<i))
                {
                    a[i]--;
                    step++;
                }
                else if(step<i&&a[i]>=2)
                {
                    a[i]--;
                    step++;

                    //cout<<i<<" "<<step<<" dsad"<<endl;
                    //continue;
                    i--;
                }
            }

            //for(i=0;i<=5;i++)
                //cout<<a[i]<<" ";
            //cout<<endl;

            res++;
        }

        cout<<res<<endl;
    }
    return 0;
}

/*
3
0 0 10
5
0 1 2 3 4
4
0 0 0 0
9
0 1 0 2 0 1 1 2 10
7
0 2 2 2 3 4 5
*/

这个题目当时写的时候很拙计,虽然样例过了,但是自己随便写了组测试数据就过不了,然后就debug了好久。。


B题:
B. Fox and Minimal path
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Fox Ciel wants to write a task for a programming contest. The task is: "You are given a simple undirected graph with n vertexes. Each its edge has unit length. You should calculate the number of shortest paths between vertex 1 and vertex 2."

Same with some writers, she wants to make an example with some certain output: for example, her birthday or the number of her boyfriend. Can you help her to make a test case with answer equal exactly to k?

Input

The first line contains a single integer k (1?≤?k?≤?109).

Output

You should output a graph G with n vertexes (2?≤?n?≤?1000). There must be exactly k shortest paths between vertex 1 and vertex 2 of the graph.

The first line must contain an integer n. Then adjacency matrix G with n rows and n columns must follow. Each element of the matrix must be ‘N‘ or ‘Y‘. If Gij is ‘Y‘, then graph G has a edge connecting vertex i and vertex j. Consider the graph vertexes are numbered from 1 ton.

The graph must be undirected and simple: Gii = ‘N‘ and Gij?=?Gji must hold. And there must be at least one path between vertex 1 and vertex 2. It‘s guaranteed that the answer exists. If there multiple correct answers, you can output any of them.

Sample test(s)
input
2
output
4
NNYY
NNYY
YYNN
YYNN
input
9
output
8
NNYYYNNN
NNNNNYYY
YNNNNYYY
YNNNNYYY
YNNNNYYY
NYYYYNNN
NYYYYNNN
NYYYYNNN
input
1
output
2
NY
YN
Note

In first example, there are 2 shortest paths: 1-3-2 and 1-4-2.

In second example, there are 9 shortest paths: 1-3-6-2, 1-3-7-2, 1-3-8-2, 1-4-6-2, 1-4-7-2, 1-4-8-2, 1-5-6-2, 1-5-7-2, 1-5-8-2.


题目大意:让你构造一张图,使得结点1到结点2最短路走的方法有n种,当然1<=n<=10^9,当时突然灵光一闪就是素数分解,然后就开始写了,不过大于1000的素数是不可以的,因为要求最多只能用1000个点,然后题目有一句话说了:不会给没有答案的n。然后我就抱着庆幸的态度交了。不过最后被hack了。直到最后也没能想通。

解题思路:不过在晚上的时候突然想到了,觉得素数分解不了的话,还可以按照权基数的思想呢,然后早上突然就觉得可以试一下二进制,看了下别人的思路,然后就觉得自己的构造捉急。就是二进制的思想。

每次
1
3 4 5
6 7 8
9 10 11
每次都让3和6,7连着,4和6,7连着.,6连接9,10,7连接9,10.....1连接5,5连接8,8连接11 ,如果到5结点的时候权是1,那么就让5往左边6,7连接即可,如果权是0,那么就不管,最后让最后三个点里面的最左边两个点都连着2,如果k&1==1,那么最后三个点里面最后一个点也连接2.就是这个思想,具体见代码。

由于k最大为10^9<2^30,那么只需要1+90+1个点就可以搞定。


AC代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

int mp[100][105];

int main()
{
    int k;
    int i,j;
    while(cin>>k)
    {
        memset(mp,0,sizeof(mp));
        mp[1][5]=1;
        if(k&(1<<30))
        {
            mp[1][3]=1;
            mp[1][4]=1;
        }

        j=3;
        for(i=29;i>=1;i--)
        {
            mp[j][j+3]=1,mp[j][j+4]=1;
            mp[j+1][j+3]=1,mp[j+1][j+4]=1;
            mp[j+2][j+5]=1;
            if(k&(1<<i))
            {
                mp[j+2][j+3]=1;
                mp[j+2][j+4]=1;
            }
            j+=3;
        }

        mp[90][2]=1,mp[91][2]=1;
        if(k&1) mp[92][2]=1;

        cout<<92<<endl;
        for(i=1;i<=92;i++)
        {
            for(j=1;j<=92;j++)
            {
                if(mp[i][j]||mp[j][i]) cout<<"Y";
                else cout<<"N";
            }
            cout<<endl;
        }
    }
    return 0;
}


C题:
C. Fox and Card Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Fox Ciel is playing a card game with her friend Fox Jiro. There are n piles of cards on the table. And there is a positive integer on each card.

The players take turns and Ciel takes the first turn. In Ciel‘s turn she takes a card from the top of any non-empty pile, and in Jiro‘s turn he takes a card from the bottom of any non-empty pile. Each player wants to maximize the total sum of the cards he took. The game ends when all piles become empty.

Suppose Ciel and Jiro play optimally, what is the score of the game?

Input

The first line contain an integer n (1?≤?n?≤?100). Each of the next n lines contains a description of the pile: the first integer in the line issi (1?≤?si?≤?100) — the number of cards in the i-th pile; then follow si positive integers c1c2, ..., ck, ..., csi (1?≤?ck?≤?1000) — the sequence of the numbers on the cards listed from top of the current pile to bottom of the pile.

Output

Print two integers: the sum of Ciel‘s cards and the sum of Jiro‘s cards if they play optimally.

Sample test(s)
input
2
1 100
2 1 10
output
101 10
input
1
9 2 8 6 5 9 4 7 1 3
output
30 15
input
3
3 1 3 2
3 5 4 6
2 8 7
output
18 18
input
3
3 1000 1000 1000
6 1000 1000 1000 1000 1000 1000
5 1000 1000 1000 1000 1000
output
7000 7000
Note

In the first example, Ciel will take the cards with number 100 and 1, Jiro will take the card with number 10.

In the second example, Ciel will take cards with numbers 2, 8, 6, 5, 9 and Jiro will take cards with numbers 4, 7, 1, 3.


题目大意:看起来是个博弈题目,A,B分别拿物品,总共有n堆物品,每堆物品有s[i]个,从上面到下面分别放,每个物品各自的价值。A先拿物品,不过他每次只能选择从某一堆最上面拿出物品,而B每次只能选择从某一堆最下面拿出物品。A,B轮流拿物品,A,B都是最优选择使得总价值最大。问你 A,B最终得分。

解题思路:我想的思路开始觉得是dp,但是觉得无从下手。后来就放弃了,看了下题解,原来贪心就可以搞定。
然后我就举了个例子。
3
3 5 6 7
3 1 2 3
4 4 3 2 1
按照这样,如果A,B每次都拿最大的,结果不一定最优。
A拿的分为:5 6 4 3 2
B拿的分为:7 3 2 1 1
但是实际上B可以先不拿第二堆的3,因为3在最下面,可以先拿第三堆得1,然后就可以拿第二堆的2了。

实际上的得分为:
A拿的分为:5 6 4 3 1
B拿的分为:7 1 2 3 2

通过多找几轮就会发现,每次一堆的最上面一半是给A了,下面一半是给B了,然后再对中间剩余的排序即可。因为是博弈,当然每个人的态度都是一样的,这样也合情合理,实际证明方法也没多想。

题目地址:C. Fox and Card Game

AC代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

vector <int> mq[105];
int xf[105];

int main()
{
    int n,s,x;
    int i,j;

    int a,b;
    while(cin>>n)
    {
        for(i=1;i<=100;i++)
            mq[i].clear();
        a=0,b=0;

        for(i=1;i<=n;i++)
        {
            cin>>s;
            while(s--)
            {
                cin>>x;
                mq[i].push_back(x);
            }
        }

        int t=0;
        for(i=1;i<=n;i++)
        {
            if(!(mq[i].size()&1))
            {
                for(j=0;j<mq[i].size()/2;j++) a+=mq[i][j];
                for(;j<mq[i].size();j++) b+=mq[i][j];
            }
            else
            {
                for(j=0;j<mq[i].size()/2;j++) a+=mq[i][j];
                xf[t++]=mq[i][j++];
                for(;j<mq[i].size();j++) b+=mq[i][j];
            }
        }

        sort(xf,xf+t);
        int flag=0;
        for(i=t-1;i>=0;i--)
        {
            if(!flag)
            {
                a+=xf[i];
                flag=1;
            }
            else
            {
                b+=xf[i];
                flag=0;
            }
        }

        cout<<a<<" "<<b<<endl;
    }

    return 0;
}

/*
2
1 100
2 1 10

1
9 2 8 6 5 9 4 7 1 3

3
3 1 3 2
3 5 4 6
2 8 7

3
3 1000 1000 1000
6 1000 1000 1000 1000 1000 1000
5 1000 1000 1000 1000 1000
*/


Codeforces Round #228 div1前三题

上一篇:Windows常用网络命令


下一篇:[LeetCode]Sort List,解题报告