【考前冲刺Day5】考试时完全没有思路怎么办?可以暴力吗?可以乱搞吗?

T1 改造二叉树

题面

洛谷上的数据有水,过了不代表正确;

这题还是比较难想的(至少我是这么认为的)

首先如果我们对一颗平衡树进行中序遍历,得到的一个遍历的序列是单调上升的。
于是我们这道题就转化成一个这样的问题:
给一棵二叉树,让它的中序遍历序列变为严格单调上升序列,最少需要多少次修改

《算法竞赛进阶指南(第二版)》的263面提过一个思考题:

把一个序列A变成非严格单调递增的(单调不下降的),至少需要修改多少个数?

比如2 3 1 4 它变成单调不降的就是2 3 3 4,修改一个数,可以发现,A的最长不降子序列是不需要被修改的,而其他的值需要增加或减小来和原来的最长不下降子序列构成一个新的最长不下降子序列,答案就是A的长度减去A的最长不下降子序列的长度。

把一个序列A变成严格单调递增的,至少需要修改多少个数?

如果2 3 1 4 它变成单调递增的就是2 3 4 5,修改两个数,这是因为3和4之间(从自然数的意义上)有0个自然数,而3和4之间(在数列上)有1个自然数,显然,你无法找到一个自然数它既大于3又小于4,我们定义两个数的差值-1为容量,而下标的差值-1我们定义为装载量

显然如果两个数之间能存在严格单调上升的序列仅当容量>=装载量成立,即容量-装载量>=0

设序列\(a\),
容量>=装载量即为\(a_i-a_j\ge i-j\)
移项得\(a_i-i\ge a_j-j\)
由于对于任意项都要成立,所以我们只要用每一项的值减去下标,答案就是长度-最长不降子序列的长度

T2 数字对

这题真的就是乱搞也能过,数据是全随机的,然而考试的时候还是写的是暴力,虽然优化成了\(O(n^3logn)\)但是和\(O(n^4)\)的分数一样.
有两种乱搞方法,一种是枚举每个点向两边拓展,另一种是枚举两个端点(这种方法等下会放代码),前者意外跑的很快...  
第二种乱搞方法是上届学长留下来的:   


对于每一个特殊区间,它的特殊点一定满足的条件是GCD=最小值
于是我们可以维护区间的GCD和最小值,
区间长度我们也可以不用暴力枚举,直接二分即可.
此时我们只二分出来了最大的长度,要想知道具体的答案,还得根据算出来的长度扫一遍数组,合法性的判定和上面是一样的  

发表评论

电子邮件地址不会被公开。 必填项已用*标注