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

前言

项目进度越来越紧,留给自己的业余时间也越来越少。 这次的题目仍来自于平时练手之作,题目1、2、3较为容易,4、5有点难度。

正文

1.Mahmoud and Ehab and the even-odd game

题目链接 题目大意: Mahmoud和Ehab在玩一个数字游戏。有一个整数n,从Mahmoud开始,轮流选择一个数字a,要求:

  • 1 <= a <= n;
  • 如果是Mahmoud选择,a必须是偶数;如果是Ehab选择,a必须是奇数。

选完数字之后,n=n-a; 不能选则输掉游戏。 假设两人的决策都很完美, 现在给出数字n,请问谁能赢。

输入数据: n (1 ≤ n ≤ 1e9)

Examples input 1 output Ehab input 2 output Mahmoud

题目解析: n=1时,Mahmoud必输; n=2时,Mahmoud必胜; n=奇数时,因为Mahmoud只能取偶数,取完之后还是奇数,那么Ehab直接取n就可以; n=偶数时,因为Mahmoud只能取偶数,那么直接取n就必胜。

    lld n;
    cin >> n;
    cout << (n % 2 ? "Ehab" : "Mahmoud") << endl;

2.Students in Railway Carriage

题目链接 题目大意: 有n个位置,还有a个班级1的学生,b个班级2的学生; n个位置排成一行,由一行长度为n的字符串表示,*表示已经有人,.表示可以坐人; 现在不希望班级1和班级2的学生坐在相邻的位置,问最多能安排多少个人坐下。

输入数据: n , a and b ( 1 ≤ n ≤ 2 ⋅ 10 5 , 0 ≤ a , b ≤ 2 ⋅ 10 5 , a + b > 0 )

Examples input 5 1 1 *...* output 2 input 6 2 3 *...*. output 4

题目解析: 一个简单的策略:对于有空位的,优先选择人数较少的班级; 其次,如果上一个位置坐了班级1的学生,则这个位置做班级2;

3.Mahmoud and Ehab and the even-odd game

题目链接 题目大意: n个字符串,长度均为m; 现在要从n个字符串中,每个选出一个字符,组成一个长度为n密码,要求: 包括数字、小写字母、特殊字符('#','*','&'中的一个);

现在假设选择字符的光标停在每个字符的最左边,每次可以左移或者右移操作,如果在最左边左移会变到最右边,在最右边右移会变到最左边; 问,最少需要操作几次,才能选出一个合法的密码?(数据保证,必然存在合法的密码)

输入数据: n, m (3 ≤ n ≤ 50, 1 ≤ m ≤ 50)

Examples input 3 4 1\*\*2 a3*0 c4\*\* output 1 样例解释:选中的密码是1a*,仅需把第三行的c移动到最右边;

题目解析: 题目的要求是选出合法的密码,那么最多移动三个光标;(其他的光标不动) 现在的抉择是移动哪些光标,使得次数最少; 先看暴力的情况: 从50个选择3个的排列是50*49*48,每次枚举的复杂度是m*2; 总的复杂度是O(N^3 * M); 是可行的方案。

思考?: 另一种解法:每行有四种抉择,不动,移动到小写字母,移动到数字,移动到特殊字符; 那么可以用dp[i][j] 来表示前i行,密码已满足状态为j的最小光标移动距离;j ∈ [0, 1 << 3],用二进制来表示状态j; 每行有四个转移方程,复杂度为O(M); 总体的复杂度是O(NM);

4.Dasha and Very Difficult Problem

题目链接

题目大意: 假设有一个数组a,数组b,长度都为n,并且l ≤ a[i] ≤ r 和 l ≤ b[i] ≤ r; 定义一个数组c,c[i] = b[i] - a[i],并且数组c里面没有相同的元素; 数组p 表示数组c中的大小关系,比如说 c=[250, 200, 300, 100, 50], 那么 p = [4, 3, 5, 2, 1];

现在给出数组a和p,还有长度n,数组b的范围[l, r]; 求是否存在一个数组b,满足要求? 如果有,输出数组b; 如果没有,输出-1;

输入数据: n, l, r (1 ≤ n ≤ 1e5, 1 ≤ l ≤ r ≤ 1e9) (l ≤ a[i] ≤ r) (1 ≤ p[i] ≤ n)

Examples input 5 1 5 1 1 1 1 1 3 1 5 4 2 output 3 1 5 4 2

题目解析: 根据题目定义,我们需要在[l, r]范围内,寻找一个数组b,满足c[i]=b[i] - a[i], c[i]各不相同,并且大小顺序满足数组p; 容易知道,b[i] = a[i] + c[i]; c[i]是不确定的,因为确定c[i]就相当于确定b[i]; 限制在于b[i]有范围,否则c[i]只需在[1, n]按顺序选择即可;

那么我们能否先按照c=[1, n],直接算出b[i]的范围,再对b[i]的值进行缩减? 先对p排序,得到[1,2,3]的数组,和新的a[i]; 那么有b[i]=a[i]+i; 可能会有 b[i]<l || b[i]>r 的情况出现。 假设找到一个最小值bMin, 一个最大值bMax; 现在需要保证最小值bMin>=l, 那么整个数组b,都应该+(l - bMin)的大小; (这里思考?,是否存在不统一加的更优解?bMin的值变大,导致其对应的c[j]变大, c[1j]可以不变,c[j+1n]的值会变大)

故而采取,c[i]实时计算,如果b[i]<l ,那么直接令b[i]=l, 那么c= b[i] - a[i],b[i]变大会导致c[i],变大。 只要保证之后b[i] <= r即可;

5.Dasha and Puzzle

题目链接 题目大意: 有一棵n个点的树,已知n个点之间的相连关系,现在需要把树的节点放到一个二维坐标轴上(保持树的结构) 要求边和x/y轴平行,边没有重叠;

输入数据: 输入,第一行n 接下来n-1行,分别是ui 和 vi,表示 点ui和vi相连,ui, vi (1 ≤ ui, vi ≤ n)

输出, 如果无解,输出NO; 如果有解,先输出YES,接下来n行,分别输入n个点的坐标 并且坐标[xi, yi] 满足 (|xi|, |yi| ≤ 1e18)

n (1 ≤ n ≤ 30) xi, yi (|xi|, |yi| ≤ 1e18)

Examples input 7 1 2 1 3 2 4 2 5 3 6 3 7 output YES 0 0 1 0 0 1 2 0 1 -1 -1 1 0 2

题目解析: 容易知道,如果某个点的边超过5个,那么必然是无解。 其他情况下,因为给出的xi,yi的范围很大,肯定是有解的。 先假定点1为root,其他点为子节点,来观察题目的trick所在: 1、子节点中的数目不定,不好分配具体的先后顺序; 2、要避免多个子节点直接相互交错; 3、避免多子节点与到之前的父节点的边存在交错;

如果从叶子节点到根节点的分配坐标,叶子节点的坐标分配需要知道父节点的坐标; 那么我们可以先假定父节点的坐标为(fx, fy),子节点的坐标就在(fx, fy)的基础上进行调整; 沿着这个思路,我们需要保证子节点的坐标和父节点的坐标保持一定的距离; 观察到点只有30个,给出的范围比较大,我们可以采用每次给节点分配2^i的距离: 这样保证多个子节点不会交错,并且不会与父节点交错;(因为2^0 + 2^1 + ... + 2^i < 2^i+1; 最大的点坐标为2^31 - 1,在合理范围内。 故而,是一种合理的解法。

总结

之前采用的是QQ群分享,今年想尝试下新的分享方式,欢迎支持。

直播课程

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我杨某人的青春满是悔恨

Swift API 设计指南(下)

一般来说,默认参数比方法族(method families)更可取,因为它减轻了 API 使用者的认知负担。

502
来自专栏marsggbo

(原创)详解KMP算法

KMP算法应该是每一本《数据结构》书都会讲的,算是知名度最高的算法之一了,但很可惜,我大二那年压根就没看懂过~~~ 之后也在很多地方也都经常看到讲解KMP算法的...

2047
来自专栏人工智能LeadAI

在TensorFlow中使用pipeline加载数据

前面对TensorFlow的多线程做了测试,接下来就利用多线程和Queue pipeline地加载数据。数据流如下图所示: ? 首先,A、B、C三个文件通过Ra...

3963
来自专栏SeanCheney的专栏

《图解算法》总结第1章 算法简介第2章 选择排序第3章 递归第4章 快速排序第5章 散列表第6章 广度优先搜索第7章 狄克斯特拉算法第8章 贪婪算法第9章 动态规划

Grokking Algorithms: An illustrated guide for programmers and other curious peop...

3829
来自专栏YouMeek

1.4 Elasticsearch DSL 常用语法介绍

课程环境 CentOS 7.3 x64 JDK 版本:1.8(最低要求),主推:JDK 1.8.0_121 Elasticsearch 版本:5.2.0 相关软...

57610
来自专栏数说工作室

【SAS Says】基础篇:读取数据(中)

特别说明:本节【SAS Says】基础篇:读取数据(上),用的是数说君学习《The little SAS book》时的中文笔记,我们认为这是打基础的最好选择。...

3375
来自专栏生信技能树

生信编程直播课程优秀学员作业展示1

题目 人类基因组外显子区域长度 学员:x2yline 具体题目详情请参考生信技能树论坛 题目数据来源为:ftp://ftp.ncbi.nlm.nih.gov/p...

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

浅析Numpy.genfromtxt及File I/O讲解

Python 并没有提供数组功能,虽然列表 (list) 可以完成基本的数组功能,但它并不是真正的数组,而且在数据量较大时,使用列表的速度就会慢的让人难受。为此...

2754
来自专栏aCloudDeveloper

string 之 strchr函数 和 strstr函数(BF算法和KMP算法的应用)

Author: bakari  Date: 2012/8/9 继上篇。。。。。 下面是我写的代码与源码作的一些比较,均已严格测试通过,分别以“string 之”...

2159
来自专栏深度学习那些事儿

探讨pytorch中nn.Module与nn.autograd.Function的backward()函数

本文讲解基于pytorch0.4.0版本,如不清楚版本信息请看这里。backward()在pytorch中是一个经常出现的函数,我们一般会在更新loss的时候使...

1604

扫码关注云+社区