发布于

UVa-10917 Walk Through the Forest [最短路+DP/记忆化递归]

题目：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1858

uva访问不到的可以去vjudge上：https://vjudge.net/problem/UVA-10917

题目大意是说有两个点1，2. 从1出发走到2，每次只走可以make progress的路径， 所谓的make progress的A到B的边指的是从存在B到2的某条路比A到2的任何路的长度都要小，实际上就是B到2的最短路比A到2的最短路要短。可以用单源最短路求出2出发的所有最短路，然后从1开始做一个DFS就可以求出正确答案。但是需要注意的就是这个DFS要记忆化一下，否则会TLE

继续阅读“UVa-10917 Walk Through the Forest [最短路+DP/记忆化递归]”
发布于

CodeForces – 727E [字符串哈希]

题目传送门： http://codeforces.com/problemset/problem/727/E

题目大意是说给出n个长度均为k的字符串（两两不同），它们可以排成一个环，这些字符串以排列好的一个环的形式给出。问能否从​\( g(g\ge n) \)​个长度为k的字符串（两两不同）中选出n个形成之前给出的字符串环排列。如果可以请给出环排列的一个线排列。

继续阅读“CodeForces – 727E [字符串哈希]”
发布于

碎碎念的年终总结

总的说来2018年的精彩程度超越了之前我所经历过的年份。 在我看来这是一个非常值得纪念的一年， 所以才有了这样一篇不那么精彩的总结。 毕竟是涉及自己最珍贵的经历的记录， 我会在这篇文章里面尽量避免academic style的， 不过说到底我也不会什么正经的academic style罢了。

继续阅读“碎碎念的年终总结”
发布于

动态规划的斜率优化

在某些情况下, 动态规划的转移数目过多导致即使使用动态规划算法也会令复杂度过高. 但往往, 在某些情况下状态转移方程具有某些特别的性质, 对转移方程进行变形就可以转化为某种斜率的形式, 利用斜率的几何意义构造凸集, 通过维护一个单调双端队列使得​\( O(n^2) \)​复杂度的状态转移优化至​\( O(n) \)​.

下面结合几个例子讲一讲。

继续阅读“动态规划的斜率优化”
发布于

VOCALOID学习日志（0）——相关软件的下载与安装（正版获取）

说到Vocaloid的相关教程，梦尘脑子里已经构思好了后续文章的想法思路，结果发现貌似想要拉萌新入坑，除了用人设让他们爱上这些可爱的妹子们，更要让他们产生调教的欲望（笑）。

所以，如果萌新们想要成为一名调教师的话，手里面总要有些工具的嘛。（虽然自己也是萌新）

嘛，于是就在这里先介绍相关软件的下载与安装方法（大量链接警告！！！）

继续阅读“VOCALOID学习日志（0）——相关软件的下载与安装（正版获取）”
发布于

矩阵乘法的strassen算法

直接按照定义计算两个n阶实数方阵的乘积需要进行​\( n^3 \)​次实数乘法

如果将方阵分割，按照矩阵的分块乘法去计算，看似通过递归化简了问题，实际上完成乘法的复杂度依然是​\( \Theta (n^3) \)​。因为矩阵分块之后分治为了八次小矩阵乘法，然后进行矩阵加法，递推式 \(T(n) = 8T(\frac{n}{2}) + \Theta(n2)\)给出的这种方法的解，依然是\( \Theta (n^3) \)

而strassen算法给出了一个复杂度为​\( \Theta (n^{\log _{2} 7}) \)​\( \approx\Theta( n^{2.81}) \)的算法

继续阅读“矩阵乘法的strassen算法”