2018.5.30 集训总结

发表于 | 分类于 | ℃热度
~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

总结：

先从第一天的比赛开始看，其实光从题目来看，我排于第七名的成绩，也就是两道水题和一道比较熟练的BFS给的，后面几题是没有思路的（大佬们太强了啊），被完虐……

我再从昨天的ACM欢乐赛开始说起————
比赛第一个小时，从A题的水题十分钟完成的速度来看，稍稍放宽了心态，然而在B题上竟然栽了跟头。最初在第三个点WA了2遍，再在14点WA了好几遍，最后又卡在了35点。最后心态几乎爆炸（内心OS：这可是一道水题啊），同样，同组的大佬们，也没发现有什么问题。就这样纠结着，最后将一个双重判定换了方向的思维的另一种判定，于是，终于是A了……此时时间已经在两小时之后了（比赛半程刚过）。
内心火急火燎得，也不知怎的其他两位大佬，竟然开始换顺序做，半小时过去，VHOS（太强了）竟然完成了G组题，然而不幸的是不能提交（辣鸡日本Vjudge）。这又是对我们心态的考验，于此同时半数以上的组早已经完成了3道了，我们的排名位置几乎已经可以看到榜底了。终于在最后的第三个小时————奇迹竟然出现了！
三小时十分钟！
C题！！AC！！
三小时三十分！
G题！！AC！！
此时我们的排名已经挤到了前十，4道AC，最多的大神组早完成了5题，我心有不甘，继续奋战，此时只剩唯我一人奋笔疾书……周围的人早已懈怠，不，还不能那么早。
努力的想着D题，dp方程却死也推不出来，最后十五分钟……
！！！哦！！！
突然有了想法，夺过键盘，最后13分钟！！！我知道这次我没有调试的时间了，只能要求自己一遍过，每个字都敲得小心翼翼，同时又得加快速度…………
3min！2min！！
敲完了！！！样例一过，直接提交，不敢浪费每一分钟！！！
竟然成功AC了！！！！！同组的大佬高兴的欢呼！！我做到了！！！
当自己平静下来时，我才发现自己的身体一直在颤抖，心跳十分的快。
最后我们虽然罚时很久，但是最终也以唯一AC 6道的好成绩位居了榜首，十分不易啊！！

（P.S:最后从岳神和刘大佬的钱包里成功坑到一顿KFC）o(●ˇ∀ˇ●)o

下面是对这几天所学内容的总结，逐条枚举：（其实很多口胡一波，并不能上手当场码题）

  • 1、$KMP$ （俗称“看*片算法”） （一%飞神）
    这是由三位大神同时发现的一种改进字符串匹配的算法（%%%），$KMP$算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个$next()$函数，函数本身包含了模式串的局部匹配信息。（强行解释一波失配函数）
    上波代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int KMP(string W,string T){
    int i=1,j=1;
    while(i<=n){
        while (j!=0&&W[j]!=T[i]) j=next[j];
        if(j==m) return i-m+1;//匹配成功，返回匹配位置s
        else{j++; i++;}
    }
    return -1;//匹配失败
}
void GetNext(charT[],intnext[]){
  next[1]=0;
  j=1;k=0;
  while(j<T[0])
    if((k==0)||(T[j]==T[k])){
      j++;
      k++;
      next[j]=k;
  }
   else k=next[k];
}

（其实并不太清楚它到底具体有什么用）=v=

  • 2、数论、定理 （一堆奇奇怪怪的东西）（边打边复习）
    首先上场的是唯一分解和$lcm$、$gcd$（这货贼重要），由此引申的是欧几里得和扩展欧。

//威尔逊定理//：它给出了判定一个自然数是否为素数的充分必要条件，就是当且仅当$p$为素数时：$(p-1)!≡-1(mod p)$，但是由于阶乘是增长的速度实在是…………（所以结论对于实际操作意义不大，感觉说了废话）

//小费马//：假如$p$是质数，且$gcd(a,p)=1$，那么$a(p-1)≡1(mod\ p)$（强制使用了一波$gcd$）（其中$gcd$为$1$代表互质）（结果证明出来了）（该同余式可以转为$ap≡p(mod\ p)$，不知道写的对不对，好像提到过）

//欧拉函数与定理//：emmm，这玩意我实在不是很懂,认识了一下$φ$，还有欧拉定理：若$gcd(a,p)=1$，则$a^{φ(p)}≡1(mod\ p)$。

//关于这些定理的例题使用//：不太熟练，不献丑=w=，学习大神们的写法，费力的理解啊啊啊…………

  • 3、$manacher$ （二%飞神）
    这个和$KMP$一样，是关于字符串的一种算法，主要针对回文串。以$O（n）$的时间复杂度以每个字符为中心，以回文串单程长度，将所取字符串扩展一倍。如果是奇数串就能顺利进行，如果偶数串，那必须插入奇怪的字符。但这种算法的神奇之处在于可以同时考虑奇串和偶串。（但不能拆坏原字符串）
    （代码好长，我决定不凑字数）(￣▽￣)”

  • 4、状压$DP$
    好吧，我承认位运算我实在是烂透了，完全没记住，差点听成大弱智╮(╯-╰)╭ 。表示状压列举的子集既能完全枚举，还能节约不必要列举的时间……（来自萌新的神奇(⊙o⊙)）

  • 5、树的$LCA$ （求树两点之间的最短路）
    先从树的$dfs$序入手，展开倍增（看得懂，表示不会写……），$tarjan$（竟然基于冰茶几（并查集）！！），$RMQ$，$emmm$（回去重新学习连通分量）。
    （不好随便口胡=-=，决定翻工学习）

  • 6、差分 （一起讲了差分约束吧）
    差分所擅长做的就是把$a$数组中$l~r$范围内的数加上或减去某个$k$值，这样只要求前缀和，运用差分就只要求前缀和，就能在$O（n）$的时间内得到整个数组的值。
    差分约束嘛，是基于图论知识$SPFA$和判环的，比如我们得到$a[x]=10$，这就是约束（条件），而如果题目给你a>b||a= b+1||a+1<= b$ 这也许就是差分吧）
    (每日胡扯)(●’◡’●)
    （%%% @hzk_cpp dalao）

  • 7、trie树（图）、AC自动机
    这两个我没怎么听懂=_=，还是一脸蒙蔽，慢慢理解吧，不敢瞎说……（不过还是要三%飞神）

  • 8、树状数组 （好东西）
    树的函数结构什么的实在是太麻烦了，光建一棵树都快累的够呛了，还常常养死……这怎么办呢……emmmmm，有时树状数组是很优秀的解法。先定义一个$lowbit$函数 $x\&-x$ 取从右数起第一位1，这样可以枚举所有子集，同时也能使程序更高效。修改其中某个量复杂度是$O(n)$，而查询竟然只要$O(1)$（神奇的算法）。
    （总而言之，运用树的概念，然后用数组来进行操作，感觉修改操作有点类似于差分的感觉）

  • 9、左偏树 （概念好多，详细记录）
    左偏树是一棵不平衡的树，和它的名字一样，果真向左偏。
    这是左偏树的几条性质：
    一、左偏树的每个节点的左右子树都是一棵左偏树。
    二、节点的距离为他右子节点的距离加$1$。
    三、如果一棵左偏树的距离一定，则节点最少的左偏树是完全二叉树。
    四、一棵距离为$k$左偏树，至少有$2k+1-1$个节点。
    五、一棵$N$个节点的左偏树，距离最大$log(N+1)-1$
    它的键值基于堆的性质，从这里，我们顺带过了一遍二叉堆的写法（只能说是过，不能说是学习，因为……实在写不出，鸭梨山大QAQ），左偏树每个节点的键值小于等于它左右子节点的键值，类似于小根堆的东东。
    再来看看距离（满足左偏性质）的概念：首先先看外节点，外节点是一个左子树或右子树不存在的（空）节点。我们把空节点的距离都设为了-1，外节点都设为0。然后某个节点的距离就是它到儿子中，（到最近的外节点）经过的边数（emmm，写不出准确的学术论文$Orz$）（参考ppt与总结）
    左偏树所支持的操作：
    一、初始化一棵空的左偏树 ($New$)
    二、插入一个节点 ($Insert$) $ O(log(n))$
    三、查询最小节点 ($Ask_min$) $O(1)$
    四、删除最小节点 ($Delete_min$) $O(log(n))$
    五、删除一个已知节点 ($Delete$) $O(log(n))$
    六、合并两棵左偏树 ($Merge$)（基于递归）$O(log(n))$
    合并：由于左偏性质，如果A的键值小于B（草率的类比于，A为小根堆顶），就把B和A的右子树合并，然后检查，如果右子树的距离大于左子树，就交换A的左右子树，并更新A节点的距离。
    当然其中如果有空树，就返回另一棵存在的树。
    而与此同时，由于左偏树的合并操作会沿着最右边的路径进行，所以，我们只要把最右边边数-1，欸，这就是左偏树的距离了。emmmm，另外学习到一棵N节点的左偏树，距离最多为$log(n+1)-1$，经过边数最多为$log(n+1)$，所以时间复杂度是log级别的（优秀而神奇的算法！）
    其他操作复杂度不一一写了，恕我比较懒QWQ
    左偏树安利blog https://wenku.baidu.com/view/25a2fb85ec3a87c24028c4b5.html

//写博客期间偷偷重学了连通分量，嘿嘿~
//期间还去了上交大和上纽大参观，忙中偷闲~

-------------本文结束(づ￣ 3￣)づ~感谢您的阅读(*╹▽╹*)-------------