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

UVa 1471 Defense Lines

题目

源地址:

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

理解

不理会逗比的国王们= =,题意很清楚,给定一个序列,要求删除一段连续的序列之后,剩下的连续递增序列最长,要求输出满足题意的序列的长度。 在初始化的时候,就可以设数组l[MAXN],r[MAXN]来分别保存从左起和从右起的最长递增序列的长度。然后用STL内置的二分来寻找链接的地方,lower_bound(Min + 1, Min + 1 + n, a[i]),返回在数组Min[1~n+1]中比a[i]大的第一个数的位置。在for循环中不断更新ans的值,使得最后的结果一定最长的序列。

Read More

UVa 11572 Unique Snowflakes

题目

源地址:

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

理解

题意是酱紫的:给定一组数,叫你求出不含有重复数字的最长子序列的长度。 使用数组pos[x]记录数字x第一次出现的位置,初始化为-1。枚举这个数列,依次记录每一个数的位置。然后用start标记当前这个子序列的起点。显然的,当枚举到i的时候,如果有pos[arr[i]]<start,说明这个数肯定在[start, i-1]之间出现过。此时就停止本次枚举,要是pos[arr[i]]>start,则长度+1,并且进行下一次枚举。直到结束,最后的长度一定是最长的子序列。

Read More

UVa 1152 4 Values whose Sum is 0

题目

源地址:

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

理解

题意非常清楚,就是在一个矩阵里面找出四个数,使得他们的和为零。 一开始的想法是DFS,把这个看成一个四层的图,不停搜索就行了。但是DFS写得太搓了,各种姿势挂,后来决定二分暴力乱搞。 思路是这样,把这个矩阵分成左右两份,然后只要一个两层的for循环,就能用两个数组保存下所有可能出现的数字组合的和。有一个小小的技巧是,第二份在保存的时候保存为他们的负数,这样在后面的二分中,只要判断是不是相等就可以了,减少了计算量。 最后感慨一下,一千六百万的数组也能开的出来= =。

Read More