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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

CTSC2011Day1题目、算法  

2011-05-03 14:04:52|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
第一题:幸福路径。
在一个有向图中,一只蚂蚁沿着图走。每走一条边,体力值乘以p;每走到一个点,它将获得这个点的权值乘以当前体力的幸福感。
问这只蚂蚁的最大幸福感。蚂蚁可以无限的走。
p<0.999999
点数小于等于100,边数1000

第二题:字符串重排
把一些字符串重新排列,要求最大化相邻两个串的lcp的长度的平方的和。输出这个和。之后输出方案。
如果有多种可能方案,给出Q个形如X必须紧接在Y后面的规则,要求能满足第1个就满足第1个,在此条件下能满足第2个就满足第2个,依次类推;
如果还有多种情况,随便输出。
串数<=40000,总长度<=200000,Q<=100000

第三题:道路监控
提交答案
选权值和尽量小的一些边,使得删去这些边之后再删K条边图中S和T就被隔开了。

算法:
第一题:
最优路径一定是沿一个链走一会儿后在一个圈里死循环。枚举这个环的起点和长度之后就简单了。
枚举的方法:计算长度为i的从j走到k的路径的最优值。
第二题:
第1问:把所有串字典序排序之后计算即可。
第2问:建立字典树,用数据结构维护每个点儿子们的顺序限制。
第三题:
有几个点网络流即可。
有几个点是近似网格状的,dp即可。
  评论这张
 
阅读(833)| 评论(4)
推荐 转载

历史上的今天

评论

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

页脚

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