程序员进阶之算法练习（三十）附基础教程

前言

BAT常见的算法面试题解析：

程序员算法基础——动态规划

程序员算法基础——贪心算法

工作闲暇也会有在线分享，算法基础教程----腾讯课堂地址。

正文

1.k-th divisor

题目链接

题目大意：

给出一个数字n，求数字n所有因子中，第k大的数字；

如果没有输出-1；

输入数据：

两个数字 n and k (1 ≤ n ≤ 1e15, 1 ≤ k ≤ 1e9)

Examples

input

4 2

output

2

input

5 3

output

-1

题目解析：

假如n=x*y（x<y)，那么x和y是n的因子，且有x <= sqrt(n)；

那么只要枚举x=1~sqrt(n)，y=n/x，这样可以得到n所有的因子；

再从因子中选择第k大的数字即可。

思考🤔：

小trick，n=9,x=3时，有y=3，但是x=y，所以只算一个因子；

2.USB vs. PS/2

题目链接

题目大意：

机房有三种电脑，一种只有USB接口，一种只有PS/2接口，一种是两种接口均有，数量分别为a、b、c；

现在机房希望给电脑配上鼠标，鼠标有两种，一种只支持USB，一种只支持PS/2；

鼠标有m个，每个仅能用于一台电脑，价格为vali；

现在希望能支持尽可能多的电脑，如果有多个选择，选择总价格最低的。

输入数据：

第一行 s a, b and c (0 ≤ a, b, c ≤ 1e5)

第二行 m (0 ≤ m ≤ 3·1e5)

接下来m行 每行 vali 和 鼠标支持类型 (1 ≤ vali ≤ 1e9)

输出：

最多能支持的电脑数量还有总价格；

Examples

input

2 1 1

4

5 USB

6 PS/2

3 PS/2

7 PS/2

output

3 14

题目解析：

要求首先是支持的电脑数量最多，其次再是价格最低。

电脑与电脑之间的差别：电脑类型A（USB接口）和电脑类型B（PS/2接口）兼容性比电脑类型C（两种接口都支持）差，那么应该优先支持类型A、B；

鼠标与鼠标之间的差别：同类型的鼠标，价格低者应该优先使用，这样总价格会更低；

综合这两者的差异，可以得到一个贪心的策略：

对鼠标按价格排序，从价格小的开始选；在配电脑的时候，优先选择类型A/B，如果没有再选择类型C。

3. Two strings

题目链接

题目大意：

给出两个字符串a和b，现在从b中删去一个连续的子串，得到字符串b'，

要求b'是a的子序列；

现在希望删除尽可能短的字符串，并 输出b';

（如果b'为空，输出'-'）

输入数据：

两行字符串，分别是a和b；

a和b的长度均小于1e5；

Examples

input

hi

bob

output

-

样例解释：删除所有的字符，得到空串，输出-；

input

abca

accepted

output

ac

样例解释：删除子串cepted，得到b'=ac，是a的子序列；

题目解析：

删除必然是某个区间l, r，先看最暴力的做法：

枚举l, r的可能性，得到新的字符串bNew，对a和bNew做一次匹配；

匹配的规则是对于bNew的每一个字符，都在原来基础上找最近的匹配，最后看bNew是否能在a中找到所有的字符匹配位置；

枚举区间是O(N^2)，匹配是O(N)，总的复杂度是O(N^3);

接下来看优化思路，

性质1：区间l, r如果满足题意，那么l-1, r或者l, r+1也会满足题意；

如果用动态规划，状态数有N^2，已经超过限制；（虽然动态规划的转移是整体O(N)）

由性质1，这里可以引入一个二分：二分区间长度。

然后再枚举区间的起点，得到bNew，再进行一次匹配；

整体的复杂度是O(logN)的二分，O(N)的枚举区间起点，O(N)的单次匹配复杂度；

这里单次匹配可以优化：

dpi表示字符串b，前i个字符匹配字符串a，的最短长度；

dpRi表示reverse_b（字符串b的转置），前i个字符串匹配字符串reverse_a，的最短长度；

那么bNew=b减去区间l, r=1,l-1 + r+1, len

只要dpi+dpRj<=lenA，那么就有解；

这样单次匹配的复杂度降到了O(1);

总体的复杂度是O(logN * N), 题目能接受的复杂度。

4.Timofey and a tree

题目链接

题目大意：

一棵树有n个点，序号是1~n，每个点有一个颜色值colori;

现在要求选择一个点，以这个点作为新的root根节点，要求其root根节点下，每颗子树内的颜色相同（子树与子树之间颜色可以不同）；

如果可以则输出YES，然后再输出点序号；

如果不可以则单独输出NO。

输入数据：

第一行 n (2 ≤ n ≤ 1e5)

接下来n-1行，每行有两个数字（x，y），表示点x和y之间有一条边；

最后一行是颜色值 c1, c2, ..., cn (1 ≤ ci ≤ 1e5)

Examples

input

4

1 2

2 3

3 4

1 2 1 1

output

YES

2

题目解析：

题目要求子树内颜色相同，那么对于边(u, v)，如果u和v的颜色不同，那么有三种可能：

1、以u为根；

2、以v为根；

3、无解；

接下来的问题是，如何判断以u为根的情况是否满足题意？

以u为根，对每个子树进行一次dfs，判断是否子树的颜色相同，即可。

5.Ilya And The Tree

题目链接

题目大意：

有一颗根为1的树，共有n个点，每个点有一个权值ai；

我们定义一个点的魅力值为：点到根的路径上，所有点的最大公约数（gcd）；

同时，我们可以选择修改一个点的权值为0；（gcd(0, m) = m）

问，每一个点的可能最大魅力值；

输入数据：

第一行，n (1 ≤ n ≤ 2e5)

第二行，ai

接下来n-1行，每行有两个数字（x，y），表示点x和y之间有一条边；

Examples

input

3

6 2 3

1 2

1 3

output

6 6 6

样例解释：

输入：首先n；

接下来是n个数字ai;

然后n-1行，表示树的边；

输出：n个点可能的最大魅力值；

点1的最大魅力值是6（不做修改），点2的最大魅力值是6（修改点2的权值为0），点3的最大魅力值是6（修改点3的权值为0）

题目解析：

先重复下题目的定义：对于树上某个点u，其最大魅力值是点u到根上的所有数字的gcd；

对于点u，如果可以修改某个某个数字为0，那么相当于从点u到根上的所有数字中去掉一个数字，再求gcd；

问题简化成，在数组x1、x2、....xk中，去掉一个数字使得gcd最大。

如果不考虑复杂度，我们可以枚举去掉任意一个数字，再计算剩下的gcd，从中选择最大的数字；

对其思路进行优化，我们用di表示前i个数字的gcd值，di表示前i个数字去掉一个数字的最大gcd值；

于是有,d1=x1, d1=0；

di = gcd(di-1, xi);

di = max(gcd(di-1, xi), di-1); //如果前i个数字去掉的是xi，那么gcd为di-1；如果去掉的数字不为xi，那么结果为di-1和xi的gcd值。

再回到树上的实现方案：

对每个点i维护一个数组di，在dfs过程不断更新数组即可。

总结

算法文集里有上百道各式各样的算法题，欢迎品尝。

本文题目源于Codeforces。

授人以鱼不如授人以渔，但是大多数人只需要鱼，并不要渔。

这里是鱼：

程序员算法基础——动态规划

程序员算法基础——贪心算法