正睿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点有向图，每次加一条边，问强连通分量的个数

最新文章

  1. 消息队列 Kafka 的基本知识及 .NET Core 客户端
  2. 关于FloatingActionButton
  3. js的作业题
  4. php中return的用法实例分析
  5. Java的四种内部类
  6. C++设计模式-Strategy策略模式
  7. 跟我一起云计算（6）——openAPI
  8. 如何调试shell脚本
  9. android 定位的四种方式
  10. iOS：访问地址薄
  11. 【M5】对定制的“类型转换函数”保持警觉
  12. HDU 1150 Machine Schedule (最小覆盖，匈牙利算法)
  13. 问题-Delphi2007跟踪变量时提示“E2171 Variable &#39;APolygon&#39; inaccessible here due to optimization”
  14. WebApi PUT、DELETE请求时出现405 - 不允许用于访问此页的 HTTP 谓词。
  15. struts2框架之文件上传（参考第三天学习笔记）
  16. python中使用双端队列解决回文问题
  17. c#：$用法
  18. JavaScript类继承, 用什么方法好
  19. 各种卷积类型Convolution
  20. pdf2swf 中文乱码问题

热门文章

  1. 问题.spring源码转换为eclipse遇到的问题
  2. 五月月赛 寻宝 exkmp + 主席树
  3. AC自动机 建立nlogn个AC自动机
  4. 最短路算法 Dijkstra 入门
  5. Two Graphs 牛客网暑期ACM多校训练营（第一场）D 图论基础知识 全排列
  6. Relatively Prime Graph CF1009D 暴力 思维
  7. 了解css中px、em、rem的区别并使用Flexible实现vue移动端的适配
  8. js 大量数据优化，通用方法
  9. 那些年，我们误解的 JavaScript 闭包
  10. docker 搭建小型的node开发环境。