CVBB ACM Team 2020-2021:teams:i_dont_know_png:qxforever

2020-2021:teams:i_dont_know_png:qxforever:circleunion

Anonymous (anonymous@undisclosed.example.com) — 2020-09-17T17:17:55+0800

圆的面积并问题和一些拓展问题给 $N$ 个圆，求其面积并。 $N \le 1000$ 解法 1 扫描线 + 辛普森积分。这里被积函数 $f(t)$ 为 $x=t$ 这条直线被圆覆盖的长度。在实现时考虑辛普森积分的特点，需要预处理出圆在 $x$$Circle(x_0,y_0,r)$$\theta_1$$\theta_2$$$ \begin{eqnarray}S&=&\iint_{D}1 dx dy\\&=&\frac{1}{2}\oint_{C}xdy-ydx\\&=&\frac{1}{2}\int_{\theta_1}^{\theta_2} (x_0+r\cdot cos\theta)d(y_0+r\cdot sin\theta)-(y_0+r\cdot sin\theta)d(x_0+r\cdot cos\theta)\\&=&\frac{r}{2}\int_{\theta_1}^{\theta_2} [(x_0+r\cdot cos\theta)\cdot cos\theta +(y_0+r\cdot sin\theta)\cdot sin\theta ]d\the…

2020-2021:teams:i_dont_know_png:qxforever:codeforces_round_638_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-05-09T12:12:08+0800

Codeforces Round #638 (Div.2) F 题意有一个长度为 $n$ 的排列，第 $i$ 个位置上的数在区间 $[l_i,r_i]$ 内，问是否有唯一满足条件的排列。输出方案，如果有多个，输出 $2$ 个。

2020-2021:teams:i_dont_know_png:qxforever:geometryproblems

Anonymous (anonymous@undisclosed.example.com) — 2020-06-29T07:54:37+0800

BUAA Spring Training 14 - B 链接题意给定二维平面上的 $n$ 个点，添加一个新点，使得在这 $n+1$ 个点的凸包的边界上的旧点数量最少，且新点必须在凸包上。$n\le 10^5$ 解题思路在初始的 $n$ 个点的凸包上旋转卡壳，答案即为两个对踵点之间点的数量的最小值。但不好处理存在多点共线的情况。$n$$r$$n\le 10$$r\le 100$$0$$0$$f(x)$$0$$0$$n$$n\le1000$$n\times (n-1)$$2$$n$$n\le 1000$$\vert x\vert,\vert y\vert \le 10^9$$\binom{n-1}{3}$$O(n^2\log n)$$10^9$…

2020-2021:teams:i_dont_know_png:qxforever:practice2021.1

Anonymous (anonymous@undisclosed.example.com) — 2021-01-31T17:38:36+0800

做题记录可能包含一些剧透？ 1477 C - Nezzar and Nice Beatmap link tag : 构造题目大意：给 $n$ 个二维平面上的点，求一个排列使得 $P$ 对任意 $i$ 有 $\angle{P_iP_{i + 1}P_{i + 2}}$ 为锐角。$n \le 5000$ 。题解：每次从没有使用过的点中选择离当前点距离最远的点，作为下一个点即可。难以想到的简单的初中几何原理。$n$$k$$ n \le 10 ^ 5$$[l_1, r_1], [l_2, r_2]$$n$$a$$n \le 2 \times 10 ^5, a_i \in [1, A]$$A \le 100$$A \le n$$f$$f$$O(n)$$cnt_f - cnt_i$$k$$T$$f$$O(nk + n ^ 2 / k)$$n$$a$$a_i, a_{i+1}$$-(a_i + a_{i + 1})$$n - 1$$n \le 2 \times 10 ^ 5$$a_i$$+a_i$$-a_i$$(n + 负号个数) \mod 3 == 1$$a_i$…

2020-2021:teams:i_dont_know_png:qxforever:qkoi_r1

Anonymous (anonymous@undisclosed.example.com) — 2020-05-10T18:26:43+0800

Quark Round 1 A 题意给定 $n,m$ 求满足 $i+j=n$ 且 $\lfloor i/j\rfloor+\lceil j/i\rceil=m$ 的正整数对 $(i,j)$ 的对数。有 $10^5$ 组数据。$n,m\leq 10^7$ 。题解将 $j=n-i$ 带入第二个式子后发现是先减后增的。在极值点两侧分别二分即可。或者分别讨论 $i