2021-2022:teams:aaub:2021.8.02_牛客6
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2021-2022:teams:aaub:2021.8.02_牛客6 [2021/08/02 23:21] prime21 创建 |
2021-2022:teams:aaub:2021.8.02_牛客6 [2021/08/03 17:27] (当前版本) hugegun [E: Growing Tree] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| 考场构造了两个小时也没玩明白 | 考场构造了两个小时也没玩明白 | ||
| + | |||
| + | zyy: done | ||
| + | |||
| + | ---- | ||
| ==== F: Hamburger Steak ==== | ==== F: Hamburger Steak ==== | ||
| 行 11: | 行 15: | ||
| xsy：done （在 99 99 2 之前没搞明白怎么分成两次wa了一发） | xsy：done （在 99 99 2 之前没搞明白怎么分成两次wa了一发） | ||
| - | ==== H: ==== | + | ---- |
| + | |||
| + | ==== H: Hopping Rabbit ==== | ||
| + | |||
| + | pmxm：类似昨晚cf，把矩形都映射到$[0,d] \times [0,d]$上就好，每个矩形用四个端点各自映射一次方便code，然后只需要任选一个未被覆盖的点作为兔子的出发点就行。 | ||
| + | |||
| + | zyy: done | ||
| ==== I: Intervals on the Ring ==== | ==== I: Intervals on the Ring ==== | ||
| 行 18: | 行 28: | ||
| pmxm&zyy： 可以考虑若最后区间交是$n$段，那么转换成每个大区间恰好不包含某一个最终解里没有包含的段即可。 如$(a,b),(c,d),(e,f)$ 那么转换成 大区间为$U - (b,c), U - (d,e), U - (f,a)$即可。 | pmxm&zyy： 可以考虑若最后区间交是$n$段，那么转换成每个大区间恰好不包含某一个最终解里没有包含的段即可。 如$(a,b),(c,d),(e,f)$ 那么转换成 大区间为$U - (b,c), U - (d,e), U - (f,a)$即可。 | ||
| + | |||
| + | zyy: done | ||
| + | |||
| + | ---- | ||
| + | |||
| + | ==== J: Defend Your Country ==== | ||
| + | |||
| + | xsy & pmxm : 猜想，奇度数的连通块从奇度数的点双删一个点就好了。（结果否定了自己） | ||
| + | |||
| + | > 原因：若删掉的是割点，直接判定割去后各个子连通块的奇偶性即可。 | ||
| + | |||
| + | pmxm: done [[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48397358]] | ||
| + | |||
| + | ---- | ||
| + | |||
| + | ==== D: Gambling Monster ==== | ||
| + | |||
| + | pmxm: 考场想到直接推期望就好了$x \oplus y > x$会被分成$\log$段，然后发现不会做每个概率都不一样的情况。 | ||
| + | |||
| + | 实际上转移方程是卷积的形式，所以用分治处理卷积转移的方式就可以了。 | ||
| + | |||
| + | ---- | ||
| + | |||
| + | ==== E: Growing Tree ==== | ||
| + | |||
| + | 题意：强制在线，动态树上加点，询问子树内的某一个颜色的个数。 | ||
| + | |||
| + | $n \log^2 n$ 做法，开颜色棵splay，splay的顺序为当前树的dfs序，那么子树问题变成splay上一段区间的查询问题，而子树查询还需要知道子树对应的区间的结尾和开头各是哪里，注意到$u$子树内一点$v$满足$lca(u,v) = u$，用这个性质可以寻找dfs序上最后一个满足该性质的点，故在splay上二分查询满足lca性质的最后一个点即可解决问题。 | ||
| + | |||
| + | 分块：设置块大小$BLK$，暴力建树、查询，树大小超过$BLK$就把这部分按dfs序加到序列中，查询时按$u$在树中和序列中两种情况处理。(邻接表用vector太慢了，实际上和log^2差不多) | ||
2021-2022/teams/aaub/2021.8.02_牛客6.1627917713.txt.gz · 最后更改: 2021/08/02 23:21 由 prime21
