注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM 582 & SRM 583  

2013-06-21 15:18:22|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
好久没有想题导致的智商下降——
充分证明了法法塔是个,b
题解什么的。。。其实不想说啊。。好不容易将题目搞完。。

好啦好啦,感谢vfk的帮助,没有神犇的教导我也不可能做出来的。。
=====================582======================
A题亦如既往。。

B题:
1到n的数,每个数都有个颜色。。对于排列p,如果i<j 且 pi>pj,那么我们无法看到pj的。
求看到的颜色变化为L-1次的排列个数。
题解:
法法塔太,了,这题想了好久好久。。。
我们从小到大确定看到的是哪个数
记f[i][j],表示前i个数,已经有了j次颜色变化的排列个数
枚举上一个看到的数是p
f[i][j]=f[p][?]* A(n-p-1,i-p-1)
因为。。放了p个数之后,i肯定放在剩下的第一个空格。。而p到i的数则在剩下的空格任意选择。。
前缀和优化一下。。

C题:
题意:
一个数n被称为半完美数当且仅当存在a、b、c三个整数使得b > 1, 1 <= c < a, n = c * a ^ b。
给你L,R,求区间[L, R]中半完美数的个数。

1 <= L <= R <= 8 * 10 ^ 16
题解:
其实本题的关键就是注意到b只能为2或者3!
接下来看vfk的题解
所以我只是搬运工。。
不过我的做法和vfk似乎在细节上有所不同。。。
下面是我的推导(参考上面的链接
SRM 582  SRM 583 - hzaskywalker - Yavin(某沙茶的代码库)
 =============================================================
583的A,B两题都是sb题。。没啥可说的。。
C题很厉害:
题意是给定一个n*m的矩形,你每次随机一个格子染色(每个格子有个概率),直到每行每列都至少有个格子染色为止。。
求期望的染色的步数。
n,m<=20,n*m<=150
题解:
差不多我们想想——状态就是有哪些行和列上有元素了。。
接下来就想办法计算呗。。
状态可以枚举行和列的较小的一个。。
这样的话就只和行有关。。
我们计算出到达这个状态的期望。。也就是前很多次无论选都只能在这里面选择的选法个数——我们可以枚举是选择了几次。。然后只能在这里面选的概率,用公式搞搞。。容斥掉,得到必须在这里选,而且全部选的概率
接下来,就是计算这个东西移动到别的地方的步数。。也就是选出去的概率,方程搞搞就行了。。
如果有错别怪我。。我看Petr的代码看懂的。。
以后有时间再看看
  评论这张
 
阅读(336)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017