2016.8.6考试总结

今日试题

今天考的是学军的题目……向总说很难,但是事实上不难,暴力分给的很多,就算是在向总的老爷机上还是拿到了170分,Rank 1

好爽好爽好爽!!!好爽好爽好爽!!!

但事实上由于向总机子太烂,卡掉了他们好多暴力分,所以我不是软壳一……

但没关系啦!!!

题解

1、Sequence

很水的数学题,直接推出通项公式,然后加几个特判就好了。

对于xn=axn-1+b这种类型的递推式,用添加常数法构建新的等比数列就能求得通项公式,求出来以后就好办了。

2、Words

看起来很神的一道题,写了个暴力加了个特判骗分

结果呢???20分……

然后我去掉特判……

80分,果然我还是太年轻了。

这道题的正解是对于n较小保利做,n较大则m较小,然后去重做。

还有一个DP做法看起来很神,但是我不会……


补:后来我发现我m=1的情况WA了,然后发现是因为case没加break

慎用case,记得break!!!教训+1

3、Distribution

搜索大法好!!!我就写了个搜索,然后输出方案,结果发现——最优方案中一个子树分得的编号是连续的!!!

非常神奇,然后我又搜了好几组10个点的数据,都是这样的规律,然后我就开始贪心,我的贪心策略是这样的:

每次在子树中找到一个点数最少的,然后进去dfs,复杂度nlogn,常数小。10分钟写完。

然后我TM发现居然有1百万……可以,好虚……

然后我就做第二题……做完后回来检查,诶诶诶诶诶?1百万……爆栈啊!!

然后加了个手写栈。

拿了50分,如果不是向总机子太差我能拿70

正解好像是Link-Cut-Tree然而我不会……


检查的时候需要多注意一点——是否会爆栈。

补:还要记得switch-case要加break

6 thoughts on “2016.8.6考试总结

  1. 我想知道第三题不写动态的怎么70分,第二题暴力怎么80分、、、
    第三题静态不是只有50分么、、、、

    1. %%%居然有人评论我了,好感动。不过,您是……?
      这天的题目我都快忘记了……
      赶快回去看了一下题目,第二题80分是好几个暴力拼凑起来的,设定一个n的阀值,我好像设的2500,n小于这个值就暴力比较,不然就骗,这样的话由于数据不强,所以可以骗到80分(不是所有的点n都很大)。
      第三题70分好像没错,m=1暴力做,m=0,nlogn做确实有70分啊。
      由于我也不太记得了,第二题改成80分到底改了哪里,所以可能讲不太清楚,还有疑问可以再回复。
      最后,多帮我拉点访问量呗(卖萌σ=ω=σ)

      1. 这动态修改的居然可以暴力多20分啊qwq,好劲啊
        第二题小于的部分子集容斥更优

    1. QAQ我不相信的~~~ʅฺ(・ω・。)ʃฺ??
      222.184.103.228江苏省淮安市 电信
      我把题目都删掉了(版权问题),你还有题目,不可能是鶸学校的~
      ✧(๑•̀ㅂ•́)و✧

不如来评论一发?