noip 模拟 (20.10.7)

October 07, 2020

2020   ·   OI   Chinese     ·   pre-university  

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

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) 了.