9
17
2015
0

CF257Div1 A. Jzzhu and Chocolate

A. Jzzhu and Chocolate
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jzzhu has a big rectangular chocolate bar that consists of n × m unit squares. He wants to cut this bar exactly k times. Each cut must meet the following requirements:

  • each cut should be straight (horizontal or vertical);
  • each cut should go along edges of unit squares (it is prohibited to divide any unit chocolate square with cut);
  • each cut should go inside the whole chocolate bar, and all cuts must be distinct.

The picture below shows a possible way to cut a 5 × 6 chocolate for 5 times.

Imagine Jzzhu have made k cuts and the big chocolate is splitted into several pieces. Consider the smallest (by area) piece of the chocolate, Jzzhu wants this piece to be as large as possible. What is the maximum possible area of smallest piece he can get with exactlyk cuts? The area of a chocolate piece is the number of unit squares in it.

Category: codeforces | Tags:
9
16
2015
1

2809: [Apio2012]dispatching

2809: [Apio2012]dispatching

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 2014  Solved: 1023
[Submit][Status][Discuss]

Description

在一个忍者的帮派里,一些忍者们被选中派遣给顾客,然后依据自己的工作获取报偿。在这个帮派里,有一名忍者被称之为 Master。除了 Master以外,每名忍者都有且仅有一个上级。为保密,同时增强忍者们的领导力,所有与他们工作相关的指令总是由上级发送给他的直接下属,而不允许通过其他的方式发送。现在你要招募一批忍者,并把它们派遣给顾客。你需要为每个被派遣的忍者 支付一定的薪水,同时使得支付的薪水总额不超过你的预算。另外,为了发送指令,你需要选择一名忍者作为管理者,要求这个管理者可以向所有被派遣的忍者 发送指令,在发送指令时,任何忍者(不管是否被派遣)都可以作为消息的传递 人。管理者自己可以被派遣,也可以不被派遣。当然,如果管理者没有被排遣,就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平,其中每个忍者的领导力水平也是一定的。写一个程序,给定每一个忍者 i的上级 Bi,薪水Ci,领导力L i,以及支付给忍者们的薪水总预算 M,输出在预算内满足上述要求时顾客满意度的最大值。


 

1  ≤N ≤ 100,000 忍者的个数;
1  ≤M ≤ 1,000,000,000 薪水总预算; 
 
0  ≤Bi < i  忍者的上级的编号;
1  ≤Ci ≤ M                     忍者的薪水;
1  ≤Li ≤ 1,000,000,000             忍者的领导力水平。
 
 

 

Category: BZOJ题解 | Tags:
9
15
2015
0

1455: 罗马游戏

1455: 罗马游戏

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 875  Solved: 352
[Submit][Status][Discuss]

Description

罗马皇帝很喜欢玩杀人游戏。 他的军队里面有n个人,每个人都是一个独立的团。最近举行了一次平面几何测试,每个人都得到了一个分数。 皇帝很喜欢平面几何,他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。 它可以发两种命令: 1. Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人,那么就忽略该命令。 2. Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了,这条命令就忽略。 皇帝希望他每发布一条kill命令,下面的将军就把被杀的人的分数报上来。(如果这条命令被忽略,那么就报0分)

Category: BZOJ题解 | Tags:
9
15
2015
0

2333: [SCOI2011]棘手的操作

2333: [SCOI2011]棘手的操作

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1090  Solved: 419
[Submit][Status][Discuss]

Description

N个节点,标号从1N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:

U x y: 加一条边,连接第x个节点和第y个节点

A1 x v: 将第x个节点的权值增加v

A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v

A3 v: 将所有节点的权值都增加v

F1 x: 输出第x个节点当前的权值

F2 x: 输出第x个节点所在的连通块中,权值最大的节点的权值

F3: 输出所有节点中,权值最大的节点的权值

Category: BZOJ题解 | Tags:
9
14
2015
0

2006: [NOI2010]超级钢琴

2006: [NOI2010]超级钢琴

Time Limit: 20 Sec  Memory Limit: 552 MB
Submit: 1842  Solved: 901
[Submit][Status][Discuss]

Description

小Z是一个小有名气的钢琴家,最近C博士送给了小Z一架超级钢琴,小Z希望能够用这架钢琴创作出世界上最美妙的音乐。 这架超级钢琴可以弹奏出n个音符,编号为1至n。第i个音符的美妙度为Ai,其中Ai可正可负。 一个“超级和弦”由若干个编号连续的音符组成,包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的,当且仅当这两个超级和弦所包含的音符集合是相同的。 小Z决定创作一首由k个超级和弦组成的乐曲,为了使得乐曲更加动听,小Z要求该乐曲由k个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。

 

Category: BZOJ题解 | Tags:
9
13
2015
0

1293: [SCOI2009]生日礼物

1293: [SCOI2009]生日礼物

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1426  Solved: 768
[Submit][Status][Discuss]

Description

小西有一条很长的彩带,彩带上挂着各式各样的彩珠。已知彩珠有N个,分为K种。简单的说,可以将彩带考虑为x轴,每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠,但多个彩珠也可以出现在同一个位置上。 小布生日快到了,于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮,小西希望这一段彩带中能包含所有种类的彩珠。同时,为了方便,小西希望这段彩带尽可能短,你能帮助小西计算这个最短的长度么?彩带的长度即为彩带开始位置到结束位置的位置差。

Category: BZOJ题解 | Tags:
9
13
2015
0

2096: [Poi2010]Pilots

2096: [Poi2010]Pilots

Time Limit: 30 Sec  Memory Limit: 162 MB
Submit: 438  Solved: 219
[Submit][Status][Discuss]

Description

Tz又耍畸形了!!他要当飞行员,他拿到了一个飞行员测试难度序列,他设定了一个难度差的最大值,在序列中他想找到一个最长的子串,任意两个难度差不会超过他设定的最大值。耍畸形一个人是不行的,于是他找到了你。

Category: BZOJ题解 | Tags:
9
12
2015
0

C. Lucky Subsequence

C. Lucky Subsequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 477444 are lucky and 517467 are not.

Petya has sequence a consisting of n integers.

The subsequence of the sequence a is such subsequence that can be obtained from a by removing zero or more of its elements.

Two sequences are considered different if index sets of numbers included in them are different. That is, the values ​of the elements ​do not matter in the comparison of subsequences. In particular, any sequence of length n has exactly 2n different subsequences (including an empty subsequence).

A subsequence is considered lucky if it has a length exactly k and does not contain two identical lucky numbers (unlucky numbers can be repeated any number of times).

Help Petya find the number of different lucky subsequences of the sequence a. As Petya's parents don't let him play with large numbers, you should print the result modulo prime number 1000000007 (109 + 7).

Category: codeforces | Tags:
9
11
2015
0

3236: [Ahoi2013]作业

3236: [Ahoi2013]作业

Time Limit: 100 Sec  Memory Limit: 512 MB
Submit: 903  Solved: 347
[Submit][Status][Discuss]

Description

 

Category: BZOJ题解 | Tags:
9
11
2015
0

3781: 小B的询问

3781: 小B的询问

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 288  Solved: 196
[Submit][Status][Discuss]

Description

小B有一个序列,包含N个1~K之间的整数。他一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。

 

Category: BZOJ题解 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com