2020-team2-024

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team2 返回]

[[Image(Rank.png,1000px)]]

[[Image(Submissions.png,1000px)]]

= 概述 =

 solved: 6/12

 rank: 11

= 流水账 =

开场签到'''D2Y18''','''J1Y56''',cxt写L提交后WA了，pb写K的分类讨论WA了，yyc想G的博弈发现想简单后开始推sg，WA了一发全是0后'''G2Y106'''，pb改好后'''K3Y116''',cxt讲给pb和yyc都查不出错，于是define int long long,'''L2Y120'''。yzc查出是右移可能会产生负数。

pb和yyc做E，cxt做B，由于感觉和之前的一道题很像，于是想直接套那个题的做法，pb写完后提交WA了，于是yyc开始帮pb调试，一直找不到问题，又找不到做法错误，于是两个人一直卡着，cxt写完B后，yyc帮着调了调样例提交'''B1Y256''',pb发现问题尝试修改但是改法还是不对，yyc和cxt做C，yyc上机但网络卡了没交上去。（交了也没过）

= 总结 =

=== pb： ===
卡题如果队友感觉比较会可以及时丢掉。

=== Creatix： ===

确实，除了能力下滑问题（B写的太慢）外，这场打得有点僵硬（没有让合适的人做合适的题）。

立个小目标，下次赛前一定团建一次

另外支持队长的“另外大家保持好心态呀，保持比赛状态才是重要的”。

[[Image(哎嘿.png,60px)]]

upd1: 既然入坑 acm，可以用c++11，那么以后一般用vector存边好了。

upd2: 重复造轮子补了一下E。虽然我看过cjb代码，但我和他dp表达式不太一样（我的式子是比赛最后队长在写C的时候推的）。而且我20min，1A，56行。

upd3: 补了一下H。我做这道题还蛮吃力的。大概要花30min机下+50min机上（包括写对拍）。

实际上我在绝对安静（蓝田自习室）+ 心态平稳的情况下从读题到过题也花了足足83min，并且第二次提交才AC，因为弄错了取反符号的优先级。

如果赛场上再遇到这种题，@队长，你可以放心的把它丢给我，我有过题的信心，但是得做好我隐身2hour的准备。

所以建议这种题pb写（逃

upd4: 我来口胡一下I题。首先容易发现一个每次施肥功效的上界，即sqrt(2c)。

设所需增高高度为d，施肥次数为k，则此时的最优分配方案显然是尽量均分。

形式化的，令m为d/k取下整，ans[d] = min_k { -k * m * m + (2 * d - k) * m + d + k * c }

算了，胡不动了，弃疗了

upd5：重复造轮子补了一下C。唉，这本来应该算是我的锅。但是当时我已经来不及想细节了，只好丢给队长了。

所花时间：在之前听过yyc的做法的情况下，机下30min，机上25min。1A，70行。

[[Image(evidence.png,400px)]]

=== yyc： ===

今天最大的问题还是题交给谁做，以及无意义验题的问题。感觉两个人不应该去一起卡E，应该早点把榜上有的题都读一遍。

另外大家保持好心态呀，保持比赛状态才是重要的。



= 题解 =

 * A：

 * B：

 * C：细节构造

 * D：

 * E：dp状态f(i, j)表示当前在i，还能走j步，最少花多少步走到n。
 容易发现有的dp状态对出边取min，有的对出边取max。

 按dp值从小到大的顺序扩展dp状态，则取min的那些状态只要有一个出边确定即可确定dp值。
 而取max的那些状态必须等所有出边都确定才能确定dp值。

 用这个策略拓展直到无法继续，容易证明此时未被确定值的dp状态都对应着inf。

 * F：

 * G：

 * H：把题目写成sigma绝对值的形式，暴力分类讨论4种情况。

 * I：

 * J：

 * K：

 * L：

 * M：

[/wiki/2020-team2 返回]

概述

solved: 6/12

rank: 11

流水账

开场签到D2Y18,J1Y56,cxt写L提交后WA了，pb写K的分类讨论WA了，yyc想G的博弈发现想简单后开始推sg，WA了一发全是0后G2Y106，pb改好后K3Y116,cxt讲给pb和yyc都查不出错，于是define int long long,L2Y120。yzc查出是右移可能会产生负数。

pb和yyc做E，cxt做B，由于感觉和之前的一道题很像，于是想直接套那个题的做法，pb写完后提交WA了，于是yyc开始帮pb调试，一直找不到问题，又找不到做法错误，于是两个人一直卡着，cxt写完B后，yyc帮着调了调样例提交B1Y256,pb发现问题尝试修改但是改法还是不对，yyc和cxt做C，yyc上机但网络卡了没交上去。（交了也没过）

总结

pb：

卡题如果队友感觉比较会可以及时丢掉。

Creatix：

确实，除了能力下滑问题（B写的太慢）外，这场打得有点僵硬（没有让合适的人做合适的题）。

立个小目标，下次赛前一定团建一次

另外支持队长的“另外大家保持好心态呀，保持比赛状态才是重要的”。

upd1: 既然入坑 acm，可以用c++11，那么以后一般用vector存边好了。

upd2: 重复造轮子补了一下E。虽然我看过cjb代码，但我和他dp表达式不太一样（我的式子是比赛最后队长在写C的时候推的）。而且我20min，1A，56行。

upd3: 补了一下H。我做这道题还蛮吃力的。大概要花30min机下+50min机上（包括写对拍）。

实际上我在绝对安静（蓝田自习室）+ 心态平稳的情况下从读题到过题也花了足足83min，并且第二次提交才AC，因为弄错了取反符号的优先级。

如果赛场上再遇到这种题，@队长，你可以放心的把它丢给我，我有过题的信心，但是得做好我隐身2hour的准备。

所以建议这种题pb写（逃

upd4: 我来口胡一下I题。首先容易发现一个每次施肥功效的上界，即sqrt(2c)。

设所需增高高度为d，施肥次数为k，则此时的最优分配方案显然是尽量均分。

形式化的，令m为d/k取下整，ans[d] = min_k { -k * m * m + (2 * d - k) * m + d + k * c }

算了，胡不动了，弃疗了

upd5：重复造轮子补了一下C。唉，这本来应该算是我的锅。但是当时我已经来不及想细节了，只好丢给队长了。

所花时间：在之前听过yyc的做法的情况下，机下30min，机上25min。1A，70行。

yyc：

今天最大的问题还是题交给谁做，以及无意义验题的问题。感觉两个人不应该去一起卡E，应该早点把榜上有的题都读一遍。

另外大家保持好心态呀，保持比赛状态才是重要的。

题解

  • A：
  • B：
  • C：细节构造
  • D：
  • E：dp状态f(i, j)表示当前在i，还能走j步，最少花多少步走到n。

容易发现有的dp状态对出边取min，有的对出边取max。

按dp值从小到大的顺序扩展dp状态，则取min的那些状态只要有一个出边确定即可确定dp值。

而取max的那些状态必须等所有出边都确定才能确定dp值。

用这个策略拓展直到无法继续，容易证明此时未被确定值的dp状态都对应着inf。

  • F：
  • G：
  • H：把题目写成sigma绝对值的形式，暴力分类讨论4种情况。
  • I：
  • J：
  • K：
  • L：
  • M：
附加文件