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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM585 & SRM 587  

2013-08-05 10:25:03|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
嘛。。。跳过了中间的SRM 586——弱弱的法法塔参加了div2
好了。。这两次的题目都不是很难的说。。

那么就直接上题了
SRM585 1000pt:
坐标轴上由(0,0)->(m,0)->(m,m)->(0,m)->(0,0)围成了个正方形(m<=100000),我们要求在以这个正方形边上的整点为顶点的三角形数,使得给定的点集S(|S|<=20)在三角形内。
题解:
嘛。。。主要是观察到单调性撒。。我们选择一个点作为三角形的一个顶点,那么连出去的两条边是有一个范围的。。。很显然正方形上的点组成了某种意义上的凸多边形,考虑三角形顺时针方向的边,那么作为边的另一个点的位置肯定是一个区间,而且是从选择的点顺时针方向的下一个点沿着顺时针方向走的一个区间。。。显然这个区间随着选择的点单调变化的说。。或者利用二分,也可以求出这个区间。。那么我们就得到了从一个点出发,连出的能够包含点集S的边的个数(想象成半平面交)。。
接下来,就是确定三角形的一个顶点的话,答案是多少?它顺时针方向能够连向一些点,逆时针方向能够连向一些点,我们要统计的对数就是它顺时针连向的点再顺时针连向的点中和它逆时针连向的点的并集的大小的和。。讲起来好纠结啊。。
我们观察这个并集。。。令顺时针连向的点为A,令逆时针连向的最后的那个点为b,那么A能够成为三角形上的点的条件是边Ab能够包含点集S。。那么并集的大小就是(A顺时针能够连向的点的个数-A到b中点的个数)。。。A的范围也是个区间~显然就是点b逆时针能够连向的点。。。接下来对这个区间,用前缀和统计A顺时针能够连向的点的个数,而A到b中点的个数显然就是连续自然数的和,直接算。。。
这题就完了。。。想起来比较麻烦,写起来还是挺简单的。。
主要是在考虑两个推广什么的:
1>m如果是10^9次方怎么办
2>点集的个数很大怎么办(这个似乎挺容易的)

SRM587:
弱弱的法法塔通过SRM586晋级到了div1后做的第一场div1——竟然没有变红T_T。。秒第二题耗了太多时间,加上没做出第二题,注定了法法塔的滚粗。。

SRM 587 900pt:
SRM585  SRM 587 - hzaskywalker - Yavin(某沙茶的代码库)
嘛,就是这样的图,也就是说,黑色的格子内部要连刚好一条白色的边。。以及每个格子的边界也要有白边。。。要求最后的图能够三分图染色。。。已经在内部连好一些边了,要求字典序最小的方案(又左上到右下为0,否则为1)
题解:
嘛。。。关键就是要大胆猜想——可我考场上可不敢这么搞啊。。
大概,无解的情况一路推过去的话,就一定是在某四块内无解。。而无解的形式也只能如下
10
11
也就是说,存在奇数个相同的连法——即异或值为1。。。
那么就是求字典序最小的方案使得最终任意两行两列的相交处的异或为0。。。
这是个很简单的问题喵
我参考了scott_wu的代码。。。不然怎么错的都不知道~考场上很多人这题都挂了
  评论这张
 
阅读(332)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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