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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

POI17 stage3 补充(lamp)  

2013-03-11 11:24:15|  分类: POI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
cheat过了这道题。。。
主要是实在不想修改线段树了——常数太渣了,真心想膜拜一下主席的线段树写法。。。
而且有些优化也不想加,全部都是最朴素的写法
唉,人太懒了,所以常数挂了之后就立刻就加了错误剪枝。。。也就是枚举光线反射次数只枚举到512。。。
算了,不想搞了,实在是筋疲力尽了。
题意:两面墙,两个互相对着,相隔10m,每面墙上有若干镜子(镜子数<=600,每面墙是个直角坐标系,镜子是一个矩形,坐标的绝对值<=1000),在第一面墙的(0,0)处有个光源照到了第二面墙上,于是就有光线进行反射(遵循光的反射定律)。求问最终第一面墙上多少镜子有光照到(以上摘抄自贴吧某傻叉的贴)

开始时lhm大神没有公布其题解。于是我试着翻译了下官方题解的前一部分,感觉真的很傻逼的样子。不过最关键的几个思路之一就出来了:

以上问题非常困难(只要明确事实,没有比赛有这么高的分)。因此,我们一步一步分析和拒绝不同的机会。
定义M为两边窗户数量的较大值。我们从考虑一条射到C墙的光线是如何反射开始理解。观察:如果光线射到C墙的点(x,y),并且(x,y)有一面镜子,那么他弹起然后击打B墙的(2x,2y).如果那儿有镜子,它反射开并且打到C的(3x,3y),而且普遍来说,反射到(kx,ky),直到最终没有射到镜子。为了简化符号,对于任意点P(x,y)和任意数c,cP定义为(cx,cy),而且类似的,对于任意矩形R,其对角线的两点为A,B,cR表示对角线为cA和cB的矩形。
我们现在看光线的反射可以看成一个照射到C的矩形O经过反射后变成了B的矩形2O。现在如果B有镜子与矩形2O相交,设为O1,那么反射到C之后便成了矩形3/2 O1。
.......
(这儿是暴力算法,省略了)
顺便说一下,现在提出个问题:一条射线停止反射(也就是没有射到镜子时)最多反射多少次?注意第二次反射一定会打到墙B,但是任意B中任意点,要么是墙,要么是非0点(因为题目中说了。。。灯塔不会再镜子内部或边界,而且窗户的坐标是整数)。因此在两次反射后光线的坐标至少变化1。因此2k次放射后坐标变化至少为k。由于窗户坐标的绝对值严格<1001,这是我们需要用来构建算法的信息。

矩形切割:
现在我们继续更快地检查镜子是否在k步之内被照亮。假设你想知道点d是否在k步能反射到,只有一条射线能在k步抵达点P——它最开始会射到C墙的1/(k+1)P。为了反弹,1/(k+1)P必须是镜子,继续,B墙的2/(k+1)P点也必须是镜子,进一步的,B墙的2*r/(k+1)和C墙的(2*r-1)/(k+1)必须是镜子。
注意,所有情况都可以移动到(有)一个共同点。换句话说,某墙的aP必须在镜子O上,可以等价为点P位于矩形1/aO \\感觉这是关键啊
然后执行如下的计算:对于每个正整数r (1<=r <(k+1)/2),而且对于每个B的镜子O画一个矩形(k+1)/(2*r)O,同理,对于每个正整数r1,(1<= r1 <=k/2),和C墙上的每个镜子O,画一个矩形(k+1)/(2*r-1)。若某个点,对于每个r和每个r1都包含在一个矩形中,那么这个点就是可以刚好在k步被光线照亮的(适当的墙,根据k等价?/*没看懂*/)。注意在同一座墙,不同的镜子是不同的,所以固定r之后,矩形是不同的—所以,代替检查哪个点是否被包含于每个r和r1的矩形,不如检查哪些点被刚好k个矩形覆盖。我们只需要考虑偶数次反射的结果,因为奇数次会反射到墙C。

解释一下吧,基本上算法的核心就是暴力枚举反射次数,那么考察点P(x,y)是否能被光线照射到,其充分必要条件就是点(K/i*x,K/j*y)位于镜子上,那么对于镜子(x1,x2,y1,y2),其条件为 K/i*x>=x1 <=> x>=x1*i/K,判断条件变成了判断一个点是否在K个矩形内不(我翻译了的题解的意思基本就是这样)。

接下来见lhm大神题解:
lhm大神的ppt上讲了另外一个很重要的方面:若反射次数为2^k*t时可以照亮某个镜子,则反射次数为2^k时也是可以照亮某个镜子。这个具体参见ppt吧。

于是就只要枚举11次反射长度,放射长度最多为1000吧,那么枚举B墙上的矩形,求出其与其余的1000*1200个矩形的交,如果其与K个矩形有交,那么其可以被照亮。。。这个也很好理解的。
反过来,就是1000*1200个矩形,若有某个地方有K个矩形覆盖,那么覆盖了该地方的B墙上的镜子就是可以被照亮的。
于是就有了扫描线加线段树的做法。。。
利用扫描线,很容易统计出覆盖次数最多的元线段的是哪条。。。所以找到那条线段,然后删除所有覆盖了那条线段的B矩形。
为了实现这步操作,我们线段树里记下三个值和一个vector,为在被反射过程中的矩形覆盖次数最多的,以及在此前提下被查询矩阵覆盖最多的,次数和位置。vector存下覆盖了该线段的B矩形。
言词不清,请见谅,昨晚睡得太晚,至今昏昏欲睡

所以
  评论这张
 
阅读(246)| 评论(4)
推荐 转载

历史上的今天

评论

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

页脚

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