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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[待更新][7-13 机考]PPCA2017第一次机考题解  

2017-07-18 15:16:45|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
太懒不想说题意
直接贴车哥oj
http://112.74.109.55/KitJudge/

非传统题
1.暴力通解
做最小生成树,然后在树上随便做dfs,当所有点都遍历过了之后直接结束
2.对于n<=20的点直接状压dp
3.对于完全图,每个点对自己的边按边权排序,然后不走重复点地随意dfs出一条路径
4.类似1,找出最小生成树的直径,这条路只走一遍,其它部分当成链上子树,在走的过程中dfs掉

传统题
1.高精度加法,(数据居然只有正数……)
2.dp
O(n^3):
f[i][j]表示当前括号匹配栈里有i个")", j个"("的概率
O(n^2):
f[i][j]表示已经放了i个括号,匹配栈里"("的答案(期望),然后再算一个g[i][j]表示概率,就可以随便转移了

  评论这张
 
阅读(14)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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