开个帖子记录自己刷挑战程序竞赛的历程

目前已经断断续续刷了两周，为了避免自己到后面就放松下来不能坚持，这里开个帖子督促下自己。如果有感兴趣的小伙伴也欢迎加入。

简单说说为什么选择开始刷《挑战程序设计竞赛》。我感觉在lc已经刷了一些题目之后，现在再通过海刷来学习新的知识点效率还是有点低。想要稍微挑战一下自己学习一下更难一点的套路。上网搜索了一番之后我觉得这本书还是挺好的，讲解比较详细，而且带有一定数量难度适中的题目。因此趁着最近有时间开始练习练习，目标是刷完第二章 2.1 - 2.7，以及中级篇的 3.1 和 3.2，还有高级篇的 4.4和 4.6.　

目前的进度只是刷完了2.1, 路才刚刚开始。

我觉得如果是在美国找工作的话刷LC足够了，而且也非常有效。LC的优势除了题库针对性强和test case多以外，还有海量的大佬在讨论区解答。多看各路大佬的答案有种发现新世界的感觉，而书上的解答是不会更新和用到最新的库的。

今天的重点在于复习各种图论算法。一般来说我不会在总结里面写code但是这一章是个例外，因为里面涉及到的算法我实在太不熟了。所以写下code以备随时查阅。我们统一输入， 假设给出某有向带权图d所有边vector<vector<int>> edges, 每个edge用一个vector表示, 包含[u, v, w]也就是起点终点和权重, 节点总数V(编号1->V)。假设起点为A， 我们用d[ u]来表示起点A到u的最短距离。

1. 最短路径问题

所有最短路径问题假设没有负环，不然很显然不存在最短路径。

1.1 bellman-ford

解决单源，有负边图中的最短路径问题。其核心思想设d[ i]是起点A到i的最短路径，则有d[j] = min(d[ i] + w[ij]),其中i是所有和j相连的点。反过来推断，我们可以先求出从A点出发1条边能到达的最短路径，然后求2条边能到达的最短路径，直到求出 V-1　条边能到达的最短路径。因此实际上我们循环 V-1 次，对所有边进行松弛操作即可, 复杂度 O(VE)。这里所谓的松弛操作是指我们利用边 u->v 来优化 d[v]的过程 (d[v] = min(d[v], d[ u] + w[uv]).

为了判断是否存在负环，我们只需要进行V次路径松弛。如果发现最后一次某d[ i]又被更新了，那么证明存在负环（因为如果没有负环，最短路径不可能经过一个点两次，换句话说最短路径最多只有V-1个点）。

代码:

int bellman_ford() {
        int d[V+1];
        int u, v, w;
        for (int i = 1; i <= V; i++) {
            d[ i] = INT_MAX;
        }
        d[A]= 0;
        for (int i = 0; i < V-1; i++)
            for (vector<int> edge: edges) {
                u = edge[0];
                v = edge[1];
                w = edge[2];
                if (d[ u] != INT_MAX && d[v] > d[ u] + w)
                    d[v] = d[ u] + w;
            }
}

最后，注意bellman-ford的一个特例:如果给出的图是DAG的话那么我们可以先计算图的拓扑排序，然后按照拓扑排序的顺序依次进行路径松弛即可。这样的复杂度仅仅为O(E).

1.2 Dijstra　

解决单源，无负边图中的最短路径问题。仔细观察一下bellman-ford算法，可以发现其中存在一些时间浪费。比如如果d[ i]不是最短路径，自然d[ i] + w[ij]也不可能是A到j的最短路径。再比如如果d[ i]没有被更新(d[ i]已经是找到的最短路径了)，下次循环我们还是会依次更新所有和i相邻的边。

为了优化，我们可以考虑假设d[ i]已经是A能出发所达到的最短路径，那么我们可以把和i相邻的边依次松弛一遍，然后就不用再考虑i了。因为在没有负边的情况下，d[ i]不可能在以后的更新过程中会变得更小。我们可以简单的在bellman-ford的基础上修改一下。我们首先需要用used数组来记住那些最短路径还没有被确定的点，然后每次松弛的时候都找 used[ i] == False 中d[ i]最小的点i。随后我们只需要松弛点i的邻居节点即可。

代码如下：

int dijstra_v1() {
        int d[V+1];
        bool used[V+1];
        int u, v, w;
        fill(used, used+N+1, false);
        fill(d, d+N+1, INT_MAX);
        d[A] = 0;
        int cost[V+1][V+1];
        for (int i = 1; i <= V; i++)
            for (int j = 1; j <= V; j++) {
                if (i == j)
                    cost[ i][j] = 0;
                else
                    cost[ i][j] = INT_MAX;
        }
        for (vector<int> edge: edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            cost[ u][v] = w;
        }
        for (int i = 0; i < A-1; i++) {
            int v = -1;
            for (int j = 1; j <= A; j++) {
                if (!used[j] && (v == -1 || d[j] < d[v]))
                    v = j;
            }
            for (int j = 1; j <= A; j++) {
                if (cost[v][j] != INT_MAX && d[j] > d[v] + cost[v][j]) {
                    d[j] = d[v] + cost[v][j];
                }
                    
            }
            used[v] = 1;
        }
}

看似很复杂，主要是我们需要先初始化这个cost矩阵，其中cost[ i][j]记录着i到j的路径长度，INF表示i和j不直接相连。这样复杂度是O(V*V)。

注意到这里最麻烦的一个操作是找d[ i]中的最小值。为了优化这个过程我们可以把d[ i]加入最小堆中，这样的复杂度就是O(ElogV)了。这里的E是因为我们对每个边都进行了一次松弛操作。然后logV是因为堆中总元素不会超过定点总个数。

int dijstra_v2() {
        typedef pair<int, int> P;
        int d[V+1];
        fill(d, d+V+1, INT_MAX);
        d[A] = 0;
        vector<P> graph[V+1];
        for (vector<int> edge : edges) {
            graph[edge[0]].push_back(make_pair(edge[1], edge[2]));
        }
        priority_queue<P, vector<P>, greater<P> > pq;
        pq.push(make_pair(0, A));
        P node;
        while (!pq.empty()) {
            node = pq.top();
            pq.pop();
            int u = node.second;
            if (d[ u] < node.first) continue;
            res = max(res, node.first);
            cnt += 1;
            for (P neigh: graph[ u]){
                int v = neigh.first;
                int w = neigh.second;
                if (d[v] > d[ u] + w) {
                    d[v] = d[ u] + w;
                    pq.push(make_pair(d[v], v));
                }
            }
        }
}

注意一些坑，比如某个点可能不止一次被加入并且从pq中pop出来，这是因为对某点v, 我们可能找到经过u1->v的最短路径以及经过u2->v的最短路径，但是只有一条是从起点A->v的最短路径。为了解决这个问题我们在pop出某点v的时候计算下此时的最短距离是否比d[ u]要小，如果是的话忽略即可。

此外，如果有负边的话，dijstra算法是不行的。最简单的例子 A->B:1,　A->C:2，C->B:-3.　A->B的实际最短路径是-1。可是根据dijstra算法，第一次找到A->B的最短路径后就不会再去考虑它了，这样会得到错误的结果。

dijstra的一个特例是所有边没有权重或者所有边权重相同的情况，这种情况下显然bfs就可以了。复杂度O(E)。

1.3 Floyd-Warshall算法

多源最短路径问题，求所有点到所有点的最短路径。可以处理存在负边的情况。假设D[i,j,k]是从i到j经过1->k号中间节点的最短路径的长度。则考虑两种情况：最短路径不经过节点k，则D[i,j,k] = D[i,j,k-1], 或者最短路径经过节点k，则 D[i,j,k] = D[i,k,k-1] + D[k,j,k-1]。综合起来也就是

D[i,j,k] = min(D[i,j,k-1], D[i,k,k-1] + D[k,j,k-1])

注意k只依赖于k-1的情况，因此空间复杂度可以优化到 O(V^2)，时间复杂度显然是O(V^3)。代码极其简单:

int floyd() {
        int dp[V+1][V+1];
        for (int i = 1; i <= V; i++)
            for (int j = 1; j <= V; j++)
                dp[ i][j] = i == j ? 0:INT_MAX;
        for (vector<int> edge:edges) {
            dp[edge[0]][edge[1]] = edge[2];
        }
        for (int k = 1; k <= V; k++)
            for (int i = 1; i <= V; i++)
                for (int j = 1; j <= V; j++) {
                    if (dp[ i][k] != INT_MAX && dp[k][j] != INT_MAX)
                        dp[ i][j] = min(dp[ i][j], dp[ i][k] + dp[k][j]);
                }
}

因为代码过于简单，在输入规模很小的情况下也可以考虑用 Floyd 算法来计算单源最短距离。


补充内容 (2019-3-3 06:47):
dijstra实现的坑
1. 注意初始化，节点编号1->V,初始化V+1个元素
2. if d[u ] <= node.first 则会出错，因为 u的邻居节点还没有被relax过

动态规划

Dynamic Programming 的核心要点在于提取并且避免重复运算，下面通过几种经典套路来介绍其思想。

1. 背包相关

1.1  0/1 背包问题

n个价值为 wi, vi的物品，从这些物品中挑选总重量不超过 W 的物品，每个物品只能挑选一次，求最大值。

直接朴素解法，考虑到每个物品都有选以及不选两种选择，我们定义 rec(i, j) 为从第i个物品开始选择，总重小于j能获取的最大价值。那么核心的递归表达式是 rec(i, j) = max(rec(i+1, j), rec(i+1, j - w[ i ]) + v[ i ])， 复杂度为O(2^n)。

画出递归调用，可以发现经常有重复调用的情况，因此我们可以用一个dp矩阵把计算出的 rec(i, j) 记录下来。这样如果调用 rec(i, j)的时候发现 dp 里面已经有值了即可直接返回。时间复杂度取决于 (i, j) 组合状态总数，也即 O(nW)。这种方法也称记忆话搜索，如果不这么做当然我们也可以通过递推来做。

设dp[ i ][j] 为前i个物品，总重量不超过j的最大价值，那么有 dp[ i ][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]). 这里需要注意三点：

a. 定义是前i个物品，也就是编号 0 -> i-1的物品。这么定义的好处是方便处理边界值。因此需要注意dp的 size为 (n+1, W+1)
b. 初始化 dp[0][0] = 1, 其他 dp[x][0] = 0, dp[0][x] = 0, 原因显而易见
c. 返回 dp[n][W] 即可  

1.2. 0/1 背包问题大重量版本

一模一样的问题，不过限制为 1 <= n <= 100; 1 <= W <= 10^9, 1 <= vi <= 100, 1 <= n <= 100;

这里的问题在于W的范围太大，因此导致了 O(nW) 的复杂度过高。然而我们注意到物品的总价值不会超10000, 因此灵机一动（个鬼）的想到可以通过价值来限制重量。我们这么定义：dp[ i ][j]是前i个物品取到价值为j的最小重量。那么我们我们既可以在前i-1个物品中选价值为j的，或者在前i-1个物品中选价值为j-v[i-1]的，再选择第i-1个物品，这样可得：

dp[ i ][j] = min(dp[i-1][j], dp[i-1][j-v[i-1]] + w[i-1])

因为显然前0个物品的总价值只能为0，因此初始化为 dp[0][0] = 0, dp[0][x] = INF。最后返回最大的j使得dp[n][j] < INF 即可。这样的复杂度就变成了 O(nV), V为总重量。

1.3. 完全背包问题

和0/1背包相同，不过现在每个物品可以取无限多次。

dp[ i ][j] = max(dp[i-1][j], dp[ i ][j-w[i-1]] + v[i-1]) 即可。表明虽然第i-1个物品取过了，不过还可以再接着取。

顺便一说dp的空间复杂度优化。当dp[ i ][j]的结果只依赖于dp[i-1][j]的时候我们可以用1D array来记录状态。但是遍历j的时候需要从大往小遍历（否则会覆盖上一轮循环的结果）。当当dp[ i ][j]的结果只依赖与dp[i-1][j]的时候则还是从小往大遍历。

1.4. 多重部分和问题

给n种硬币，每种硬币个数为 C[ i ], 币值为 A[ i ], 问可否凑足总计为 m 的数额。

和背包类似的凑硬币问题(本质上就是 combination sum)，区别在于这里硬币的种类有限，并且每种给出了具体的数量。一种比较容易想到的思路是用 dp[ i ][j] 来表示前i种硬币凑面值为j的凑法，最后返回dp[n][m]。然而稍加分析发现这样做复杂度较高。因为dp[ i ][j] = dp[i-1][j] + dp[i-1][j - k*A[i-1]] for all j >= k*A[i-1]。最后需要写一个三重循环，复杂度是 O(m * sum(Ci))。

我们发现这里实际上只需要知道能不能凑，不需要知道具体的凑法。因此一个机智到爆的定义方法是用 dp[ i ][j] 来表示凑足 j 后第i-1种硬币最大的剩余个数 (-1 表示凑不满).　那么我们有

(1) if dp[ i ][j-1] >= 0 : dp[ i ][j] = C[i-1] 　　                    #  前i-1种硬币就足够凑满j了，第i-1个硬币可以全部剩下;
(2) if j > A[i-1] or dp[ i ][j - A[i-1]] <= 0: dp[ i ][j] = -1      #  剩下的硬币总数小于第i-1个硬币的面值，或者我们不能凑足 j的数这种情况显然不能满足要求;
(3) else: dp[ i ][j] = dp[ i ][j - A[i-1]] - 1                              #  我们只要先凑足j - A[j-1], 再取一个C[i-1]就好了。

初始化：dp[0][j] = 0, dp[ i ][0] = C[i-1], 含义很明确：如果需要凑足的面额为0，那所有硬币都能剩下来。最后如果只要有dp[n][m] != -1 则返回 true, 否则返回 false. 复杂度 O(nm).

PS: 这是楼教主男人八题里面的一道，果然不同凡响。。。

2. 字符串/数组相应问题

2.1. LCS 问题

给两个子串s, t, 求这两个子串最长公共子序列长度。

经典题目了，dp[ i ][j]定义为s[:i]和t[:j]的LCS, 随后我们有

if s[i-1] == t[j-1] : dp[ i ][j] = dp[ i ][j] + 1
if s[i-1] != t[j-1] : dp[ i ][j] = max(dp[i-1][j], dp[ i ][j-1])  # 分别对应不取s[i-1]和不取t[j-1]这两种情况

初始化的时候，dp[x][0] = 0, dp[0][x] = 0, 因为只要有一个字符串位0，公共子串长度一定位0. 最后返回 s[n][m], n, m 分别位 s, t 长度。

1.2. LIS 问题

最长上升子序列，给一个数列 A，问其中最长的严格递增的子序列长度。

也是经典老题了。

思路1: dp[ i ]定义为前i个字符。dp[ i ] = 1 + max(dp[j] | for all j < i and A[j-1] < A[i-1]),复杂度 O(N^2)

思路2：dp[ i ]定义为长度为i的LIS的最小末尾元素。首先dp所有元素定义为 INF。然后对每个A[j], 寻找最大的i使得dp[ i ] < A[j],更新dp[i+1] = min(dp[i+1], A[j])来减小长度为i+1的LIS的末尾元素即可。注意dp是递增的，这个过程可以用二分优化，复杂度可以做到 O(NlogN).

3. 计数问题

3.1.划分数

给两个数n, m, 问把n分成不超过m类有几种分法。比如 n=4, m=3则输出4，代表有4种分法：2+1+1, 3+1, 4, 2+2。

用dp[ i ][j]来表示j分成不超过i类的分法。一种思路是从j中先取k，然后再把j-k划分成i-1类，这样就成了 sum(dp[i-1][j-k]) for k = 0->j. 可惜这种做法是错误的。因为会把 1+2+1 和 2+1+1 分别计算成两种不同的结果，然而它们实际上是一种。

正确而诡异的思路是这样的：在分成的i类里，要么没有一个是0，要么至少有一个0，前者的话，我们把i类每个减去1，就可以把 j - i 分成i类的结果是一样的。因此对应dp[ i ][j-i], 第二种情况则对应dp[i-1][j], 相当于把j分成最多i-1份。因此dp[ i ][j] = dp[ i ][j-i] + dp[i-1][j].

初始化：dp[x][0] = 1, 代表把0划分位任意不超过x类都有一种分法0。最后返回 dp[m][n], 复杂度 O(mn)。

3.2. 多重组合数

给n类物品，每类物品有A[ i ]个，从这n类物品中取m个，有多少种取法，注意相同类别的物品无法区分。

这题看上去感觉和多重部分和问题很像，区别在于多重部分和要求取出的数总和为目标值，而这里是问具体的取法。我们用dp[ i ][j]来表示前i个物品取j个的取法。显然 dp[ i ][j] = sum(dp[ i ][j-k]) for k <= j and k <= A[i-1], 表示我们可以现在前i类(0->i-1)数里取j-k个，然后再在第i-1类数里取k个, 因此要求k必须小于第i个数的总个数。写个三重循环可以解决。

下面就开始骚操作了。我们分两种情况考虑。

if j <= A[i-1]: dp[ i ][j] = sum(dp[ i ][j-k-1]) + dp[ i ][j] for k=1->j-1
if j > A[i-1]: dp[ i ][j] = sum(dp[ i ][j-k-1]) + dp[ i ][j] - dp[ i ][j-1-A[i-1]] for k=1->j-1

同时注意 dp[ i ][j-1] = sum(dp[ i ][j-k-1]) for k=1->j-1, 因此综合起来的dp转移表达式就是：

if j <= A[i-1]: dp[ i ][j] = dp[ i ][j-1] + dp[ i ][j] for k=1->j-1
if j > A[i-1]: dp[ i ][j] = dp[ i ][j-1] + dp[ i ][j] - dp[ i ][j-1-A[i-1]] for k=1->j-1

这样就可以在 O(nm) 时间内解决了。。

初始化: 前x类物品取0个都有一种取法，因此dp[x][0] = 1, 其他项为0。返回 dp[n][m] 。

先把之前的总结贴上来。每一小节加上一些概念和习题思路总结，比较好的题目下划线表示。

2.1.1 深度有限搜索其思路是从某种状态开始，不断转移状态直到无法转移，然后退回前一步的状态，不断重复该过程直到搜索到需要的解（或者遍历完所有的状态）。dfs　通常用递归实现，代码简洁。但是需要注意需要避免访问重复的状态，否则会导致死循环

习题:

poj1979: red and black

输入一个矩阵，每个元素表示黑色瓦片，红色瓦片，或者障碍物。输出所有能到达的黑色瓦片的个数

思路：dfs水题

aoj0118: property distribution

输入矩阵，每个元素表示三种不同的物种，相邻同一物种属于同一区域，求区域个数

思路: number of island的简单变形

aoj0038: ball

输入0-9 的全排列，问是否可以把它们分为两组，每组都是递增，同时保持在原排列中相对位置不变。

思路：穷举当然是可以做的，每个数可以尝试将其放在左边那组或者右边那组。但是这题其实贪心也可以做。如果既可以放在左边也可以放在右边，那么我们一定放在左边。这样保证左边的tail比右边的大。如果某个球来了左右都不能放，那么fail.

poj3009 curling

输入一个迷宫，有障碍物。给一个球，问最少需要扔多少次可以将球扔到终点位置。球一旦被扔出去除非撞到障碍否则不会终止。同时撞到障碍后该障碍消失。球最多可以扔１０次。

思路：一开始看到最短需要多少次不假思索就上了bfs,写着写着发现不太对劲－这题的特点在于每次球扔出去之后会对整体的状态造成改变，因为障碍物会被撞飞。所以用bfs也不是不可以写，但是需要同时记录下每次扔球之后的新的障碍物的分布，比较麻烦。再加上这题限制了最多１０次扔球，因此完全可以dfs上了。

要点：
1. 不要思维定式的看到最短，最小就想bfs,特别是限定了搜索深度的问题，dfs也不是不可以
2. 仔细审题，这题有个藏的比较深的条件就是我们不能把球往相邻是障碍物的格子扔。最开始没注意到这个条件我debug了很久很久。。

2.1.5 广度优先搜索

和dfs主要区别在于遍历的顺序。bfs总是先搜索距离初始位置更近的状态。也就是说它的顺序为开始状态-转移１次能到达的状态－转移２次能到达的状。。对于同一个状态宽度有限搜索只经历一次，因此复杂度一般为 O(转移数 * 转移方式).

bfs通常用队列实现，一般来说容易出错的地方在于我们需要将初始状态也标记为已经访问。

习题:

Aoj0058: Cheese

给一个矩阵，里面有障碍物，1-N个奶酪工厂，一个老鼠需要从第一个奶酪工厂吃到最后一个(必须按顺序来),求最短路径

思路：分别进行N次BFS即可。注意每次bfs之间需要重置visited数组。

Poj3669: meteor shower

输入是Ｍ个流星的打击位置以及时间，问某人从原点出发到达安全地点的最短距离是多少，注意流星打击后的地方不能经过。

思路：依然是bfs，初始化状态的时候需要注意把流星打击的坐标位置初始化为最小打击时间。这样bfs的时候通过当前时间和流星撞击时间则可知道是否能够到达邻居位置。

要点:
1. 一个地点可以被流星撞击多次，因此需要取最小打击时间
2. 注意只能在第一向限行动（x>=0, y>=0)。

aoj0121: Seven Puzzle

类似与华容道。输入0-7的排列（排成两行），０可以和上下左右交换，求最小交换次数可以排成 0 1 2 3 4 5 6 7

思路：当然也是bfs了。状态有多种表示方法。我觉得比较简单的是用字符串，交换可以直接调用swap函数，然后遍历过的状态可以直接放到 unordered_set 中避免重复访问。

要点：
1. 如果采取正向bfs你就输了。。这题的要点在于可能的query会非常多，比如 > 1000 个。然而输入的规模其实又不太大。这种情况我们可以采取反向 bfs, 也就是从 0 1 2 3 4 5 6 7 这个最终状态做bfs，记录所有能到达的状态以及相应的最短距离。然后每来一个 query，我们直接从记录的map中寻找一下答案就可以了。

2.1.7 剪枝

在解空间非常大的时候其实我们没必要把所有解都遍历一遍，如果某个状态我们知道无论如何也无法获得解，那么可以提前返回。

穷竭搜索既可以用bfs也可以用dfs，具体选择需要根据题目要求来判断。这里做一个小总结：
1: 如果是要所有结果，dfs
2: 如果要某一结果即可，dfs + bactracking
3: 如果要最短距离，最小xx，考虑bfs

当然也不是绝对的，比如 poj3009 curling 那题

习题：

poj2718: smallest difference

输入一行递增数列，输出这两个数列能形成的两个整数之间的最小差值。

思路: 直接穷举，没啥奇技淫巧

要点：
1. next_permutation的用法。手写dfs会超时
2. 如何用 stringstream 输入不定长而且其中有空格的数列
3. 细心，注意开头为０而且超过１位的数是不算的
4. 需要分别处理数列长度为奇数和偶数的情况，可以抽象出一个方法来把数列从 lo 到 hi 位的转化位int.

poj3187: backward digit sums

输入一列数和整数k，寻找是否存在排列使得其两两相加最后的结果等于k.

思路：next_permutation的另一个简单应用。

poj3050: hopscotch

输入一个整数矩阵，输出遍历该矩阵能形成的不相同的六位整数的个数

思路：dfs水题

aoj0525: Osenbei

煎饼题，大概意思是给一个0/1矩阵，每次可以把某一行或者某一列全部翻转，求最后最多的１的个数。输入规模行0<R<=10, 列 0<C<=1000

思路：这题颇为有趣值得玩味。一个最直接的思路是穷举各行各列的翻法，这样的时间复杂度是 O(2^(R+C)), 但是同时注意到输入规模R的限制是 < 10, C的限制是 < 1000。这样我们就可以考虑也许不需要去遍历列的情况。我们只对行进行遍历，然后对每种情况greedy的搜索最多１的个数。思路是如果某列０比１多，那么我们就翻转之，这样可以获得更多的１．复杂度为 O(RC*2^R)

此外，我写了一个利用位运算加快速度的版本，也就是我们只存每行二进制的整数表示，比如00101存成7，这样每行翻转就用一个简单的 a = ~a　就可以实现了。然而不知为何最后结果迷之 wa, 最后只要写了个朴素的算法，也就是用二维0/1矩阵来保存输入。

这得顶啊. 加油啊.

C++ or Java ?

马克~~~~

"上网搜索了一番之后我觉得这本书还是挺好的" 是哪本书？

持续关注一波

肥宅快乐水 发表于 2019-2-11 08:15
这得顶啊. 加油啊.

多谢鼓励。。希望不鸽