Codeforces Beta Round div.2 #228 A B C D E

Codeforces Beta Round #228 A B C D E

http://codeforces.com/contest/389


A. Fox and Number Game

题目地址

题意
给出一些数,你可以这样操作,取出xi>xj的两个数,让xi=xi?xj,这样重复操作,求出最后这些数的最小和。

分析
如果xi>xj,要让xi尽量小,那就减去xj直到小于xi,即xi=ximodxj
会发现这简直就是求gcd的过程。
所以最后每个数都会变成他们的最大公约数。

CODE


B. Fox and Cross

题目地址

题意
给出一张只有.和#的图,问里面的#能不能用十字型的五个#覆盖完全。不能重复覆盖。

分析
暴力搜索。

CODE


C. Fox and Box Accumulation

题目地址

题意
有n个箱子,每个箱子都有它的承受能力xi,即第i个箱子上面最多能放xi个箱子。问放箱子最少能放几堆。

分析
刚开始看成箱子的重量了,竟然wa 10,卡了好久发现题目看错了...
本来想从大到小排序,然后贪心看看当前box能不能放在某一堆里面,开了一个数组做第i堆的容纳量,结果贪心出了问题,因为放上去时的箱子可能可以在其他地方做底层,而这样会把原来该在底层的箱子都堆在某一个高堆上,而使贪心出错。
最后改了一下,把xi从小到大贪心,容纳量数组变成当前箱子数量。看当前箱子能容纳某个堆的数量。

CODE


D. Fox and Minimal path

题目地址

题意
构造一张图,使得1和2有n条最短路。

分析
这题想了好久,终于自己弄出来了....
人家考的是二分法构造图,我给整了个很奇葩的方法....
考虑这样的情况,如果1连着10个数,2连着10个数,这10个数是相互连接的,那1和2间就有10×10条最短路了。
所以,准备1×10个数作为个位数的连接网,2×10个数作为十位数连接网....只要450左右个点就能构造出9位数了。
这样1和一边的10个数连着,2只要选择n个点相连,那就是n*10^i了,然后9位数都能表示出来了。 因为要是最短路,所以路径长度必须都相同。所以个位数和2不能直接相连,所以构造下路径就行了。
由于只能处理9位数。1e9就不能用了,当然也可以改成10位数,反正我是直接又牵出来一条线了。 画了好久的图,实现了好久,终于过了,热泪盈眶TAT。

CODE


E. Fox and Card Game

题目地址

题意
ab两个人取牌,有很多堆牌,一个从前面取,一个从后面取,两个人都要尽量取多,最后两人各取了多少,a先取。

分析
由于要尽量取多,那么两个人都会尽量让对方不要取到大牌,所以每堆牌前面部分都会让a取到,后面部分都会让b取到。
需要考虑下奇数堆时,中间那张怎么取。
把奇数堆中间那张记录下来,最大的是先取的那个,接下来是后取的那个,以此类推。

CODE


Codeforces Beta Round div.2 #228 A B C D E

上一篇:UVa 152 一堆树


下一篇:leetcode JAVA Binary Tree Level Order Traversal 难度系数3 3.36