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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

省选前衡八题目汇总梳理(1020-1029)  

2012-04-10 20:39:27|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1020:安全的航线:计算几何题。二分答案然后判定。这题我对着数据调的,调了很长时间。注意各种细节就可以了。
1021:循环的债务:这题是DP。我的记忆化搜索。从此题我学到了……DFS里面的变量能不声明就不声明,参数能不传就不传……我DFS中少传了一个参数,快了300ms。
1022:小约翰的游戏:博弈论的题,经典的Nim游戏的修改版(Anti-Nim),用SG函数秒掉。
1023:仙人掌图:记得我写这题时,是NOIP第一试的晚上。利用时间戳、low数组做,碰到环就用队列维护一下。
1024:生日快乐:看到这道题,我感动死了——终于碰到水题了……dfs之。
1025:游戏:就是要求一坨数,和为N,其最小公倍数值共有多少种?DP之。
1026:windy数:数位统计即可。
1027:合金:把材料的成分抽象成平面上的点,把锡忽略掉。然后如果两个原材料连一条线,所有需求材料都在左边连一条正的有向边,都在右边连一条反的有向边,都在线上连双向边,要是点是混乱分布的就什么边也不连。然后,就是用Floyd求最小环。数形结合还带个图论的好题。
1028:麻将:判断再来什么牌可以胡的题……囧……其实很简单……枚举解再判断是否可行即可。
1029:建筑抢修:我总觉得贪心题很难想,比如说这题。先按T2排序(orz!我绝对想不到),然后利用类似LIS的思想维护长度为K的序列的最小结束时间。(orz!我更想不到了。)点下面链接膜拜AekdyCoin:

知识点总结:
判断多边形的顶点是否是逆时针给出:我只想到了一个囧方法:用叉积求一遍有向面积,如果为正就是逆时针的,不然是顺时针的。
判断两条线段是否相交:首先用矩形快速判断,然后使用四次叉积。
判断一个点是否在多边形内:引一条平行于x轴的射线,求与多边形的交点个数。如果和一个线段的交点在端点上,那么如果是y值最大的端点那个就算相交,不然忽略。如果交点数个数是2的倍数则不在多边形内部,反之,在。
SG函数、Nim游戏、Anti-Nim游戏:博弈论内容,我一下子说不清楚,建议了解一下。关于博弈论貌似没什么好的介绍,我是七拼八凑到处看才略懂的。
使用dfn和low:通常我们用它们来求割点、割边、强连通分量,它们的用处很大。
数位统计:可以解决这样的问题:从1到a这么多个数中,满足某个条件的数有多少个。这个条件必须是和数的值无关,跟每一位上是什么数有关。
Floyd最小环:如果说环上可以出现多个重复的点的话,一开始置f = 0,然后Floyd一遍,然后求f的最小值即可。如果那不算环的话,并且图是有向图,就在Floyd同时求出最小环。
代码:
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        f[j] = a[j];
res = INT_MAX;
for (int k = 1; k <= n; k++)
{
    for (int i = 1; i < k; i++)
        for (int j = i + 1; j < k; j++)
            res = min(res, a[j] + f[k] + a[k][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            f[j] = min(f[j], f[k] + f[k][j]);
}
//QQ空间坑爹吃TAB和空格

    这次写题解有点吃力……都不太记得怎么做的了囧。
  评论这张
 
阅读(553)| 评论(1)
推荐 转载

历史上的今天

评论

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

页脚

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