ACM校赛总结

这两天突然ddl堆到一块,一直在赶ddl, 直到现在还没有搞完。。。但是还是要抽空写一篇总结出来的(毕竟也这么长时间没更博客了)

题目列表:http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=363

上手先看A题,看了半天才看懂题意,发现是个水题,队友写了一发加了一点点小trick就过了。

B题意思是给一棵树,可以从节点1到任意一个节点增加一条边。定义d(1,v)为1到v的最短路径长度(无权),求最小的\sum d(1, v)

这种题显然是要先跳过的对吧。。于是就开始看后面的。

C也是个水题,不过有点麻烦。队友敲的过程中看到好多人过了J题,于是看了眼J题,发现是比A还水的水题。于是等队友过了C之后上手搞掉了J。这样开场的三个签到题就做完了。

D题是一个很难的构造,看了一眼就放弃了,并且直到终场也没再去想这道题。

这时候我们注意到了F题,好像还比较可做的一道题。大意是给一些区间,选最多的区间使得没有一个点属于选中的三个及以上的区间内。开始我们想按左端点排序,然后扫一遍,过程中选与当前区间相交的右端点最小的区间。但是好像细节越想越多,我觉得我们可能思路错了,队友码了一发也没对。于是我翻了翻书 ,看看有没有类似的题(误), 结果还真找到了一道,并且贪心策略很简单,只要每次在能选的范围内选右端点最小的就行了。我猜这个贪心策略同样适用于这道题,于是上手写了一发,第一次输出的时候忘了排序WA了,第二次就过了。

然后某大腿搞了半天E,改了几次居然过了orz。我连题是什么都没太懂,这大腿抱的真实在。

之后搞G。题意很长,不复述了。先想到暴力枚举,时间不够。我想到把每一行能匹配到的行号记下来,最后一次dfs看看有没有符合要求的排列。队友给我说了他的做法但我没太懂,于是他就上手去敲了,然后1Aorz。。赛后听到也有人用dfs过了,心里舒坦了点。。

然后又是某大腿,在我们不知道I题是个啥玩意的情况下就过了。再次orz。。。

没看H题纯粹是被那个数学形式吓到了。但队友看过之后告诉我题意后我们发现就是个水题。但是写完交了一发居然没过。之后我们各种构造数据,都没啥错。最后我们觉得可能是数据里面有0,我们的程序在有0的时候会gg,处理了一发真的就过了(噗,说好的没有0呢)。

最后一直在搞B了。我提供了一个idea,就是推出路径从(1,v)转移到(1,w)(w\in(son(v)))的公式,于是两遍dfs就搞定了。不过细节太多,我很长时间没码代码码力不够,就交给队友了,但到终场也没调试出来(被H坑了太多时间),不过也不算遗憾了。总之这场比赛就是抱大腿拿名次的比赛。。。。我果然还是太弱了,该多刷刷题了(但是最近时间真的紧啊orz还有机器学习这个大坑,不知道能不能挤得出时间。。)

暂时就写这么多了,很晚了,电脑也快没电,明天想起来再补一些什么吧

2017-04-10 02-14-08屏幕截图

补一波比赛的照片(拍摄:钱已澄)
8

1 2 3 4 5 6 7

 

1 条思考于 “ACM校赛总结

发表评论

电子邮件地址不会被公开。

*