2016-C04-team2

从 Trac 迁移的文章

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

原文章内容如下：

||User||Problem||Result||Memory||Time||Length||Submit Time||
||TaZoF||J||WA|| || ||797||2016-08-04 14:18:23||
||TaZoF||B||WA|| || ||1876||2016-08-04 14:17:23||
||TaZoF||J||WA|| || ||775||2016-08-04 14:13:39||
||TaZoF||B||WA|| || ||1155||2016-08-04 14:10:10||
||TaZoF||B||WA|| || ||1002||2016-08-04 14:09:19||
||TaZoF||B||WA|| || ||999||2016-08-04 14:06:34||
||TaZoF||B||WA|| || ||936||2016-08-04 14:01:16||
||TaZoF||C||AC||0||339||2219||2016-08-04 13:34:09||
||TaZoF||C||CE|| || ||2922||2016-08-04 13:32:34||
||TaZoF||K||TLE|| || ||2292||2016-08-04 12:53:36||
||TaZoF||K||TLE|| || ||2199||2016-08-04 12:42:32||
||TaZoF||D||AC||0||75||542||2016-08-04 12:35:51||
||TaZoF||K||TLE|| || ||1793||2016-08-04 12:30:54||
||TaZoF||D||WA|| || ||684||2016-08-04 11:58:04||
||TaZoF||A||AC||0||1305||706||2016-08-04 11:38:23||
||TaZoF||A||WA|| || ||705||2016-08-04 11:25:01||
||TaZoF||E||AC||0||663||2839||2016-08-04 11:09:12||
||TaZoF||G||AC||0||5702||1647||2016-08-04 10:33:36||
||TaZoF||J||WA|| || ||471||2016-08-04 09:45:17||
||TaZoF||I||AC||0||3||512||2016-08-04 09:42:37||

== 流水账 ==
=== TsReaper ===
今天我们队的发挥比较正常，能力范围内大部分题目都答对了，学长们都挺不错的。

开场一段时间后我们很快发现了两个简单题I和J，'''I1y22'''，不过J没有答对（练习结束后发现貌似数据出了问题）。我们看到其他队也没有答对J，决定先把J放着。Starve学长很快看出G是分治+树状数组，一段时间后'''G1y73'''。网络流E题我们也很快发现了，'''E1y109'''。我写E的时候学长们讨论出了A的做法，经过调试'''A2y138'''。感觉虽然开题顺序比较奇怪，但是一些题目是我们队比较擅长的，还算合理。

Starve学长做A的时候我和hzf学长讨论D，得到了D的dp式。不过这个式子是O(nsqrt(n))的，时间上承受不了。我愚蠢地猜了一个结论，并没有答对；之后换成记忆化搜索才'''D2y195'''。在此期间Starve学长也尝试了K，不过超时了（练习结束后发现貌似数据也出了问题...）。

剩下比较可做的题只有B和C了。稍微想了想C我发现之前做过一个类似的题目，只不过C还套上了几何题的包装。Starve学长帮我写好了几何的处理部分，我写剩下的部分，'''C2y254'''。最后半个多小时我们猜想了B的做法，然而并没有成功。

=== hzf ===
开场从K开始看，看到大于10^18^的答案输出too many我就以为这是个奇怪的搜索之类的...以为不太好做...结果好像是枚举...~~虽然最后数据好像出了问题？~~不过感觉还是我的锅阿这本是简单题的赶脚？看到J，感觉很水，上手写，wa了一发，赛后发现这题数据有问题...然后被学长们叫去看D，逐渐能够发现是dp的感觉...但是复杂度不太对，starve学长写完G和我一起讨论D，他感觉是个斜率优化...我乍看上去很科学...~~完全没注意到其中的除号是取整...~~之后又讨论了A，我乍看上去觉得是最小路径覆盖...但点太多啦...很快starve学长得出了科学的贪心策略，之后tsr学长写完E，换starve学长写A，我和tsr学长继续讨论D，发现了斜率优化不是很科学，就又猜了个奇怪的结论...对拍后交了一发，wa了...后来发现tsr学长发现记忆化搜索就可以有科学的时间复杂度...剩下的两题B和C，C题tsr学长一眼秒了...强，B题我猜测端点排序后选择的区间是连续的，又错了...正解要求先剔除包含其他区间的区间后，再应用类似的结论做dp...

=== 3z ===
ls和lss说得好！

== 总结 ==
=== TsReaper ===
 * 今天学长们发挥正常，都很棒。记忆化搜索的复杂度以后可以多考虑一下。

=== hzf ===
 * 比赛后期还是不要弃疗的好...如果能想出正确的结论，学长们肯定能码出来阿...

=== 3z ===
 * 比赛最后半个小时，看到Domino过了B之后很慌张，导致思考得很混乱，如果稳健一点一步一步地想也许能发现一些性质
 * 还是交简单题前要仔细读一遍代码，防止在很弱智的地方WA
 * 手速还是太慢。。

== 题解 ==
I和J是简单题，略过...

=== B - Better Productivity ===
一开始我们猜想对端点排序后，每条生产线上的员工是连续的，事实上并非如此。可以构造一个反例：三个员工两条生产线，(1,10),(2,100),(3,4).

我们可以先把生产时间包含其他员工的所有员工去掉，这样剩下的员工生产时间就没有包含关系了。此时每条生产线上的员工就是连续的，这可以证明。

接下来我们就是要处理之前被去掉的员工了。因为这些员工的生产时间包含了别人的生产时间，所以想要让答案最优，只有两种选择：自己独占一条生产线，或者和没有被去掉的员工合并（这样贡献是0），枚举多少人独占一条生产线即可。

=== C - Cleaning Pipes ===
去掉几何的包装，题目就是：给一张有n个点的图，如果选择了一个点，那么所有和该点连接的边都被“占领”了。是否存在一种选点方案，使得每条边都被“占领”，而且只被“占领”一次。只要用图的黑白染色即可，如果没有染色矛盾就是可行的，否则不可行。

=== D - Debugging ===
设f(i)表示处理i行代码的最小代价，我们可以枚举插入printf的次数j，就有f(i) = min(f([i/(j+1)]) + P*j + R)（[]表示上取整）。由于[i/(j+1)]只有根号数量的值，显然[i/(j+1)]相同时j越小越好，这样我们需要转移的次数就不会很多，用记忆化搜索即可。

=== E - Elementary Math ===
比较明显的最大流/二分图匹配。二分图一边表示数对，一边表示运算结果，然后做二分图匹配，看看能不能把所有数对都匹配上即可。

== 补题 ==
=== TsReaper ===
~~B~~

=== hzf ===
A, B, C, E, G
UserProblemResultMemoryTimeLengthSubmit Time
TaZoFJWA 7972016-08-04 14:18:23
TaZoFBWA 18762016-08-04 14:17:23
TaZoFJWA 7752016-08-04 14:13:39
TaZoFBWA 11552016-08-04 14:10:10
TaZoFBWA 10022016-08-04 14:09:19
TaZoFBWA 9992016-08-04 14:06:34
TaZoFBWA 9362016-08-04 14:01:16
TaZoFCAC033922192016-08-04 13:34:09
TaZoFCCE 29222016-08-04 13:32:34
TaZoFKTLE 22922016-08-04 12:53:36
TaZoFKTLE 21992016-08-04 12:42:32
TaZoFDAC0755422016-08-04 12:35:51
TaZoFKTLE 17932016-08-04 12:30:54
TaZoFDWA 6842016-08-04 11:58:04
TaZoFAAC013057062016-08-04 11:38:23
TaZoFAWA 7052016-08-04 11:25:01
TaZoFEAC066328392016-08-04 11:09:12
TaZoFGAC0570216472016-08-04 10:33:36
TaZoFJWA 4712016-08-04 09:45:17
TaZoFIAC035122016-08-04 09:42:37

流水账

TsReaper

今天我们队的发挥比较正常，能力范围内大部分题目都答对了，学长们都挺不错的。

开场一段时间后我们很快发现了两个简单题I和J，I1y22，不过J没有答对（练习结束后发现貌似数据出了问题）。我们看到其他队也没有答对J，决定先把J放着。Starve学长很快看出G是分治+树状数组，一段时间后G1y73。网络流E题我们也很快发现了，E1y109。我写E的时候学长们讨论出了A的做法，经过调试A2y138。感觉虽然开题顺序比较奇怪，但是一些题目是我们队比较擅长的，还算合理。

Starve学长做A的时候我和hzf学长讨论D，得到了D的dp式。不过这个式子是O(nsqrt(n))的，时间上承受不了。我愚蠢地猜了一个结论，并没有答对；之后换成记忆化搜索才D2y195。在此期间Starve学长也尝试了K，不过超时了（练习结束后发现貌似数据也出了问题...）。

剩下比较可做的题只有B和C了。稍微想了想C我发现之前做过一个类似的题目，只不过C还套上了几何题的包装。Starve学长帮我写好了几何的处理部分，我写剩下的部分，C2y254。最后半个多小时我们猜想了B的做法，然而并没有成功。

hzf

开场从K开始看，看到大于1018的答案输出too many我就以为这是个奇怪的搜索之类的...以为不太好做...结果好像是枚举...虽然最后数据好像出了问题？不过感觉还是我的锅阿这本是简单题的赶脚？看到J，感觉很水，上手写，wa了一发，赛后发现这题数据有问题...然后被学长们叫去看D，逐渐能够发现是dp的感觉...但是复杂度不太对，starve学长写完G和我一起讨论D，他感觉是个斜率优化...我乍看上去很科学...完全没注意到其中的除号是取整...之后又讨论了A，我乍看上去觉得是最小路径覆盖...但点太多啦...很快starve学长得出了科学的贪心策略，之后tsr学长写完E，换starve学长写A，我和tsr学长继续讨论D，发现了斜率优化不是很科学，就又猜了个奇怪的结论...对拍后交了一发，wa了...后来发现tsr学长发现记忆化搜索就可以有科学的时间复杂度...剩下的两题B和C，C题tsr学长一眼秒了...强，B题我猜测端点排序后选择的区间是连续的，又错了...正解要求先剔除包含其他区间的区间后，再应用类似的结论做dp...

3z

ls和lss说得好！

总结

TsReaper

  • 今天学长们发挥正常，都很棒。记忆化搜索的复杂度以后可以多考虑一下。

hzf

  • 比赛后期还是不要弃疗的好...如果能想出正确的结论，学长们肯定能码出来阿...

3z

  • 比赛最后半个小时，看到Domino过了B之后很慌张，导致思考得很混乱，如果稳健一点一步一步地想也许能发现一些性质
  • 还是交简单题前要仔细读一遍代码，防止在很弱智的地方WA
  • 手速还是太慢。。

题解

I和J是简单题，略过...

B - Better Productivity

一开始我们猜想对端点排序后，每条生产线上的员工是连续的，事实上并非如此。可以构造一个反例：三个员工两条生产线，(1,10),(2,100),(3,4).

我们可以先把生产时间包含其他员工的所有员工去掉，这样剩下的员工生产时间就没有包含关系了。此时每条生产线上的员工就是连续的，这可以证明。

接下来我们就是要处理之前被去掉的员工了。因为这些员工的生产时间包含了别人的生产时间，所以想要让答案最优，只有两种选择：自己独占一条生产线，或者和没有被去掉的员工合并（这样贡献是0），枚举多少人独占一条生产线即可。

C - Cleaning Pipes

去掉几何的包装，题目就是：给一张有n个点的图，如果选择了一个点，那么所有和该点连接的边都被“占领”了。是否存在一种选点方案，使得每条边都被“占领”，而且只被“占领”一次。只要用图的黑白染色即可，如果没有染色矛盾就是可行的，否则不可行。

D - Debugging

设f(i)表示处理i行代码的最小代价，我们可以枚举插入printf的次数j，就有f(i) = min(f([i/(j+1)]) + P*j + R)（[]表示上取整）。由于[i/(j+1)]只有根号数量的值，显然[i/(j+1)]相同时j越小越好，这样我们需要转移的次数就不会很多，用记忆化搜索即可。

E - Elementary Math

比较明显的最大流/二分图匹配。二分图一边表示数对，一边表示运算结果，然后做二分图匹配，看看能不能把所有数对都匹配上即可。

补题

TsReaper

B

hzf

A, B, C, E, G

附加文件