2016.7.22 数据结构考试总结

今日试题

今天考数据结构,然后只考了一道数据结构……晕死……然后最后一题我做过,白骗100分,本来可以190准虐场,可惜第一题打错文件名,然后只有130,跪烂!!!下次再不能打错文件名了……

今天的题目不算很难,有些题目多想想就会正解了,但是我的速度还是太慢,要多练习数据结构题,多熟悉模板,才能取得进步。

今日题解

1、landlords

鬼畜!第一题打了个表30分,推了个30分的斐波那契数列,本来稳稳的60分到手了,然而……

landlords-->landlord20150725074121_WLRiw.thumb.224_0

60分再见,然后瞬间被踩死……我也是醉了,这个故事告诉我们一定要多看几遍题目,切忌得意忘形忘记检查文件名……

正解是暴力构矩阵+快速幂……听完后觉得……

964c5979155f4ebb348d10be3d6f600d

2、sqr

一样看出网格图,然后证明最大点是a[n]最小点事a[1],然后拿走30分,然后就没往后想了,事实上再多想想就可以证明,全图一定只有两种点权,然后求最小割,用平面图转对偶图跑dijkstra即可。

不过没时间了,因此还是要加快速的,并且不要在一道题目上花费过多的时间。

3、forest

这就是遥犇说的送分题?送到你家里去了……

两眼一抹黑,根本不会做,然后没时间写暴力了……于是不了了之。

下次一定要抓紧时间写暴力。

正解是用替罪羊树处理不同森林的权值关系,然后加入线段树中进行统计,即可AC

4、gamble

为什么数据结构的题目能跟数学题目撞车啊???

我晕,然后怒A

然而太得意忘形结果第一题文件名写错了……友尽……

正解:黑板染色+二分图匹配

不如来评论一发?