博客网 >

FZU 1336 Hacker on CET 解题报告
作者:分类:默认分类标签:

今天他们那里的比赛题,挺有意思的,我本来还想做做试试呢,上来就被一个表达式求值的题堵住了,RE N次,后来发现是一个白痴级错误,郁闷了~~不做了~~都是原创题,好像不是很容易,下面这道应该是比较简单的,就让我想了好久~~也可能是绕弯子了,还请大牛指点。

Hacker on CET
http://acm.fzu.edu.cn/problem.php?pid=1335

我的思路是,有n道题,设ans[n][0]表示符合要求的情况数,ans[n][1]表示有奇数个A或奇数个C的情况,ans[n][2]表示有奇数个A且奇数个C的情况,则递推式为:

ans[n][0] = ans[n-1][0] * 2 + ans[n-1][1]                          (1)
ans[n][1] = ans[n-1][0] * 2 + ans[n-1][1] * 2 + ans[n-1][2] * 2    (2)
ans[n][2] = ans[n-1][1] + ans[n-1][2] * 2                          (3)

但是这题n可到10^9,显然要设法找到一个闭合的形式才行。观察可以发现,ans[n][1] = ans[n][0] + ans[n][2],而ans[n][0] + ans[n][1] + ans[n][2] = 4^n 即所有可能的情况,所以有

ans[n][0] + ans[n][2] = (4 ^ n) / 2                                (4)

令(1) - (3)得 ans[n][0] - ans[n][2] = (ans[n-1][0] - ans[n-1][2]) * 2

可以看到(ans[n][0] - ans[n][2])是公比为2的等比数列,而ans[1][0] = 2 , ans[1][2] = 0

所以 ans[n][0] - ans[n][2] = 2 ^ n                                 (5)

联立(4)(5)可解得

ans[n][0] = 2^(n-1) * (2^(n-1) + 1)

因为题目只要求输出最后两位,用手算即可求出(2^(n-1) % 100)的循环(我手懒,写个程序找的,hoho~~其实只有20个数),剩下的工作用常数时间即可完成。:)

<< 流水帐@050731 / 7.27 log >>

专题推荐

不平凡的水果世界

不平凡的水果世界

平凡的水果世界,平凡中的不平凡。 今朝看水果是水果 ,看水果还是水果 ,看水果已不是水果。这境界,谁人可比?在不平凡的水果世界里,仁者见仁,智者见智。

中国春节的那些习俗

中国春节的那些习俗

正月是农历新年的开始,人们往往将它看作是新的一年年运好坏的兆示期。所以,过年的时候“禁忌”特别多。当然,各个地方的风俗习惯不一样,过年的禁忌也是不一样的。

评论
0/200
表情 验证码:

RoBa

  • 文章总数0
  • 画报总数0
  • 画报点击数0
  • 文章点击数0
个人排行
        博文分类
        日期归档