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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

省选前衡八题目汇总梳理(1030-1039)  

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

  下载LOFTER 我的照片书  |
体育中考完了才回来……囧。

1030:文本生成器:用总文章数-不可能文章数。求不可能文章数用AC自动机+DP即可。
1031:字符加密:把字符串复制一遍接在后面,然后用后缀数组对后缀排序即可。
1032:祖玛:标程方法有误,貌似数据有误,我拒绝做!
1033:杀蚂蚁:模拟题,题目描述有四页纸,我写了447行……里面略带计算几何内容。
1034:泡泡堂:类似田忌赛马的题目……首先排个序……然后贪心贪两次……就行了。
1035:Risk:计算几何题。首先所有点都和和自己相连的最左的那个点连一条有向边,然后把多边形们全部都算出来存下来。然后按包含关系排序。如果多边形A包含B,那么A放前面,如果没有包含关系就随便排。然后进行点的定位操作:对于每个点,从后往前扫,找到第一个能包含它的多边形,就是这个点所在的国家。判断两个国家是否相邻很好办,扫一下每条线段,线段左侧和右侧的国家就是相邻的。注意一点,一个多边形还和包含它的最小的多边形相邻。这道题我当时做的时候先是本地测90分,拿几何画板画了半天才意识到这个测试点错了体现出了我思路中的一些问题,于是30%的代码重写……AC……
1036:数的统计:动态树问题。(注意:动态树是一类问题,不是数据结构!)可以用link-cut-tree写,也可以用树链剖分写。link-cut-tree较好写,树链剖分果断不会,听着就复杂。
1037:生日聚会:DP问题。f[nBoy][nGril][maxBoySubGril][maxGrilSubBoy](sub是减法的意思。看我变量名就知道状态了……)
1038:瞭望塔:先半平面交,然后扫一遍取最小值。
1039:无序运动:这道题我辛辛苦苦想出来了做法,写了个暴力,root告诉我数据有误……好吧……我无语了……这题可以用KMP解。

知识点总结:
AC自动机:能处理多串匹配问题。
后缀数组:构造后缀数组有O(n)的算法但不好写,我用的O(nlogn)的倍增法构造的。实现较简单。(见许智磊的论文:《后缀数组》)
求点到直线的距离:先求垂足,然后求点到垂足的距离。
求垂足:以下是求p到直线be的垂足。
double u = ((e.x - b.x) * (e.x - p.x) + (e.y - b.y) * (e.y - p.y)) / (sqr(e.x - b.x) + sqr(e.y - b.y));
double px = u * b.x + (1 - u) * e.x, py = u * b.y + (1 - u) * e.y;
参数方程两行秒杀。(px,py)即为所求。
link-cut-tree:写个splay,写个access操作,lct就大功告成了。(可以去膜拜yangzhe的论文:《QTREE解法的一些研究》)
  评论这张
 
阅读(565)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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