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

前言

项目进度越来越紧，留给自己的业余时间也越来越少。
这次的题目仍来自于平时练手之作，题目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[1_{j]可以不变，c[j+1}n]的值会变大）

故而采取，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群分享，今年想尝试下新的分享方式，欢迎支持。

直播课程