杂记 - 广州纪中游学总结

这是个什么 Blog??


Part1. 小序

广州纪中游学结束后第四天,应教练要求(其实我自己也想),对此次的学习作一个总结。

大概内容包括以下方面:

  • 自己以及同学们的表现;
  • 新学到的知识点;
  • 发现到的缺点;
  • 希望在之后的学习中巩固或新学的知识点。

Part2. 总结正文

#1 游学的表现&状态

先从我自己说(毕竟对自己的状态是最清楚的),从模拟赛成绩的角度看,感觉发挥比较稳定,不会太靠后,虽然不一定每一次都能够获得高分,但是能够与平均分拉开一段距离。

然后从每一道题来说,发现题目的具体考点会对我产生很大影响。在一次模拟赛中,我做出了一道难度较大的最短路题目,但是另外一道相较简单的签到题没有想到正解。大致分析原因有二:①做最短路那道题的时候花费了较多的时间,又因为签到题位于最后一道题的位置,就误以为最后一题很难,于是没有花费太多时间思考正解,而是选择花费较少时间写出一个暴力;②对最短路比较熟悉,想的时候思路比较清晰,但是对于另外一道算法不明显的没有什么套路的题就不是特别擅长。

在考后的讨论&讲解中,个人参与非常积极,也有能力上台讲自己的思路。发现纪中本校的学生分享自己的思路更为主动,而且可以看出他们的表达能力很强,也很善于思考——哪怕是在讲自己的思路时出现了一些疏漏,也能够与其他选手讨论然后更正,或是自己研究出结果后继续与其他同学分享。

接下来就是几场课程,对我个人而言,参加得比较积极,而且难度也比较合适(晚上 NOI 难度的课程都没去,在机房里总结上午及下午的内容)。课程的内容总体来说难度偏高,不一定每一个知识点都能够听懂,尤其是数据结构板块,LCT以及可持久化Treap都是半懂,还需要在课后自行梳理。

再来分析各位同学的情况(主要是提高A组,省选组以及提高B组不是特别清楚),A组这边的情况不是特别乐观,大多数同学的发挥不稳定,可能在某一次比赛中突然找出正解,而在另外的比赛中爆零……因此甚至还产生了一些抵触、不愿意交题的情绪(按他们的话说 “不能AC题目,感觉做起来没意思” ),会出现有暴力分不去骗或是得不到的情况。个人认为这种 OI 赛制应该以尽量得分为目的,而不是一定要 AC 一道题。但是这样也会有另外一个极端就是“习惯做不出正解”,所以个人认为在之后的 OI 赛制模拟赛中可以降低题目难度

#2 新知

  • 使用 K-D 树求平面中离某个点欧几里得距离最小的点;

  • 平面上两点的曼哈顿距离($|x_a-x_b|+|y_a-y_b|$)等于将两点旋转 $45^\circ$ 后的切比雪夫距离($\max\{|x_a-x_b|,|y_a-y_b|\}$);

  • LCT的基本操作:Access(),MakeRoot(),Split(),Link(),Cut()

  • AC自动机上的 DP & 差分;

  • 后缀数组的重新学习;

  • 回文树的基本构造;

  • 最小费用最大流;

  • 最小割套路建图;

  • 网络流求最大权闭合子图&建图&应用;

  • 最大独立集、最小顶点覆盖、最小边覆盖

    最大匹配+最小边覆盖=顶点数

    最大独立集+最小顶点覆盖=顶点数

  • 上下界网络流中的无源汇网络可行流;

Tab. 以上划线知识点只是初步理解;

#3 Bug

好像有一点多

  1. 对搜索算法的陌生:主要是太久没有写过纯粹的搜索了,每次感觉写搜索就是大暴力……基本上忘了还有 IDA*,双端搜索之类的东西。

    具体体现在 Day1T1 ,一道用 IDA* 做的题目。

    另外,不知道 IDA* 的时间复杂度……平时不敢用。

  2. 关于 DAG 以及 二分图——建图:拆点、拆边;几种转换关系,之前根本没有听说过:

    DAG中最小路径覆盖 = 顶点数 - 对应二分图中最大匹配

    DAG 转 二分图 的建图方法。

  3. 分块……

  4. 数学:中国剩余定理、扩展欧几里得定理;

  5. 并不怎么常用、非常难写而且容易被卡的动态倍增(以及其他动态维护);

  6. 线段树维护的一些神奇操作(或者是树状数组),包括扫描线;

  7. 动态规划各种杂题,比如区间DP、状压DP,各种数数题、带组合数转移的 DP……

#4 期望

线段树线段树线段树!!!

恶补一下数论(把理论转换为代码)……

动态规划的难题……


The End

Thanks for reading!

Email: lucky_glass@foxmail.com,欢迎提问!

0%