2020-2021:teams:hotpot:ctuopencontest2016

差别

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

到此差别页面的链接

--- 2020-2021:teams:hotpot:ctuopencontest2016 [2020/05/12 15:17]
喝西北风
+++ 2020-2021:teams:hotpot:ctuopencontest2016 [2020/05/29 13:14] (当前版本)
misakatao 已恢复为旧版 (2020/05/15 19:12)
@@ 行 58: / 行 58: @@
 dp0[i][j]表示i的子树中选j个，且根节点不选的合法方案数；dp1[i][j]表示i的子树中选j个，根节点选中且子树中有与根连接的点被选中的合法方案数；dp2[i][j]表示i的子树中选j个，根节点选中且子树中无与根连接的点被选中的合法方案数。
-递推的时候，对根节点的每个子节点，类似01背包即可。
+递推的时候，对根节点的每个子节点，类似01背包（取max改为加）。最终答案为dp0[1][m]+dp1[1][m]。
 时间复杂度：$O(nm^2)$
@@ 行 76: / 行 76: @@
 ===题解===
-按照一行的树为单位扫描线即可，少于一半加一行，多于一半减一列，等于一半统计答案。因为要分别判断四个角所以需要做四次。每次先按某一个坐标排序，从小到大或从大到小加，多了就从大往小或者从小往大删，每次维护一个大根堆或小根堆即可。
+按照一行的树为单位扫描线即可，少于一半加一行，多于一半减一列，等于一半统计答案。因为要分别判断四个角所以需要做四次。每次先按某一个坐标排序，从小到大或从大到小加，多了就从大往小或者从小往大删，每次维护一个大根堆或小根堆即可。复杂度$O(N \log N)$
 ====I - Suspicious Samples====
@@ 行 83: / 行 83: @@
 ===题意===
+给长度为n的序列，每个元素两个参数t（时间）,v。保证t严格递增。m次询问，每次问大于/小于，在k以内之前的时间里所有v的最大/最小/平均的元素个数。
 ===数据范围===
+$n\le 10^5，m\le 10$
 ===题解===
+因为数据不大，直接线段树+二分即可。如果数据再大一些，比如n是$10^6$，可以用前缀和+单调队列。
+时间复杂度：$O(n\log n m)$或$O(nm)$
 ====J - Colorful Tribune====
@@ 行 114: / 行 122: @@
 =====Replay=====
-第一小时：
+第一小时：gyp,lxh面对一堆题看中了F。发现F可做，于是gyp开始写F。lxh,tyx开始看B，并想出来了。gyp写F不过样例，让lxh先写B并1a。
+第二小时：gyp继续调F，继续不过样例。让lxh先写，写完却发现计蒜客上没有这道题。tyx发现J过的人很多，尝试并迅速通过。
-第二小时：
+第三小时：gyp继续调F，lxh和tyx想H。gyp终于过了F，lxh和tyx也想出了H。lxh开始写H，tyx看G并想出，tyx与gyp交流G。
-第三小时：
+第四小时：lxh写H未果。tyx写G但wa。gyp想出I，gyp开始写I。gyp的I一直wa。lxh开始看D并产生思路。
-第四小时：
+第五小时：lxh开始写D。tyx发现gyp未加多组数据。I通过。tyx的G一直wa。lxh写完D却tle。
-第五小时：
+赛后，tyx的G交到cf上ac，cf上的标程交到计蒜客上wa。
 =====总结=====
   * 一定要注意有没有多组数据！

2020-2021/teams/hotpot/ctuopencontest2016.1589267843.txt.gz · 最后更改: 2020/05/12 15:17 由喝西北风