2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_2

差别

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

到此差别页面的链接

--- 2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_2 [2020/07/18 00:31]
mountvoom [B. Boundary]
+++ 2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_2 [2020/07/24 10:41] (当前版本)
hardict [lpy]
@@ 行 9: / 行 9: @@
 主要还是思维问题，EG两题一直在xsy卡题的时候思考，还是没有想出来。另外以后看一道题要把内容共享给队友，节省看题时间
 ===== lpy  =====
+题目最好全看完，没有思路可以去看看没看过的题目，不要盲目跟榜
+要与队友多分享题目内容，尽量覆盖所有题
+E题这种思维+性质题还需要加强
 ===== xsy  =====
@@ 行 18: / 行 24: @@
 ====== 题解  ======
-===== 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 =====
@@ 行 29: / 行 43: @@
 需要注意的是，一个圆上如果有$n$个点，那么交点的个数为$\frac{n(n-1)}{2}$
+复杂度为$O(n^2\log n)$
+by MountVoom
+===== D. Duration =====
+水题，求出从$00:00:00$到两个时刻的秒数作差即可。
+by MountVoom
 ===== F ======
@@ 行 36: / 行 60: @@
 by Hardict
+===== H. Happy Triangle =====
+题意是维护一个多重集，支持插入，删除和询问是否能在集合中找到两个数$a, b$与给定的$x$够成三角形。
+分情况讨论：
+$x$是三角形最长边，那么从比它小的数中选出两个最大的进行判断即可。
+$x$是三角形第二长的边，那么从比它小的数中选一个最大的，从比它大的数中选一个最小的进行判断即可。
+以上两种情况都可以用一个可重集直接维护。
+$x$是三角形的最短边，此时从比它大的数中找两个数，且这两个数的差尽可能小，那么我们要找的两个数在多重集中一定互为前驱后继(即相邻)。把数据离线后得到每个数据最终的位置便可以很方便的用线段树来维护两个数之间的差值，查询时也可以很方便的找到线段树中不小于$x$的第一个位置。
+by MountVoom
 ====== 补题 ======

2020-2021/teams/alchemist/2020_nowcoder_multiuniversity_2.1595003484.txt.gz · 最后更改: 2020/07/18 00:31 由 mountvoom