【周总结】2017-8-1~2017-8-7

总结

本周参加了一个提高组集训，记录一下。

day1

早上考试ak了，好吧1个半小时做完玩耍了2个小时。题目前两题都是一眼题，t3是网格图上的生成树，随便贪心一下就好了。

下午神犇（王聿中老师）讲数论，以扩欧、同余、逆元为主，似乎听得懂。中国剩余定理有点迷。

day2

早上考试，做完还有1个小时，于是认真检查，本以为能ak，结果t1真A了；t2只有15分，扩欧+折半爆搜居然挂掉了，考完和A了的同桌对了半天还是不知道哪错了，后来才发现没有特判0（0没有逆元）；t3拿了75分，这题要数据分治：25分是BFS，我居然写挂了（队列开太小）；剩下75分标算是状压+BFS，我随便打了个spfa，当某个点遍历超过3000次就封住，似乎骗过去了。

下午神犇继续讲课，讲组合计数、容斥原理，似乎挺简单的。很多问题要求满足条件的，可以先求不满足条件的再容斥。

day3

早上考试，时间有点紧，t1问题想复杂了，发现了是栈，但没有想到是模拟，强行推性质，还好A了；t2悬线模板题（有一个地方很值得注意：每次从上往下搜时要分别记录左右端点而不能只记录最短长度）；t3好题啊，大致是求一段回路，除了起点至少还要经过2个其他点，并且每个其他点只能经过1次，考场上想到把与起点相邻的点两两求最短路，然而floyd似乎太慢，于是写了spfa（类似dp做法），结果挂了，标算是由于每两个点只要被分到不同组就可以，所以按照二进制位分组，然后跑最短路，很巧妙。

下午神犇继续讲课，讲图论，似乎都会。

day4

早上考试，看着都不会，于是3道暴力。没想到80+30+30；t1写的思路完全对，但数组开小了，标算似乎可以被卡；t2正解贪心+堆优化；又是这个套路，，把每一段算成贡献就可以贪心了；t3树形dp，好复杂，记录最近站点在是否子树内，距离是多少。

下午神犇（茹逸中）讲课，讲dp，发现自己有很多经典问题还不会；后面几道区间dp倒是会做。神犇分析考试时说这张卷子很简单。。。

day5

悲惨的要死！早上考试，感觉t1、t2都A了，就去写t3暴力；结果t1 MLE（我写的dp正解啊）；t2 WA（只有10分，最短路+状压dp的思路又是对的啊）；t3全场没人得分（暴力也挂了，莫非数据挂了？），思路是贪心。

下午神犇继续讲dp，树形dp思维量有点大，有空多练练；状压还比较简单（主要是没讲难的）。

day6

早上考试，标算和数据居然发下来了，似乎还不错，又成功得到并列第一；t1数学找规律；t2先将点$(x,y)$转换为$(x+y,x-y)$，那么点$(x_1,y_1)$和$(x_2,y_2)$的曼和顿距离就变为了$max(abs(x_1^{'}-y_1^{'}),abs(x_2^{'}-y_2^{'}))$，然后成功把新点坐标转换了一下，把两点的曼哈顿距离变为横纵坐标差的较大值，然后就可以发现加入的点一定在一个矩形上，然后dp即可，然而考前听人说是费用流，建模1小时才意识到被坑了，结果发现标算里的min_cost是最小费用没有流；t3全卷最sb的题，没有之一，分数规划+DAG上的dp。

下午神犇依旧讲dp，数位dp好东西，插头dp强行听不懂。

day7早上考试，最后一天果然挂了。t1推了2个半小时结果挂了（似乎差了一点点），正解是枚举每个人的区域，然后利用一些组合的思想（我是强行算公式）；t2数位dp，cf上的原题，day6刚讲过；t3全卷最sb的题，还是没有之一，预处理每个字母对每个串的相似度就好了，结果放在最后写了20分钟不到来不及了

下午讲分治（二分和分块），挺水的样子。

经过订正，有这么几个感想吧：

  • 累加或平方的时候一定要注意LL；
  • 数组的范围要注意；
  • 初始化的时候要初始完全（多组数据时特别注意）；
  • 修改一段代码后如果有重复地方千万不要忘记修改！！！

于是就结束了，向大佬学习！！！！！！