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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

4-7集训队互测  

2014-04-07 17:49:23|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
嗯,滚粗的最惨的一次OI比赛吧。
“说句大话,本来我是能AK的。”
大话说起来真简单
考挂都是自己弱——不知道有多少人用这句话来逃避自己的失败——但是用在这个时候真是太恰当不过了

首先给绍一的大神跪了,互测几乎完全是被绍一大爷们统治的状态啊。
然后是ydl大爷和花神的代码能力。以前没意识到。。。现在陷入绝望的深渊中

最终成绩是拿了25分,rank2了,只不过是倒数的,可怜的sy神,貌似比我还惨,pat pat
果然应该回家种田的。

现在开始总(吐)结(槽)。
在考试开始前我就开始估摸着大概没有可做题吧,那么就是暴力大战了。。。至少我是不会放一道能够让人A的题目到互测里的。。。。。。。。。。。
我还是too young啊。。。大概所有人里面就我的心态最不对吧。
啊呜啊呜
有谁像我这么良心的给90分暴力!

似乎由于第一天的影响,我最先看到的是第二题。结果发现是xyz大爷的题,简直吓尿。不可做但是看看题瞻仰一下还是可以的吧。
去掉乱七八糟的条件之后,题意是这样的:给定很多个点的集合,点的总数小于35000。如果点a到点b的曼哈顿距离小于c_a或者欧几里得距离小于r_a的话,点a能够攻击到点b。请对于每个集合回答,有多少个点能够攻击到这个集合中的点。
看到题的第一眼感想是:哟,貌似见过来着= =
大概就这么想起来了:
如果点在一条直线上,nlogn可以直接搞的,这个是在平面上去重变得相当复杂。但是数据范围比较小,说不定有什么比较好的做法。
35000。。不大不小的一个数,nsqrt(n)或者nsqrt(n)logn的做法?
距离查找的话是裸的k-D树吧。但是k-D树很容易被卡,xyz大大肯定没这么好心。一看数据范围,果不其然。但是给了20分,而且不用去重。
那就用其它乱搞吧,分块啊,四分树啊。。随便试了下都很容易被卡,为了不玩脱也就不敢冒险。
剩下的分别是20分的不用去重的,和20分的只有圆的。
不用去重的只要对坐标讨论,即可将曼哈顿距离和欧几里得距离分开。曼哈顿距离随便什么数据结构即可,欧几里得距离有点小难。
于是可以归为一个很经典的题:给定平面上的n个圆,对于每个点查询它在多少圆中。
虽然很经典,但是没见谁出过。。也找不到原题。
不过显然就是判断一个点在多少个半平面内的那题的加强版而已。将圆分成sqrt(N)部分,每部分O(n^2)求出交点离散化,利用拓扑序变化只有O(n^2)次,用扫描线,对于查询可以二分,这样就可以做到O(Nsqrt(N)logn)了,由于坐标范围比较小,都不用排序,挂个链即可。。这在我所知范围没有更优的复杂度了。
这个做法是没有去重的。不过很明显可以发现将N分成sqrt(N)块后只有200个数了,用三个longlong存下来,可以视为一个比较大的常数吧——嫌麻烦就暴力bitset流吧。
问题就这样被nsqrt(n)logn解决了,可喜可贺。
——从这时候起我产生了我能够A掉这题的错觉。但是我坚信这题没有其它做法了。

于是就在欢快地在考场上啪计算几何了。。由于是在ubuntu下模板都没找到,就只能欢快地写了。
啪啪啪
咪啪
咪啪~
咪啪~~
咪啪咪啪咪啪
代码拍起来真他妈爽啊

因为不知道怎么很好地一起处理圆和曼哈顿,所以就只写了圆的。。。但仅仅是这样,调那么大段代码也耗掉了我两个小时。。
虽然耗的时间比较久,但是能够A掉一道题还是很高兴的嘛。。(嘛,说不定我早忘了这是考试了。。
但是当我好不容易调好程序,兴高采烈交了发A+B。。
虽然nsqrt(n)logn是丑了点,但实测也是在两秒以内啊。。tsinsen比本地的机器可是要快的啊。。但是时限仅仅只有1s。。
wtf........
4-7集训队互测 - hzaskywalker - Yavin(某沙茶的代码库)


因为xyz大大保证了除了第一个点其它的都是极限数据。。
那么一个常数较差的程序就只能得10分了。。不由想起了冬令营的第一题。。可喜可贺,可喜可贺。
但是智商是负数实在没办法将那个logn优化掉。。那么想必正解不是这样的吧。。除了对数据范围无限的怨念也没有别的办法了。

在又折腾了十分钟常数后,突然意识到好像还有两道题来着,既然如此就来看看吧。
第一题是zhj大神的题,题意是求割,使得三种权值的和的积最小,n<=50,m<=100。
第三题是crx大神的题,题目太长不看。。。看样子和置换有关,不过仔细看数据范围,明显是套着数学题外壳的数据结构题。。嘛,没意思。

所以就开始搞最小割了。不过这个模型有那么点裸啊,最小乘积生成树记得在2012年的冬令营上就介绍过了,做法相当经典,只不过这题是最小割。
不过没关系,那个做法只是个乱搞而已,而乱搞的做法往往是有很强通用性的。
于是我又开始愉快地啪代码了~咪啪~

大概也就十几分钟吧,代码就愉快地啪好了——复制粘贴了sap和三维计算几何部分。
惊讶地发现我也是写过三维凸包的人,看着我那缩得不能再缩的代码,只想感慨盾哥真神也!
常规流程,写暴力和对拍。。
卧槽。。为什么答案是错的。。
时间就是如此哗啦啦啦地流逝。。而我一直在好奇我代码哪儿写错了。。
四点的钟声就这么敲响了,然后我意识到了考试只有两个小时,而我目前得分为25分。。。
吓尿了。。赶紧啪了第三题暴力重新回来意识流我的代码哪儿写错了。。
惊讶地发现我最小割求反了,但是又觉得没有求反。。又发现我叉积似乎叉错了,但是又有一种没错的感觉。。那就没办法了。。算法有bug,加个随机化吧,我就不信能够被卡。
哟,对拍,好,小数据完全没问题。。
嘛,不管啦,继续去思考第二题怎么卡常数。

完全想不出啊。怎么做呢?怎么做呢?
是不是应该写点前几个点的暴力来多拿几分?
有点想睡觉了,还是不管了吧。

觉得第二题完全无望之后滚回去看第一题,结果。。发现只要权值一大就为爆成负数。。
真是蛋疼。。赶紧改改,赶紧改改。。。

!!!!!!!!!!!!!!
怎么考试就要结束了啊。。。。。完全不知道我代码哪儿错了呀。。。
T_T、、
就这样彻底滚粗了,幸好我代码里夹了暴力,5分还是拿得到的吧。

考试结束。。题号公布赶紧交了发代码。。。。
于是总分如前所述。。
不过昨天分数出来的挺快的,应该是考试一结束就公布了吧。
匡大爷告诉我说我是倒数第二名。
没垫底真高兴,sy菊苣对不起了。

好了接下来就是考后改题的故事了。
非常非常忧伤的故事。。
当时考试结束后发现花神和ydl大爷都A了第二题,而且代码量非常短,觉得非常非常非常非常不科学。
——能够有题目被A掉真是超出了我的想象啊。
去问了下花神第二题的复杂度:O(Nsqrt(N)+N^2/32)
确实也就是bitset暴力流加个神马东西。
还能怎么做呢?莫非又是喜闻乐见看错了题?
于是仔细看了下题:
“保证在数据生成时不考虑一个点的具体位置,而将它的横纵坐标分开考虑”
神马时候题目最后多加了一句话?
直接明说数据就是随机的不是更好吗。。。顿感人生被浪费了

心灰意冷的我重新打开了我第一题的程序,有事没事往评测机上交。。认真地再次写了个比较靠谱的数据生成器,进行了新一次的对拍。。。
突然间发现我好像连最小割都没求对的样子?
确实是犯了个很严重的算法错误,在网络流之后求权值,我又傻乎乎地将从S出发搜索到的满流的边加入了答案——而正确做法应该是统计连接了S部和T部的边有哪些。。
之后发现我最开始按照寻找某一维坐标最小值生成的平面会有bug,在很多情况下会退化成直线。这个东东的存在直接否定了我的算法正确性,但在我祭出随机大法之后,亦不战而屈之。
but。。。
在我的代码与大量小数据对拍无误之后。。
为毛交上去还是0分啊。。不科学啊,我就不说直接贪心取和S相连的或和T相连的边中权值和最小的就可以拿25分。
莫非???
心情不愉快的我将数据生成器中的S设为n,T设为1重新跑起了对拍。。
发现我的答案很靠谱啊,啊咧,为何答案会是0?
擦。。网络流是粘贴的代码,默认了n就是汇点。。。
欲哭无泪啊。

A了第一题,补了几集番之后再来写第二题。。
k-D树实在是好写好调,很快就写好了。。交上去——10分,其余点全部超时。
之后开始漫长地瞪着我的程序发呆的旅程。。。直到熬到凌晨四点才最终A掉。
原因是什么呢?很简单,在本地我随机数据要跑20s。。。比我的那个nsqrt(n)logn还要慢。。
很是怀疑我对k-d树的理解是否正确,毕竟那个sqrt(n)来得有点魔法。
但是在我将那个东东通过意识流证明了一下,仔细比对了我的程序运行情况得出结论:
我的复杂度确实是nsqrt(n)的,只是因为奇妙的原因跑得比别人慢了几倍了。
标程不也是0.6s才A么。。大概就慢了30倍左右吧。
卡常数永远是一件痛苦的事情,其中的艰难与困苦远超想象,特别是对于我这种从来只关心算法复杂度的人而言。
不过最终还是0.9s卡过去了,留下无数的怨念。。
实在受不了就睡了。。

今天早上起来仔细看了下第三题,其实这题里面还是有点数学推导的。
\sum_i<lcm(n_k) \sum_{n} gcd(i,n)
可以枚举gcd,然后转化为欧拉函数。所以此题就是要你:
1.维护长度为n的置换,可以交换任意两个元素。
2.并要求维护每个轮换的长度的质因数分解的信息。
显然两个问题之间是没有关系的。维护位置关系直接treap搞定,交换要么是将一个轮换拆成对换,要么是将两个轮换合并。所以很平凡的操作。
要求维护质因数分解其实是有难度的。。为什么呢?
因为n<=10^8,数的个数是10^5个,怎么破?
这个问题相当难,没法线性筛,内存开不下,所以基本上都会想到那个叫做什么pollard p..什么o来着的算法。。
但其实只要把sqrt(n)一下的质数搞出来,暴枚就可以了。。
所以问题解决。
在连写带拍搞了接近三个小时之后,怒交一发。。
又tm是TLE。
一看标程时间:2.3s。。
好好好,我也知道标程写得好,但是你是2.3s开个4s时限没问题吧,何必欺人太甚。
嘛,纠结了好久最后通过预处理逆元将常数卡进去了。。
不过没意思,真的没意思。。

总之我考完之后的最大感想有这么几点:
1.滚粗一时爽。。。零爆爆,底垫垫
2.果然考挂自己弱,绍一大爷太屌不能多说
3.卡常数卡常数卡你mb的常数
4.集训队互测的题竟然是能做的,感觉世态炎凉,人心不古啊
5.花了10块钱买了两瓶咖啡在考前灌下去都没能阻止我在考场梦游。。累觉不爱了
6.wyt你药不能停啊
  评论这张
 
阅读(1154)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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