比赛总结

牛客多校第三场 2/4/11

AC：A、H
补题：D、J

总结：

本场比赛我们三个人开题是4，3，3分配的，然后有谁发现签到题，就会找另外一个说一下思路，然后开始敲代码。这场比赛发现A题是签到题，然后就交给了cs来写，因为考虑的时候没有讨论好情况的分类，导致wa了几发，最后换wyf在cs的代码的基础上改了一部分代码，然后wa了一次后就过了，赛后再看这道题交的代码，发现在cs的代码上的pow函数前加一个强制类型转换就可以A了，这应该就是精度的问题了，之后再遇到要用pow函数和sqrt函数时，需要更加谨慎，要记得加强制类型转换，以避免出现一些意想不到的错误。串到数值的计算时正向遍历求。然后发现H题比较简单，但是因为我们三个对于哥德巴赫猜想不够了解，在这一题上浪费的时间比较多了一点，最后在wyf的讨论下拿下了这一题。然后就是J题，在这一题上，首先是cs提出了思路（虽然有一些用处，但是最终发现这还是有一点误导了三个人的思路），因为困在这个思路上之后，ska开始写代码，其实思路也算是正确，自己造的样例也是可以通过的，但交上去就是不对，最后补题发现最多只有两种情况，一种是无环拓扑排序，另外一种即是有环就正着输出一次，反着输出一次即可。wyf对图不太了解，开的D题，思路是正确的，就是在最后输出最少操作次数时想法有点混乱，自己想的样例不够大，对判断造成了误导，补题的时候理顺之后修改两行代码就过了。比较错误的是比赛的时候开了G题，浪费了一些时间。

通过这场比赛发现我们需要对于一些基础的数学知识的了解以及一些思维题的锻炼。

题解：

• D：只有矩阵是全0或者全1的时候才会满足题目要求，故每行要么与第一行相同，要么与第一行翻转后相同，列同理，然后对于行列分别进行统计，输出一个较小的值即可。
• H：哥德巴赫猜想：三种情况，1：一个数即判断是否是质数；2：两个数若是和为奇数则判断 \(sum-2\) 是否是质数；3：其他情况则是判断 \(sum-2*n\) 是否大于等于 0 即可。
• J: 拓扑排序一遍，看是否有环，无环输出拓扑排序，有环就正着输出 \(1...n\) 和反着输出 \(n...1\) 即可。

牛客多校第四场 3/4/12

AC：A F L
补题：J

总结

还是开题不太顺利，最后一道题卡了比较长时间，最后cs想到了正确解法，上手写wa了一发通过了；之后的两道题比较顺利，讨论的时间不长而且都是一遍过；
最后又是卡到了dp上，这是这周第二次卡dp了，之后要好好补补dp的题，找找精髓；我们赛后问了黄敏行同学如何写dp，他说首先要看哪些是必须要遍历一遍的，如果空间还够那么就要考虑我怎么设置状态能够把整个题目要求描述清楚，然后状态转移就出来了，一开始可以先不考虑复杂度，尽管写，之后再慢慢优化，毕竟dp的代码量一般不大，不会占用很多的时间。

题解

• A：全0全1必有一对，再跑一遍kmp就能判断哪个对了
• F：每次淘汰的不是最左倾就是最右倾的，看中间的人，投谁谁出局，按照这个性质直接模拟
• J：dp，重点补题，题解总结
• L：每一行或列的最终状态只和对它的最后一次操作以及以后的操作有关，从后面向前面扫描即可

杭电多校第三场 1/2/12

AC：1011
补题：1005

总结

这场多校总体来说较难，整场很坐牢，只写出来一道题，另外一道dp没有做出来；一开始签到题wa一发是因为数组没开够大的。

对于dp题我们三个人还是比较薄弱，尽管最近以来一直将重点放在了dp上，但是一到了真正做新题，在状态定义和转移方程上总是晕晕的，最经常出现的情况就是状态总是定义不对，转移方程的复杂度太高；而在平时练习中，我们对于特定的dp，如状压dp、树形dp这种针对性强的可能还有一些正确的思路，但是对于一道普通的dp新题，我们总是犯难，可能还是需要比较多的积累才能形成质的飞跃。

题解

• 1011：只有五种放大的比例，每个单拿出来枚举就行
• 1005：dp，重点补题，题解总结

杭电多校第四场 3/6/11

AC：1003 1006 1012
补题：1007 1010 1011

总结

这场开题没有特别顺利，我首先读的就是1006，但是没有太读懂，不知道是签到，wyf读了1012感觉可以写，不过我们三个都没有什么思路，导致卡了很长时间，20分钟之后cs看到1006过的人比较多就去看1006了，35分钟左右wyf提供了可行性解决方案，cs也推出来公式，我先上手写1012，ac之后cs迅速写完1006；这时ac两道之后我们没有罚时，因此排名还比较可观。

接下来感觉是被针对了，我和wyf讨论完1003之后觉得非常正确（事实上和标准答案思路一模一样），然后我就上手写，写完之后觉得没啥问题就交了一发，结果T了，于是我们三个人在那里分析复杂度，绞尽脑汁的进行优化，最终在比赛前5分钟ac了；这就导致了我们在1010那道题上基本没有花时间，在优化期间wyf其实已经朝着1010正解的方向考虑了，但是因为1003卡住就没有仔细认真的推导，但是感觉他当时的思路如果再推导个20分钟肯定出答案；考完试我把第一遍的1003代码换成fread原封不动的交了上去，结果过了，感觉出题人主要卡的是读入，，这样卡T未免不太合理吧...

题解

• 1003：将所有的值和其所属的set编号放入pair排序，用尺取法维护一个存在所有编号的区间，总复杂度 \(O(kn + nlogn + 2n)\)
• 1006：简单数学题
• 1007：
• 1010：用三色染色法可以得知（1，0，0）和（2，0，0）为唯二的最终状态，并且对于任意 \(n >m > 3\) 均可转化为 \(n \times (m - 3)\) 的情况，对于 \(n,m \leq 3\) 时手动玩一玩就行了
• 1011：
• 1012：a+b看作对答案的贡献，每次轮流拿a+b最大的

课程总结

本周还是粗略补了一下之前课程的知识，每个人都看了基础部分内容，并做了相关的习题；
这周讲了高级数据结构以及字符串，总的来说高级数据结构没太听懂...感觉讲的比较混乱也比较难，只能靠下课自己补了；字符串方面讲的比较基础，是之前学过的kmp马拉车等等，但是张博凯同学竞赛水平比较强，所以这些东西也讲的比较深入，我们还是要自行消化一下的。

自由学习情况

石珂安

整体总结了dp相关知识，打了几场codeforces：

这场认真补了一下c题：总结题解


还有些题没时间补，之后慢慢看

团队模板等材料整理情况

总结了fread（他真的太快了），dp例题模板
一些字符串的模板、高精度、图论等等
所有的模板、材料都在github仓库

整体总结

本周学习情况

本周打多校和补题花了不少时间，尤其是每周重点补的dp，（是真的需要花费不少时间去理解）

下周学习目标

因为本周卡的题都是dp，因此下周准备大量刷dp的题。
另外每次的签到题都会wa一些或者思路受阻，多做做模拟赛比如codeforces之类的。
总体来说现在的方向比较明确了，每个人先把基础补好，然后学一学自己所负责的方向，应该接下来一段时间都是这个目标