算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
剩下两题陆续补上。。。
A.
找出小于等于n的三个数使他们的最小公倍数最大。

算法分析:
   如果n是奇数,结果是n*(n-1)*(n-2)。
   如果n是偶数,结果可能是(n-1)*(n-2)*(n-3) 或
   lcm n,n-1,n-2
   lcm n,n-1,n-3
   lcm n,n-1,n-4
   四种结果。。。。
http://codeforces.ru/contest/235/submission/2398536

B.
给一个01序列A,定以sum(A) = 所有连续的0的长度平方和。
序列的每个位置i,为1的概率是Pi。
问sum(A)的期望是多少?

算法分析:
   首先要求末尾是0的连续长度的期望L
   L(i) = Pi * (L(i-1) + 1)
   那么SUM的期望就是
   SUM(i) = SUM(i-1)*(1-Pi) + (SUM(i-1)+2*L+1)*Pi
http://codeforces.ru/contest/235/submission/2399734

C.
给一个文本串S。10^5个模式串。模式串总长度不超过10^6。
求每个模式串,的原串或者,旋转若干次后的到的串在文本串中出现了多少次。

算法分析:
   构造文本串的SAM即可。。。在匹配的过程中,维护已经匹配的最大长度。

http://codeforces.ru/contest/235/submission/2419799


剩下的题以后补上。
posted on 2012-10-24 14:13 西月弦 阅读(465) 评论(2)  编辑 收藏 引用 所属分类: 解题报告codeforces

FeedBack:
# re: codeforces #146 div1
2012-10-24 16:20 | Rookie
这位大牛,B题能再说详细一点吗?  回复  更多评论
  
# re: codeforces #146 div1
2012-10-28 11:43 | 西月弦
@Rookie
首先是求包含末尾那一个的联通分量 i 的长度期望 L(i)

显然 L(i) = P(0) * 0 + P(1) * (L(i-1) + 1)

重点是求SUM值。。。

根据定义 SUM = p0 * 0 + p1 * 1 + p4 * 4 + ... +p(l^2) * l^2 +.....
对于每个 pl^2 * l^2 如果第i位是 1 那么l^2 就增长了 L^2 + 1,pl^2变成了pl^2 * P(1),反之则是 p(l^2) * P(0) * l^2。

所以SUM(i) = P(0) * SUM(i-1) + P(1) * (SUM(i-1) + L*2 + 1)  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理