aoapc

UVAOJ11198

Written by  on March 26, 2015

UVA11198 Rujia Liu的神题啊,虽然AC率有40%,但是AC的人数只有两三百个。。随便搞一搞就前150了 Orz。。。 题意就是给一个序列,只有当两个元素异号且绝对值之和是质数才可以移动到彼此的左右边,即ai可以移动到aj的左边或者右边,aj也可以移动到ai的左边或者右边,问最少移动多少次就可以使整个序列递增排列。

[Read more...]

UVAOJ10001

Written by  on March 17, 2015

UVAOJ10001 Great thanks to: 孟海 难点不在算法,在题意。 题目给一个字符串,然后求是否有一个字符串能够通过题目所给的自动机规则变换过来,如果存在,则输出REACHABLE,否则输出GARDEN OF EDEN,就是寓意始祖,即这个字符串无法通过所给的自动及变换规则变换过来。

[Read more...]

AOAPC I: Volume 3.Brute Force-Backtracking:Easy

Written by  on March 15, 2015

<<算法竞赛入门经典>> UVaoj第四卷暴力求解简单回溯习题: 10474-Where is the Marble? 之前的习题卷里面也收录了这个习题,输入N个数, 然后再输入要查找的Q个数, 依次输出Q个数中每个数在N个数中被找到的位置, 找不到就not found.

[Read more...]

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...]