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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

省选前衡八题目汇总梳理(1080-1089)  

2012-04-16 20:44:36|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1080:劣质编码:神题!绝对是神题!标准解法丢了句二维的用最短路,三维的用记忆化搜索搞得我头晕眼花不知所云。至今标准解法依然不会捉……求教……help!!!!不过我最后是用的WJMZBMR的奇葩暴力解法过的……
1081:超级格雷码:Hint写道:请不要提交此题.... 这题解法请见http://www.lydsy.com/JudgeOnline/discuss/thread.php?tid=991
1082:栅栏:这题是USACO上的原题,是道搜索,可以去NOCOW上看几种神剪枝。截止记者发稿,NOCOW仍然处于上不去的状态……
1083:繁忙的都市:这是大水题,Kruskal即可。
1084:最大子矩阵:本来以为是神犇题,结果一看数据范围:矩阵的列数<=2……囧……一秒钟变水题对不对……首先判断列数,如果是1,就是最大子序列问题……怎么做都可以……如果是2,就记f[j],表示第一列到了第i行,第二列到了第j行,方程不细说,意会吧。
1085:骑士精神:题目背景很雷,应该改名为神经的骑士才对……这题迭代加深再搞个估价函数排除一些绝对不可能的情况就可以了。
1086:王室联邦:这题真心有意思。首先以任意节点为根DFS,DFS的任务是解决以当前节点为根的子树(不包括当前节点)中的节点的归属,并汇报不知道去向何方者。具体做法是:对于每个正在处理的节点v,定义一个等待序列,扫一遍它的孩子。在扫的时候,假设当前for循环正在处理的是孩子u,DFS(u),然后把传回来的等待序列加到v的等待序列中。如果v的等待序列节点数超过了B,那么就让等待队列中的节点组成一个省,省会是v,但v不划入那个省中。最后,for循环结束,把v加入到等待序列中,return。在主函数中接收DFS的返回值,若等待序列为空,皆大欢喜;但事实上,等待序列不可能为空。那么等待序列中的节点数一定不超过B + 1,怎么办?答案就是放在上一个被划分出的省中去,那么上一个被划分出的省一定<=2B - 1,而现在最后无家可归的节点数一定<= B + 1,所以放在上一个被划分出的省中去节点数一定不超过3B!而且最后被划分出来的省一定和最后无家可归的节点中的某一个相邻!那么考虑什么时候会出现无解呢?答案就是我们找不到“上一个被划分出的省”。
1087:互不侵犯:1087果然是一道霸气的题……讲国王的……状态压缩DP的即可。
1088:扫雷:大水题。不会做请放弃省选搞NOIP去吧。
1089:严格N元树:首先推个递推式出来,然后开个高精度来算。

知识点总结:
今天没什么知识点,没什么要总结的。
  评论这张
 
阅读(1527)| 评论(5)
推荐 转载

历史上的今天

评论

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

页脚

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