Svtter's Blog

从最初的csdn到博客园到wordpress到hexo，一直到现在的leanote。

中间的一些小众博客平台就不谈了。

现在用leanote的主要原因是csdn页面太丑。

• 中间国产的几个博客配置系统也使用过，对markdown的支持惨不忍睹。当然其中也不缺乏不错的产品，只是一个好的前端太重要。。

• wordpress在我半年前配置的时候也总是不顺畅。之前使用sae搭建的实在不怎么样，但是自己上传慢慢安装之后心中对空间的使用始终存在芥蒂。

leanote除了限制流量以外没有什么，不过我就是一小弱渣，肯定不会有什么问题。

存在问题，比如进行UML学习的时候，发现简单的设计我也做不出，对UML图掌握程度比较差。

此外，设计模式并没有好好地敲代码，理解的也不够透彻。

代码全部贴在github。因为UML图挂在processon上了，不过没有加连接。等写完全文就把链接加上。

首先是对象的行为模式：

1. 策略模式

针对一组算法，将每个算法封装到具有共同接口的独立类中，从而使得他们可以相互替换。

2. 状态模式

改变类中的状态。

策略模式和状态模式很像，不同在：状态模式解决内在状态的改变，策略模式解决内部算法的改变。感觉上没什么特别大的区别。- -。

3. 命令模式

---

类的行为模式：

1. 模板方法模式

拖了好久才写这份总结，中间考试，聚会，等等都推迟了这事儿。写的过程中一度想要不写了，可能是觉得结果有些不尽人意吧。

赛程

早上6点多起床，然后吃了个早饭，大概7点钟出发，路上前面的两位都在听歌，我因为耳机找不到，也没有下电影，思想神游了4个小时，也是挺佩服自己的 — 或者是刷微博？

到了以后大体上逛了下山科的校园，挺大，环境也不错，但是明显能够感觉出年轻，没有岁月的味道，心情一直是比较平静的。下午热身赛，没有特别出彩，已经不记得当时在个什么名次上 — 反正也不是很重要= =

然后就是正式比赛，拿了铜牌。

不想空洞的描述这场比赛，还是随意一点，然后再简单整理一下吧。

比赛之前的晚上发现自己博弈部分没有掌握好，图论部分也是没有完全看完重点，但是因为第五届的比赛的原因，觉得无妨，图论题目应该出了也做不出来（的确，没做出来，笑），博弈因为去年有一个（后来想到可能是记错了），所以也是没有很在意，觉得应该不至于不幸的一次就搞到我不擅长的地方吧！

结果正式比赛正好考到博弈和图论，博弈费了好些力才推理出来，图论一开始搞错了题目的意思，最后分析题目计算时间复杂度的时候就已经发现可能超时间，但是没有找出合理的办法 — 其实在当时看看，也的确应该是去试试，因为感觉可能比较简单，AC的人并不少。

当然赛后发现如果有那个知识，那么这道题目还是比较简单的，哈哈。

GH题目就是比较简单的质因子分解+哈希，但是糟糕的是当时虽然想到质因子分解，但是没有具体的细想，去探究，深度不够。 — 也是因为受了之前比赛的影响，很多时候因为我自己想得太深方向还不对结果浪费了时间。

总结

算法书籍 莫队算法 最大团 最短路 A _搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此，A_搜索算法是最佳优先搜索的范例。 集束搜索（又名定向搜索，Beam Search）——最佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现最前面的m个最符合条件的节点，m是固定数字——集束的宽度。 二分查找（Binary Search）——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。 分支界定算法（Branch and Bound）——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。 Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。 数据压缩——采取特定编码方案，使用更少的字节数（或是其他信息承载单元）对信息编码的过程，又叫来源编码。 Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。 Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。 离散微分算法（Discrete differentiation） 动态规划算法（Dynamic Programming）——展示互相覆盖的子问题和最优子架构算法 欧几里得算法（Euclidean algorithm）——计算两个整数的最大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。 期望-最大算法（Expectation-maximization algorithm，又名EM-Training）——在统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大可能估计值；第二步是最大化，最大化在第一步上求得的最大可能值来计算参数的值。 快速傅里叶变换（Fast Fourier transform，FFT）——计算离散的傅里叶变换（DFT）及其反转。该算法应用范围很广，从数字信号处理到解决偏微分方程，到快速计算大整数乘积。 梯度下降（Gradient descent）——一种数学上的最优化算法。 哈希算法（Hashing） 堆排序（Heaps） Karatsuba乘法——需要完成上千位整数的乘法的系统中使用，比如计算机代数系统和大数程序库，如果使用长乘法，速度太慢。该算法发现于1962年。 LLL算法（Lenstra-Lenstra-Lovasz lattice reduction）——以格规约（lattice）基数为输入，输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用：背包加密系统（knapsack）、有特定设置的RSA加密等等。 最大流量算法（Maximum flow）——该算法试图从一个流量网络中找到最大的流。它优势被定义为找到这样一个流的值。最大流问题可以看作更复杂的网络流问题的特定情况。最大流与网络中的界面有关，这就是最大流-最小截定理（Max-flow min-cut theorem）。Ford-Fulkerson 能找到一个流网络中的最大流。 合并排序（Merge Sort） 牛顿法（Newton’s method）——求非线性方程（组）零点的一种重要的迭代法。 Q-learning学习算法——这是一种通过学习动作值函数（action-value function）完成的强化学习算法，函数采取在给定状态的给定动作，并计算出期望的效用价值，在此后遵循固定的策略。Q-leanring的优势是，在不需要环境模型的情况下，可以对比可采纳行动的期望效用。 两次筛法（Quadratic Sieve）——现代整数因子分解算法，在实践中，是目前已知第二快的此类算法（仅次于数域筛法Number Field Sieve）。对于110位以下的十位整数，它仍是最快的，而且都认为它比数域筛法更简单。 RANSAC——是“RANdom SAmple Consensus”的缩写。该算法根据一系列观察得到的数据，数据中包含异常值，估算一个数学模型的参数值。其基本假设是：数据包含非异化值，也就是能够通过某些模型参数解释的值，异化值就是那些不符合模型的数据点。 RSA——公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用，大家也相信它有足够安全长度的公钥。 Schönhage-Strassen算法——在数学中，Schönhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为：O(N log(N) log(log(N)))，该算法使用了傅里叶变换。 单纯型算法（Simplex Algorithm）——在数学的优化理论中，单纯型算法是常用的技术，用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组，以及一个等待最大化（或最小化）的固定线性函数。 奇异值分解（Singular value decomposition，简称SVD）——在线性代数中，SVD是重要的实数或复数矩阵的分解方法，在信号处理和统计中有多种应用，比如计算矩阵的伪逆矩阵（以求解最小二乘法问题）、解决超定线性系统（overdetermined linear systems）、矩阵逼近、数值天气预报等等。 求解线性方程组（Solving a system of linear equations）——线性方程组是数学中最古老的问题，它们有很多应用，比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组，可以使用高斯—约当消去法（Gauss-Jordan elimination），或是柯列斯基分解（ Cholesky decomposition）。 [阅读全文]

• 浙江省赛题目，分析后直接暴力即可，奈何场上脑子里全是floyd，WA无数次。

• 做题一定要先分析时间复杂问题，采取暴力方法，然后再考虑复杂问题解决方法。

• 此外今天开始使用赛用vimrc才发现出现不少问题，还好提前使用了。

隐式图搜索，多个状态然后减枝。。没看懂李大大所说可以承受是个啥意思。。

做起来实在太累了。。减枝的部分看了别人的代码，发现着实麻烦，不如用优先队列来的痛快=- =还有用优先队列做的= =

主要是$vis[x][y][p][c]$这组状态比较难搞，但是给了优先级（时间短的先出队），事情就好办了。

问能不能拼接一条项链，条件是首尾相同构成环。

这个题的坑在：

1. 虽然保证连通，但是不一定每个颜色都有，所以单纯的暴力euler(1)是很愚蠢的。

2. 题目本身是要求顺序输出的，也就是dfs不能回溯，如果回溯，为了保证准确性，需要交换uv的位置来保证。

3. 通过统计出度入度判断是否满足欧拉回路。

插件管理方面

1. 对于Vundle，可以给每个插件添加一个简单的配置文件，针对不同的插件进行不同的载入，有时间可以实现一下。
2. 或者可以重新造轮子，自己写一个插件管理器，实现功能。
3. 莫非已经实现了功能而我没有发现？= =

Map.vim

1. /tmp/tmp.cpp

ACM.vim

1. 添加gdb调试脚本功能。
2. 添加一键比对功能。

另外

可以将一部分相关的func转移。

火会蔓延，人被火追着跑，能否跑出边界的问题。

bfs火之后bfs人，或火和人放在一个队列里面bfs

坑是没有火的情况，如果从0更新火势图而不是inf开始，那么可能造成没火不能跑的情况。