2016-C06-team2

从 Trac 迁移的文章

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

原文章内容如下：

||User||Problem||Result||Memory||Time||Length||Submit Time||
||TaZoF||C||CE|| || ||557||2016-08-06 14:09:35||
||TaZoF||C||TLE|| || ||1097||2016-08-06 14:08:06||
||TaZoF||D||AC||0||3||568||2016-08-06 14:02:28||
||TaZoF||D||WA|| || ||516||2016-08-06 14:00:58||
||TaZoF||D||WA|| || ||497||2016-08-06 14:00:13||
||TaZoF||D||WA|| || ||520||2016-08-06 13:59:46||
||TaZoF||C||WA|| || ||1428||2016-08-06 13:53:28||
||TaZoF||C||WA|| || ||1398||2016-08-06 13:50:56||
||TaZoF||B||AC||0||16||2565||2016-08-06 13:26:28||
||TaZoF||B||WA|| || ||2343||2016-08-06 12:45:28||
||TaZoF||J||AC||0||356||3634||2016-08-06 12:26:24||
||TaZoF||J||TLE|| || ||3609||2016-08-06 12:21:09||
||TaZoF||A||AC||0||6||1206||2016-08-06 11:54:27||
||TaZoF||F||AC||0||19||1977||2016-08-06 11:43:44||
||TaZoF||E||AC||0||36||874||2016-08-06 10:22:27||
||TaZoF||G||AC||0||53||1062||2016-08-06 10:13:56||
||TaZoF||G||WA|| || ||1060||2016-08-06 10:11:17||
||TaZoF||H||AC||0||3||1296||2016-08-06 09:38:13||
||TaZoF||D||WA|| || ||498||2016-08-06 09:14:25||

== 流水账 ==
=== TsReaper ===
今天学长们仍然比较平稳，把我们能力范围内的大部分题都答对了。

开场Starve学长发现了简单题D题，却没有答对。不过其他队也没有答对，大家认为大概是数据的问题，就放在一边。hzf学长也发现了简单题H，'''H1y28'''，之后又发现了简单题G，不过输出答案的时候漏了一个句点，'''G2y63'''。hzf学长写题的时候我和Starve学长讨论C和E，C想了一个貌似科学的结论，幸好学长找到了反例。而E题学长的思路是比较正确的，上机后不久'''E1y72'''。之后我写了C题Starve学长猜想的做法，可惜写好之后构造了一些数据，发现这个做法并不正确。此时有队伍过了J题，Starve学长也觉得J是比较容易的几何，我就和hzf学长讨论。学长发现F是网络流，我们也讨论出了建图的模型，在Starve学长J调不出来的时候我写了F，几经调整'''F1y153'''，之后发现学长们在吃午饭就顺便写了刚刚简单讨论的A题，'''A1y164'''。

午饭后Starve学长继续调J，我与hzf学长讨论B的细节问题。在Starve学长'''J2y196'''后我上机写了B但并没有答对。此时我们队能选择的题只有B和C了，Starve学长决定先上机写一个做法，我与hzf学长debug B。最后我们决定写一个checker来检验答案的合理性，果然发现了细节错误，修改后'''B2y256'''。最后半小时其他队的学长发现了D的数据问题在哪里，大家就愉快地开始了尝试，'''D5y292'''。最后我们乱搞C，并没有答对。练习结束后其他队的学长告诉我们题意是不是理解错了。

=== hzf ===
还是从最后开始看...看到H发现是简单题，'''H1y28'''，之后tsr学长给我讲了B的题意，我觉得他说的解法很有道理！然后我继续看G，这时候榜上刚好有队过了G，我就上机写了...喜获1WA..原来是句点忘记打了...惨！背锅！以后所有文本我都复制吧...或者看的更认真！'''G2y63'''

tar学长给我讲了F的题意，我怎么觉得做过类似的...就构了一个图...tsr学长觉得挺科学...之后tsr学长上机先写C，结果有反例...惨...于是决定先写F，写完发现样例都过不了...惨...进入卡题阶段...经过讨论发现F的有条边要双向，以及有写边少加了...改了之后1A～这时候发现1队过了A，和tsr学长讨论后发现A不难，随即过了。之后J题和starve学长一起检查了一下模版，发现模版将边界上的点也认为是“内部点”，修改一些细节后，收获一个TLE...幸好starve学长及时发现，模版传参传了个vector，改成全局后AC...

之后就只剩下B，C，I题没做，而I似乎不可做...B题tsr学长思路甚是正确，于是先写B。这段时间我想了会儿C，毫无头绪...~~赛后发现读错题啦~~这时候tsr学长写好了，检查后交...获1WA...之后生成数据暴力check，终于check到一组assert fail...检查后发现一个循环的上界错啦...惨...改后AC...之后全队一起想C..各种贪心...惨...卡到结束...

== 总结 ==
=== TsReaper ===
 * 其实自己对F的构图仍然不是特别理解，可以再学一波姿势。
 * 发现很多人通过的题目自己没有通过，很有可能是题意理解错了。

=== hzf ===
 * 对于输出文本一定需要认真，特别是标点符号
 * 对于大多数队伍均通过，而本队毫无正确思路的题目，应重读题目，考虑题意是否理解正确
 * 把vector作为参数占用大量时间！

=== 3z ===
 * 心态还是要平和，卡题的时候不要急躁

== 题解 ==
=== A - Promotions ===
暴力算出所有点的前驱pre和后驱post，对于一个点，如果n-(post+1)<A，说明他一定会被选中。同理，如果对于一个点，pre>=A，说明他一定不会被选中。

=== B - Black Vienna ===
暴力枚举所有可能的三元组，然后用条件检验即可。有一些细节可以看一下我们的练习代码。

=== C - Canvas Painting ===
注意数字的顺序我们可以自己调整，这样这题就是哈夫曼树的裸题了。

=== E - Wooden Signs ===
注意到一个关键性质：某一个箭头的尾部坐标，只可能和之前箭头的头部坐标，或者第一个箭头的尾部坐标相同。这样我们枚举当前箭头的尾部坐标和哪个箭头的头部坐标相同，显然它们之间的箭头尾部和朝向都是一样的，否则这两个箭头就没有对应关系了。这是一个O(n^2^)的dp。

=== F - Landscaping ===
比较经典的最小割模型：源向一种颜色的格子连边，另一种颜色的格子向汇连边，容量都是修改的费用。相邻的格子之间连接一条双向边，容量是爬坡的费用。这样，割掉与源/汇的连接就表示改变格子种类，割掉两个格子之间的连接就表示爬坡。做最大流即可。

== 补题 ==
=== TsReaper ===
I

=== hzf ===
I
UserProblemResultMemoryTimeLengthSubmit Time
TaZoFCCE 5572016-08-06 14:09:35
TaZoFCTLE 10972016-08-06 14:08:06
TaZoFDAC035682016-08-06 14:02:28
TaZoFDWA 5162016-08-06 14:00:58
TaZoFDWA 4972016-08-06 14:00:13
TaZoFDWA 5202016-08-06 13:59:46
TaZoFCWA 14282016-08-06 13:53:28
TaZoFCWA 13982016-08-06 13:50:56
TaZoFBAC01625652016-08-06 13:26:28
TaZoFBWA 23432016-08-06 12:45:28
TaZoFJAC035636342016-08-06 12:26:24
TaZoFJTLE 36092016-08-06 12:21:09
TaZoFAAC0612062016-08-06 11:54:27
TaZoFFAC01919772016-08-06 11:43:44
TaZoFEAC0368742016-08-06 10:22:27
TaZoFGAC05310622016-08-06 10:13:56
TaZoFGWA 10602016-08-06 10:11:17
TaZoFHAC0312962016-08-06 09:38:13
TaZoFDWA 4982016-08-06 09:14:25

流水账

TsReaper

今天学长们仍然比较平稳，把我们能力范围内的大部分题都答对了。

开场Starve学长发现了简单题D题，却没有答对。不过其他队也没有答对，大家认为大概是数据的问题，就放在一边。hzf学长也发现了简单题H，H1y28，之后又发现了简单题G，不过输出答案的时候漏了一个句点，G2y63。hzf学长写题的时候我和Starve学长讨论C和E，C想了一个貌似科学的结论，幸好学长找到了反例。而E题学长的思路是比较正确的，上机后不久E1y72。之后我写了C题Starve学长猜想的做法，可惜写好之后构造了一些数据，发现这个做法并不正确。此时有队伍过了J题，Starve学长也觉得J是比较容易的几何，我就和hzf学长讨论。学长发现F是网络流，我们也讨论出了建图的模型，在Starve学长J调不出来的时候我写了F，几经调整F1y153，之后发现学长们在吃午饭就顺便写了刚刚简单讨论的A题，A1y164。

午饭后Starve学长继续调J，我与hzf学长讨论B的细节问题。在Starve学长J2y196后我上机写了B但并没有答对。此时我们队能选择的题只有B和C了，Starve学长决定先上机写一个做法，我与hzf学长debug B。最后我们决定写一个checker来检验答案的合理性，果然发现了细节错误，修改后B2y256。最后半小时其他队的学长发现了D的数据问题在哪里，大家就愉快地开始了尝试，D5y292。最后我们乱搞C，并没有答对。练习结束后其他队的学长告诉我们题意是不是理解错了。

hzf

还是从最后开始看...看到H发现是简单题，H1y28，之后tsr学长给我讲了B的题意，我觉得他说的解法很有道理！然后我继续看G，这时候榜上刚好有队过了G，我就上机写了...喜获1WA..原来是句点忘记打了...惨！背锅！以后所有文本我都复制吧...或者看的更认真！G2y63

tar学长给我讲了F的题意，我怎么觉得做过类似的...就构了一个图...tsr学长觉得挺科学...之后tsr学长上机先写C，结果有反例...惨...于是决定先写F，写完发现样例都过不了...惨...进入卡题阶段...经过讨论发现F的有条边要双向，以及有写边少加了...改了之后1A～这时候发现1队过了A，和tsr学长讨论后发现A不难，随即过了。之后J题和starve学长一起检查了一下模版，发现模版将边界上的点也认为是“内部点”，修改一些细节后，收获一个TLE...幸好starve学长及时发现，模版传参传了个vector，改成全局后AC...

之后就只剩下B，C，I题没做，而I似乎不可做...B题tsr学长思路甚是正确，于是先写B。这段时间我想了会儿C，毫无头绪...赛后发现读错题啦这时候tsr学长写好了，检查后交...获1WA...之后生成数据暴力check，终于check到一组assert fail...检查后发现一个循环的上界错啦...惨...改后AC...之后全队一起想C..各种贪心...惨...卡到结束...

总结

TsReaper

  • 其实自己对F的构图仍然不是特别理解，可以再学一波姿势。
  • 发现很多人通过的题目自己没有通过，很有可能是题意理解错了。

hzf

  • 对于输出文本一定需要认真，特别是标点符号
  • 对于大多数队伍均通过，而本队毫无正确思路的题目，应重读题目，考虑题意是否理解正确
  • 把vector作为参数占用大量时间！

3z

  • 心态还是要平和，卡题的时候不要急躁

题解

A - Promotions

暴力算出所有点的前驱pre和后驱post，对于一个点，如果n-(post+1)=A，说明他一定不会被选中。

B - Black Vienna

暴力枚举所有可能的三元组，然后用条件检验即可。有一些细节可以看一下我们的练习代码。

C - Canvas Painting

注意数字的顺序我们可以自己调整，这样这题就是哈夫曼树的裸题了。

E - Wooden Signs

注意到一个关键性质：某一个箭头的尾部坐标，只可能和之前箭头的头部坐标，或者第一个箭头的尾部坐标相同。这样我们枚举当前箭头的尾部坐标和哪个箭头的头部坐标相同，显然它们之间的箭头尾部和朝向都是一样的，否则这两个箭头就没有对应关系了。这是一个O(n2)的dp。

F - Landscaping

比较经典的最小割模型：源向一种颜色的格子连边，另一种颜色的格子向汇连边，容量都是修改的费用。相邻的格子之间连接一条双向边，容量是爬坡的费用。这样，割掉与源/汇的连接就表示改变格子种类，割掉两个格子之间的连接就表示爬坡。做最大流即可。

补题

TsReaper

I

hzf

I

附加文件