差别

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

--- 2022-2023:teams:kunkunkun:2022-nowcoder-2 [2022/07/31 13:03]
sd_ltt
+++ 2022-2023:teams:kunkunkun:2022-nowcoder-2 [2022/08/31 14:30] (当前版本)
purplewonder
@@ 行 1: / 行 1: @@
-====== 2022 牛客暑期多校训练营4 ======
+====== 2022 牛客暑期多校训练营2 ======
-===== A =====
+===== A-Falfa with Polygon =====
+**题目大意：给定一个$n$个点的凸包，要求从中选出$k$个点构成一个子凸包，求子凸包的最大周长**
-===== B =====
+**发现对于子凸包来说，只有一条边是从大标号点连向小标号点，这一条边容易单独考虑，而对于剩下的$k-1$条边可以用DP处理**
+**设$E_m[i][j]$表示从$i$点经过$m$条边到达$j$的最长距离，容易得到转移方程**
+$$
+E_{a+b}[i][j]=\max\limits_{i\leq k\leq j}(E_a[i][k],E_b[k][j])
+$$
+**该转移方程可以使用矩阵快速幂优化，复杂度$O(n^3logn)$**
+**上述转移方程是经典区间DP，猜想其具有决策单调性**
+**设最优的$E[i][j]$由$k=V[i][j]$转移而来，对$V[i][j]$打表，若矩阵的每一行每一列都单调，则满足决策单调性**
+**根据决策单调性的结论，记录每一次转移的$V[i][j]$，直接将转移方程中的$i\leq k\leq j$改为$P[i][j-1]\leq k\leq P[i+1][j]$即可优化至$O(n^2logn)$**
+===== B-light =====
+**题目大意：给定一个有厚度的凸多边形围墙和一个点光源，问围墙内有多少面积有光**
+**已知凸包外围，利用半平面交可以得到凸包内围**
+**若只有凸包内围顶部，将点光源与凸包内围顶部连线，与地面交成一个凸包，则这个凸包为照亮区域**
+**接着考虑凸包内围底部，实际照亮区域为凸包内围底部与照亮区域的交，半平面交可以解决**
+**可以提前处理一些特殊情况，比如点光源的高度比围墙低**
+===== E-Falfa with Substring =====
+**对于所有的$0\leq i\leq n$，求长度为n的字符串中恰好出现了i个”bit” 子串的字符串数量**
+**考虑容斥。首先容易想到，先在字符串中确定一些"bit"，然后其他位置任选，于是设$G[i]$表示在字符串中先确定$i$个"bit"，其他位置任意的方案数**
+**利用隔板法以及一些组合技巧，可以得到**
+$$
+G[i]=C_{n-2i}^i*26^{n-3i}
+$$
+**设字符串中恰有$i$个“bit”的方案数为$F[i]$，利用二项式反演可以得到**
+$$
+F[i]=\sum_{j=k}^{n/3}(-1)^{j-k}C_j^kG[j]
+$$
+**这是经典$NTT$形式，将组合数拆开，构造系数即可$NTT$优化**
+===== I-let fat tension =====
+移项预处理矩阵即可\\
+时间复杂度 $O(nkd)$
+===== J-Link with Arithmetic Progression =====
+最小二乘法
+$$
+\hat{a}=\dfrac{\sum_{i-1}^n(x-\bar x)(y-\bar y)}{\sum_{i=1}^n(x-\bar x)^2}\\
+\hat b = \bar y - \hat a\bar x
+$$
+时间复杂度 $O(n)$
+===== Replay =====
+最开始开的是G。基本属于签到题了。
+最开始大家想到的是一个显而易见的分成两半的做法，但是显然是不正确的。
+后来很快想到了根号的写法，然后很快就过了。
+之后开的是K。高湘一看出来是一个dp，并且看起来不怎么难写的样子。后来也挺快写完了。
+D题是一个一眼看出思路的取ln+spfa判负环。
+最开始是我写的。但是的确对于spfa判负环这个知识点太久没有写过，有些生疏，导致交了许多发wa，以为是精度问题。
+后来高湘一重构了一份代码才过。
+期间罗皓天看出来I题是一个最小二乘法，随便写了写就过了。
+其实I题感觉上去挺诡异的，最开始一直想着不会是那么简单的最小二乘法就能搞完，考虑了一个二元二次函数求最小值点的做法，但是最小二乘法就过了，的确是意外之喜。
+C题是一个nim游戏的拓展。问题分为了两部分，两部分都要猜结论，并且我还不太会证明结论。所以最开始猜的结论wa掉之后就很慌。最后实际证明正确答案应该是把我第一次交的第一部分和我第三次交的第二部分整合起来。但是考试的时候不太敢再交了，于是就亏出一道题。
+H题也算是比较亏的一道题。大致是一个区间加+求最大值的操作。首先是没有考虑清楚题目，便直接莽了一个线段树上去。后来考虑清楚才去写差分。其次是在统计楼层的时候，对于那些只需要坐一楼的情况，没有分辨是上楼还是下楼，直到比赛结束才想起来判断。也因此又亏了一道题。
+===== Dirt =====
+G题第一发：交了一个错解，即二分的解。
+G题第二发：怀疑是行末空格的问题，于是又交了发错解。
+D题第一发：交了一个错误的spfa判负环方法。
+D题第二发：以为是精度问题，换成long double又交了一发。
+D题第三发：发现有一个地方忘了改，换成long double又交了一发。
+D题第四发：以为是精度问题，调了下eps又交了一发。
+D题第五发：是高湘一写的比较正确的解。但是空间开小了。
+D题第六发：是高湘一写的比较正确的解。但是没看出来空间开小了。
+C题第一发：第二种情况判错了。
+C题第二发：第二种情况判错了。顺带把第一种情况也改错了。
+C题第三发：把第二种情况改对了。但是第一种情况还是错的。
+H题第一发：少判断一种情况（见replay）
+H题第二发：愣是没看出来改了哪，反正是又交了一发。
+H题第三发：愣是没看出来改了哪，反正是又交了一发。

CVBB ACM Team

用户工具

站点工具

差别

页面工具