概述
QAQ 由于并没有数据，而且没有A掉的是提交答案题目，所以并没有修改 QAQ
只能放题解了，代码还没有拿到，不过在清华听了一波习题讲评的安利
第一题 成绩单
先说暴力分
对于单调序列来说最优决策一定是把原序列分成若干段，DP即可
对于单峰序列来说最优决策一定是类似于"汉堡抽肉"一样的东西，即每次从中间抽取一段
然后这样我们就有40分辣
对于n<=20我们可以利用状压DP解决
如果常数写的好听说能过n<=30
这样加起来就有60-70分啦
最后说正解，我们采用区间DP，设f(i,j)表示i->j的最优解的答案
不难发现每个区间的状态只需要确定mx和mn就可以了
不妨枚举mx和mn，这样对于这个区间会分成若干段不能被当前mx和mn包含的区间
显然我们对于这部分区间是不能贪心的，但是我们分完区间之后可以对这些区间在做一次DP
DP就是当前区间是单独来选还是跟之前的区间连着一起选，搞一搞转移就可以了
时间复杂度O(n^5)，常数非常小所以跑的飞快
第二题：
一眼丝薄题，一开始看到空间限制还以为是强行可持久化题目
后来想了想觉得很简单，空间是为了骗你写可持久化树链剖分的
既然题目比较简单就直接说正解了
我们建出一个trie，对于每个可能的询问开一个vector记录
然后每次更新的时候在trie上跑一跑顺便更新vector就可以了
查询的时候我的方法是直接在对应点的v
最后
以上就是复杂魔镜为你收集整理的6.5 THUSC 考试题解的全部内容，希望文章能够帮你解决6.5 THUSC 考试题解所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复