- 博客(113)
- 收藏
- 关注
RSS订阅原创 UVa 12333 - Revenge of Fibonacci （大数 + 字典树）
挺简单的一道字典树，注意计算范围， 如果序号大于等于100000就返回-1。套用的刘汝佳的大数加法。
2015-05-08 15:46:00
770
原创 UVa 12563 - Jin Ge Jin Qu hao（01背包）
比较简单的01背包问题。输入的n最大为50， 而且n + 1首歌长度大于t，即t最大为 50 * 3 * 60 + 678。接下来就可以DP了。
2015-05-02 17:24:28
444
原创 UVa 11400 - Lighting System Design（DP）
为了使所用费用最少， 那么最优的选择是直选一种，这样只需要一种电源的钱。
2015-05-02 17:14:57
379
原创 UVa 1347 - Tour（DP）
求从左上点出发到右下点，再回到左上点的最短路径， 每个点只能走一次。这个问题可以抽象成两个人从左上走到右下，求最短路径。设d[i][j] 为 第一个人走到i, 第二个人都到j的最短路径。那么为了避免两个人走同一个点， 可以让i走i + 1， 或者 j 走到 i + 1。为保证每一次第一个人都在第二个人前面，d[i][j] = min{d[i + 1][j], d[i + 1][i]}.
2015-05-02 17:09:45
362
原创 UVa 10129 - Play on Words（欧拉道路）
给出n个单词， 是否可以把所有单词排成一个首尾相连的排序。典型的欧拉道路的题， 把字母当成结点，然后判断是否为欧拉道路。欧拉道路存在的两个条件：1.最多只能有两个结点的入度不等于出度，两点有一点的入度 - 出度 = 1，此为起点， 另一点出度 - 入度 = 1， 此为终点。另外就是每个点的入度等于出度。2.忽略方向得到的地图连通。
2015-05-02 16:53:13
367
原创 UVa 437 - The Tower of Babylon（DP）
给出n种长方体， 每种可以取多个， 每个长方体只能放在顶面长宽严格小于它的长方体上， 求出最高能放多高。一道DAG。设出dp[id][k]， 表示第id个长方体第k条边做高时的状态。
2015-04-16 15:49:44
338
原创 UVa 1025 - A Spy in the Metro（DP）
第一次写DP， 好激动啊。 这道题看了好几天了， 终于看懂了， 没看书把它写了出来。
2015-03-31 22:39:17
320
原创 UVa 208 - Firetruck（剪枝）
刚做的时候不懂事， TLE好几次， 就放下了。刚才突然有了灵感， 用set保存下能到目标点的路径， 然后判断就可以。
2015-03-26 17:44:38
366
原创 UVa 10868 - Bungee Jumping
物理题- -， 求速度与位移的关系。dv / dx = (dv / dt) / (dx / dt) = a / v = k * x / vv * dv = k * x * dx积分就能得出公式。
2015-03-25 00:00:02
500
原创 UVa 12716 - GCD XOR
打表出几个数据后会发现如果 a ^ b == gcd(a, b) == c， 那么 b == a - c。类似筛法选素数， 求出所有符合条件的c即可。这道题要打表，不然会TLE。
2015-03-24 23:53:42
304
原创 UVa 12412 - A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)
写一个简单的管理系统， 我WA在了要删除的有重名， 而且重名的挨着， 会删不掉- -
2015-03-24 23:48:22
336
原创 UVa 12325 - Zombie's Treasure Chest
两种枚举， 当N / S1比较大的时候枚举S1个数， 反之枚举S2个数。如果都不大， 那么S2个S1和S1个S2的体积一样， 如果S2 * V1 > S1 * V2， 则枚举S2的个数， S2最多能取到S1 - 1个， 否则就和S2个S1的体积一样大了。
2015-03-24 23:46:12
364
原创 UVa 11971 - Polygon（概率）
把木条抽象成一个圆， 那么在圆上选取一点， 过圆心平分圆， 如果剩下的n个点在圆的同一侧， 则不能构成矩形， 跟N无关。不能构成矩形的概率p = 1 / 2 ^ n， 起始点共有k + 1种， 所以能构成矩形的概率为1 - p * (k + 1)。
2015-03-24 23:42:29
401
原创 UVa 11346 - Probability
根据对称性， 求出第一象限的概率就可以了。令x * y = S， 则y = S / x。即 x * y > S的点在y = S / x上。概率为线上的面积 / (a * b)。然后用积分求出下半部分面积。
2015-03-24 18:21:51
365
原创 UVa 11105 - Semi-prime H-numbers
题意是：形如 4 * n + 1的数称为H数， H素数就是不能写成两个不为1的H数的乘积， H半素数是两个不为1的H素数的乘积。H数和H素数类似于自然数和自然数的素数， 对H数用筛法把H素数筛出来， 然后再把H半素数求出来， 打表即可。
2015-03-24 18:21:10
413
原创 UVa 11040 - Add bricks in the wall
设第三层的数为x， 则第三层已知的两个数相加再加上2 * x就等于第一层的数。以此类推。
2015-03-24 18:10:01
269
原创 UVa 10820 - Send a Table（欧拉函数）
找出1 - n 中所有与n互质的个数。根据欧拉函数phi(n) = n * (1 - 1 / p1) * (1 - 1 / p2)...(1 - 1 / pn)， 其中px为n的所有质因数。
2015-03-24 12:54:57
301
原创 UVa 10622 - Perfect P-th Powers
给出一个数x，找出2 - x中一个数b， 使得x = b ^ p中p最大。枚举2 - sqrt(x)， 如果x小于零则要判断p是不是奇数， 如果x是偶数只需要枚举2， 4， 6， 8...； 如果是奇数则枚举3， 5， 7， 9...。
2015-03-24 12:51:00
251
原创 UVa 1647 - Computer Transformation（大数）
一道找规律的题， 奇数个为上一个数乘2加1， 而偶数个是减一， 套个大叔模板就行了。
2015-03-23 00:11:24
384
原创 UVa 1636 - Headshot（概率）
第一枪没子弹， 那么只可能是00或 01 。 统计0的总数， 然后再统计00的总数， 就是再打一枪的概率。
2015-03-19 13:26:10
491
1
原创 UVa 1210 - Sum of Consecutive Prime Numbers
很简单的一道题。因为是连续的， 所以直接按顺序把每个素数加起来， 如果和大于或等于要求的数， 那就删掉第一个。
2015-03-19 13:23:21
322
原创 UVa 814 - The Letter Carrier's Rounds（模拟）
模拟邮件的发送，把每一个地址保存下来， 然后在搜索能否找到匹配的地址。
2015-03-19 13:17:37
1921
3
原创 UVa 508 - Morse Mismatches
把每个莫斯密码存下来然后一一对应就可以了。紫书上描述有问题。 第一：如果有多个精确匹配的， 要输出字典序最小的， 这里因为他给的序列就是按字典序排好的， 所以输出第一个精确匹配的； 第二： 只要是模糊匹配， 都要输出“？”。
2015-03-13 17:57:56
404
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人