标签归档:优先队列

bzoj-USACO除草计划A

我已经做了30/30


继续阅读

Codeforces Round#372 Div.2

A. Crazy Computer

ZS the Coder is coding on a crazy computer. If you don't type in a word for a c consecutive seconds, everything you typed disappear!

More formally, if you typed a word at second a and then the next word at second b, then if b - a ≤ c, just the new word is appended to other words on the screen. If b - a > c, then everything on the screen disappears and after that the word you have typed appears on the screen.

For example, if c = 5 and you typed words at seconds 1, 3, 8, 14, 19, 20 then at the second 8 there will be 3 words on the screen. After that, everything disappears at the second 13 because nothing was typed. At the seconds 14 and 19 another two words are typed, and finally, at the second 20, one more word is typed, and a total of 3 words remain on the screen.

You're given the times when ZS the Coder typed the words. Determine how many words remain on the screen after he finished typing everything.

继续阅读

[bzoj 1029][JSOI2007] 建筑抢修

Description

  小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏:经过了一场激烈的战斗,T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤,如果不尽快修复的话,这些建筑设施将会完全毁坏。现在的情况是:T部落基地里只有一个修理工人,虽然他能瞬间到达任何一个建筑,但是修复每个建筑都需要一定的时间。同时,修理工人修理完一个建筑才能修理下一个建筑,不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕,这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序,以抢修尽可能多的建筑。

继续阅读

AIO2005 Solution

Cute Numbers

For you, numbers have personalities. The number 4 is elegant, 18 is strong and 42 is enigmatic. And, of course, any number ending in 0 is cute.

The more zeroes at the end of a number, the cuter that number is. Therefore 70, 36640 and 1800090 are only a little bit cute (ending in just one zero), whereas 400 and 99200 are very cute (ending in two zeroes) and 30000 is really really cute (ending in four zeroes).

Your task is to read in a number N and determine how many zeroes are at the end of that number, so you can tell just how cute the number is.

继续阅读

AIO2011 Solution

Pirates

Yarr! Welcome aboard the Black Pearl! I'm Captain Mia Swamp, and this is my First Matey, Growlybills. We've heard you're handy with these computing contraptions, so I'll make you a deal: help us out with a little problem, and we won't feed you to the sharks.

You're in? Thought so.

\includegraphics[width=10cm]{map_meta}

See that map yonder? That long, thin island there is the Isle of Obstaclewick. Boring place. All you need to know is that it's L nautical miles long from east to west, and so thin we all just say it has zero width.

Our ship, the Black Pearl, is sailing the north coast of the island, X nautical miles from the west point. See the other ship, the one sailing the south coast, Y nautical miles from the west point? That's the HMS Smallerout, our target. It may look like a wibbly-wobbly old thing, but it's carrying some of Britain's greatest treasures.

We can sail either way around the Isle of Obstaclewick, approaching the Smallerout from either side. What we want you to do is tell us which way is shorter. We don't want to overwork the... volunteers... in the galley. So that's your job, landlubber! Write us a program that calculates the shortest distance we have to sail to reach the Smallerout!

继续阅读

[bzoj 4198][NOI2015] 荷马史诗

Description

追逐影子的人,自己就是影子。 ——荷马

Allison 最近迷上了文学。她喜欢在一个慵懒的午后,细细地品上一杯卡布奇诺,静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了,Allison 想通过一种编码方式使得它变得短一些。
一部《荷马史诗》中有 n 种不同的单词,从 1 到 n 进行编号。其中第 i 种单词出现的总次数为 wi。Allison 想要用 k 进制串 si 来替换第 i 种单词,使得其满足如下要求:
对于任意的 1≤i,j≤n,i≠j,都有:si 不是 sj 的前缀。
现在 Allison 想要知道,如何选择 si,才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下,Allison 还想知道最长的 si 的最短长度是多少?
一个字符串被称为 k 进制字符串,当且仅当它的每个字符是 0 到 k−1 之间(包括 0 和 k−1)的整数。
字符串 Str1 被称为字符串 Str2 的前缀,当且仅当:存在 1≤t≤m,使得 Str1=Str2[1..t]。其中,m 是字符串 Str2 的长度,Str2[1..t] 表示 Str2 的前 t 个字符组成的字符串。

继续阅读