acm

UVAOJ208

Written by  on March 15, 2015

UVAOJ208 这题隐藏的真深啊,看起来这么单纯可爱的一道DFS我居然TLE了两次。。。 我果然还是太naive了。。。 总而言之,虽然数据范围很小,但是依旧需要剪枝,在DFS之前首先要预处理一下,排除掉无法抵达终点的点,只用从终点开始反过来DFS遍历即可。

[Read more...]

AOAPC I: Volume 3.Brute Force-Elementary Skills

Written by  on March 15, 2015

<<算法竞赛入门经典>> UVaoj第四卷暴力求解基础技巧习题: 10167-Birthday Cake 横竖只有[-500,500],直接实力暴力即可,另外目测测试数据没有那么大,直接[-100,100]也会给过。。。

[Read more...]

UVAOJ165

Written by  on March 10, 2015

UVAOJ165 165 – Stamps Time limit: 3.000 seconds  Stamps  The government of Nova Mareterrania requires that various legal documents have stamps attached to them so that the government can derive revenue from them. In terms of recent legislation, each class of document is limited in the number of stamps that may be attached to it. The government wishes to know how many different stamps, and of what values, they need to print to allow the widest choice of values to be made up under these conditions. Stamps are always valued in units of $1.

[Read more...]

UVAOJ10012

Written by  on March 6, 2015

UVAOJ10012 题意其实就是是把一堆圆球放在一个箱子里,因为箱子的最小高度是固定的(即最大的圆的直径),所以题目要求最小的箱子宽是多少,注意球必须同时接触地面,即不能层叠起来,这里一开始很自然地想到了直接全排列暴力(因为球最多只有8个),但是下图的这种情况很容易被忽略,这也是这个题目的AC率如此之低的原因:

[Read more...]

UVAOJ301

Written by  on March 4, 2015

UVAOJ301   301 – Transportation Time limit: 3.000 seconds  Transportation  Ruratania is just entering capitalism and is establishing new enterprising activities in many fields including transport. The transportation company TransRuratania is starting a new express train from city A to city B with several stops in the stations on the way. The stations are successively numbered, city A station has number 0, city B station number m. The company runs an experiment in order to improve passenger transportation capacity and thus to increase its earnings. The train has a maximum capacity n passengers. The price of the train ticket is equal to the number of stops (stations) between the starting station and the destination station (including the destination station). Before the train starts its route from the city A, ticket orders are collected from all onroute stations. The ticket order from the station S means all reservations of tickets from S to a fixed destination station. In case the company cannot accept all orders because of the passenger capacity limitations, its rejection policy is that it either completely accept or completely reject single orders from single stations.

[Read more...]

UVAOJ131

Written by  on February 24, 2015

UVAOJ131 131 – The Psychic Poker Player Time limit: 3.000 seconds  The Psychic Poker Player  In 5-card draw poker, a player is dealt a hand of five cards (which may be looked at). The player may then discard between zero and five of his or her cards and have them replaced by the same number of cards from the top of the deck (which is face down). The object is to maximize the value of the final hand. The different values of hands in poker are given at the end of this problem.

[Read more...]

UVAOJ11205

Written by  on February 24, 2015

UVAOJ11025 题意就是求最少只用几个LED灯就可以区分给出的所有的LED,这里关键就是用到状态压缩和与运算。 比如LED灯一开始是:

[Read more...]

AOAPC I: Volume 2.Data Structures-Graphs

Written by  on February 21, 2015

<<算法竞赛入门经典>> UVaoj第三卷数据结构图习题: 572-Oil Deposits 纯DFS水题,碰见一个pocket来一波DFS即可。 657-The die is cast

[Read more...]

UVAOJ196

Written by  on February 21, 2015

UVAOJ196 196 – Spreadsheet Time limit: 3.000 seconds    Spreadsheet  In 1979, Dan Bricklin and Bob Frankston wrote VisiCalc, the first spreadsheet application. It became a huge success and, at that time, was the killer application for the Apple II computers. Today, spreadsheets are found on most desktop computers.

[Read more...]

UVAOJ10596

Written by  on February 19, 2015

UVAOJ10596 真是跪了。。。明明书上是先讲拓扑后讲欧拉的。。。却先搞这么大一串欧拉的题目,搞得我每次读题都会先各种先发制人想是不是拓扑,完了每次最后发现是欧拉也是醉了。。。

[Read more...]