2016.7.15分治考试总结

今日试题

果然还是考炸了,150……分治我以前都没往难的学。今天我把能打的暴力都打了……毕竟我昨天才学的树分治……今天后面三题思维难度都很大,第二题代码难度也很大。只是有些分数没拿到还是有点可惜,下面我只会总结我还能拿分的部分,链分治什么的组合数学的下午没事就学吧。

1、sequence

这道题是昨天上课讲的原题,我上课还是很认真的,因此半小时AC。

没什么好讲的就是树状数组。

2、light

原题是SPOJ上的QTREE IV,正解是链分治,我写的暴力30分,然而60分的DP我是会做的只是没想到……哭死

DP求树的直径我一直都会,这道题只要O(n)地DP m次就好了,如果一个点被开灯了,就讲dp[now][0]设成-INF这样就不会计入答案了。

我蠢死了,以后还是要多想想,说不定就多点分呢?

3、matrix

正解是分治,然而我写的暴力悬线法,事实上有人单调栈骗分过了90……暴力也没写好,常数写丑了,只有10分,本来可以30分的。。。我蠢死了,事实上正解多想一想,往分治上套很容易想出来的。。。

正解就是把矩形从中间切成两半,统计过中线的,由于每次只修改一个点,因此每次只要修改一条水平线,每次操作是O(nlogn),总复杂度O(n^2logn),可过。。。

4、tree

出题人声称这是道水题,然而全场最高分20……

完全不会做,贪心骗10分……

正解很难想到,也很蠢,就是二分地给所有白边加上一个数来限制百变的数量,得到正好为ned条白边的方案时输出。这谁想得到啊,太非主流了吧……

所以跪烂了,就是这样,不过还是基本尽力了……

不如来评论一发?