程序员进阶之算法练习（二十二）

前言

时间来到6月，又是一年高考时。 几年之前是坐在教室怀念高考，现在是上班敲着代码怀念学生时代。

正文

1、Lakes in Berland 题目链接 ** 题目大意：** 给出n行m列的cell，每个cell与其上下左右联通； cell为*表示陆地，为.表示水，n*m的cell之外是海洋； 被陆地围起来，并且没有和海洋连接的区域称为湖； 现在要求把某些cell从.改成，使得图只有k个湖；（题目给出的图，有不小于k个湖），并且修改的点最少； 输出最少的修改点数，再输出修改之后nm的cell。 n, m and k (1 ≤ n, m ≤ 50, 0 ≤ k ≤ 50)

Example

 input
 5 4 1
 ****
 *..*
 ****
 **.*
 ..**
 output
 1
 ****
 *..*
 ****
 ****
 ..**

** 题目解析：** 要使得修改的点最少，那么应该从cell最少的湖开始修改； 可以对全图进行一次遍历，用dfs找出所有的湖，然后排序； Tips：不要给函数定义太复杂的功能； 这次在尝试在dfs的返回值携带数量和当前是否为湖的信息，导致WA了几次；

2、One-Way Reform 题目链接 ** 题目大意：** n个点（n=200），m条无向边，没有重边和指向自己的边； 现在把无向边改成有向边，要求入度等于出度的点最多。 ** 输入：** t，表示样例个数。 每个样例先输入n，m，再输入m条边； ** 输出：** 先满足要求的点数，再输出所有边(u，v）u=>v。

Example ** input** 2 5 5 2 1 4 5 2 3 1 3 3 5 7 2 3 7 4 2 output 3 1 3 3 5 5 4 3 2 2 1 3 2 4 3 7 ** 样例解释：** 样例1：3个点，分别是1、2、5。 样例2：3个点，分别是1、5、6。

** 题目解析：** 这个题目需要一点脑洞。 如果一个联通图里，所有点的度数都是偶数，那么存在一条回路，使得所有点的点的入度=出度。 这也是无向图存在欧拉回路的充要条件： ** 一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。** 接下来就是要开脑洞的时候：某个点如果是奇数，那么和一个虚拟的点0连接。 那么会得到一个无向图，并且所有点的度数都是偶数的无向图。（因为度数为奇数的点的数量必然是偶数） 对每个点遍历一次（dfs），标出有向边即可。 满足要求的点数，就是度数为偶数的点数。

3、Dense Subsequence 题目链接 ** 题目大意：** 给出一个字符串s，全小写字母组成；再给出整数m。 现在让你从s中选择某些位置，把对应位置的字符标记为绿色； 要求s的所有长度为m的子串，都存在至少一个绿色字符； 把所有绿色字符按字典序最小重新排列得到的字符串str，求让str的字典序最小。 s的长度不大于10w。

Examples ** input** 3 cbabc ** output** a ** input** 2 abcab ** output** aab ** 样例解释:** 样例1：选择第3个字符为绿色字符； 样例2：选择第1、2、4个字符为绿色字符，把绿色字符重新排序，字典序最小字符串的是aab;

** 题目解析：** 字母要求的是不是最后的字符串长度最短，而是字典序最小；那么，aab相对于ab而言是更优解。 可以想到一个贪心：先尽可能选择字符a，再尽可能选择b，再到c、d、e... 假设a可行，那么如何找到尽可能少的字符串a，能够覆盖整个字符串？ 这里用到另外一个贪心：在字符串[0, m-1]中，必然会有一个绿色字符，而且这个字符串越靠近m-1，越有利于后面的字符串被绿色字符串覆盖； 于是，可以设定一个区间[posStart, posEnd]=[0, m)，从posEnd-1开始倒着选择字符，找到目标字符再扩展posEnd，直到posEnd>=n； 如果当前字符串c作为绿色字符不能覆盖整个字符串，那么从c+1开始枚举； 这里还有一个trick，在枚举字符串c的时候，需要用<c的字符串先扩展，再枚举字符c； 虽然代码里面有一个for，两个while，但是整体的复杂度仍是：O(N)！！

4、Goods transportation 题目链接 ** 题目大意：** n个城市，城市之间存在单向边； 每个城市都会产出p[i]单位的货物；每个城市最多卖出s[i]单位的货物； 对于所有编号为 i、j的城市（1 <= i < j <= n） 都存在一条边i=>j，能运送一次，最多为c单位； 输入n、c以及p[i] 和 s[i]，输出能卖出去的最大单位数； n and c (1 ≤ n ≤ 10 000, 0 ≤ c ≤ 1e9)

** Examples** ** input** 3 0 1 2 3 3 2 1 ** output** 4

样例解释： c=0，那么城市之间不能运输，那么只能卖出1 + 2 + 1 = 4 单位；

** 题目解析：** 题目给出的就是网络流，但是N=1w，边的数量非常多； 按照题目给的条件建图：

       点           流量
   src 到 n个城市    p[i]
n个城市 到 dest      s[i]
 i 城市 到 i+1的城市   c

容易知道最大流=最小割，在给出题目中因为所有的城市都存在边到src和dest， 那么必然存在边p[i]或者s[i]为割，而且流量为c的边必然不会在最小割内； （因为如果p[i] 和 s[i]都不在割内，那么点i就和src与dest相连）

那么问题变成： dp[i][j] 表示最小割中，前i个城市有j个城市与src相连的最小割容量； dp[i][j] = min(dp[i-1][j-1] + s[i], dp[i-1][j] + j*c + p[i]);

dp[i-1][j-1] + s[i] 表示第i个城市直接连src的边，加入最小割； dp[i-1][j]+ j*c + p[i] 表示i城市连src的边不加入最小割，那么为了断开点i与dest的关系，需要断开前i个点中，所有与src相连的点到i的边（c*j），还有p[i]的边；

代码是很短的。

typedef long long lld;
const int N = 222222, M = 22;

int p[N], s[N];
lld f[N];

int main(int argc, const char * argv[]) {
    int n, c;
    cin >> n >> c;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        f[i] = 1LL << 62;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j; --j) {
            f[j] = min(f[j-1] + s[i], f[j] + (lld)j * c + p[i]);
        }
        f[0] += p[i];
    }
    lld ans = f[0];
    for (int i = 1; i <= n; ++i) {
        ans = min(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

总结

最近被各种价值观影响： 老老实实写代码没有用，功劳都是别人的； 程序员是项目组的最底层，各种加班，还要背锅； 房价涨的飞起，存钱赶不上涨的房价； ... 其实这些只是大家茶余饭后的谈资，下班后喷产品，上班还不是都乖乖听产品做功能。都不喜欢加班，可是需求没做完，bug没改完，并不能提前回家；需求做完了会有新需求，某些bug修复可能会触发别人若干年前埋下的bug。房价涨的飞起，可是自己又不能影响什么。 换了新环境，其实就是从一个封闭的小圈子走到另外一个封闭的小圈子。每个圈子的关注点都不一样，在各种环境下坚持自己的认知和想法是一件很重要的事情！