2016.7.13贪心考试总结

今日试题

今天考得不错,270,第3名。事实上我可以有330分的,因为出题人第二题数据太水,后来改了数据,卡掉我60分wwwwwww……

这次贪心考得好,一个原因是题目很简单,而且贪心是我的强项,但是有一些题目没有进一步思考从而拿到满分,实在可惜,下一次我会加强研究,争取每道题都写出正解。

另外这一次我吸取了上一次的教训,每一道题都写了暴力所以即使后面的算法出现了错误,也仍然获得了暴力分数。

今天的题解放在这里了,有一道题我有特殊解法(骗分法),会在下面写出。下面的题目是按我的做题顺序(也是难度顺序)给出的。

3、Team

做题感想

这是一道水题。。。然而我一开始傻逼了,写了个树状数组,复杂度n两个log(二分+树状数组),然后写别的题目去了,结果快结束了,我才发现两个log会炸。最后仔细分析一下,发现决策是单调的,然后给了自己一巴掌把正解写完了。。。这个故事告诉我们,最后一定要检查,既要造极限数据测时间极限,又要写对拍验证正确性,不然很可能跪烂。

4、Farm

做题感想

这题很水,只是放在最后再配上奇葩的图有点吓人,但我一眼秒。

2、Xor

做题感想

这题我傻逼了,一开始写了个暴力,后来想优化,结果优化出了一个随机数据下时间复杂度超级低的枚举算法。这还不算完,本来这样在水水的数据下可以A了,我居然脑残写了个正确性没有保证的线性基,然后。。。A了?

结果出题人一看,你这骗分让你A了,不行,卡死你,然后改数据,卡掉60分。最后发包了,我把那个优化过的枚举测一下,结果。。。A了,真的。

这个故事告诉我们,除非正确概率非常大,不然非正确性算法一定不要交上去!!!宁可交个优化过的暴力,当然遇到这种情况还应该将大小数据分离处理,大数据用非正确算法,小数据暴力,这样可以最大化分数。

骗分方法简介

当我们得出每一条路径到根节点的异或和时,问题转化为有n个数和1个0,求其中任意两数异或和的最大值。本来应该暴力查找任意两个数的异或和,但是我加了如下优化:

首先排序,找到最高位是哪一位,然后第一个数只在最高位是这一位的数中选择,例如:

  • 111001101            a[1]
  • 110100110            a[2]
  • 101101101            a[3]
  • 010010100           a[4]
  • 001010101            a[5]
  • 000111101            a[6]
  • 000100101           a[7]

那么要计算异或和的两个数中那个更大的数在a[1],a[2],a[3]中选。

然后对于这些数中的每一个数都找到其最早的是0的那一位数

如a[1]是第4高位,a[2]是3,a[3]是2,所以就分别找到最高位是这一位的数(二分)

如a[1]--a[6],a[7],a[2]--a[5],a[3]--a[4]

因此只要检验这些组合即可,随机数据期望复杂度O(n^2/900),事实上在n=100000时操作次数约为100000*100000/900≈10^7次,然后就可过了

构造数据可以卡成O(n^2/4),所以还是最好别用,仅以此娱乐。

1、Battle

做题感想

这道题是一道很好的题目,需要经过缜密的思考才能得出正解,而我是经过一些公式的推导,得出了一个错误的贪心方法,最后仔细思考一下就A了。

这告诉我们一定要写拍。。。另外要多思考。。。

不如来评论一发?