差别

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

--- 2022-2023:teams:kunkunkun:2022-nowcoder-4 [2022/07/31 19:28]
sd_ltt
+++ 2022-2023:teams:kunkunkun:2022-nowcoder-4 [2022/08/31 15:19] (当前版本)
purplewonder
@@ 行 16: / 行 16: @@
 最后答案即为 $\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 =====
 求边长为 $𝑎$ 的凸正 $𝑛$ 面体收缩 $𝑘$ 次后的面数和边长。
@@ 行 31: / 行 90: @@
 时间复杂度 $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

用户工具

站点工具

差别

页面工具