THUWC2018游记

前言

  这次THUWC有pretest,非常不错。但还是要对拍。

DAY1

  上午先去报个到。

  下午1:30开始比赛,状态还是很好的。

  开场先看题。

  发现t1是个联赛贪心题,就花了半个小时写完+拍完了。

  然后同时开t2、t3。感觉t2的\(O(n^2)\)挺好写的,但只有\(10\)分,就先放了一下。

  感觉t3很可做,就开始写t3。

  想法很简单,先把\(A\)串的sam建出来,然后每次把\(B\)串在sam上跑了一遍就可以得到答案。

  但是我的做法有点小问题,于是对拍会拍出错,所以就缝缝补补,花了\(4\)个小时写出了一个看起来挺对的sam+exkmp+hash。

  接着发现t2的\(40\)分部分分是个很简单的DP,就花了\(20\)分钟写完了。

  pt分:\(100+40+100=240\)

  出来后听说t3的pretest超水,感觉要炸了。

DAY2

  早上开营仪式,THU又在黑PKU。

  下午因为各种原因延迟了一个小时。

  开场依旧是看题。看到t3时被吓到了。。。这是什么题啊。。。就是一个人工智能的题,给你一堆博客&论文,要你实现一个算法,还要调参。

  我那么弱,就先开前两题吧。

  感觉t2是个DP,推了一下,推出了一个容斥DP的式子,又发现可以分治FFT,于是就花了一个小时把这道题写完了。

  接着看t1。

  先随便猜了几个结论,但都被叉掉了。

  后来找到了一个比较靠谱的结论:

  • 如果一个城市往后走能走到的范围内有油价比当前城市小的城市,就加足够多的油,开到最近的油价比当前城市低的城市。
  • 否则加满油,开到油价最低的城市。
  • 起点和终点要特殊处理。

  于是我写了一个暴力,交了上去,wa了。

  随后检查了一下,发现是暴力写错了,然后改了一下,ac了。

  接下来就是简单的优化部分了。求下一个比这个点油价低的城市可以用线段树,连续跳很多步可以用倍增。

  因为这个东西很多部分组成,我就每写一部分就交一次,最终花了两个小时通过了这道题。

  最后一个小时实在没事干,就开始刚t3。

  因为我太弱了,就选择了最简单的SUSAN。(其实是因为高级算法都需要微积分的知识,但我一点都不会)

  随便对着第一个样例调了一下参,就交上去了。

  pt分:\(100+100+30\)

DAY3

  顺利进入面试。

  因为首字母比较靠后,就等了四个小时。

  等待的过程中有几个学长来讲题了。然后我发现我d1t3是错的(虽然很接近正解)。

  感觉我要凉了。

  他还讲了一些熟练的算法竞赛选手的做题过程,可我一项都没做到。

  接着面试和去年不太一样,增加了一个朗读环节。就是一段英文,要你读+翻译。

  感觉我已经很凉了。

  然后又问我了两个问题,都是数学问题。

  感觉我已经凉了。

  有一道题非常有意思。

  “给你一个rand7(返回\([1,7]\)之间的一个整数),现在要你实现一个rand10,问你要怎么做。你可以先说一个简单的做法。“

  我:那就随机两次,得到一个\([1,49]\)之间的数,如果在\([1,10]\)内,就返回,否则就再随机一次。

  面试官:“还有没有更好的做法?”

  我:“。。。那就在\([1,40]\)之内就返回对应的数,否则继续随机。”

  面试官:”可以。“

  这是什么面试题啊。。。

  中午吃饭时听说进面试保底有THUSC门票,感觉还不错。

  下午讲了一堆奇怪的东西。

  接着就是发协议,顺利滚粗拿到无条件一本约。

总结

  感觉这次考得还可以。

  总共有五题可做,我感觉我过了三题,剩下的两题都拿到了不错的分数。

  剩下的那道不可做题也拿到了一点分。

  这次THUWC必须给好评。

  有pretest,所以做题非常爽,打出了平时改题的感觉。

  时限松的令人感动,不需要任何优化或卡常都可以通过本题。所以想到正解就可以大胆写。

  这两点可以区分开(我这种)暴力卡常选手和熟练的算法竞赛选手。

  最后sk,dcx,我拿到了一等约,zwl,myh拿到了二等约。myh真可怜。

上一篇:DTD验证XML文档


下一篇:【百度地图API】北京周边7日游——图标按路线轨迹行动