CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
pmxm：电脑坏了打的很菜，还是不能不写。

==== C: Delete Edges ====

考场构造了两个小时也没玩明白

zyy: done

----

==== F: Hamburger Steak ====

pmxm：从大到小煎饼即可，考虑 99,99,2 可以知道分成两次烤的煎饼是不会有问题的。

xsy：done （在 99 99 2 之前没搞明白怎么分成两次wa了一发）

----

==== H: Hopping Rabbit ====

pmxm：类似昨晚cf，把矩形都映射到$[0,d] \times [0,d]$上就好，每个矩形用四个端点各自映射一次方便code，然后只需要任选一个未被覆盖的点作为兔子的出发点就行。

zyy: done

==== I: Intervals on the Ring ====

zyy：是不是答案只有两个区间交 (WA了一发)

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差不多)
CVBB ACM Team

用户工具

站点工具

页面工具
