TC 538 DIV II 300+500

 最近TC一路猛跌,现在光荣的在div2厮混。昨晚打了一场,全是ws题,可惜自己手速不够快,没抢到分也没cha够人。

300:
给你一个只包含LR?的序列,表示你每一步走的方向,?表示L、R都有可能,问你最远你能走多远(过程中)。

标准做法:贪心,枚举所有?为L或R。两遍扫。大略的证明,如果最远点在左边,那么过程中向右绝对没好处;反之亦然。
for i = 0 ,a = 0, i < len , i++
if s[i] = 'L' , a++
else a--
ans = max(abs(a),ans)
for i = 0 ,a = 0, i < len , i++
if s[i] = 'R' , a++
else a--
ans = max(abs(a),ans)

我的做法:由于本人经研究发现,自己贪心最弱,所以遇题从不敢写贪心,于是剪枝爆搜了一把。
O(2^(len/2))的搜索,亏着len <= 50
将原串中连续的L、R、?压缩成一个pair。LLL=pair(L,3),塞到一个vector里面。
dfs之,遇到?pair的时候分化。
由于最坏情况为L?R?L?R?......所以最坏有25个离散的?,离散的LR不影响,因为不产生分支。
所以为O(2^25)的搜索。tc服务器比较快,俨然过了。

500:
没有发现水题本质哇,就是一个猜结论题。
你一开始在(0,0),给你一个xy坐标序列,一个奇偶预测p。问你是否能找到一个走法序列使得你的步数满足这个预测。
举例:序列为(1,1),(1,0),p=1
则(0,0)-偶->(1,1)-奇->(1,0) :奇,所以存在这样的序列。

结论:
咱们画个图表示一下:上层点代表偶点,下层点代表奇点。
奇解的情况:
________
                \
                 --------------
偶解的情况:
________                       __________
                \                    /
                 --------------
将序列的每个元素自加,奇就为奇点,偶就为偶点。
因为初始点为偶点,那么序列中存在的偶点有两个选择,要么缀在这个偶点之后,要么缀在之后的某个奇点之后。
假如存在奇点,那么也有两个选择,要么缀在偶点之后,要么插入偶点之间。
如果奇缀偶后为最终结果,那么该解为奇解。
如果奇插偶中为最终结果,那么该解为偶解。
那么显然,当序列中不存在偶点一定得不到偶解;不存在奇点则一定得不到奇解。

竟然想了半个小时,泪目。

posted on 2012-03-21 10:32 BUPT-[aswmtjdsj] @ Penalty 阅读(365) 评论(0)  编辑 收藏 引用 所属分类: 乱搞


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年3月>
26272829123
45678910
11121314151617
18192021222324
25262728293031
1234567

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜