比赛总结

牛客多校第五场 3/4/10

AC：C、D、G
补题：H

总结：

本场比赛我们三个人开题是4，3，3分配的，然后有谁发现签到题，就会找另外一个说一下思路，然后开始敲代码。
首先发现 G 题就和之前做过的一道题很相似，直接遍历加上尺取法就可以了，ska 很快就敲完代码，然后交上去就直接 ac 了。然后就发现 D 题就是一个简单的数学题，直接模拟即可，但是发现如果全部遍历就会 TLE，这时 cs 提出因为是因子，就可以直接遍历 \(\sqrt{n}\) 就足够了，这样大小两个因子都能遍历到了，然后再稍微处理一下边界处就可以了，cs 很快便将代码敲出来了，然后一边敲，一边调整，最后测试通过后，就交上去，然后 ac 了。最后做的是 C 题，ska 已经读过题了，就给我们讲了一下题目大意，cs 发现了这道题目中的条件 因为会总共出现 \(\frac{n(n-1)}{2}\) 条边，再加上有好多通过这道题目的，我们就开始大胆的猜测加上模拟结论了，最后我们发现答案要么是 \(n-1\) 要么是 \(n\)，但是第一次我们的条件整错了，只考虑在行中出现全 0 行就是 \(n-1\)，没有考虑列的情况，导致 wa 了一发，然后又再想了想，发现条件应该是只要出现全 0 行或者全 0 列，答案都是 \(n-1\)，修改之后交上去就 ac 了。最后我们 3 个就开始攻关 H 题，这就是一个典型的 dp 题目，还是因为我们 3 个对于 dp 的熟悉不够，不能很好的定义相应的状态，然后找出相应的状态转移方程，导致我们就一直没有将这道题目做出来。

通过这场比赛，我们 3 个觉得我们还是要坚持上周的想法，需要多加练习 dp，一定要将 dp 的短板给补上。

题解：

• C：只要检查是否出现全 0 行或者全 0 列即可
• D：直接模拟即可，但是注意小因子和大因子是成对出现的，直接在遍历小因子的时候同时处理大因子即可。
• G: 遍历加尺取即可。
• H：dp。首先需要预处理出i-j能取得的最大奶酪重量，然后dp进行转移。

牛客多校第六场 2/4/12

AC：E G
补题：B C

总结

开题依然是444，各自读题。之后发现G题过的比较多。ska和wyf开始想G，cs继续看别的题。G题思路出的比较快，很快就码完代码，但是少考虑了c是0的情况，wa了。修改后又wa，因为忽略了题目里面两个数不相等的情况，再次修改后才通过。之后三个人一起想E题。cs最先出的思路，之后ska也出了思路，此时cs码完代码提交后通过。然后三个人一起想C题。因为之前对数学题做的不多，这次题目想的比较偏，刚开始想找规律，然后手动列了几个之后发现规律并不取。然后就开始打表，打完表之后发现部分规律，也对之前的一些假设进行了否认。最终也没能解决。

题解

• G：只能出现gcd的倍数，判断c是不是gcd倍数和0即可。
• E：利用前缀和，然后判断给定区间 \([l，r]\) 的 \(sum[l-1]\) 与 \(sum[r]\) 是不是同奇或者同偶，且这段区间内的前缀和的奇数个数或者偶数个数是否大于等于 \(k\) 即可。
• C：首先将双阶乘转化为单阶乘。奇数情况下最后的双阶乘同理单阶乘求0的个数方法进行求解5的幂次。题目转化为单阶乘的5因子的个数。发现是等差数列求和，计算出公式配合求出。
• B：枚举+数学，需要用到一个组合数定理，我们仨都不会

杭电多校第五场 2/4/12

AC：1007、1012
补题：1001、1006

总结

这场多校比上次好一些没有很坐牢，但是还是出现了一些意想不到，以及特别无语的失误。
开题阶段，我们还是 4/4/4 这样读题的，首先我们发现了第 7 题和第 12 题是可以写的，然后就 cs 开始仔细思考第 7 题的解法，wyf 和 ska 开始讨论第 12 题，很快 cs 想到了第 7 题的解题思路，开始写代码，但是写着写着发现有一些数学处理没有掌握，便让 ska 开始写第 12 题的代码，根据模板很快就写完了，然后交上去 wa 了，因为思路是比较正确的，应该就是一些细节部分没有处理好，所以 ska 和 wyf 就开始一起检查调试，最终发现是数组开的不够大，导致 wa，改过之后就 ac 了，然后两道题有相通之处，期间 cs 给 wyf 也讲了第 7 题的思路，仔细推敲之后发现没有什么 bug，然后就继续开始码第 7 题，很顺利的码完了，但是在测试的时候，发现还是有一些小错误，在线性同余的处理那里不是很合适，然后 wyf 思考之后给出了另外一种写线性同余的方式，然后再测试样例，发现样例的小数可以通过，大数那里就会出错，检查代码之后发现是在求和取余那里不能用 +=，这样会出现错误，修改之后，就交上去了，但是遗憾的是 TLE 了，然后我们就开始计算复杂度，感觉有可能是常数的问题，于是 wyf 看过之后提出，要不要先进行一下预处理，修改后交上去就 ac 了。然后我们就开始看其他题目了，在处理第 7 题期间，ska 精读了第 1 题，就由他给我们讲了第 1 题的题意，cs 首先想到了解题思路，于是开始码代码，ska 和 wyf 就开始看了第 6 题，对于第一题，思路就是直接暴力求解，很快 cs 就将代码写完了，测试样例发现结果完全正确，然后就交了上去，结果发现 wa 了，然后因为思路比较简单，就是纯暴力，我们三个都不理解为什么会出错，想着要是错应该也是 TLE，于是三个人开始一起调这个代码，我们甚至都开始检查我们的模板函数了，手推了一次也没发现什么错误，我们还是不理解，最终我们 3 个人都困在了这道题上，也没时间再好好想想第 6 题了，导致这场比赛成了极大失误，其实第 6 题如果好好想想，我们还是能够写出来的。
比赛结束之后我们发现其实我们的第 1 题思路确实是没有什么错的，就是完全暴力，但是在处理细节的时候所用的模板不是很好，在计算点到线段的距离的时候，我们的模板在其中用到了海伦公式，但是海伦公式中用到了两层 sqrt 函数，这样的操作就会导致精度的丢失，结束后修改为利用向量的算法，交上去就过了，其实在比赛的时候，wyf 也提出了精度的问题，但是因为 3 个人都不是很擅长处理这样的问题，就没有深入思考，去换一种思路求三角形的高，就导致调了好久，冲了好久都没能 ac。

通过这场比赛我们发现，我们 3 个人不能同时困在一道题上面，即使需要调试代码，我们也得保证至少得有一个在想其他的题目，否则就会很容易让可以通过的题目最后也没时间仔细想。

题解

• 1001：直接暴力求解，但是在算的时候一定要注意精度问题，海伦公式会用到两次 sqrt，这样会导致精度丢失，需要改用向量求解，积累到模板上！！！
• 1012：直接暴力枚举就行，要加一个break防T
• 1007：是一个数学题，直接暴力计算概率，然后利用线性同余计算结果即可。
• 1006：简单DP，比赛时候一直在调1001，这题没咋看，赛后没看题解直接写就过了

杭电多校第六场 1/2/11

AC：1001
补题：1006

总结

这场多校非常无力和坐牢。开题443分别读题，找签到题。
开始阶段，榜上第一题过的比较快。cs和ska就开始想第一题，wyf去看别的题。第一题思路出的比较快，cs开始码代码，但是因为缺少相等特判wa了一发。找到特判的条件后因为快速幂没有取模的原因又wa了一发。改ksm的时候直接上手改的，ska一时糊涂把指数也给取模了，然后又wa了一发。wyf对别的题目也没有想出来思路就也来degub，发现是快速幂取模的问题，修改后A了。此时榜上第十题过的比较多，我们就开始想第十题，首先我们下意识认为题目给的就是一个环，然后开始推整圈下来的公式，但是发现剩下需要遍历的部分时间复杂度也不允许，而且余下的部分也推不出log或者O(1)的处理方法。耗费了大量时间也没有找到合适的解决方法。后来ska发现题目中给的数据也可能是互不连通的多个环，也可能是链接环，于是我们果断放弃了这个题。榜上第六题的AC数已经接近了第十题，于是我们转战第六题。第六题感觉是暴力枚举，但是复杂度不允许，于是我们往dp的方向上去思考了，最后没能解决。后来确定思路就是暴力枚举，但是没有想到降低复杂度的预处理方法，最后就只A了一个题。

题解

• 1001：就是分开讨论n等于k和不等于k的两种情况，排列组合一下，利用ksm求解。
• 1006：直接暴力枚举每一个数改变 \([-300, 300]\) 对答案的贡献，补这个题耗费了2天多，枚举贡献的逻辑实在不太好懂...

课程总结

本周讲了基础图论和数学进阶的内容。基础图论之前基本都学习过基础知识，课程基本能够跟上，但是代码之前图论练习的不多，还没有进行对应的题目练习。数学部分难度比较大，之前同样没有做过相应的题目，还需要时间来理解和练习。
图论进阶方面李国鸿同学讲的很好很清楚，一些算法ska去年学过做过相关题目，但是有些新的图论算法没了解过，而且难度较大，可能需要时间理解做题

自由学习情况

石珂安

学习了图论，整理了以前遗漏的匈牙利算法，还有就是补题，这周难度较大，补题花费了比较长的时间，另外这周没有cf，补了之前cf的一些题目，针对特殊题目写了题解，可以在博客中看到

王永峰

主要是复习字符串相关内容，哈希，kmp和字典树和AC自动机。对张博凯讲解的字符串知识内容进行理解和巩固。整理AC自动机，fail树相关的内容。

陈市

主要是进行了dp的学习和数论相关知识的学习与了解，我们对于数学方面的问题还是不够敏感，不能很好的想到解题思路。

团队模板等材料整理情况

总结AC自动机及用途模板。
一些字符串的模板、数论、图论等等
所有的模板、材料都在 github仓库，commit记录都可以看到

整体总结

本周学习情况

本周多校题目感觉比之前难许多，大部分时间还是在学习一些东西。补题的难度也比之前大。周二和周四晚上两个队讲的题大部分明白了。

下周学习目标

上难度的题目，需要绕几个弯的题目就很难做出来，下周计划多参加cf提升一下思维的锻炼；例如很多枚举的题目，知道是枚举，但是不非常暴力的，总是想不出来很巧妙的方法，需要大量做题提高这方面的思维能力
总体来说现在的方向比较明确，每个人先把基础补好，然后学一学自己所负责的方向，应该接下来一段时间都是这个目标。