https://wiki.cvbbacm.com/ 2026-04-30T02:33:41+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-09-17T17:17:55+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:qxforever:circleunion&rev=1600334275&do=diff 圆的面积并问题和一些拓展 问题 给 $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… text/html 2020-05-09T12:12:08+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:qxforever:codeforces_round_638_div._2&rev=1588997528&do=diff Codeforces Round #638 (Div.2) F 题意 有一个长度为 $n$ 的排列，第 $i$ 个位置上的数在区间 $[l_i,r_i]$ 内，问是否有唯一满足条件的排列。输出方案，如果有多个，输出 $2$ 个。 text/html 2020-06-29T07:54:37+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:qxforever:geometryproblems&rev=1593388477&do=diff 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$… text/html 2021-01-31T17:38:36+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:qxforever:practice2021.1&rev=1612085916&do=diff 做题记录 可能包含一些剧透？ 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$… text/html 2020-05-10T18:26:43+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:qxforever:qkoi_r1&rev=1589106403&do=diff 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<j$ 以及 $i\geq j$ 的情况，最后推出式子 $\lfloor \frac{n-1}{m} \rfloor-\lfloor \frac{n-1}{m+1}\rfloor+\lfloor \frac{n}{m} \rfloor-\lfloor \frac{n}{m+1} \rfloor$$n$$m$$0$$1$$t$$v$$v$$t+1$$(a,b,w)$$a=v$$b=v$$t+w$$k$$(t_i,v_i)$$t_i$$v_i$$n\leq 200$$k\leq 5000$$t\leq 10^9$$f[i]$$i$$O(n^3+k^2)$$O(n^3+n\times k)$$n$$\sum w_i\…