2014 ACM-ICPC 亚洲地区赛 西安站小结

弱菜第二次参加地区赛,继续流水帐记录下。

西安赛区举办很隆重,西工大校园也是够大,只是长安校区太远,从火车站打的到友谊校区再坐公交到长安校区花了2个多小时ORZ~本来以为赶不上热身赛,结果热身赛是15:30开始,时间很够。

热身赛1个小时半,4道题。3分钟就看到有人出了D,仔细看是map计数,统计单词出现次数,大小写不区分,输出为大写。以前做过这种题,当时死活想不起怎么用STL里的MAP,无奈先让老范和纪存写其他题先。老范写的C,多边形的面积和周长计算,几何模板套用,打完代码发现有点小问题,接着思考去了。纪存写的A的模拟,是要写一个类似JAVA中的String to (Integer、Double、String)的模拟,目测坑多,写到一半纪存又思考去了。这时我才有点想起如何用MAP,立即code,打完测试,提交1Y

    • 。交完老范也想到哪儿出问题了,改完提交C,1Y。之后时间不是很多了,我们继续思考A,后来发现A一个队伍都没过,还是果断放弃了。热身赛结束2题排在120左右,铜牌区,还行~

其间先吐槽下住宿问题,本来以为住宿很高大上,后来发现房间差的很,插座除了电视外只有厕所一个,全部灯只有一个壁灯好的,床单枕头发黄恶心,电视小的可怜。不过除了住宿外,西工大其他都安排的很好~

第二天正赛,上来我先看的F,纪存K,老范D。几分钟后刷榜有人过了A,开始看A。A题干长的让人想吐,具体是讲的老罗的锤子手机和他的情怀,以及锤子官网访问次数始终是3的倍数的问题被人发现等等等等。最后要求一个“情怀数列”,全文就一句话讲了这东西,就是所有数都是3的倍数。刚要打代码老范提醒hint里提示到数字过小不是情怀什么的,仔细一看貌似是这样。但是再往下看居然看到一句话,说本题的陈述和提示,全部都是joke,不要太在意- -,实在给跪ORZ~提交1Y,看了下排名110+。

回来再次看K,K大概讲的是一个无限数列,S1=A,S2=B,此后每个数都是前两个数做差取绝对值。最后会发现数会循环在某两个数。我简单的打了个代码测试停止的数,发现最后停的都是两个数的最大公约数。这时老范想到了方法,将类别分为A%B==0以及A%B!=0两种,算法类似gcd,大体是这样的:

1
2
3
4
5
6
while(x%y!=0) {
ans += x / y;
int z = x % y;
x = y;
y = z;
}

最后这种类别的会转化为A%B==0的,ans再加上A/B+1就OK了。要提的一点是题干上貌似没说A>B,所以要先交换下。

写完提交,发现WA,当时就慌了,忽然发现当A=0或B=0时会出现/0的RE,修改后提交依然WA。这才发现前两次提交交到A题上了ORZ,不过A题已经AC,不算次数,再次提交K的时候1Y,真是运气好。。查看一下排名60左右,很有希望。

之后看的F,是个染色问题,纪存写了一个DP,发现时间复杂度过大,空间复杂度也过大。后来又写了个压缩路径,空间复杂度能过,但是依然会TLE。之后我拿纪存的程序检验n m k的数字关系,最后写出一条地推公式,然后写了一个用矩阵加速的矩阵快速幂加打表阶乘,可以用o(log(k)log(n)),但是空间复杂度是o(kk),最后他们一致认为会爆,就没实现了。

我们再次转移 到老范看的I,是个模拟IP的问题,a.b.c.d/e,e是子网掩码。题目给出了部分IP,相当于一些IP区域段,需要我们求这些区域段相对全网的补。我们始终无法搞定算法,最后没办法也放弃了。

直到结束都没出第三题。。封榜前是排在107,最后出的结果排在130,拿到了铜牌,还不错,哈哈~