专栏首页落影的专栏程序员进阶之算法练习(二十二)

程序员进阶之算法练习(二十二)

前言

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 文字排版入门—— 排版基础、CoreText和图文混排

    字符是文字的最小单元,以这段文字为例,每个字都是一个字符;需要注意,字符是一个抽象的概念; 当文字真正绘制出来时需要选择字体,以“A”这个字母为例,当字母'A...

    落影
  • 程序员进阶之算法练习(十四)

    前言 坚持做算法练习对开发的好处是抽象能力变强,拿到一个需求能很快对其进行抽象,然后再用学过的设计模式相关知识进行整理,最后用代码实现。 最大的好处在于:对...

    落影
  • 程序员进阶之算法练习(三十三)LeetCode专场

    BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继续Lee...

    落影
  • 大数据时代的质量观

    2012年2月,美国《纽约时报》发表了一篇主题为“大数据时代”的文章,称大数据时代已经来临,数据分析大师们正在获得更多发展机遇。 大数据是全球新型工业化进...

    腾讯研究院
  • 入门者:该如何实施数据分析的过程?

    数据分析是指通过建立审计分析模型对数据进行核对、检查、复算、判断等操作,将被审计单位数据的现实状态与理想状态进行比较,从而发现审计线索,搜集审计证据的过程。 数...

    小莹莹
  • 【SLAM】卡尔曼滤波:究竟滤了谁?

    一派是基于马尔科夫性假设的滤波器方法,认为当前时刻的状态只与上一时刻的状态有关。另一派是非线性优化方法,认为当前时刻状态应该结合之前所有时刻的状态一起考虑。

    小白学视觉
  • 一个看似纠结的MySQL标签需求的梳理

    我们日常工作中总是会有一些看起来繁琐,吃力不讨好的事情,但是这些需求我们不能一概而论,为了落实规范而动用规范的大棒。

    jeanron100
  • 剑指Offer的学习笔记(C#篇)-- 二进制中1的个数

    新颖的解法,使得该题目运用到了二进制的位运算符。先了解一下位运算符!

    WeiMLing
  • 省流量即省钱 - Nginx 开启支持谷歌Brotli压缩算法

    Brotli最初发布于2015年,用于网络字体的离线压缩。Google软件工程师在2015年9月发布了包含通用无损数据压缩的Brotli增强版本,...

    缘、妙不可言
  • 数字经济的浪潮下,新零售正在蜕变

    当赋能成为新零售时代的主题,我们看到越来越多的玩家开始将发展的目光聚焦在了赋能上。尽管赋能的确可以在一定程度上找到发展新路子,但是,如果仅仅只是把赋能看成是新零...

    孟永辉

扫码关注云+社区

领取腾讯云代金券