2017-Onsite09-team2

从 Trac 迁移的文章

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

原文章内容如下：

不想写
=== chenjb ===
伤心得不想说话
=== oipotato ===

=== subconscious  ===

=== 补题 ===
 * A：按时间轴倒序dp即可，注意处理同一时刻多个选择的细节。
 * B：bfs模拟
 * C：
 * D：可以证明若将n个人的宝石数排成一个序列，则每一种不同的序列产生的概率是相等的。于是只需要计算不同序列前r大的和，不同序列的方案数即可算出答案。枚举序列前r大中出现的最小值k，dp(i,j,s)表示将s个宝石分给i个人，其中>k的有j个，其余的都<k的方案数和>k的宝石的数量和，枚举=k的数量加入答案即可。
 * E：枚举判断每个点能不能到其他的某个点，能的话连一条有向边（到达关系显然不满足双向）。对于两个定点和一个初速度，显然有至多两个抛物线满足条件，此时取仰角大的即可。由于最远距离是一个凸函数，于是三分或其他数学知识求出极值点的仰角，再二分或运用数学物理知识得到恰好落在中点的仰角。随后暴力枚举两点连线和每一条横竖的边的交点，比较这个点需要的高度和实际高度判断可行性即可。建完图之后跑bfs即可。
 * F：枚举宽度，dp。
 * G：sub
 * H：答案不会超过2，2的话取交叉转一转，1的话就线段树维护区间覆盖即可。
 * I：好好处理读入，发现同一行的三角形可以树状数组nlogn维护。
 * J：
 * K：贪心取度数最小的k个点，构造即可。

不想写

chenjb

伤心得不想说话

oipotato

subconscious

补题

• A：按时间轴倒序dp即可，注意处理同一时刻多个选择的细节。
• B：bfs模拟
• C：
• D：可以证明若将n个人的宝石数排成一个序列，则每一种不同的序列产生的概率是相等的。于是只需要计算不同序列前r大的和，不同序列的方案数即可算出答案。枚举序列前r大中出现的最小值k，dp(i,j,s)表示将s个宝石分给i个人，其中>k的有j个，其余的都k的宝石的数量和，枚举=k的数量加入答案即可。
• E：枚举判断每个点能不能到其他的某个点，能的话连一条有向边（到达关系显然不满足双向）。对于两个定点和一个初速度，显然有至多两个抛物线满足条件，此时取仰角大的即可。由于最远距离是一个凸函数，于是三分或其他数学知识求出极值点的仰角，再二分或运用数学物理知识得到恰好落在中点的仰角。随后暴力枚举两点连线和每一条横竖的边的交点，比较这个点需要的高度和实际高度判断可行性即可。建完图之后跑bfs即可。
• F：枚举宽度，dp。
• G：sub
• H：答案不会超过2，2的话取交叉转一转，1的话就线段树维护区间覆盖即可。
• I：好好处理读入，发现同一行的三角形可以树状数组nlogn维护。
• J：
• K：贪心取度数最小的k个点，构造即可。

附加文件

• icpc2018.pdf by chenjb