noip 模拟 (20.10.7)

下午又是讲一些神神奇奇的图论,从

Codeforces infrastructure is temporarily unavailable, we are working on fixing it.

开始我就意识到估计又要是一个一事无成的下午了(昨天博弈论做了一半就做不下去了哈哈) 所以还是看上午没做完的题目吧

T1 倾斜的线

画图,不难发现,对于每一组点$(x_i,y_i)$
有$y_i=kx_i+b_i (k=\frac{p}{q})$
对于截距$b_i$排序后,所取的两个点是连续的

T2 扭动的树

根据二叉搜索树的性质

$i$在$j$的左子树上$\Rightarrow key_i<key_j$
$i$在$j$的右子树上$\Rightarrow key_i>key_j$

因此对$key$进行排序,那么就转化为了一个 区间dp 问题

  • 50%

$f_{i,j,k}$表示对于区间$[i,j],root=k(k \in [i,j])$的$sum_{max}$
枚举合法的lson,rson

$f_{i,j,k}=max{f_{i,k-1,lson}}+max{f_{k+1,j,rson}}+sum_{i,j}$

$O(n^4)$

  • 70%

特判$gcd^n_{i=1},f_{i,j}=max{f_{i,k-1}+f_{k+1,j}}$
比赛的时候就想到这里

  • 100%

不难发现,每一个区间$[i,j]$的根节点只有可能是$i$或$j$
那么令$f_{i,j,0/1}$对应该区间的两个根节点,便不需要向下枚举根节点了

$f_{i,j,0}=max{f_{i,k-1,1}+f_{k+1,j,0}}+sum_{i,j}(gcd_{i-1,k}\neq 1)$ > $f_{i,j,1}=max{f_{i,k-1,1}+f_{k+1,j,0}}+sum_{i,j}(gcd_{j+1,k}\neq 1)$

$O(n^3)$

T3 打铁的匠

比赛的时候打了暴力,50%

标程没有看懂,题解貌似是权值线段树
打完再来更

T4 分宿舍

关押罪犯


写作业(shui jiao)了。




Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • 数据结构复健(一):字符串算法
  • 实现一个 std::vector
  • 数据结构复健(四):树链剖分
  • 2022 届湖北省二十一所重点中学高三第三次联考数学试题
  • 2022 届湖北省二十一所重点中学高三第三次联考数学参考答案与评分细则