差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2022-2023:teams:kunkunkun:2022-nowcoder-4 [2022/07/31 13:36]
sd_ltt [B-2D Internet Angel]
+++ 2022-2023:teams:kunkunkun:2022-nowcoder-4 [2022/08/31 15:19] (当前版本)
purplewonder
@@ 行 14: / 行 14: @@
 \end{aligned}
 $$
-最后答案即为 $\dfrac{\sum A_i}{S}$，$S$ 为区域总面积。
+最后答案即为 $\dfrac{\sum A_i}{S}$，$S$ 为区域总面积。\\
+时间复杂度 $O(n)$
+===== C-Easy Counting Problem =====
+**考虑构造生成函数：**
+$$
+f(x)=\prod_{i=0}^{w-1}\sum_{j=C_i}^{\infty}\frac{x^j}{j!}=\sum_{j=0}^\infty d_jx^j
+$$
+**则对于每一个$n$来说，答案即为$n!d_n$**
+**这样的形式无法求解，由$e^x=\sum_{i=0}^{\infty}\frac{x^i}{i!}$可得**
+$$
+f(x)=\prod_{i=0}^{w-1}(e^x-\sum_{j=0}^{C_i-1}\frac{x^j}{j!})=\sum_{k=0}^{w-1}e^{kx}g_k(x)
+$$
+**w个多项式相乘，直接暴力展开，内部的多项式用NTT去做，可以在$O(w^2clogc)$的时间复杂度内求出$g_k(x)$**
+**对于每次询问$n$，将$e^{kx}$展开为$\sum\limits_{i=0}^\inf \frac{k^i}{i!}x^i$，可以在$O(wc)$的时间复杂度内求出$d_n$**
+**总复杂度为$O(w^2clogc+Qwc)$**
+===== G-Wall Builder I =====
+**题目大意：有一个大矩形，其四边上均有一些射线发射器。射线撞到矩形边框或者其他射线就会停止。你需要选定射线发射器启动的顺序，使得最终切割出来的小矩形中最大的那个尽可能大。**
+**可以发现，最终所求的矩形一定最多由三条射线围成，于是大力分类讨论**
+**枚举底面的关键射线，然后旋转平面四次，可以减少讨论内容**
+**没有射线：当没有发射器时合法**
+**一条射线：**
+**当发射器为底部最左边发射器，且左部无发射器，且在顶部最左边发射器的左边时，计算贡献**
+**当发射器为底部最右边发射器，且右部无发射器，且在顶部最右边发射器的右边时，计算贡献**
+**两条射线**
+**两条射线相互垂直：**
+**当发射器为底部最左边发射器时，与左部最下边发射器计算贡献**
+**当发射器为底部最右边发射器时，与右部最下边发射器计算贡献**
+**两条射线相互平行：将底部和顶部发射器按坐标排序，每次计算相邻发射器所围成的矩形，最左边和最右边的矩形要求左部和右部无发射器**
+**三条射线：**
+**平行的两条射线在同侧：寻找左部最上边和右部最上边的发射器，枚举底部相邻发射器计算贡献，最左边和最右边要求左部和右部只有一个发射器**
+**平行的两条射线在异侧：只在底部最左边和最右边的发射器处可能出现**
+===== J-Counting Fish Again =====
+**如果两次线段的$X+Y$相等，则可能发生合并与拆分操作，直接暴力计算贡献即可**
+**对于每个$X+Y$，都用一个Set维护其中所有的线段**
+**考虑计算一条线段的贡献，如果斜线在鱼的左下角，那么可以直接计算贡献，否则要求鱼不能越过坐标轴**
+**鱼不能越过坐标轴是线性约束，用图形表示的话，答案是三角形被直线割去一部分后的内部格点数**
+**格点数可以用类欧计算，把情况讨论清楚即可**
+===== L-Black Hole =====
+求边长为 $𝑎$ 的凸正 $𝑛$ 面体收缩 $𝑘$ 次后的面数和边长。
+一次收缩定义为作该几何体所有面中心的三维凸包。
+正 $n$ 面体只有五种，每次收缩后有对应关系：$4\rightarrow 4,6\rightarrow 8,8\rightarrow 6,12\rightarrow 20,20\rightarrow 12$\\
+所有的收缩比例都可以通过计算二面角以及正多边形中心到边的距离得到。对任意一个正多面体，用一个平面在恰当的方向去截这个正多面体的一个角，可以得到一个正棱锥，由于每个侧面都是全等的，很容易计算出二面角的三角函数值，稍加运算即可得到收缩比例，即
+$$
+\rightarrow4:\dfrac13,\,
+\rightarrow8:\dfrac{\sqrt{2}}2,\,
+\rightarrow6:\dfrac{\sqrt{2}}3,\,
+\rightarrow20:\dfrac{\sqrt{5}+5}{10},\,
+\rightarrow12:\dfrac{\sqrt{5}+1}6,\,
+$$
+时间复杂度 $O(Tk)$
+===== Replay =====
+N、K、D都是偏签到的题。其中N是高湘一做的，KD是我写的。一共wa了四发。
+A是一个排序+dp。有点类似国王游戏的感觉。也很签就是了。
+之后开始长时间的坐牢。
+H是一个很可做的模拟。但是我读错题目了，于是wa了许久才知道必须拼成一个矩形。
+L是一个很奇怪的题目。最开始猜了一些结论，之后便是无穷无尽的推式子。辛苦罗皓天了。
+M是一个计算几何，照例是高湘一做的。到最后也没有调出来。
+整个比赛有挺多没开的题都挺可做的。只能说做题的时候出现的失误有点多了，也就没有太多时间看其他的题目。
+===== Dirt =====
+N:最开始用的long long，然后就炸精度了。
+K:没有考虑n=1的情况。
+A:最开始排序的方式错了。
+H:题意读错了。此外选择的做法也不是很确信正确的，于是微调了许多，浪费许多罚时和时间。
+L:尝试各种系数坐大牢。

CVBB ACM Team

用户工具

站点工具

差别

页面工具