Tag Archives: 区域赛

天津赛区网络赛非正式题解

首先声明:因为大部分题目是请神牛来出的,有几个题目我只写了暴力的验证程序而没有实现可以AC的程序。我这里写的解法有的只是看标程猜出来的,难免有不准确之处。如果有不对的地方,也是因为我对标程的理解有误。题目本身的正确性是可以保证的,这个请放心。

A. 首先离散化,然后用一条扫描线从左向右扫描事件,要求一个数据结构可以动态增加和删除线段,并且可以查询恰好被覆盖了K次的区间长度。标程的做法是分块处理,把整个Y轴分成长度约为SQRT(N)的小块,这样一条线段的中间部分会覆盖若干整个小块,两端的部分逐元素处理。对每个小块,用一个hash表H维护被覆盖了i次的长度H[i],以及该小块作为整体被覆盖的次数q。查询时对每个小块查询H[K-q]即可。期望的时间复杂是O(N*sqrt(N))

B. 二分答案,用2-SAT验证。把每轮游戏看作一个布尔变量,有两种取值。假设所有圆的最小半径为r,如果不同轮的某两个圆心的距离小于2r,说明这两个不能同时选择。由此得到一系列限制条件,恰好组成一个每个子式都包含两个变量的合取范式,再判断这个2-SAT问题是否有解即可。

C. 很赞的题目。我们考虑用一个矩形框住所有点,如果要求矩形边平行于坐标轴,则容易发现结果就是简单的把x,y坐标求最值,得到矩形(minx, miny) – (maxx, maxy)。如果我们要求矩形的倾角为a,则可以把所有点都旋转a角度得到新的坐标,然后用同样的方法来做。一个重要的观察是,f(a) = (maxx – minx) – (maxy – miny)是随着a的变化而单调变化的。当a从0度增加到90度,f(a)的符号必然变化(当然,也有一直是0的特殊情况……),把f(a)=0的那个时刻用二分法计算出来就可以了。

当然,此题也有其他方法来做,不过这种方法我觉得是最简捷优美的。

D. 有点麻烦的表达式处理题,基本上大家都要WA几次才能过。注意负号是可以作为单目运算符的,而正号不行,比赛的时候很多人问这个地方。还有就是范围越界的情况可能要尤其注意一下。

E. 如果不考虑那个VIP,N个房间可以被最多K把钥匙打开的情况,实际上就是1..N的置换组成最多K个环的情况,这个就是第一类strling数之和S1[n][1]+S1[n][2]+…+S1[n][k]。在这些情况里面,如果钥匙1恰好锁在房间1里也是不行的,所以还要减去N-1个房间被最多K-1把钥匙打开的情况数。

F. 水题,O(n^2)直接写就可以。

G. 我还没看懂标程是怎么做的,貌似是很神奇的解法。此题题解待补充。

H. 数学题,求曲线积分以后可以得到耗能关于时间t的函数e(t) = X * sqrt(w^2*r^2+v^2) * (t*v*sqrt(r^2+t^2*v^2) + r^2*log(2*v*(t*v+sqrt(r^2+t^2*v^2)))) / (2*v),此函数关于t单调增,二分求解e(t)=E即可。注意特殊处理r=0的情况。

I. 如果四个点不能组成凸四边形,则必然是其中三个点组成一个三角形,另一个点在该三角形内部。于是我们可以O(n)枚举一个点作为内部中心,试图从其他的点里选出三个来,组成三角形把它包围住,看看有多少种可能的选择。继续观察发现,如果三个点不能圈住中心点,则必然是存在一条通过中心点的直线,使得这三点都在直线的同侧。于是我们可以把所有点(除了中心点)按极角排序,然后线性转圈扫描一下就可以统计出来了。总的复杂度是O(n^2*logn)

J. 最后的矩形一定是在四个方向都遇到了-1或者边界才停止扩张。预处理出每个点(i,j)向左能扩张到的点L[i][j],向右能扩张到的点R[i][j]。对每个查询,外层以y递增,内层以x递增的顺序枚举(x,y),假设此点是矩形的底部,并且矩形是向上扩张直到某个(k,y)为-1或边界(这里k<x)。则此时矩形的上边界为k+1,下边界为x,左边界为max{L[k+1][y], L[k+2][y], … L[x][y]},右边界为min{R[k+1][y], R[k+2][y], … R[x][y]}。因为x是从上到下扫描过来的,左右边界可以顺便更新。Special Area的选择就是在这个区域内选择一个最大值,这个可以用二维RMQ在O(1)时间内完成。总的复杂度就是O(N*M*Q)

K. 每当一个点x被mark的时候,对所有点对(i,j),更新cost[i][j] = min(cost[i][j], cost[i][x] + cost[x][j]),复杂度为O(N^2)。这种操作最多有N次,故总复杂度是O(N^3)

Roba@TJU_Neptune杭州成都总结

赛季一开始,我们队便被HanoiTower在哈尔滨的出色表现逼上了绝路。金牌对我们没意义,拿不拿slot对我们没意义,按照赛前的内部规则,我们必须要在杭州或成都拿到学校排名前二的成绩才可以去WF,而大概扫一眼这两个赛区报名的队伍之后,大家心里都明白,这基本上是个Mission Impossible。当然这话我不能对队友说,我的要求是,不要总想着最后要拿前几名,我们的目标和哈尔滨比赛之前一样,银牌保底,拿到金牌就算胜利,至于能排到前几那是由rp决定的,以我们的实力还强求不得。这个目标在所有Regional比赛开始之前就已经定下了,也并不因为哈尔滨的结果而改变。从最后三场比赛的结果来看,两金一银,应该说是基本完成了任务,所以我虽然对不能去final有很大的遗憾,但也并不是不可接受的成绩。两位队友的表现很出色,而我总感觉自己并没有完全尽到队长的责任。下面就把两场比赛的过程大概描述一下,合肥已经写过了所以略去。

杭州:

A. 比较简单,枚举以后贪心

B. 一个组合计数问题,不会做

C. 数论题,RSA的破解,n很大,但e值较小,我们枚举了一个东西过了,不用java很难写

D. 最直接的BFS会超时,需要加各种剪枝/贪心/随机等等来水

E. 我从头到尾没读懂题

F. 数据范围给得很暧昧,可以O(n^2)暴过,我们很诡异的WA了几次后重写才过的

G. 迭代删点,这题出得挺有意思

H. 判断两个DFA是否等价,我们有一些不确定的思路,但时间也来不及了

I. 模式识别,不可做

J. 并查集的变形

仍然按照惯例,lx前,mdz后,我中。和合肥一样我负责输密码,配置IDE等等,然后再开始读题。先读D发现和B题有关联,于是跳过去读E,E题来来回回读了好几遍愣是不明白什么意思,然后开始无限怀疑自己的智商……以前虽然做不出题吧好歹还能读读题出出数据啥的,现在连题都读不明白了您说我还混个啥劲……这时候lx上来说A可做,我心想不会吧居然连续两站的A都是水题?叮嘱了一下不要着急就让他去写了,上去之前他说可能时间稍长,如果有更水的题可以先上。然后我读了B,D,发现B不会做,D被那个warning吓到了不敢做,这时候mdz说J题十分钟,然后把lx赶下去开敲,敲得倒确实挺快,敲完了问我:并查集里加一个把元素独立出来的操作没有问题吧?我说囧,问题大了,你还是下来先想清楚吧……mdz上机的时间我简单确认了下lxA题的算法,发现没有问题,然后lx把mdz赶下来继续敲A,敲完直接y了,发现场上的球大部分都是A,貌似也已经有了G,于是我去读G,读了发现又不会,往网络流上凑了半天无果,继续怀疑自己的智商ing……mdz还在坚持不懈地想J,我说算了这题未必是简单题,正说着呢好几个J球就挂起来了……他提出了一个在我看来是很yy的方法,但想来想去也找不到错误,就是在提出单独元素的时候做个标记,然后加一个虚拟的点上去,总的复杂度还是并查集的那个复杂度。mdz就去继续写了,我还是不放心,出了一坨数据,他的程序写完都能过,然后交上去1y了,大赞啊……然后lx也提出了G题迭代删点直到不能再删的做法,我又感觉这个做法很yy,又是举不出反例,又出了一坨数据,然后lx写完交上去又过了(因为小错WA了一次,很快发现了)……大家可以发现前期我基本没有做出任何贡献,就一直在负责读不懂题和质疑队友的正确算法了……囧……

这时候我们3题,还是比较快的,还在第一梯队里,但很明显后劲不足了。其他的题目里,教主过了C,香港中文过了H,不过F当时还没人过。mdz读了F认为可做,他的方法极角排序后做RMQ,复杂度O(nlogn),这个算法其实是错的,但他和我讨论后我居然认为可行……继续呼唤智商啊,之前怀疑正确的算法,现在又放过了错误的算法……然后他就写了,然后理所当然地WA掉了……这时候lx有了一些C题的思路,但肯定要用Java的大数,Java他俩都不熟(当然,我也不熟-_-),只好我来上。幸亏前一天的练习赛把Java环境搞清楚了,不过配置那些东西还是花了些时间。接下来的时间就是lx一边完善他的算法,我一边照着他的算法写Java程序,里面还用到了一个很囧的大数开平方,我把Auto Popup打开以后,在BigInteger和BigDecimal的方法列表里那个找啊找啊找不到,然后一直在和F搏斗的mdz突然抬头说,我有一个迭代法开平方的Java程序……于是我就把那个程序抄过来了,然后又遇到了N多语言上的囧问题,像什么怎么把对象复制一份啊(我后来用的方法是给他加一个BigInteger.ZERO,汗),怎么在BigInteger和BigDecimal之间转化啦,等等等等,然后终于编译通过啦……lx出了一些数据,发现如果p=q的话他的算法会挂掉,但题目中貌似隐含的意思是p!=q,我们商量后决定,先交一次再说,然后1y了……这道题我充当了一个不熟练的码工角色,算法全不是我想的,还写得磕磕拌拌……不过不管怎么说也算对队伍有个贡献了……

mdz已经发现了F题算法的错误,但想不出比平方更好的方法了,当时看到4题的队伍过F的居多,过C和H的都是少数,我就想恐怕平方加些优化能水过。于是mdz继续去改他的程序,写成平方又加些可能的优化,改完再交是WA了,刚看到这个WA我是很高兴的,因为居然不是想象中的TLE,以为是程序里有一些小错改过来就搞定了。结果我和mdz把代码来来回回看了N多遍,又出了不少数据,也没发现明显的错误(后来把lx也拉来看了,也没看出错误。)mdz按我的建议改了几个小地方,又WA了一次。这时候就有点囧了,时间已经接近封板,从其他队提交来看最可能过的也就是F和H,lx在想H,有一些不确定的想法,mdz卡在F上,我是两头跑。mdz劝我重写F,其实当时我是感觉这样有点冒险了,不过他那个程序实在查不出错,我就只好开始完全重写。这次重写就是照着平方的算法去的,稍微换了一下思路,为了减少错误,也并没有加什么特别的优化,另外也尽量避免了浮点数的计算,因为我一直感觉mdz之前的程序可能会有精度问题。写得还算不慢,写着写着突然反应过来这是我快到封板了才第一次开始写C++的程序,完全不是我们队的风格么……写完之后又出了一个囧事,我的程序在Sun Studio里编译运行没有任何问题,但用PC^2的Test就出现莫名其妙的编译错误,当时也就只有半小时多一点的时间吧,尽管我也算身经百战,当时真有点发蒙了,改了很多可疑的地方,还是不行。后来一部分一部分地把代码注释掉,终于发现问题出在我定义了一个叫做SS的结构体……以前对于没有明确名称的结构体我经常用这个SS当作名字的,从来也没有过问题,不知道Solaris上的编译器是怎么搞得,真是无语了……被这个破问题耽误了估计得有十分钟,然后我就安慰自己说,好事多磨,这个交上去肯定过了。然后果然过了,哈哈。

最后的一点时间,mdz去敲剩下的唯一貌似可做的H题,他那个算法正确性也不敢保证,最后是写完了没有调过Sample,临结束前瞎交了一个上去,当然WA掉了,比赛就此结束。后来和别的队伍讨论,我们的想法还算靠谱,但要做的修补还有很多,最后那一点时间已经确实不够了。于是我们最后就是五题。

 

成都:

只列一下我们想了的题吧

A. 一个进程调度的问题,需要O(nlogn)的做法,我们在场上没有想出来

C. dp,其实我感觉也并不好想,lx把它过了

D. 应该是建一棵树然后统计,但我发现就算只建树想写一个比平方快的方法都很难,就扔了

E. 离散化后统计,O(n^4)可以过

G. 最后有个贪心的想法,但时间来不及了,没写完

H. 生成树的个数,还要用polya原理处理旋转等价,lx在这题上想了很久无果

I. 描述很长,其实是个水题,就是最短路

J. mdz过了,我没看题,是个立方的算法

一开始我看了DE,很快有E的球出来了,但我想了半天没有想到低于四次方的做法,N是100,就不太敢写。然后mdz说J题里有个词”square”,如果指的确实是正方形的话就有立方的算法,我让他用clar问了一下,得到肯定的回答后他就上去写了。写完得到一个RE,然后很快又rejudg成TLE,但这题N=300,按道理怎么写也不应该超时的,这或许就预示着这将是一场艰苦的比赛啊。然后我硬着头皮写四次方的E,因为mdz不会超时的算法都超了,我这个写的时候自己虚得很,写完交上去RE了,那个囧啊。mdz也是很虚地上来说,没发现代码的错误,优化个常数试试吧,然后优化了一下,yes了……这时我也发现了我代码的两个弱智错误,这时候已经全场都是E球,不管三七二十一再交,过了……

这时候lx有了C题的想法,跟我说了一下,我感觉是好像是对的,但并不确定,这种刷墙的题以前我好像做过类似的,但印象中是一直没过,所以有点阴影,这题lx就上去写了。然后我和mdz继续读题,我就发现没什么会做的题了-_-。后来A球稍多了,就开始想A,但总是想不出O(nlogn)的算法。lx的C题也得也不太顺,但WA了好几次之后还是过了,很赞的说。我上去想用O(n^2)水一下A,结果WA掉了,当时心里很高兴,结果发现是因为我代码写扯了,改对以后TLE了……555……

从这时开始囧起来了,A球越来越多,但我和mdz都没有好的想法,mdz提了一个很复杂的方法,复杂度也算不清楚,因为也没题做就让他上去写了。然后发现除了这四题别的题都只有很分散的提交,就不知道怎么办了。lx一直在想H,我在继续想A。mdz的A写完还是 TLE,我仍然无想法,lx对H也无想法,只看着场上的气球越来越多,越来越多……

这时候已经接近封版,我想不能再栽死在一道题上了,再扫了一遍别的题目,并且耐心把I读了,读了之后大呼上当。趁mdz上机的时候仔细规划了一下,找了个空隙机时很快把这题1y了,这时候场上的I题还不多,不过我知道大家很快都会发现它的本质的。果然最后一小时过了四五题的队伍都把I过了,而我们仍然对剩下的题没有好想法。最后半个多小时的时候lx说G题有一些办法,于是就上去写了,写WA了一次,再修改就没有时间写完了。最后也就只有四题。

赛后我们问了旁边的HDU的A题,确实是有巧妙的O(nlogn)的做法,我们确实是没想到,所以挂死了也没什么好说的。感觉这场比赛成绩不好的原因,一是大家状态都不太好,一上来的三道题没有1y的,二是我这个队长没有发挥出应有的作用,在整场除了完成了两个代码(还WA了一次)之外没有提供任何有用的想法,对A题的思考陷入惯性思维里出不来了,而且没有及时引导队友,比如lx就一直在希望不大的H上想了很久,如果早一点让他只想G的话这题就说不定能做出来。其实对于第一点在杭州的时候就有所体现,我在场上几乎没有提供出什么好的想法,当时我是说因为题目不适合我的思路,而且队友的出色发挥一定程度上掩盖了我的问题,结果这次就暴露无遗了,如果说一场比赛发生这种情况可以用“思路不适合”来辩解,那么连续两场都是这样就没有道理了。不过,我的参赛选手生涯已经结束,这个问题也无法弥补了,呵呵。在这里写下两场比赛的过程和经验教训,希望能给lx以及所有留下来的TJU ACMer在来年的比赛里作一个参考吧,并祝HanoiTower在World Final里取得好成绩:)。

ps. 再说一遍,这个只是比赛记录,我的退役感言还得慢慢写呢,嘿嘿

合肥之行 – Day3

这次只写比赛,比较扯淡的东西以后再补。先简单列一下题目,这里列的只是当场的想法:

A. 我没看题,被lx秒杀了

B. 也没看题=,=,好像是离散对数,但是是经典问题的加强版。据说有结论,我们不会做

C. 图论,利用求割边的那些东西

D. 图论,利用强连通分量缩点和传递闭包

E. dp,要用线段树优化,时限比较卡,我超时到最后

F. 一个特殊图(区间图加强版?)的最大团,不会做

G. 二分+Farey序列

H. 计算几何的计数题,不会做,只会暴力,超时到最后

比赛开始后,仍然按照惯例,lx从前往后,mdz从后往前,我从中间开始。读了D题,有一些大致的思路,但也有一些地方想不好如何处理,感觉不是马上能做,lx读了A说能做,就上去写了。mdz跟我说H暴力的话复杂度是10^8量级,或许能水过。然后跟我说了F,然后我就直接走上了不归路……没仔细想就以为是区间图的最大团了,这时候正好lx把A题1y了,然后我就开始翻出区间图求PEO的那些东西来搞,但是我那个模板只是判断弦图的,关于最大团问题的具体结论我已经记不大清了,当时很后悔没有带一本图论书来。猜了两种结论,都WA掉了。这时候已经耽误了不少时间,当时虽然是把这题放弃了,但还是一直留着一个幻想以为过一会儿我就能把结论想起来。这时候旁边WHU已经过了C,lx也正好想了一个C的算法,在我改F的时候交替着上机把C写完了,但也是WA,后来又改了个小错还是WA。然后我就一边依依不舍地yy着F,一边给lx查错,结果听lx讲完算法后发现他的想法基本不靠谱=,=,马上被我举出反例了……他说当时跟mdz商量了一下,mdz说感觉是对的于是就上了=,=,看来一上场大家的感觉都不大准啊……然后我们讨论出了利用双连通分量的方法,感觉是没什么问题了,我就上去重写C,结果写完又WA……崩溃……同时mdz在写H的暴力,不知道他后来交了没有,然后又来帮我们想C和D,这段时间我们做得有点混乱,大家也都有点着急,这就是中期之前我们出了一题就囧住了的原因。

还好C题我的算法框架还是没有问题的,不久发现了一个小错,这时候我又急躁了,直接改完就再交。然后又WA……奔向厕所,然后突然想到还有一个小错,回到座位发现lx也发现了那个错误,改之再交,终于在150min,两人写了两份代码,5次提交之后得到了第二个Yes。这时候我才突然反应过来F题因为时间区间可以跨过零点,所以不是一个真正的区间图,那么可能要对经典模型进行修改才行,不过我连经典模型都忘记怎么证的了=,=,于是直到这时才真正把F放弃。这时mdz提出了D题的解决方法,我感觉前期心情有点太急了,于是有意求稳了一下,这题我俩讨论了较长的时间,把所有细节都分析清楚了,然后我才开始上机,同时让mdz出数据。与此同时lx也基本想出了G题的做法,但他那题有点不太好写,我在他下机规划的空隙把D完成了,mdz出的数据也直接全部通过,然后直接提交1y。几分钟之后lx的G题也改对了,又一个1y。感觉这两道题我们是完成得比较好的。

这时候还有大概100分钟,我们4题排第二,但第一名很快做出了第6题,而且他们过的几题我们都没有好的思路,当时就感觉压力很大了。这时候场上过得稍多的是E,很明显是一个需要优化的dp,但这题一开始他们两个都不愿去想,这种优化dp也一直是我们队的薄弱环节,我又一直在和自己的弱智错误搏斗,所以直到这时候我才有时间开始想这题。同时lx想B,mdz继续对H加一些常数优化,不过B和H我都没有好的想法。写E题的时候我又有点着急,一开始转移方程没想好,后来线段树的实现还出了好几个小错,直到结束前半个多小时才过了Sample,结果交上去却TLE了。从数据规模上分析这题的时限确实很卡,复杂度是O(MNlogN),M=100,N=10000,但因为过的队比较多我就硬上线段树了,没想到真的会TLE。后来又加了些常数优化,但还是TLE。最后lx说了一个O(MN)的算法,但被我反驳掉了,我也试图想过O(MN)的算法,但总是感觉想不好。后来问WHU他们就是用O(MNlogN)过掉的,这几天我要好好检查一下我的线段树为什么那么慢了……另一边mdz的H也在TLE中。lx的B本来还有些不太确定的想法,也没时间写了。比赛就这样很囧的结束。

从总体上来说,我们确实没有完全发挥出来,但也并不能算是做得很烂。如果我最后的E能过,那么我感觉我们就已经几乎做到最好,没有什么遗憾了。冠军那支队表现出的确实是超越我们之上的实力,我们输得心服口服,这样水平的队伍也确实足够有资格进入Final。虽然不计名次,我知道大家都有点YY能拿个冠军,不是我们没尽力,只是对手太强大啊……虽然我这么说有点推卸责任,呵呵……

当然这次比赛也暴露出了我们队的很多问题,前期我太早地把时间浪费在一道没有把握的题上,而且因为我在敲F导致lx不能把C题与我进行讨论,得出了错误的算法,然后又因为我着急把C题赶回来而出了一堆小错,浪费了大量的时间。如果我们前两题的速度能够跟上当时的第一梯队的话,后面的E可能也就不会没时间仔细优化了。这一系列的连锁反应都是由于我的草率造成,这个我要检讨一下。还有就是冠军队诡异的过题顺序确实对我们造成了一定的影响,这次比赛的8个题我们都没有轻易放弃,每道题都有某人或某两人想过不短的时间,甚至对于没把握的题都完成了代码,只因为已经有人过了就想水一下而已。所以赛后lx一直纳闷怎么感觉时间过那么快。如果能尽早集中火力的话或许结果会好一些。两个队友的表现都比我好得多,mdz想出了D的正确方法,lx单枪匹马干掉了G,相当的赞。我自己则是先跳了一个到最后也没人过的F坑,还没爬出来又让C坑拌了好几个跟头,最后终于挂在E坑里了。囧……

好了就写这么多了。我代表全队给大家道个歉,希望大家能认为我们还不算太给TJU丢人,请期待Neptune在后面赛区的表现。

ps. 最后要赞一下Zing,最后一分钟搞定D题。可惜还是rp差了一点,没有银牌。在杭州爆发吧,哈哈。

合肥之行 – Day1

晚上十一点多的火车,到车站的时候就发生了一件囧事,出租车师傅手快,到站就把计价器按零了,然后小票就打不出来了 =,= 在火车上又发生一件囧事,就是我们上去之后发现有两个位置已经有人占了。把乘务员叫来仔细查验以后发现是他们把时间弄错,应该是13号,买成了18号的票,然后检票什么的都没发现……我们是半路上车,当时车上就已经熄灯了,望着窗外发了会儿呆就睡了。貌似睡得不太好,不是因为情绪紧张,是因为我白天睡多了 =,=

到了合肥,发现和印象中的石家庄(不过石家庄我已经很久没有去过了)很有几分神似,都是那种很破败的省会城市的样子。不过中科大的校园还是相当不错的。合肥比天津要热五六度,在街上走了一路就感觉有点热了,有点后悔衣服穿多了。吃完饭去一个叫“包公园”的地方玩,里面有包公的祠堂、蜡像、遗迹之类的,还不错。比较囧的是景点的英文名叫Lord Bao Park,我一直在想对ACMer来说是不是应该翻译成“包教主的公园”?@_@

回学校的时候又囧了,我们是在六点多钟的时候打算打车回来,结果就发现出租车根本不鸟我们。有很多明明是空车,但就不亮那个红灯,招手也不停。后来好不容易拦了俩车,师傅说是因为他们都是七点交接班,所以都不拉活了……囧,但那正好是下班高峰期啊……

回到科大的时候碰到一队人,其中一人喊我“萝卜”,不过天比较黑,没认出来是谁,汗

然后还有一个囧事是说因为我们是特邀队,所以没有衣服,但我们报名费可没少交啊,这个可真是有点郁闷了,这个问题正在交涉中。

晚上玩了会儿杀人,扯了会儿淡,就到现在了。今天就这么多事了,明天教练会和热身赛,加油。:)