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

前言

最近在接触新知识,也是选择2017年的方向。 其他文集更新会放缓,没有学习就没有心得,肚中无墨就无从下笔。 但是算法练习还是挺好玩的,欢迎关注algorithm文集

正文

A. Bus to Udayland 题目链接 题目大意: 输入n行字符,每行5个字符; 表示公交车上n排位置,X表示有人,O表示空位,|是过道。 问是否能找到两个连续的空位; 如果可以,输出"YES",并且空位改为++后输出; 如果没有输出"NO"; n (1 ≤ n ≤ 1000)

Example

input

5 XX|XX XX|XX XO|OX XO|OO OX|XO

output

YES XX|XX XX|XX XO|OX XO|++ OX|XO

** 题目解析:** 只有两种情况,前两个或者最后两个。 分情况讨论即可。

B. Chris and Magic Square 题目链接:http://codeforces.com/contest/711/problem/B 题目大意: 输入一个n*n的数组矩阵,在数字为0的位置填入一个正数(只有一个位置为0),让矩阵的行列对角线和相同。 如果没有答案输出-1; 如果答案,输出完整的矩形。 n (1 ≤ n ≤ 500)

Example

input

3 4 0 2 3 5 7 8 1 6

output

9

input

4 1 1 1 1 1 1 0 1 1 1 2 1 1 1 1 1

output

-1

** 题目解析:** 看似很难,但是因为只有一个位置为0,题目简化许多。 我们假设存在答案,那么可以: 根据上一行和当前行的差值,可以计算出0应该填的数字。 再判断一下结果是否符合即可。

C. Coloring Trees 题目链接 题目大意: 有n棵树排成一行,m种颜料(数字1~m); 输入n个数字,表示n棵树当前的颜色(0为uncolor,其他为当前的颜色); 树的排列顺序有一个魅力值, 连续的相同颜色值算1点魅力值,例如: 树的颜色排列为 [2, 1, 1, 1, 3, 2, 2, 3, 1, 3],其魅力值为7,分别如下: {2}, {1, 1, 1}, {3}, {2, 2}, {3}, {1}, {3}

如果树的颜色是uncolor,代表可以染色; 输入n*m个数字,表示第i颗树染色成第j种颜色的代价cost[i][j];

问,如果要把树的魅力值变为k,需要的最小代价是多少?(如果无解,输出-1)

n, m and k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100)

Example

input

3 2 2 0 0 0 1 2 3 4 5 6

output

10

input

3 2 2 2 1 2 1 3 2 4 3 5

output

-1

** 题目解析:** 从给出的数据范围来看,容许时间复杂度比较大的做法。 从给出的选择来看,每次的抉择只有uncolor的树,假设要染色的树是i,大概的类别有: 1、color[i-1] != color[i+1],这时color[i]可以等于color[i-1]或者color[i+1],或者都不相同; 2、color[i-1] == color[i+1],这时color[i]可以等于color[i-1]和color[i+1],或者都不相同; 因为题目要求的是特定的魅力值,故而不能用贪心的做法。 考虑用动态规划来做, dp[i][j[k] 表示前i个,color为j,最后一个为颜色k的最小代价; 对于第i颗树,color为j的状态,考虑以下的状态: 1、color[i] != 0,不能染色,那么j=color[i]的状态,可以通过dp[i-1]的状态中获得最小代价; 1、color[i] != 0,不能染色,那么j!=color[i]的状态,不合法,忽略; 1、color[i] == 0,能染色,那么枚举j的状态,从dp[i-1]转移即可。 具体的转移方程较多,可以见代码。

** 思考?: 如果把k去掉,改成最大值,是一道不错的面试题。**

** D. Directed Roads** 题目链接 ** 题目大意:** 给出n个点,每个点有一条从其出发的有向边; 现在选择一个边的集合,对集合的每条边进行一个翻转的操作; 要求:让n个点没有形成环。 问有多少种集合可能,结果对MOD取余。 n (2 ≤ n ≤ 2·1e5) MOD = 1e9 + 7.

Example

input

3 2 3 1

output

6

input

4 2 1 1 1

output

8

题目解析: 注意重点:每个点初始状态只有一条有向边,那么每个环都是简单的环(没有重叠的环)。 那么把所有的点分成两种,环上的点,环外的点。 不在环上的点有k个,那么有2^k个选择。 第i个环的数量为num[i],有2^num[i] - 2个选择。(全选和全不选是不行的) 结果之乘积就是答案。

总结

不知道你们有没有这样一种感觉,当你换到一个新的环境,接触到很多新的知识之后,本能地开始排斥这些新的内容。 表现出来的行为就是焦虑,觉得很多事情未完成,但是仍然注意力不集中。 明知道这些知识很重要,但是就不愿意去学,觉得这个东西很难且以后也很少用到。 这种焦虑就是人与人的价值观区别,甚至有的人会抱着好奇心的态度去接受这种新知识。 不去评判价值观的好坏,但如果能怀着好奇的心态迎接新的生活,总归会过的轻松点。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

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

前言 我认为的编程能力: 基础知识:数据库、操作系统、网络原理等; 编码能力:软件架构(MVVM、MVP)、设计模式、编程语言(C、JAVA、C++)等;...

474100
来自专栏窗户

平方根的C语言实现(一) —— 浮点数的存储

  曾经做一个硬件成本极度控制的项目,因为硬件成本极低,并且还需要实现较高的精度测量,过程中也自己用C语言实现了正弦、余弦、反正切、平方根等函数。   以下,无...

460100
来自专栏WOLFRAM

九宫格数独游戏

28680
来自专栏落影的专栏

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

前言 时间来到6月,又是一年高考时。 几年之前是坐在教室怀念高考,现在是上班敲着代码怀念学生时代。 正文 1、Lakes in Berland 题目链接 ...

50090
来自专栏chenjx85的技术专栏

leetcode-453-Minimum Moves to Equal Array Elements

33760
来自专栏小樱的经验随笔

单表代替密码原理及算法实现

    要了解单表替代密码就得先了解替代密码,在这里我就做一下简单的介绍:       替代是古典密码中用到的最基本的处理技巧之一 。       替代密码是指...

60860
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--二分查找

算法是什么? 算法就是完成一组特定任务的方法。 比如将大象放进冰箱需要三步: 打开冰箱 将大象放进冰箱 关闭冰箱 这就是一种算法。 如果用计算机语言来叙述...

34360
来自专栏ACM算法日常

ACM之坑&套路

写在前边:这些梗都是敝人自己做题和比赛时曾经坑过自己的地方,特别在这里记录一下,所有的链接都是本博客中的题解链接(有大致题意说明和代码),原题请到OJ上自行寻找...

10320
来自专栏杨建荣的学习笔记

使用贪心算法解决集合覆盖问题

有的同学可能对这些州没概念,这个简称就跟京代表北京,鲁代表山东,甘代表甘肃一样,细细一看,都是西部的一些州。

16420
来自专栏数据结构与算法

P1613 跑路

题目描述 小A的工作不仅繁琐,更有苛刻的规定,要求小A每天早上在6:00之前到达公司,否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资,...

30290

扫码关注云+社区

领取腾讯云代金券