这个是求字符串循环之后的最小串：把字符串先复制一份放到原串末尾，然后对两个串相互比较，这里先比较i=0和j=1这两个串，如果出现了字符不相等的情况，需要选择i和j其中一个改变其值，改多少呢？
如果a[i+k] > a[j+k]，那么把i变成i+k+1即可，为什么呢？为什么i不可能是i到i+k中的值呢？因为无论i取i到i+k中的任何值（假设为i+m），那么我们都可以找到另一个串a[j+m]比a[i+m]要小（因为a[j+k] < a[i+k]），因此i如果变成i+m的话，其实不是最优的。
贴下关键部分的代码
int go(){
int i = 0, j = 1 ...SRM 208 DIV1 的level 3，题意是给一个张网，每个给子里有一定量的苹果，求然后有三个人从左上角走到右下角，每个人走过一个格子的时候就会把当前格子里的苹果都带走，问三个人能拿到的最多的苹果是多少。
很显然的一个解法dp，dp[step][i][j][k]，意义是走完step步，第一个人在(i,step-i)，第二个人在(j,step-j)，第三人在(k,step-k)的时候能拿到的最多苹果是多少。
这题还有另一种解法，是要观察出一个性质，就是三条路径除了第一行和最后一行，路径不会相交，就是说可以理解成从第一行连到最后一行的三条路，路径不相交，相交肯定不是最优的，这个比较容易证明。然后是dp的时候怎么能体现出这个三条路径不相交的性质来。dp[row][i][j][k]为第row行，当前三条路径终点在(row,i)，(row,j)，(row,k)三个点时能拿到的最多苹果 ...
1、任何的01背包，都可以把价值V和容量W互换，就是说有两种方法可以解背包，比如将n个物品放入容量为W的背包，问能获得的最大价值。可以转化为，将n个物品放入容量为V（V为所有物品的价值总和）的背包，能获得的最小价值（对应于原问题中的最小重量）是多少。所以，当某个方向的问题不可解时（比如状态太多，或者状态下标要用浮点数表示什么的）就可以将其用另一个方向做，典型的问题是hdu2955抢银行。
2、有的时候我习惯用dp值为-1代表某个状态不可达，因为有些时候怕如果赋值为正负无穷的话会运算越界，但是如果设置不合法dp值为-1的话，一定要确保正常的dp值不能为-1。
3、打印解路径。可以用两个一维数组打印（一个数组是dp数组，另一个是决策数组s，s[i]记录dp[j]是怎么转移来的），这个时候需要背包是恰好装满时候的背包，如果是可以不装满的背包，无法用两个一维数组来打印解路径，需要至少用一个二维数组，但是其实任何不装满的背包都可以按照装满背包的方法解，最后再检查一遍所有的合法值就行了。
总结一下接触过的常用数据结构（FIFO队列和栈就不说了，SPLAY、Treap、红黑树什么的看情况再写）
先说下STL，STL迭代器分为五种，input，output，正向，双向，随机存取。支持后面特性的迭代器一定支持前面的。
STL中，vector和deque都支持随机访问；set，map和list都只支持到双向迭代器，不支持随机存取，也就是说不能对这三个的迭代器进行+-运算（但是可以进行++，--运算，因为支持双向迭代）；stack，queue，priority_queue不支持迭代器，它们都是容器适配器。
队列内的元素是单调排列的，和普通队列的区别在于队列尾部可以弹出元素。常用于优化DP什么的，一般可以把复杂度相对高的东西优化不少。
问题是：给定一个数组，支持两种操作：A.修改某个元素的值，B.查询某个区间[L,R]的所有元素的和
树状数组也叫Fenwick Tree，本质是用数的二进制进行快速计算，设置一个C数组，C ...
典型的求素数用的是筛子的方法，最简单的程序是这样的
void getPrime(int n){
int mk[100005] = {0};
vector<int> prime;
for(int i=2; i<=n; i++){
if(!mk[i])prime.push_back(i);
for(int j=i+i; j<=n; j+=i)
mk[j] = 1;
}
}
那如果要筛出<=n的质数，大概的复杂度是多少呢？
其实需要的次数为n x (1 + 1/2 + 1/3 + 1/4 ...
恩，本篇文章再写一点深入的思考。忽然发现我的博客开始走找各种被人忽略的细节的路线了。今天要为大家带来的是差分约束的两个题，并且会为大家说明一下自己做这题时候的思考和网上流传的一些错误，不想让网上抄来抄去的东西误导了大家的思路。OJ数据弱，这个是真的，题目那么多，不能保证每个题测试数据的质量，所以很多错误的程序也能过，导致了大家可能把错误的思路也认为是正确的了。恩，下面开始正文。
题意：n头牛站在x轴上，并且x[1]<=x[2]<=...<=x[n]，然后给定了一些喜欢的关系和讨厌的关系，喜欢的关系是（a，b，c）代表牛a和牛b的距离不才能超过c，讨厌的关系也是（a，b，c）代表牛a和牛b的距离至少是c，然后求牛1和牛n的最大距离是多少。如果没有合法的站位，输出-1；如果牛1和牛n可以无穷远，输出-2；否则输出牛1和牛n的最大距离。
这个题看上去很水的，差分约束的题，按照“最长路求最小值，最短路求最大值”的理论建图就行了。需要注意的一个细节就是，如果同时满足没有合法的站位和牛n牛1可以相距无穷远，那么按照题意应该是输出-1的 ...
写个博客记录一下最短路的几种算法，尽量做最正确的解答，减少大家的疑惑，网上有好多讲的都抄来抄去，还有好多讲的都是错误的。。。
熟悉的最短路算法就几种：bellman-ford，dijkstra，spfa，floyd，下面针对这几个算法具体解析一下。
首先说明一点，就是关于负环的问题。
bellman-ford可以用于边权为负的图中，图里有负环也可以，如果有负环，算法会检测出负环。
dijkstra只能用于边权都为正的图中。
spfa是个bellman-ford的优化算法，本质是bellman-ford，所以适用性和bellman-ford一样。
floyd可以用于有负权的图中，即使有负环，算法也可以检测出来。
任何题目中都要注意的有四点事项：图是有向图还是无向图、是否有负权边，是否有重边，顶点到自身的可达性。这几点非常重要，可以在我下面的讲解中体会。
这个最简单，只能在边权都为正的图中用这个算法，不论是有向图还是无向图。算法是个贪心的过程，每次拿出一个没有被标记过的距离最小的顶点，并从这个点进行扩展，也就是尝试松弛从这个点出发的每条边。为什么一定要用在正权图中呢？因为算法的过程相当于把整个图中的点一个一个加入到“处理完”集合S的过程，并且处理完集合中的点的距离一定是从源点到该点的最小距离。如果图中有负权，会导致一个进入集合中的点可能在后面的过程中距离值变得更小，算法就错了。举个例子来说：有向图 ...
题意：一个无向图，求从一个顶点到另一个顶点的恰好经过k条边的最短路径，可能有自环，无重边。
分析：这个题其实就是矩阵乘法，用了dp的思想，dp[k][i][j]代表恰好经过k条边的i到j的最短路，那么dp[k][i][j]=min{dp[k-1][i][p]+g[p][j]}（其中g是原图）。可以用矩阵乘法来做，因为对于dp[k-1][i][j]来说，只要乘以一次原图矩阵，就相当于做了一次转移，得到的就是dp[k][][]矩阵。我想说这个题除了状态设计和floyd稍微沾了一点边之外，其他一点关系都没有了，竟然看到网上好多人用写floyd的循环顺序来写这个题，真是令人费解，这个题只是改了矩阵乘法的最内层，改变了矩阵乘法的运算规则，和floyd真的没关系啊！！！
另外，矩阵乘法的规则和在图中求一个点到另一个点的恰好经过k条边的方法数的规则是一样的，二者的状态转移方程也是一样的，所以矩阵乘法不需要经过任何修改就能做这种求恰好经过k条边的方法数的题，而不用像这个题还得做些修改。这些题都需要注意初始化的东西 ...
题意：一个无向图，所有边权为正，求这个无向图中的一个权值最小的环（环的权值定义为环中所有边权值的和）。要求环的顶点数至少为3个，且图中可能存在重边。
分析：这个题我最开始只有搜索的想法，后来看到了floyd的做法，才折服了，向强大的floyd致敬！ 这个题可以这么想，抛开floyd的思路，我们知道每个环中都有一个顶点标号最大的顶点（比如为k）。我们可以枚举这个顶点，枚举完这个顶点之后我们再枚举另外两个和它相邻的顶点i和j（i，j < k）。如果这个时候我们知道i到j的不经过k的最短路（设为p），那么我们就可以把边i->k，k->j和路径p组合起来，成为一个环，如果这个环的权值小于当前求出的所有环里面的最小权值的话，那么就更新一下最小值，并记录路径。
恩，这个思路看上去是挺好的，但是我们怎么求i到j的不经过k的最短路呢？想到了什么？floyd！ floyd的本质是个dp，dp[k][i][j]代表i到j的中间节点（不包括i和j）都在区间[1，k]时，i到j的最短路。floyd算法的最外层循环是个从小到大枚举k的过程，当最外层刚刚进入第k次循环的时候 ...
题意：一个图，有两种边，一种是双向边，权值为正，一种是单向边，权值为负。
问能否在图中找到一个负环。
分析：典型的找负环的题，但是这个题没有规定起点，所以直接从点1开始做bf是错误的。
bellman-ford算法可以判断一个从源点可达的环，那这个题需要做n次bf吗？
其实可以建立一个源，从源向每个图中的点引一条任意权值的边（不必为0），然后用bf就行了。
本质上就是初始化和经典的初始化不同，细节见代码。
/*
POJ 3259
code by heifrank
*/
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int MV = 505;
vector< pair<int, int> > G[MV];
int d ...Page 1 / 1