【cf335X】MemSQL start[c]up Round 2 – online version

2015年6月23日1,6891

A. Banana

枚举sheet数,找到第一个不能用已有sticker凑出的

B. Palindrome

f(i,j)表示末尾在i之前,长度为j的回文序列的最大头位置

C. More Reclamation

用(len,x,y)表示一个游戏状态,2*len的完整格子,左端的状态为x,右端的状态为y

x,y = 0/1/2 分别表示(完整),(左侧/右侧第一行第一格不可删),(左侧/右侧第二行第一格不可删)

边界情况:

len=0时sg值为0

len=1时sg(1,2,1)=sg(1,1,2)=0

其余sg(1,x,y)=1

枚举删除一个中间格子+记忆化搜索求sg值

把初始状态分成若干个子游戏,将它们的sg值异或起来,结果为0先手必败,否则先手必胜

D. Rectangles and Square

给出的矩形不重合是此题的关键

预处理s(i,j)表示(1,1)(i,j)这个矩形范围内被覆盖的格子数

l(i,j)表示(i,1)(i,j)这一列被矩形左边界覆盖的格子数

r(i,j) u(i,j) d(i,j)同理

枚举矩形左下角作为正方形顶点,枚举正方形边长,用以上这些信息判断是否合法

E. Counting Skyscrapers

题解说的很清楚

戳这里有中文题解/题面,orz wmd

http://blog.csdn.net/wmdcstdio/article/details/44646631

F. Buy One, Get One Free

神题

问题转换为求最大收益

从大到小dp到一个价格为A的商品时

1.A跟之前未配对的商品配对,收益为A

2.拆开之前一个收益为P的配对(x,y),使之与两个A配对(x,A)(y,A),收益为2A-P

这样的意义是,如果我需要一个比较优的配对,从堆中取出(x,y),需要两个从堆中取出(x,A)(y,A)

显然我们一定优先拆收益最小的配对,所以用一个小根堆维护

若P<A,则P是不优的,所以删除它,往堆中放两个A

这样的意义是,如果我需要一个比较优的配对,从堆中取出(x,A),需要两个从堆中取出(x,A)(y,A)

复杂度nlogn

 

  • zld37949552015年6月23日 上午9:56 回复

    黄学长虐题无数!太神啦!

    #1