Accelerator‘s Blog

对比了一下hzwer神犇的算法汇总，看来基本数据结构和初级数据结构已完成。高级数据结构目前只学了树状数组和线段树，平衡树是下一步打算攻破的数据结构，接着树就告一段落吧= =

字符串什么的学了KMP、AC自动机和Trie，后缀数组和后缀自动机是要学的内容。

图论相关最近没有动啊啊啊！趁着过年前这几天赶快研究一下图论算法吧：关于读图：前向星；最短路问题：单源最短路：Dijkstra算法（边权为正）及堆优化、Bellman-Ford算法（有负环）、SPFA；多源最短路：Floyd-Warshall算法；图的连通：连通分量；然后就是网络流：最大流、最小割、费用流；最小生成树（MST）：Prim、Kruskal；拓扑排序；

数学相关：最近复习了一下数论算法（CRT、Ext-GCD），学了一下生成函数（这东西比较神）；考虑接下来过年这几天肯定事情多，就多学点数学算法吧= =

Quine 

让我来讲故事：晚上又来写UOJ的题，写了两道后发现UOJ上有很多很奇葩的东西，突然一个不和谐的东西映入了我的眼帘，

点击这里：http://uoj.ac/problem/8

这题真把我吓到了，但是我想能不能直接输出，发现直接输出会无穷嵌套下去QAQ，我静下心来想一想，VFleaking好像经常用黑科技来玩人，于是果断到度娘上找了个Quine的模板交上去，把代码贴在这：

#include <stdio.h>
char* recurse="#include <stdio.h>%cchar* recurse=%c%s%c;%cint main(){printf(recurse,10,34,recurse,34,10,10);}%c";
int main(){printf(recurse,10,34,recurse,34,10,10);}

这东西里面的内涵好像还挺多的，这里就不赘述了。。。

最近开始水Codeforces上的题，感觉Codeforces上的题都很不错呢~~就是数据结构题比较少，据说俄罗斯人都比较喜欢高端算法和数学。感觉只要是标签里有"dp"、"math"的题我基本上就只能看看了= =

一个晚上的成就：

5道A题（发现基本上都是染色计数和简单博弈）：CF513A值得一做，其他染色计数类的题基本上就是要注意想办法精简代码以减小时间复杂度.

2道B题(其实就是数据范围不同啦)：能从一个搜索问题引发出数学推导=_=这道题确实值得研究：CF513B2。看着题解写了一道C题：CF513C：为毛这道题看了10min才看懂= =我也知道是算期望，可就是算不出来，╮(╯▽╰)╭看着题解才算出来= =。

此外还有几道看了看题目的题（说白了就是没思路），贴在这日后处理：

CF509B、C、D，513G2.

水题到此结束，现在继续往前学= =

这是一道水题：使用扩展欧几里得算法即可。

关于扩展欧几里得算法：

众所周知，欧几里得算法有这样的性质：gcd(a,b)  = gcd(b,a mod b)；

而扩展欧几里得算法是用于解形如：ax+by = gcd(a,b) = k 的不定方程通解；

那么这样的通解存在且b∈N*时有：bx'+(a mod b) y' =gcd(a,b)同样有解；

由于 a mod b = a - [a/b]b，则原方程可化为：y'a+(x'-[a/b]y')b = gcd(a,b)；递归求解即可，复杂度O(log n)。

经过近一周的学习与刷题，我在这段时间还是学到了一些东西的，这里做一下总结和计划。

关于数据结构：

线段树：包含了二分的思想在其中，是用来优化时间复杂度的利器；

树状数组：就是运用前缀和的思想来维护一棵树，利用这棵树中的性质达到快速查询的目的。