UVa 1025 A Spy in the Metro

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3466

理解

其实题目还是蛮吓人的= =,因为上来就是Line1~7的输入。其实题意不难,有从左到右编号为1~n的车站,有m1辆车从第1站往右开,有m2辆车从第2站往左开。主角在t=0的时候从第1站出发,要在t时刻遇见车站n的一个间谍。要求求出最短的等待时间,没有的话就输出impossible。 小脑一动,可以知道,每一次有三个选择:等待,向左,向右。我们可以用dp[t][i]来表示第t时刻在第i个车站,然后用vis[t][i][sta]来表示三种选择。全部预处理一遍之后,dp求解最短时间即可。

Read More

Codeforces Beta Round 7 A Kalevitch and Chess

题目

源地址:

http://codeforces.com/problemset/problem/7/A

理解

同样是理解题- -。 给定一个被黑白棋子占满的棋盘,能进行的操作为将一行或者一列由黑色变白色,问最少需要多少步,能将棋盘全都变为白色。 一开始感觉应该用DFS来做,但是想了想,其实用模拟就能搞定。思路很简单,只要用两层循环,由上到下,由左到右,判断是否为B。如果是B,则有tmp++;如果不是,则继续。再然后,判断tmp是不是等于8,如果是,则进行一次行的翻转,如果不是,则列的翻转数为tmp。

Read More

CF拉练第二场

比赛地址 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=62027#overview 比赛总结 水掉A和B之后,就卡在了C和D上。C只是一个变形的最长上升子序列,却没有敲出来;D题是卡了半天,输出各种理解错,一直到还有20分钟结束的时候才过,这时候已经没有时间看E了。不过赛后了看,反正我也过不了E,23333。 分题讲解 A题(模拟) 没啥好说的,其实根本就不用判断人名是否相同。 http://xuanwo.org/2014/11/05/CF-5A/ B题(模拟,字符串) 注意理解题意,是左右摆动以保持平衡。 http://xuanwo.org/2014/11/05/CF-5B/ C题(LIS) 稍微变形一下的最长上升子序列就写不出来,说明做题太死板,不懂变通,要加强。 http://xuanwo.org/2014/11/07/CF-4D/ D题(贪心) 小心输出上的trick= =。 http://xuanwo.org/2014/11/07/CF-3B/ E题(几何) 论开脑洞的重要性,没有完善的证明。 http://xuanwo.org/2014/11/06/CF-2C/ 更新日志 2014年11月7日 完成题解。

Read More

Codeforces Beta Round 3 B Lorry

题目

源地址:

http://codeforces.com/problemset/problem/3/B

理解

读懂题略微花了一点时间,主要是生词多,有点吓人= =。有一辆卡车,要装载一些船只,有1和2两种。然后给出n个船的类型和容积,要求给定卡车体积v的情况下,装载的船的最大容积。 一开始的想法是理解成一个背包问题,但是给的v太大,用DP处理可能会超时。后来就用简单一点的思路,直接暴力贪心。把两种船分开,分别进行排序。小脑一动就能明白,最优解肯定是选取价值高的,然后枚举选择i只1船,则选择2船只的个数就是min((v - i) / 2, tc)*其中tc为2船总个数*。 输出上有一个trick,就是每个编号之间都有一个空格= =,因此WA一发。。

Read More

Codeforces Beta Round 2 C Commentator problem

题目

源地址:

http://codeforces.com/contest/2/problem/C

理解

题意很清楚,就是给定三个点,要求出一个点到这三个点的视角相同。要是存在多个这样的点,则选择那个视角最大的点。

小科普——视角 定圆O和不在O上的定点A,从A向O引两条切线,这两条切线所形成的角可以看做视角。 又因为已知O的半径r和OA的长,显然,视角的大小为2*asin(r/OA),也能够利用sin(r/OA)的值来衡量。

做法很神= =,首先找出这个三个点构成的三角形的圆心,然后计算出sin(r/OA)的值,然后分别在上下左右探测,看看哪个值更小。如此循环,直到step的值小于eps就能输出了。

Read More

UVa 11093 Just Finish it up

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2034

理解

比赛的时候没有敲出来。 当时看范神拿了一血,默默地去看题。然后觉得应该跟小白书上那个加油站的优先队列是一样的题目,敲了一会儿之后感觉不对,然后就放弃了这道题。后来想想,这两道题的区别在于,一个是环形的路线,一个是单向的路径,处理的方法应该是不一致的。比赛过后想到,其实就算是环形,也是可以处理成单向问题的。只要开一个两倍MAXN的数组,然后从起点开始截取n个数,就能将一个环从起点处截成一条直线。然后就能用类似的办法进行处理了。 具体的实现过程是这样:只要用一个数组保存可以添加的油量,然后不断减去消耗的油量,然后再不断进行求和。很显然,当a[i]>=start时,这个站点时可以通过的;当a[i]<start时,这个站点是不可通过的。然后再遍历寻找字典序最小的起点。

Read More

UVa 12627 Erratic Expansion

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4352

理解

因为有图,所以题意还是蛮清楚的。求给定时间,给定范围中气球的个数= =。 也是我心比天高太年轻,试图直接把红球个数和n关系直接撸出来,后来发现着实有点困难。不过发现每当过去一小时,这一行的红球数都会变为原来的两倍。这样问题就变得简单了起来,我只要使用一次递归分治就可以了~

Read More