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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

省选前衡八题目汇总梳理(1050-1059)  

2012-04-13 21:10:00|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1050:旅行:题目很短,自己去看吧。把边排个序,然后枚举最小边,然后从小到大依次添边,若S和T连通了,就用当前边的权值除以最小边权值更新答案。
1051:受欢迎的牛:题目很短,自己去看吧。为了说话方便,我们称被所有牛欢迎的牛为神牛……考虑只有一只神牛的情况,那么神牛一定是处于树的根部。若有多只神牛,那么神牛一定是被神牛欢迎的,所以神牛们是一定是处于一个强连通分量中的。那么用Tarjan求强连通分量再判断即可。
1052:“覆盖问题:给你N个点,要求用3个L*L的正交正方形将其全部覆盖住,求L的最小值”。二分答案+枚举第一个正方形的位置+枚举第二个正方形的位置+判断剩下的点是否能被最后一个正方形完全覆盖即可。注意,若用一个最小的正交矩形将所有点框住,那么所枚举的正方形一定要至少与矩形共用的其中一个角
1053:反素数:“对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足:g(x)>g(i) 0<i<x,则称x为反质数。例如,整数1,2,4,6等都是反质数。现在给定一个数N,你能求出不超过N的最大的反质数么?”其实就是要求不超过N的约数个数最多的数。所有1...N的数字都能通过A=p1^a1*p2^a2...pk^ak 的方式,表示它的约数个数为 (a1+1)*(a2+1)*...*(ak+1)。约数个数最多的数a肯定满足a1>a2>a3>...>ak,不然的话必可找到ai<ai+1,交换这两个的值后使得数a的约数个数不变,a变小。有了这个结论,接下来就搜索就行了。
1054:移动玩具:题目过于水了,太简单以至于完全可以忽视此题了。如果不会请回去上NOIP基础课。
1055:玩具取名:题目意思我说不清楚,自己去看吧。这题是区间DP。
1056:排名系统:题目意思我说不清楚,自己去看吧。这题我写的trie+splay,用时排名垫底了……
1057:棋盘制作:“给你一张黑白随机染色了的纸,要你做一张最大的矩形和正方形的国际象棋棋盘。”记下每个格子向上一黑一白地走,最多能走几格,然后记个向左延伸向右延伸的最大宽度,随便扫扫……呃,这题算法不是我不想说清,是我语文太差说不清楚啊囧。
1058:报表统计:题目意思我说不清楚,自己去看吧。逆向思维。把命令全部读入然后倒着处理。这样子min_gap和min_sort_gap均用堆给秒了。
1059:矩阵游戏:“给你一张黑白随机染色了的正方形方格纸,每次可以交换其中两行或两列,问是否可以在主对角线上形成黑色的一条。”这道题我自己YY了很久没出来,然后看了题解豁然开朗。强烈建议大家自己先想想,先别看题解,这题的模型转化挺有意思。(一眼看出解法的大牛勿鄙视)题解用白色写在下面了:
二分图匹配。如果你认真想了会觉得很orz的。

知识点总结:
求强连通分量:既可以用tarjan也可以用自带拓扑序的kosaraju。
二分图匹配:匈牙利算法(O(E))即可。

今天的知识点总结出来的好少……
  评论这张
 
阅读(614)| 评论(3)
推荐 转载

历史上的今天

评论

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

页脚

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