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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

在北京的集训(7-19)  

2012-07-19 15:32:30|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

今天是做绍兴一中的三个练习题

 

第一题:

给一个无向图,求两个点之间最短路的个数(如果两个点之间的距离超过2,就输出“太长”)

N,M都是1e5范围的数。

其实只用处理距离是2的情况即可。

很简单,用大-小分治即可。

大度数的点和大度数的点之间的结果暴力算,打一个表。

小度数的点和小度数的点之间暴力算。

大度数和小度数之间:枚举小度数点的邻居,在大度数点的邻居们中查找。

 

第二题:

一副牌,四个花色,点数从1~正无穷。从中选不超过K张,他们点数和是n,求选法的种数。

K<=10

n<=1e9

先写一种搞笑的dp:

dp[i][j]=和是i,j个牌的方法数。

转移:考虑有几个1

dp[i][j]=dp[i-j][i]+dp[i-j][j-1]*4+dp[i-j][j-2]*6+dp[i-j][j-3]*4+dp[i-j][j-4]

写出这个奇葩的递推方程后,可以用矩阵搞了。

 

第三题:

A[0..n-1],把这n个数分成3组,使得每组的和的极差最小。

n<=20

方法:meet in the middle

搜索前10个,把后10个数能够得到的结果造表,用数据结构组织起来,每搜索出一个结果就在数据结构里查找最佳的。

想办法做到n*sqrt(3^n)

  评论这张
 
阅读(1840)| 评论(10)
推荐 转载

历史上的今天

评论

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

页脚

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