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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

NOI2011Day2题目大意及算法  

2011-08-10 17:29:57|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
第一题:
给一个带权值的树,每个边的费用是它的权值乘以它两边的两个子树的大小的差的绝对值。求费用和。
N<=10^6
算法:
这题不会做可以买车票回北京了。

第二题:
有N个活动要在两个会场举办。每个活动有起始、终止时间。同一时刻不能让两个会场都举办活动。你挑出一些活动让他们举办,使得举办活动少的那个会场举办的活动最多。并且,你还要回答,for i=1 to n,如果活动i不能不举办,那么举办活动少的会场举办活动最多是多少。
N<=200
算法:dp
f[i][j][k]表示到了时间i,从j到i这段时间的活动是在一个会场举办的,第一个会场举办了k个活动时第二个会场能够举办的最多活动。
g[i][j]表示从时间i往后,第一个会场举办了j个活动的情况下第二个会场举办的最大值。
不难想该怎么算。
O(N^3)

第三题:
一个N*M的棋盘有黑、白子和一个空格。Alice可以把空格相邻的一个黑子移入空格。Bob可以把空格相邻的一个白子移入空格。轮流移动,不能移动的输。给一个A和B的棋谱,问A哪些步把本来必胜的棋局弄成了必败。
算法:
先想明白为什么空格不可能移动一圈之后移动回来。
之后用二分图匹配的思路搞。

人大附中出了两个金牌:)
  评论这张
 
阅读(1777)| 评论(6)
推荐 转载

历史上的今天

评论

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

页脚

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