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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

在北京的集训(7-23)  

2012-07-23 20:29:28|  分类: OI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今天是陈高远讲课啦!

第一题:SRM533 D1 hard
pikachu
用"pi"、"ka"、"chu"作为字母给一些单词编码(即,给每个单词关联一个用"pi""ka""chu"拼成的串),使得任意的字母串至多有一种解读为单词序列的方法;给定每个单词的词频,问编码串的长度最少是多少,以及编码的方案数有多大。单词数N<=40。注意:"pi","ka",“chu"在串中的长度依次是2,2,3。
例如:有两个单词要编码,词频都是1,那么最优的编码长度是4,两个单词分别可以用"pi","ka"编码,有两种方案。

很想Huffman编码,对吧?不过,这其实是一个dp题。
来自SRM533
方法:从一个树根开始“生长”字典树,每片当前的叶子可以用于编码单词,也可以长出三片新的叶子。
我们按深度考虑问题。
设f[i][j][k][l]表示编码了频率前i高的单词,目前最浅、最浅+1、最浅+2的叶子的数量是j,k,l的情况下的答案。我们考虑当前最浅的叶子都干什么去了,进行转移。
编码有些麻烦。如果你想练习,可以去TopCoder找找数据。

第二题:ARC#002 D - ボードゲーム
http://arc002.contest.atcoder.jp/tasks/arc002_4
概括题意:N*M棋盘,双方只有兵,兵只能往前走(每次一步),可以吃子。问谁能够最先派己方的兵到对方底线。

看似博弈论,实则是一个贪心。其实有点围棋的感觉。不妨做。核心思想是要开辟疆土,之后等对方送死。(看日文的题是一种挑战!)

第三题: ARC#003 D - シャッフル席替え
http://arc003.contest.atcoder.jp/tasks/arc003_4
概括题意:一个圆桌坐了N个人,人和人之间可能有无向的“关系”。进行K次随机交换(每次选两个人,交换他们的位置)。问最后的状态里有“关系”的人都不相邻的概率(精确到1e-3)。
N<=11 K<=20

其实题目意思不用读,只要看到“1e-3”这个条件即可。方法:模拟4000000次。
这题的难点是计算AC概率。不会的同学请补习数学。我计算的结果:
0.999937

今天的题,除了第一个,还是比较和谐的。
  评论这张
 
阅读(1545)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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