2018-Sp32-lyk

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(1.jpg,800px)]]

[http://10.71.10.90/pia/trac/wiki/2017-Sp169-team2 Legilimens]

[/wiki/2018-team3 返回Helianthus]

[https://vjudge.net/contest/254466#overview]

== 流水账 ==
开场lyk签到A，'''A1y5'''。lyk把B题丢给heltion，heltion丢了回来，lyk写，TLE了一发，改进后'''B2y29'''。jhguai签J，'''J1y36'''。heltion推出了D，有地方没有取模WA了一发，'''D2y49'''。heltion想到C的博弈思想，给lyk解释完，lyk写了一波，'''C1y92'''。jhguai想到了K的正解，给lyk讲，lyk写了一波，'''K1y157'''。全队想E和G，G生成函数不懂，放弃。E题想到了bitset合并背包，可是统计答案一直是错误的，6题打银。

== 总结 ==
=== LYK ===
今天我好像没有用任何脑子，全是队友喂给我做法，我去码。E题bitset优化背包，以及点分治，都有想过，可是点分治没有细想，误以为必须暴力M^2^合并。

=== Jhguai  ===

=== Heltion ===


== 题解 & 补题 ==
  * ~~E~~：点分治 按照dfs序顺序从根出发做背包，可以用bitset优化，NMlog(N)log(M)
  * F：
  * ~~H~~：树分块，支持合并和栈撤销的并查集，不能路径压缩，要启发式合并 （二队：第一棵树中，第一个点选sqrt个关键点使得任意一个点到祖先中第一个关键点的路径长度不超过sqrt，之后对于每个关键点，在第二棵树从根开始遍历，如果遍历到的点属于我枚举的关键点的控制范围，则暴力将路径上的边添加，需要使用支持加边、删边的按秩合并并查集）
  * ~~G~~：容斥 生成函数 分治ntt
  * ~~K~~：对a[i]分类，记录每个a[i]下不同b[i]%a[i]的个数，暴力维护前缀和，查询时二分后暴力统计
  * ~~I~~ ：建图跟[http://10.71.10.90/pia/trac/wiki/2018-Sp33-lyk 杭二多校]里的G题基本一样

Legilimens

[/wiki/2018-team3 返回Helianthus]

https://vjudge.net/contest/254466#overview

流水账

开场lyk签到A，A1y5。lyk把B题丢给heltion，heltion丢了回来，lyk写，TLE了一发，改进后B2y29。jhguai签J，J1y36。heltion推出了D，有地方没有取模WA了一发，D2y49。heltion想到C的博弈思想，给lyk解释完，lyk写了一波，C1y92。jhguai想到了K的正解，给lyk讲，lyk写了一波，K1y157。全队想E和G，G生成函数不懂，放弃。E题想到了bitset合并背包，可是统计答案一直是错误的，6题打银。

总结

LYK

今天我好像没有用任何脑子，全是队友喂给我做法，我去码。E题bitset优化背包，以及点分治，都有想过，可是点分治没有细想，误以为必须暴力M²合并。

Jhguai

Heltion

题解 & 补题

• E：点分治 按照dfs序顺序从根出发做背包，可以用bitset优化，NMlog(N)log(M)
• F：
• H：树分块，支持合并和栈撤销的并查集，不能路径压缩，要启发式合并 （二队：第一棵树中，第一个点选sqrt个关键点使得任意一个点到祖先中第一个关键点的路径长度不超过sqrt，之后对于每个关键点，在第二棵树从根开始遍历，如果遍历到的点属于我枚举的关键点的控制范围，则暴力将路径上的边添加，需要使用支持加边、删边的按秩合并并查集）
• G：容斥 生成函数 分治ntt
• K：对a[i]分类，记录每个a[i]下不同b[i]%a[i]的个数，暴力维护前缀和，查询时二分后暴力统计
• I ：建图跟杭二多校里的G题基本一样

附加文件

• 1.jpg by lyk248289469