2016-E01-team2

从 Trac 迁移的文章

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

原文章内容如下：

||User||Problem||Result||Memory||Time||Language||Length||Submit Time||
||TaZoF||E||WA|| || ||G++||2631||2016-07-28 16:39:28||
||TaZoF||J||AC||0||273||GCC||2145||2016-07-28 15:40:37||
||TaZoF||E||WA|| || ||G++||2613||2016-07-28 15:35:04||
||TaZoF||C||AC||0||3||GCC||1698||2016-07-28 13:56:36||
||TaZoF||G||AC||0||26||G++||1584||2016-07-28 13:28:37||
||TaZoF||C||WA|| || ||GCC||1688||2016-07-28 13:26:10||
||TaZoF||G||WA|| || ||G++||1377||2016-07-28 13:06:51||
||TaZoF||D||AC||0||122||GCC||724||2016-07-28 12:50:38||
||TaZoF||F||AC||0||3||G++||803||2016-07-28 12:39:20||
||TaZoF||F||WA|| || ||G++||696||2016-07-28 12:30:05||
||TaZoF||B||AC||0||3||GCC||824||2016-07-28 12:14:01||
||TaZoF||B||WA|| || ||GCC||821||2016-07-28 12:12:12||
||TaZoF||A||AC||0||0||GCC||139||2016-07-28 12:03:35||

比赛链接: http://acm.hust.edu.cn/vjudge/contest/124554

== 流水账 ==

=== TsReaper ===
练习前20分钟我们讨论了一波队名，在经过了Happy Coding Friends，Codimon Go以及随机生成队名之后，还是决定把三个人的id各选一个字母组成队名。后来发现念不出来，就往中间插了两个元音...

开始后我从A开始看，Starve学长从E开始看，hzf学长从K开始看。A题是个签到题，'''A1y3'''，好久没见过这么签到的签到题...B题也是个签到题，然而手滑把>=写成>，'''B2y12'''。Starve学长发现了模拟题F题，但是似乎并不难写，交流了一遍题意之后就让Starve学长上机了。而hzf学长的三个题貌似都不是简单题，暂时还不太有明确的思路。

Starve学长写题的时候我发现模拟题C题和签到题D题也都很简单（感觉这一场的签到题都在我这边- -），就和hzf学长交流起了其它题的题意。I题是一个几何题，我不太擅长，决定先放在一边。J题有一个奇怪（其实并不奇怪）的式子，一下子也没有什么思路，也暂时搁置。H题虽然看似简单，但是细节很多，也暂时放弃。此时Starve学长写好了F题然而并没有答对，我就上机开始写D题。写了一小段时间之后Starve学长发现了程序中的错误，改了改'''F2y39'''。不久我的D题也写好了，'''D1y50'''。

此时两位学长发现了G题是一个相对简单的二分，Starve学长再次上机。我和hzf学长开始讨论E题和I题。E题貌似是dp或者贪心，但是这样的dp之前没有见过，状态转移方程也推不出来，学长决定贪心一下试试看。I题我们想到了朴素的O(n^2^)做法，然而n <= 10000。Starve学长的G题并没有答对，我就开始写C，学长们debug G。C题交上去以后也没有答对，幸好学长们发现了G题的错误，'''G2y88'''。我看了几遍C题的代码并没有发现错误，请Starve学长帮忙debug，发现漏了一个条件判断，改了改'''C2y116'''。

虽然前期犯了一些不该犯的错误，不过罚时也还好。练习开始两个小时左右我们就进入了中档题阶段。因为现场赛的回放记录中有队伍过了E题，我们决定先做一下E，然而过了很久也没有很大的进展。hzf学长想了一个贪心的做法，虽然听起来有点怪，但是也找不到反例，就让学长上机试一下。回放中又有队伍过了I题，我就和Starve学长开始想I题。学长希望通过半平面交、凸包、分治等方法希望把复杂度降低到O(n(logn)^2^)，但是我们并不会写...

练习进行了三个小时后我们决定讨论一下J题，发现J题其实是很简单的二分+最大流，感觉一开始跳错了坑...hzf学长写好了E题但是样例过不了，我就上机开始写J题。然而不知道为什么，感觉写题的时候有点疲惫，还不小心把模板抄错了，表现得非常急躁，影响了队伍的士气。中间休息了一下，让hzf学长继续调E题，可惜没有通过。最后发现了J的错误，'''J1y220'''。

之后hzf学长继续调E题，我们就在E题和I题间摇摆不定。最后一个小时Starve学长决定上机尝试一下I，但是程序过于复杂还是放弃。最后半小时我们决定乱搞一下，让hzf学长正着贪心一遍，倒着贪心一遍，不过仍然没有通过。结束时中档题仍然只答对了一题。

赛后阅读sf学长队伍去年的练习小结，发现I题暴力可过，~~有一种想要殴打学长们的冲动~~

=== 3z ===

Tsr学长说了这么多。。

=== hzf ===
Tsr学长都说完啦

== 总结 ==

=== TsReaper ===

 * 签到题少犯错，不然太亏...
 * 心态要平稳。感觉自己太情绪化，而且容易有负面情绪，很容易影响队伍士气。
 * 离15分钟一道简单题，中档题尽量全部做完的目标还是太遥远了...多练习吧...
 * 简单题和中档题之间的“沟”太大，不知道该怎么办...

=== 3z ===

 * 代码有问题的时候还是尽量和队友一起debug，一个人debug可能在坑里转不出来。。
 * 手速还是太慢，羡慕Tsr的手速
 * 心态要平和（其实我觉得这场比的还不错啊~
 * 要相信评测机的速度啊，最后没有事情干的时候要敢于写暴力！

=== hzf ===

 * 读题要认真，题意转述错了坑了队友。。
 * 想题的时候多听队友的意见，否则经常掉进坑里出不来 

== 题解 ==
sf学长说很多比赛不提供题解...还是写一下题解，希望以后做这套比赛的学长能用到...？

ABCDFG是简单题，略过...

=== E ===
很容易得到一个贪心的结论：信号塔一定会建在某间房子右端点+R处。

如果我们能考虑哪些点放复合信号塔，剩下的没有被覆盖的房子用1类/2类信号塔覆盖，就能得到答案。

先把房子按右端点排序。设g[i][j]表示只用1类/2类信号塔满足第i~第j座房子的需求，且第i-1座房子右端点+R处有一座复合信号塔的最小花费。设f[i]表示满足前i座房子的需求的最小花费，我们就可以枚举最后一座符合信号塔放在哪里，也就是f[i] = min(f[j-1] + g[j+1][i] + C3)。答案就是f[n].

=== H ===
如果直接对每一段路线求交了多少保护金，在正方形的角上很容易多算或者漏算，总之会有各种细节问题。

所以我们整体考虑问题，求出每一个正方形与路线相交的区间，区间的端点表示的是从整条路径的起点出发走过的距离。这样就变成了一个比较容易的问题：如何用最少的区间覆盖一个区间并。而且不会出现正方形的角上各种细节，非常科学。

=== I ===
感觉正解不是O(n^2^)的，然而更优复杂度的做法并不会...

对于一段路线l，如果之后的路线出现在了以l两端为垂心分别作垂线的长条形范围内，就不符合要求。这样我们暴力检查之后路线是否经过这个区域即可。这个判断条件还可以更加简化成一个半平面。

=== J ===
二分答案，这样我们就得到了在当前的答案下，每个人最多可以付多少次车钱。

设第i个人可以付Pi次车钱，他在第Di1, Di2, ... Dik天有坐车，那么就从源点向第i个人连容量为Pi的边，从第i个人向第Di1, Di2, ... Dik天分别连容量为1的边，然后每天向汇点分别连容量为1的边。做一遍最大流，看看最大流是否等于总天数即可。

== 补题 ==

=== TsReaper ===
~~E~~, ~~H~~, ~~I~~, K

=== 3z ===

E, I

=== hzf ===
E, I
UserProblemResultMemoryTimeLanguageLengthSubmit Time
TaZoFEWA G++26312016-07-28 16:39:28
TaZoFJAC0273GCC21452016-07-28 15:40:37
TaZoFEWA G++26132016-07-28 15:35:04
TaZoFCAC03GCC16982016-07-28 13:56:36
TaZoFGAC026G++15842016-07-28 13:28:37
TaZoFCWA GCC16882016-07-28 13:26:10
TaZoFGWA G++13772016-07-28 13:06:51
TaZoFDAC0122GCC7242016-07-28 12:50:38
TaZoFFAC03G++8032016-07-28 12:39:20
TaZoFFWA G++6962016-07-28 12:30:05
TaZoFBAC03GCC8242016-07-28 12:14:01
TaZoFBWA GCC8212016-07-28 12:12:12
TaZoFAAC00GCC1392016-07-28 12:03:35

比赛链接: http://acm.hust.edu.cn/vjudge/contest/124554

流水账

TsReaper

练习前20分钟我们讨论了一波队名，在经过了Happy Coding Friends，Codimon Go以及随机生成队名之后，还是决定把三个人的id各选一个字母组成队名。后来发现念不出来，就往中间插了两个元音...

开始后我从A开始看，Starve学长从E开始看，hzf学长从K开始看。A题是个签到题，A1y3，好久没见过这么签到的签到题...B题也是个签到题，然而手滑把>=写成>，B2y12。Starve学长发现了模拟题F题，但是似乎并不难写，交流了一遍题意之后就让Starve学长上机了。而hzf学长的三个题貌似都不是简单题，暂时还不太有明确的思路。

Starve学长写题的时候我发现模拟题C题和签到题D题也都很简单（感觉这一场的签到题都在我这边- -），就和hzf学长交流起了其它题的题意。I题是一个几何题，我不太擅长，决定先放在一边。J题有一个奇怪（其实并不奇怪）的式子，一下子也没有什么思路，也暂时搁置。H题虽然看似简单，但是细节很多，也暂时放弃。此时Starve学长写好了F题然而并没有答对，我就上机开始写D题。写了一小段时间之后Starve学长发现了程序中的错误，改了改F2y39。不久我的D题也写好了，D1y50。

此时两位学长发现了G题是一个相对简单的二分，Starve学长再次上机。我和hzf学长开始讨论E题和I题。E题貌似是dp或者贪心，但是这样的dp之前没有见过，状态转移方程也推不出来，学长决定贪心一下试试看。I题我们想到了朴素的O(n2)做法，然而n <= 10000。Starve学长的G题并没有答对，我就开始写C，学长们debug G。C题交上去以后也没有答对，幸好学长们发现了G题的错误，G2y88。我看了几遍C题的代码并没有发现错误，请Starve学长帮忙debug，发现漏了一个条件判断，改了改C2y116。

虽然前期犯了一些不该犯的错误，不过罚时也还好。练习开始两个小时左右我们就进入了中档题阶段。因为现场赛的回放记录中有队伍过了E题，我们决定先做一下E，然而过了很久也没有很大的进展。hzf学长想了一个贪心的做法，虽然听起来有点怪，但是也找不到反例，就让学长上机试一下。回放中又有队伍过了I题，我就和Starve学长开始想I题。学长希望通过半平面交、凸包、分治等方法希望把复杂度降低到O(n(logn)2)，但是我们并不会写...

练习进行了三个小时后我们决定讨论一下J题，发现J题其实是很简单的二分+最大流，感觉一开始跳错了坑...hzf学长写好了E题但是样例过不了，我就上机开始写J题。然而不知道为什么，感觉写题的时候有点疲惫，还不小心把模板抄错了，表现得非常急躁，影响了队伍的士气。中间休息了一下，让hzf学长继续调E题，可惜没有通过。最后发现了J的错误，J1y220。

之后hzf学长继续调E题，我们就在E题和I题间摇摆不定。最后一个小时Starve学长决定上机尝试一下I，但是程序过于复杂还是放弃。最后半小时我们决定乱搞一下，让hzf学长正着贪心一遍，倒着贪心一遍，不过仍然没有通过。结束时中档题仍然只答对了一题。

赛后阅读sf学长队伍去年的练习小结，发现I题暴力可过，有一种想要殴打学长们的冲动

3z

Tsr学长说了这么多。。

hzf

Tsr学长都说完啦

总结

TsReaper

  • 签到题少犯错，不然太亏...
  • 心态要平稳。感觉自己太情绪化，而且容易有负面情绪，很容易影响队伍士气。
  • 离15分钟一道简单题，中档题尽量全部做完的目标还是太遥远了...多练习吧...
  • 简单题和中档题之间的“沟”太大，不知道该怎么办...

3z

  • 代码有问题的时候还是尽量和队友一起debug，一个人debug可能在坑里转不出来。。
  • 手速还是太慢，羡慕Tsr的手速
  • 心态要平和（其实我觉得这场比的还不错啊~
  • 要相信评测机的速度啊，最后没有事情干的时候要敢于写暴力！

hzf

  • 读题要认真，题意转述错了坑了队友。。
  • 想题的时候多听队友的意见，否则经常掉进坑里出不来

题解

sf学长说很多比赛不提供题解...还是写一下题解，希望以后做这套比赛的学长能用到...？

ABCDFG是简单题，略过...

E

很容易得到一个贪心的结论：信号塔一定会建在某间房子右端点+R处。

如果我们能考虑哪些点放复合信号塔，剩下的没有被覆盖的房子用1类/2类信号塔覆盖，就能得到答案。

先把房子按右端点排序。设g[i][j]表示只用1类/2类信号塔满足第i~第j座房子的需求，且第i-1座房子右端点+R处有一座复合信号塔的最小花费。设f[i]表示满足前i座房子的需求的最小花费，我们就可以枚举最后一座符合信号塔放在哪里，也就是f[i] = min(f[j-1] + g[j+1][i] + C3)。答案就是f[n].

H

如果直接对每一段路线求交了多少保护金，在正方形的角上很容易多算或者漏算，总之会有各种细节问题。

所以我们整体考虑问题，求出每一个正方形与路线相交的区间，区间的端点表示的是从整条路径的起点出发走过的距离。这样就变成了一个比较容易的问题：如何用最少的区间覆盖一个区间并。而且不会出现正方形的角上各种细节，非常科学。

I

感觉正解不是O(n2)的，然而更优复杂度的做法并不会...

对于一段路线l，如果之后的路线出现在了以l两端为垂心分别作垂线的长条形范围内，就不符合要求。这样我们暴力检查之后路线是否经过这个区域即可。这个判断条件还可以更加简化成一个半平面。

J

二分答案，这样我们就得到了在当前的答案下，每个人最多可以付多少次车钱。

设第i个人可以付Pi次车钱，他在第Di1, Di2, ... Dik天有坐车，那么就从源点向第i个人连容量为Pi的边，从第i个人向第Di1, Di2, ... Dik天分别连容量为1的边，然后每天向汇点分别连容量为1的边。做一遍最大流，看看最大流是否等于总天数即可。

补题

TsReaper

E, H, I, K

3z

E, I

hzf

E, I