3.5测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-------------------------------------------------------------------
题面大概可以在SuperOj上找到
-------------------------------------------------------------------
T1：
神奇的题...
数据随机是一个很重要的条件
首先不难发现最优答案的转折点的行（列)一定是单调不上升或者不下降序列（实际上是大于等于或者小于等于前面每一个数）
因此可以从A或者B中找一个含第一个点的单调不上升或者不下降子序列来组成的新的矩阵上跑暴力DP
然后复杂度就是O（单调序列的长度^2)
然后单调队列的长度是多少呢，因为是随机的，所以可以来算一下期望
第i个数要大于前面每一个数，概率是1/i
期望长度是概率相加
1/1+1/2+...+1/n=lg(n)
所以期望长度是lg(n)的，复杂度O(T*lg^2(n))
-------------------------------------------------------------------
T2:
首先因为只有一个木棍可以分成带实数的两个部分，所以坑定三边有一边长度是整数
另外还可以知道最优解一定用上了所有木棍（用反证法：如果最优解没有用完木棍，那么可以把没用的加到和墙平行的一边上，面积更大）
为了方便，设长度为整数的一边长度是x，总长是s
讨论一下：
如果这个边是和墙平行的边，那么面积是x*(s-x)，这是个二次函数，最大值在x=s/2处
如果这个边是和墙平行的边，那么面积是x*((s-x)/2)，这是个二次函数，最大值在x=s/4处
对于每一种情况算一个最优解出来比一下就好
现在假设某个情况最优解是x=x'
那么只需要选一些木棍让他们的和最接近x'
这个是np的，考虑用meet-in-middle算法（我第一次知道这个算法还有名字...)
把木棍分成两部分，一部分2^(n/2)枚举一下所有可能长度，放到表里面
另一部分2^(n/2)枚举一下所有可能长度，在表里面询问和他加起来最接近aim的（可以二分查找）
复杂度O(n*(2^(n/2)))
-------------------------------------------------------------------
T3:
首先把每天按边长排序
每一次就是把所有还不在一个连通块内的点搞成一个连通块
首先，如果没有限制的话，就可以把连通的点缩成一个点（儿子缩向父亲），用并查集维护一下
但是可能有限制，有限制的话，可能在图B上连通的点在图A上不是连通的
所以可以维护两个并查集，第一个把图B上连通的点缩成一个点，第二个把图A上连通且图B上连通的点缩成一个点
然后就可以暴力维护，每次跳第二个并查集
如果访问到一个点就给他记一个代价，那么如果没有限制，那么每个点最多一个代价
在有限制时，某个点代价增加1的条件是要想把两个连通块合并时，连接这两个连通块的限制数是这两个连通块的大小，这个值最少为1，因为只有Q个限制，因此因为限制产生的代价最多Q个
因此复杂度O(α*(M+Q))
-------------------------------------------------------------------
话说最近赶脚做题的时候思路很匮乏
这次的题，第一题比较神奇不说，T2和T3感觉还是能想出来的，至少应该接近达到标算
但是我连T2的3^n暴力都没想出来，T3树链剖分到死，结果50分没有限制的都没想出来...
感觉现在做题，还不如以前什么都不会的时候天天乱搞得分率高
脑洞还是要大一点...
-------------------------------------------------------------------
评论 (0)
