Codeforces Round #274 (Div.1)

VictorWonder posted @ 2014年10月29日 19:33 in Codeforces with tags 解题报告 , 1036 阅读
难得的下午场,肯定是要参加的了,在Claris大神的帮助下,最后竟然AC了四道题目,变成了紫名(感觉下一次要狂掉rating了)。
 
Problem 2A
考试的时候一看题意,直接枚举所有情况,复制粘贴再修修改改,感觉很顺手。
 
Problem 2B
一共只需要操作1000次,所以直接枚举每一次操作好了,每次操作找到最大和最小的山峰,然后一个加一,一个减一,很明显,最后肯定不存在山峰减了之后又加回来。
 
Problem 1A
开始时脑抽了,以为会有没有答案的情况。将所有考试按照时间顺序排序,然后判断一下考完第i门之后是第几天。
 
Problem 1B
这道题卡了我很久,主要是分类讨论太过于恶心,最后也果然是fst了,其实只要将各种情况都考虑到就行了。
主要有这么几种情况:
(1)能够直接找到x和y,那么输出0
(2)能够找到x或y中的一个,那么输出1
(3)能够找到x+y或者y-x,那么输出1
(4)什么都找不到就输出2
 
Problem 1C
DP题,在最后的两分钟终于做出来了,竟然没有fst,各种感动啊TAT。
f[i]表示目前在第i层,且从最开始一直到现在走到第i层一共有多少种走法,然后用前缀和以及滚动数组搞一下就行了。
 
Problem 1D
还是DP题,对于每一件物品,放在它上面的东西肯定是要被拿走的(否则就是没有意义的),所以我们只需要依次考虑有哪些物品需要放在第i个物品上就行了。
dp[i][S]表示最上面放置第i个物品且还有S的重量可以承受所获得的最大价值。
 
Problem 1E
我用的是离线的做法,先将所有的点加入到矩阵里面,再求出一个最大子正方形,然后删除每一个点,每次删除之后都更新一下最大子正方形的大小。
对于每个点我们都要维护其往左走遇到的第一个X和往右走遇到的第一个X,将点(x,y)拿走之后,对于1~n行第y个位置都更新往左和往右能到达的最大位置,接着再从1~x行判断从该行开始能否形成新的更大的子正方形。
据说还有一些神奇的做法,不过像我这么懒的人,还是挑种简单的做法好了。
 
 
 
代码:

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter