2018-team8-E02

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(day2.png)]]

== 流水账 ==

zhhhplus: 比赛开始我开始从后往前看，看到有两道奇怪的几何题样子的题目，于是决定先去把几何的point板子给敲掉，让队友接着看题。然后在敲板子的过程中，听到远处wyz说H是个签到题，于是让他们俩赶紧读一下H题，敲了一半几何板子就换cyw上来写了H。写完了H之后看了一下榜，发现I过得更多，我就开始看I，此前lsy告诉我D题好像就是个缩点之后找无入度点，感觉很显然，把书翻到tarjan那页给她了。我签完I题之后接着敲了一会儿几何板子，接着给lsy写D题，从cyw那了解到G题的题意（此时已经和lsy交流了并且），觉得可以写个cmp然后sort一下（没注意到要求对角线元素不能为0，同时cyw也没有看到每行只有少量非零元素的条件），同时还看掉了J题题意，得到了做法，有空闲的时候上去写了G题，发现是WA之后稍微改了一下交交看发现还是WA，连续WA了3发，中间cyw过掉了A，于是决定把G给lsy写状压DP，然后lsy过掉了D题开始写G题，cyw看了C题，跟我讲了题意之后在lsy过了D题写G题之后写了C题，因为数组开小了RE了一发，快速改掉之后过掉了C题，然后在lsy写G题的过程中我把凸包板子敲了上去，打算等lsy写完G题写J题的主程序部分。至于E题，一开始lsy在写G题的时候告诉我答案是询问字符串的子序列，但是我觉得不太对劲，重新读了一下题意，然后发现可能并不是这样，让cyw来确认一下。在读题的时候我看到了写在题面右下角的“后缀自动机”，觉得后缀自动机写这题很轻松，问了一下lsy会不会后缀自动机，之后决定这题做法的时候大家也不约而同地觉得后缀自动机很稳，写了后缀自动机，在最后一个多小时的时间里，lsy做这个E题，cyw和我讨论K题的题意，觉得是一个sb题，但是数据范围实在太小，可能会有蹊跷，于是搁置没做，在E题陷入困境的时候cyw抄了一个点到线段的板子进去以及一个线线相交的板子进去，并且开始写dfs，但是提交的结果是WA，最后在E题调试和K题找不出错中结束训练。

== 总结 ==

zhhhplus: 赛后发现K题读错题意了，机器人只会走球路径的垂线，翻了一下题面，找到了一个全队都不认识的单词，是垂直的意思，感受到了世界对英语渣的恶意。至于E题，SAM的做法倒是没错，但是时间复杂度相对于题面给出的过于优秀了，其实应该考虑更加暴力的做法，比如赛后200ms过的wyz的O(mnlogn)的做法（竟然能过）。不过就当熟悉SAM的板子了。总体来说没有昨天打得那么爆炸，但是罚时太多了，可能是因为签到的时候就WA了好几发的缘故。G题和E题都用了题目不需要的强度的算法，下次可能需要好好想想可行的更加简单的做法。除此之外，感觉队伍缺少交流，这可能有一部分是因为题目风格导致机时占用比较满，同时也是队友之间不够熟悉的原因，这场中看榜的次数也较少，可能是因为看到一道做一道吧。关于题目分配和比赛交流的事情打算在明天讨论一下。另外，搬了一个大的显示器到训练位上，感觉还行。

LIN452:
①切中了签到题 D，d题因为不熟悉强联通分量 和dag的性质，切题较慢，而且出现了bug。但也补了自己的一个漏洞，避免下次再犯。
②看到d题就直接想到简单状压dp，但是由于【初始化】（dp数组和cnt未成功清零）wa了两发。教训：引导我关注多case问题的初始化，每个数组每一行数据的清零。
③想e题，考虑到了sam做法，根据板子回忆起sam，但是由于对sam的理解有误，解法也相应有错误。而且直到wa了之后才慢慢反应到思路有问题。
问题总结：
①细节注意
②对算法掌握要熟练

== 补题 ==

 * K: Pepcy_Ch
 * E:

流水账

zhhhplus: 比赛开始我开始从后往前看，看到有两道奇怪的几何题样子的题目，于是决定先去把几何的point板子给敲掉，让队友接着看题。然后在敲板子的过程中，听到远处wyz说H是个签到题，于是让他们俩赶紧读一下H题，敲了一半几何板子就换cyw上来写了H。写完了H之后看了一下榜，发现I过得更多，我就开始看I，此前lsy告诉我D题好像就是个缩点之后找无入度点，感觉很显然，把书翻到tarjan那页给她了。我签完I题之后接着敲了一会儿几何板子，接着给lsy写D题，从cyw那了解到G题的题意（此时已经和lsy交流了并且），觉得可以写个cmp然后sort一下（没注意到要求对角线元素不能为0，同时cyw也没有看到每行只有少量非零元素的条件），同时还看掉了J题题意，得到了做法，有空闲的时候上去写了G题，发现是WA之后稍微改了一下交交看发现还是WA，连续WA了3发，中间cyw过掉了A，于是决定把G给lsy写状压DP，然后lsy过掉了D题开始写G题，cyw看了C题，跟我讲了题意之后在lsy过了D题写G题之后写了C题，因为数组开小了RE了一发，快速改掉之后过掉了C题，然后在lsy写G题的过程中我把凸包板子敲了上去，打算等lsy写完G题写J题的主程序部分。至于E题，一开始lsy在写G题的时候告诉我答案是询问字符串的子序列，但是我觉得不太对劲，重新读了一下题意，然后发现可能并不是这样，让cyw来确认一下。在读题的时候我看到了写在题面右下角的“后缀自动机”，觉得后缀自动机写这题很轻松，问了一下lsy会不会后缀自动机，之后决定这题做法的时候大家也不约而同地觉得后缀自动机很稳，写了后缀自动机，在最后一个多小时的时间里，lsy做这个E题，cyw和我讨论K题的题意，觉得是一个sb题，但是数据范围实在太小，可能会有蹊跷，于是搁置没做，在E题陷入困境的时候cyw抄了一个点到线段的板子进去以及一个线线相交的板子进去，并且开始写dfs，但是提交的结果是WA，最后在E题调试和K题找不出错中结束训练。

总结

zhhhplus: 赛后发现K题读错题意了，机器人只会走球路径的垂线，翻了一下题面，找到了一个全队都不认识的单词，是垂直的意思，感受到了世界对英语渣的恶意。至于E题，SAM的做法倒是没错，但是时间复杂度相对于题面给出的过于优秀了，其实应该考虑更加暴力的做法，比如赛后200ms过的wyz的O(mnlogn)的做法（竟然能过）。不过就当熟悉SAM的板子了。总体来说没有昨天打得那么爆炸，但是罚时太多了，可能是因为签到的时候就WA了好几发的缘故。G题和E题都用了题目不需要的强度的算法，下次可能需要好好想想可行的更加简单的做法。除此之外，感觉队伍缺少交流，这可能有一部分是因为题目风格导致机时占用比较满，同时也是队友之间不够熟悉的原因，这场中看榜的次数也较少，可能是因为看到一道做一道吧。关于题目分配和比赛交流的事情打算在明天讨论一下。另外，搬了一个大的显示器到训练位上，感觉还行。

LIN452:

①切中了签到题 D，d题因为不熟悉强联通分量 和dag的性质，切题较慢，而且出现了bug。但也补了自己的一个漏洞，避免下次再犯。

②看到d题就直接想到简单状压dp，但是由于【初始化】（dp数组和cnt未成功清零）wa了两发。教训：引导我关注多case问题的初始化，每个数组每一行数据的清零。

③想e题，考虑到了sam做法，根据板子回忆起sam，但是由于对sam的理解有误，解法也相应有错误。而且直到wa了之后才慢慢反应到思路有问题。

问题总结：

①细节注意

②对算法掌握要熟练

补题

  • K: Pepcy_Ch
  • E:
附加文件