CodeforcesRound#228div1前三题

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 x_i boxes
on its top (we‘ll call x_i 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.

$bubuko.com,布布扣$

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 thanx_i 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 x₁,?x₂,?...,?x_n (0?≤?x_i?≤?100).

Output

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

Sample test(s)

input

3
0 0 10

output

input

5
0 1 2 3 4

output

input

4
0 0 0 0

output

input

9
0 1 0 2 0 1 1 2 10

output

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.

$bubuko.com,布布扣$

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

$bubuko.com,布布扣$

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

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

题目地址：A.
Fox and Box Accumulation

AC代码：

#include
#include
#include
#include
#include
#include
using namespace std;
int a[102];
int main()
{
int n,i,x;
while(cin>>n)
{
memset(a,0,sizeof(a));
for(i=0;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 {
a[i]--;
step++;
}
else if(step=2)
{
a[i]--;
step++;
//cout< //continue;
i--;
}
}
//for(i=0;i<=5;i++)
//cout< //cout< res++;
}
cout< }
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题：

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?≤?10⁹).

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 G_ij 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: G_ii =
‘N‘ and G_ij?=?G_ji 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

output

4
NNYY
NNYY
YYNN
YYNN

input

output

8
NNYYYNNN
NNNNNYYY
YNNNNYYY
YNNNNYYY
YNNNNYYY
NYYYYNNN
NYYYYNNN
NYYYYNNN

input

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了。直到最后也没能想通。

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

每次

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&＃43;90&＃43;1个点就可以搞定。

题目地址：B.
Fox and Minimal path

AC代码：

#include
#include
#include
#include
#include
#include
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< {
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< 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< }
}
return 0;
}

C题：

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 iss_i (1?≤?s_i?≤?100)
— the number of cards in the i-th pile; then follow s_i positive
integers c₁, c₂,
..., c_k, ..., c_{s_i} (1?≤?c_k?≤?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]个，从上面到下面分别放，每个物品各自的价&＃20540;。A先拿物品，不过他每次只能选择从某一堆最上面拿出物品，而B每次只能选择从某一堆最下面拿出物品。A，B轮流拿物品，A，B都是最优选择使得总价&＃20540;最大。问你
A，B最终得分。

解题思路：我想的思路开始觉得是dp，但是觉得无从下手。后来就放弃了，看了下题解，原来贪心就可以搞定。

然后我就举了个例子。

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
#include
#include
#include
#include
#include
#include
using namespace std;
vector 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 for(;j }
else
{
for(j=0;j xf[t++]=mq[i][j++];
for(;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< }
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
*/