停课总结

二个月差不多就干了这些…

专题学习

DP

主要考虑题目为什么用 DP,如何高效设计状态。

主要是经验方面的积累。

注意积累一些常见的状态设计方法,部分题目用到了容斥,状态设计可以让需要容斥掉的东西大大简化。

题目来源:CF AT,会花时间,但是很有必要。

数学

花时间学习和理解。本阶段的主要任务,以板块形式系统总结为一篇博客。

数论基本完成。正在搞多项式。

特别是在数论相关的算法,仅仅会算法的模板并没有太大作用,更重要的是理解这样为什么比其他方法高效,运用到了问题中的哪一点特殊点,这类方法适用与哪些问题。

多项式常见于生成函数的题目,建议是先基本学会多项式的基本操作,然后开始做生成函数的题,单论多项式并没有太多考点,注意积累常用题目的生成函数形式,如何化简,更重要的是理解生成函数在进行操作时的意义。

题目来源:HDU POJ,有很多生成函数的题,但是比较杂,可以找一找别人总结的提单。

杂题

主要考虑近期 abc arc cf div2 的题,有利于保持对于题目的手感。

对于自己赛时(包括 vp ) 中 AC 的题以及赛后想出来的或者是看题解搞出的题都建议记录一下,不用太多。

贪心在竞赛中经常占有一定比例,一些 DP、图论的题本质上也是利用贪心减少不必要的状态,最重要的是贪心策略从何而来,如何证明正确性,应该尽可能从一些经典算法中获取贪心的思路,理解这些算法的本质,特别是最短路、最小生成树。

模拟赛

赛时

优先保证整体的成绩,尽量不因为某道题影响整体发挥,找出自己的节奏。

尽量保证暴力不挂分。考虑好自己的分数规划,尽量不出现 5min D题极限暴力的情况。

赛后

赛后过题后,应该更多考虑模拟赛时未 AC 的原因,如:时间不足、码力不足、某个 Trick 没想到、某个性质没推出来。

注意提高自己思维上的薄弱点。

另外也从代码实现的角度考虑考虑是否出现的复杂的已学习算法赛时写不出来的情况,比如淀粉质这种的,是否需要加练,以及部分算法自己的常见低级错误,考虑改一种写法。

比如:

diff --git a/a.cpp b/a.cpp
index 4be369e..01d1717 100644
--- a/a.cpp
+++ b/a.cpp
@@ -46,10 +46,13 @@ namespace pro{
 while(qu.size()>0){
   node temp=qu.top();
   qu.pop();
+  while(qu.size()>0&&sure[temp.i][temp.kk]){
-    while(sure[temp.i][temp.kk]){
       temp=qu.top();
       qu.pop();
     }
+  if(sure[temp.i][temp.kk]){
+    break;
+  }
   sure[temp.i][temp.kk]=1; 
   for(int i=fir[temp.i];i!=-1;i=nxt[i]){
     int disto=dp[temp.i][temp.kk]+1;

核心目标是不让代码实现成为竞赛中的瓶颈甚至是丢分点。

后续目标

  1. 字符串(未开始,暂无安排)
  2. 数学(主要任务,但是要注意质量)
  3. DP(练习重点,花时间,不着急)