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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

BJOI2012 Day3(30%)  

2012-05-27 14:55:59|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
应大家要求,我先把北京集训的题目贴出来。至于数据,我正在慢慢联系,看出题人是否同意公布。
http://115.com/file/e7jf38x9#bjoi-all.zip

今天的题目很和谐。

题目是否让贴出来我正在联系。可以先概括一下题意。

第一题:tree
一个无向图,每个边有两种权值(都是正的),
求一个生成树,使得他的两种权值的和的乘积最小。
N<=300 M<=10000

第二题:chess
若干个饼干,每次可以把一个饼干啃一口(之后分成两块)。啃的第i口的得分为啃的长度乘以2^i。两人轮流啃。
先啃的那个人的第一口不算分。问先啃者是否必胜。
数据范围:很和谐。

第三题:color
N*M的棋盘放若干个颜色的车(每种颜色的车有数量要求),不同颜色的车不能互相攻击,问方法数。
N,M<=30

说说分数:
300 范浩强
290
280 薛钟行
270
260
250
240 罗剑桥
230
220 chenruilin
210
200 sinian
190
180
170
160
150
140
130
120 mengtao
......
......

说说算法?
第一题:哎!国家冬令营原题啊!
方法:对每个生成树,把他的两个权值和视作平面上的点。那么最优的生成树一定在凸包上。把凸包求出来即可。
凸包怎么求?我们先求出x、y分别最小的两个点p1、p2。
之后,连接p1、p2,用类似最优比率生成树的方法,计算距离直线p1p2最远的点p3。p3一定在凸包上。
之后,递归的构建p1p3、p3p2之间的点。
复杂度?不要在意了。

第二题:经典博弈
如果把问题变成放最后一个棋子的人赢,那么就是经典的SG函数的应用了。
而实际上,这题和那题没有区别!
唯一的特例:一堆石子的时候要特判。
为什么?你可以数学归纳一下。或者,你也可以枚举数据(我考试的时候就是这么干的),之后实践检验真理。

第三题:经典dp
我还用说吗?原题啊!
对每种颜色的棋子,计算恰好占据a行、b列的方法数(容斥原理)。
对于多种颜色,背包。

我的代码:
  评论这张
 
阅读(1828)| 评论(9)
推荐 转载

历史上的今天

评论

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

页脚

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