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

前言

时间来到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。房价涨的飞起，可是自己又不能影响什么。
换了新环境，其实就是从一个封闭的小圈子走到另外一个封闭的小圈子。每个圈子的关注点都不一样，在各种环境下坚持自己的认知和想法是一件很重要的事情！