牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共6篇）

省选模拟4 题解

A. 点点的圈圈因为题中保证的特殊性质，容易发现圆之间的关系形成树形结构。对于每棵子树，选择树的根或者累计所有子树的答案。问题在于建图，容易发现这个可以用KDTree优化。考虑将所有的点建在KDTree上。用每个点的圆覆盖KDTree，当完全覆盖时直接塞入对应点的vector中。...

结论题 set 扫描线 lct 主席树线段树 tarjan KD-Tree 计算几何

2020-01-12

0 875

省选模拟22 题解

A. 遮天蔽日学习了计算几何相关的很多新技巧。求过一点$P$，圆$O$的切线：通过两点距离、半径，用反三角函数可以解得一个角度，然后就可以算了。求直线$PQ$，与圆$O$的交点：作点$O$关于$PQ$的垂线，通过半径和垂线长度，可以算得垂足与交点的距离，然后就可以算了。求多边形的重心...

回文自动机网络流 manacher 计算几何

2020-02-09

0 388

省选模拟38 题解

A. Inverse 似乎这类问题的套路都是考虑每一个点对。然后考虑一个 dp 。设 $f_{k,i,j}$ 表示考虑后 $k$ 轮，最终 $i$ 在 $j$ 左面的方案数。对于每个 dp 值可以简单枚举翻转区间， $O(n^2)$ 转移。然后发现这个玩意可以优化，如果枚举翻转区间...

分块单调指针差分 dp 计算几何平衡树凸包

2020-03-05

0 428

省选模拟72 题解

A. 新访问计划 B. 计算几何其实题中这个常数 $c$ 的定义很奇怪，所以大概可以猜想，对于所有的情况都是有解的。然后有这样一个做法，考虑弄一条直线出来，然后把 $n$ 条线段的对应端点都映射到这条直线上。比如坐标系上的点 $(x,y)$ 映射到倾斜角为 $a...

矩阵树定理计算几何分治二分图网络流线性代数凸优化

2020-04-16

0 405

noi前第十场题解

A. 集合划分可以直接写出一个简单的 \(dp\)，然后发现这个 \(dp\) 的信息只需要存 \(A\) 集合选的个数和末尾选的哪个集合。不妨写成一个多项式，那么我们只关心边界的情况。所以写一个分治 \(FFT\) 即可。 B. ACT4！⽆限回转！考虑对于每条边，枚举所有能到达...

计算几何分治多项式 dp 辛普森积分

2020-07-22

0 405

noi前第十一场题解

##A. 数容易发现答案是 \(f_m=\sum \limits_{i=0}^n a_i[x^i](1-x)^m(1+x)^{n-m}\) 然后就有一个显然的 \(O(n^2)\) 做法，并不会优化。一个优化的方法是，考虑 \((1-x)\) 和 \((1+x)\) 相加为 $2$。所以可以将...

组合计数计算几何多项式 dp

2020-07-24

0 501