算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
250pt
      给一个长度不超过50的01串S,问最少可以分割成多少个由5的幂组成的二进制数。

算法分析:
   高精预处理出5的幂的二进制数就是个沙茶动态规划了...


500pt
   有一个n*m的01矩阵,支持两种操作,操作1是选择1行将其所有的0变成1,1变成0。操作2是选择1列。
   现在整个矩阵都是0,问恰好进行R次操作1和C次操作2以后,恰好有S个1的不同操作有多少种。
   不同操作与顺序无关。至于某行/列的操作次数有关。

算法分析:
   我们先要计算出“有效操作”有多少。因为对一行操作两次和没操作没有区别...
   设有效操作1的次数是r,有效操作2的次数是c,那么一定有r*m+c*n-2*r*c == s
   r和c通过枚举求得,对哪些行/列进行有效操作可以通过组合数来求...

   无效操作相当于将b个无差别的球放到a个有差别的格子里,有
      f(a,b) = f(a-1,0) + ... + f(a-1,b)
   预处理出来就可以了...

明天放代码,pratice room 开不了题了...
posted on 2012-10-02 23:42 西月弦 阅读(227) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

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