正睿OI DAY3 杂题选讲

时间:2022-03-05 11:34:26

正睿OI DAY3 杂题选讲

CodeChef MSTONES

n个点,可以构造7条直线使得每个点都在直线上,找到一条直线使得上面的点最多

  1. 随机化算法,check到答案的概率为\(1/49\)
    1. \(n\leq k^2\) 暴力
    2. \(n\geq k^2\),找点x,求直线l经过x,且点数最多,点数\(\geq k+1\),递归,否则再找一个

One Point Nine Nine

现在平面上有\(n\)个点,已知有一个常数\(D\)。
任意两点的距离要么\(\leq D\),要么\(\geq 1.99D\)
请问有多少点集的子集,满足任意两点距离\(\geq1.99D,n\leq 1000\)

每个缩完的点的度数至多为2,因为要么一堆点聚在一起,要么距离很远,三个点的角度接近\(180°\)

那么对于每个连通分量讨论环/链dp

GYM 100162K

一棵树,两个操作

  1. 加叶子
  2. 询问一些节点两两lca

答案显然是这些节点按dfs序排序后两两lca,

所以可以拿splay维护dfs序

或者按时间分块,\(\sqrt n\) 次重构树

GYM100739H

给定连通图中每个点的度数,求满足条件的图

考虑构造生成树,树中每个节点有一个度数,分析原度数可以求出一个范围

然后分配一下

排列题

给定n和a,求\(\forall i,i+a-n<p_i<i+a\)的排列个数

zbl,wsl

cw某大爷切过~

FIBTREE

给定一个有 \(n\) 个节点,初始点权都为 \(0\) 的无根树。

  现在让你处理 \(m\) 次操作,有下面 \(4\) 种类型

  1. 链上加斐波那契数列,其中 f[1]=1,f[2]=1,f[3]=2,⋯f[1]=1,f[2]=1,f[3]=2,⋯
  2. 链上求和
  3. 给定树根,子树求和
  4. 回到第 x 次询问时的状态

强制在线

  1. 用公式(爆搜)求出\(\sqrt5\) 的二次剩余,套进斐波那契公式里面得到两个等比数列,树剖处理
  2. 树剖处理
  3. 讨论一下询问子树和当前根在定了根的树下的关系
  4. 可持久化一下(有什么出题的必要吗kora!

后面的题咕了吧,之后补

CEOI2016 Kangaroo

[JSOI2016]独特的树叶

树同构,hash

CF603E

lct

link cut digraph

n点有向图,每次加一条边,问强连通分量的个数