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

ydc的博客

 
 
 

日志

 
 

codeforces 219 div1  

2013-12-19 22:27:36|  分类: codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
其实几天前就做了的
今天晚上效率各种低,脑子很晕
不过也在计划着解决一些后顾之忧了
感觉我好弱……

这场CF……又被A卡了
每次都被A卡……我是时候滚回div2了(不过div2 只做AB也会跌吧)
考试的时候看到A,想了个贪心,1WA
又想了个贪心,2WA
无力的去看B
想了想用个O(n^4)的做法切了
回过去看A,又换了个想法,3WA
又交了一发,终于A了
是一个O(n log n)排序+O(n)扫的做法
然后放弃治疗去搞英语了

尼玛C就是个单调队列啊……
我为何在还有“充足”的时间的情况下都不去弄啊
最后竟然涨了rating
感人肺腑

题解:
D:
这题是在从机房回家前几分钟看的题意,然后回家的路上想了想。利用单调性扫描的区间是O(n)的当然秒想……就是不知道怎么快速的插入、删除一个点并查询题意的那个东西,唯一的想法是维护公共LCA,但显然没前途
第二天突然想起做ZJOI捉迷藏的时候有一个括号序列的模型感觉有戏,继续想……还是想不出来
课间操的时候一个结论穿过记忆的长廊
“一棵树上m个点连接他们的花费是将他们按DFS序排成a1,a2,a3……am,然后答案是(dis(a1,a2)+dis(a2,a3)+dis(a3,a4)+……+dis(a[n-1],a[n])+dis(a[n],a[1]))/2”
尼玛这不是裸题吗??
于是中午去机房花个十分钟A了
不过考试的时候我肯定A不掉
因为我早忘了这个结论了啊!!!
E:
学习了反演……
来总结一下吧
时间匆忙就不用latex了……可能有点丑
给定常数r,一个点P关于原点O的反演指的是……在射线OP上找到Q使得|OP|*|OQ|=r^2
那么点反演得到的是点
一个过原点的圆,反演是个不过原点的直线
我利用许胖的“zhuo xi di"时间推了一下
假设反演后的点是(x,y),反演前是(tx,ty),我们有sqrt((tx)^2+(ty)^2)+sqrt(x^2+y^2)=r^2,t*(x^2+y^2)=r^2
所以t=r^2/(x^2+y^2),反演前的点是(r^2x/(x^2+y^2),r^2y/(x^2+y^2))
设反演前的圆是(x-a)^2+(y-b)^2=a^2+b^2,那么有(tx-a)^2+(ty-b)^2=a^2+b^2,t^2(x^2+y^2)-2t(ax+by)=0,因为t=r^2/(x^2+y^2),所以t*r^2-2t(ax+by)=0,t(r^2-2ax-2by)=0
由于t显然不等于0,r,a,b是常数,所以圆反演是个不过原点的直线。当然我们这样也就把直线的方程式搞出来了(当然实际中随意取两个点反演连接一下就行了)
由于如果不过原点,反演前的圆方程就不是(x-a)^2+(y-b)^2=a^2+b^2所以就得不到后来那个式子了,所以不过原点的圆反演是个圆

由于反演是个一一映射的关系……所以两个点反演后重合那么原本就是同一个点了
还有就是……以原点为圆心r为半径做圆,那东西叫反演圆
反演圆外一点,反演后在反演圆内;反演圆内一点,反演后在反演圆外。反演圆上点反演后显然在圆上

然后反演还有什么呢……我也不知道,我只做了这一道题
顺便吐槽……上面的推导这样打下来也实在太丑了吧!!
latex相比还是好看多了

这道题的话就是说……先把每个点反演了。如果两条直线有交点,那么就说明反演前的圆是有交点的。所以就是n个点里选一个……平行四边形!
用HNOI2011的数矩形的做法……将每个线段的中点求出,如果中点重合就是……平行四边形?
有可能两条重合的直线,他们不能构成平行四边形
所以我们对于中点相同的直线,按直线斜率排序,只能取斜率不同的。将中点相同的的直线按斜率分组后,一个显然的dp出来了
dp[i][j]表示在第i组,现在选了至少j条直线了,0<=j<=2。然后dp[组数][2]就是答案
实际实现中我使用s1,s2两个变量求的……因为列出转移方程之后显然可以做到O(1)空间
  评论这张
 
阅读(293)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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