差别

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

--- 2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_2 [2020/07/17 22:13]
maxdumbledore [G. Greater And Greater]
+++ 2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_2 [2020/07/24 10:41] (当前版本)
hardict [lpy]
@@ 行 9: / 行 9: @@
 主要还是思维问题，EG两题一直在xsy卡题的时候思考，还是没有想出来。另外以后看一道题要把内容共享给队友，节省看题时间
 ===== lpy  =====
+题目最好全看完，没有思路可以去看看没看过的题目，不要盲目跟榜
+要与队友多分享题目内容，尽量覆盖所有题
+E题这种思维+性质题还需要加强
 ===== xsy  =====
+题目一定要及时看，比如B题H题看完没多久就做出来了，但是看得很晚，还好极限写出来了H。
+要注意随时关注榜单，卡题的时候视情况去开一下其他的题。
+要随时与队友进行沟通。
 ====== 题解  ======
-===== A. XXXX =====
+===== A. All with Pairs =====
-...
-by cmx
+这题比赛的时候竟然没想出来，奔着后缀数组一去不回....这种前缀等于后缀的应该自然的往KMP那边联想。
+首先前缀总数和后缀总数都是O(n)级别的，可以使用哈希快速统计个数，比如计数后缀然后枚举前缀，但是答案可能会有重复。
+比如两个"aba"，前缀"a"和"aba"都会被算到，但是可以发现他们一定满足短的那个是长的那个的一个后缀，很容易想到是KMP中的next数组就是解决的这个问题。
+于是最后从前往后使用$cnt[next[i]] = cnt[next[i]] - cnt[i]$去重即可。
+by MountVoom
+===== B. Boundary =====
+所有的圆都会过原点$O$，如果点$A, B, O$三点共圆，那么$OA, OB$的中垂线会相交于圆心。
+于是求出所有点与原点连线的中垂线并两两求交点，最后统计交点个数，出现最多的点对应的圆上有最多的点。
+需要注意的是，一个圆上如果有$n$个点，那么交点的个数为$\frac{n(n-1)}{2}$
+复杂度为$O(n^2\log n)$
+by MountVoom
+===== D. Duration =====
+水题，求出从$00:00:00$到两个时刻的秒数作差即可。
+by MountVoom
+===== F ======
+求出矩阵，然后行列分别一次单调队列
+就可以求出以$(i,j)$为左上角,$(i+K,j+K)$为右下角的正方形的最大值
+求矩阵时可以利用gcd优化($(a,b)=(a+b,a)=(a,b+a)$)，但我优化了炸内存，没有优化过了
+by Hardict
+===== H. Happy Triangle =====
+题意是维护一个多重集，支持插入，删除和询问是否能在集合中找到两个数$a, b$与给定的$x$够成三角形。
+分情况讨论：
+$x$是三角形最长边，那么从比它小的数中选出两个最大的进行判断即可。
+$x$是三角形第二长的边，那么从比它小的数中选一个最大的，从比它大的数中选一个最小的进行判断即可。
+以上两种情况都可以用一个可重集直接维护。
+$x$是三角形的最短边，此时从比它大的数中找两个数，且这两个数的差尽可能小，那么我们要找的两个数在多重集中一定互为前驱后继(即相邻)。把数据离线后得到每个数据最终的位置便可以很方便的用线段树来维护两个数之间的差值，查询时也可以很方便的找到线段树中不小于$x$的第一个位置。
+by MountVoom
 ====== 补题 ======
+===== E =====
+线性基为$logN$个，那么$i>19$时$ans[i]=ans[i-2]$
+而$i \leq 19$时利用异或卷积计算答案
+by Hardict
 ===== G. Greater And Greater =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具