2017-Sp290-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
=== chenjb ===

=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：保留纵向后变成放两个点使得覆盖的区间最多，扫描线维护，删除经过一个点的所有区间，然后取剩下区间覆盖层数最大值+删去的区间数量更新答案即可。

 * B：n^3^建出图，n^3^floyd。

 * C：打表找规律，构造是稳定的。实际上可以规约成Supnick Matrix TSP，作差后函数为f(x,y)=(sqrt(x)-sqrt(y)^2^，满足Supnick，套用max构造即可，注意因为不是回路，要找到最优的拆分。

 * D：按题意模拟。

 * E：二分答案之后，直接区间合并。

 * F：模拟。

 * G：暴力积分。

 * H：

 * I：cjb

 * J：1000*1000的状态用来表示存在一种走法使得真人站在i，模拟的人类站在j，bfs走出一个路径直接结束。

 * K：2-sat

 * L：每次贪心取需要天数最多的人。

流水账

chenjb

oipotato

subconscious

题解

• A：保留纵向后变成放两个点使得覆盖的区间最多，扫描线维护，删除经过一个点的所有区间，然后取剩下区间覆盖层数最大值+删去的区间数量更新答案即可。
• B：n³建出图，n³floyd。
• C：打表找规律，构造是稳定的。实际上可以规约成Supnick Matrix TSP，作差后函数为f(x,y)=(sqrt(x)-sqrt(y)²，满足Supnick，套用max构造即可，注意因为不是回路，要找到最优的拆分。
• D：按题意模拟。
• E：二分答案之后，直接区间合并。
• F：模拟。
• G：暴力积分。
• H：
• I：cjb
• J：1000*1000的状态用来表示存在一种走法使得真人站在i，模拟的人类站在j，bfs走出一个路径直接结束。
• K：2-sat
• L：每次贪心取需要天数最多的人。