美团 3.18 第二次笔试

在收到邮件前就在官网看到是进人才库了。没事写着玩吧。

第一题：

小美在玩一项游戏。该游戏的目标是尽可能抓获敌人。

敌人的位置将被一个二维坐标 (x, y) 所描述。

小美有一个全屏技能，该技能能一次性将若干敌人一次性捕获。

捕获的敌人之间的横坐标的最大差值不能大于A，纵坐标的最大差值不能大于B。

现在给出所有敌人的坐标，你的任务是计算小美一次性最多能使用技能捕获多少敌人。

/*

* 第一行两个整数N,K，以空格分开，分别表示彩带有N厘米长，你截取的一段连续的彩带不能超过K种颜色。

* 接下来一行N个整数，每个整数表示一种色彩，相同的整数表示相同的色彩。

* 1≤N,K≤5000，彩带上的颜色数字介于[1, 2000]之间。

*/

e.g. :

3 1 1

1 1

1 2

1 3

output: 2。抓第一个和第二个或者第二个和第三个。

给坑了，我加了测试用例。点完调试说ac我就跳了。最后回来点保存的时候发现提交好像只过了18的用例？？

第二题：

小美现在有一串彩带，假定每一厘米的彩带上都是一种色彩。

因为任务的需要，小美希望从彩带上截取一段，使得彩带中的颜色数量不超过K种。

显然，这样的截取方法可能非常多。于是小美决定尽量长地截取一段。

你的任务是帮助小美截取尽量长的一段，使得这段彩带上不同的色彩数量不超过K种。

/*

* 第一行两个整数N,K，以空格分开，分别表示彩带有N厘米长，你截取的一段连续的彩带不能超过K种颜色。

* 接下来一行N个整数，每个整数表示一种色彩，相同的整数表示相同的色彩。

* 1≤N,K≤5000，彩带上的颜色数字介于[1, 2000]之间。

*/

e.g.

5 3

1 1 2 3 4

output : 3

简单题，略过。

第三题：

现在小美获得了一个字符串。小美想要使得这个字符串是回文串。

小美找到了你。你可以将字符串中至多两个位置改为任意小写英文字符’a’-‘z’。

你的任务是帮助小美在当前制约下，获得字典序最小的回文字符串。

数据保证能在题目限制下形成回文字符串。

注：回文字符串：即一个字符串从前向后和从后向前是完全一致的字符串。

例如字符串abcba, aaaa, acca都是回文字符串。字符串abcd, acea都不是回文字符串。

输入：一行，一个字符串。字符串中仅由小写英文字符构成。 * 保证字符串不会是空字符串。 * 字符串长度介于 [1, 100000] 之间。

e.g. acca

output: aaaa

没搞懂字典序是什么意思。过了80都的用例。应该是简单模拟时漏了条件。

分类情况讨论：

1. 本来就是回文串： 如果长度为偶数，修改字母最大的即可。长度为奇数，可能需要比较正中间的字符和剩余字符中最大的字母（没考虑到这里）
2. 有一个字母没对上：如果长度为偶数，将不对称的两个都修改为a。如果长度为奇数，如 aczba。则应该考虑修改成acaca和aazaa（没考虑奇数情况）
3. 有两个没对上：都修改成a。

第四题：

现在商店里有N个物品，每个物品有原价和折扣价。 小美想要购买商品。小美拥有X元，一共Y张折扣券。 小美需要最大化购买商品的数量，并在所购商品数量尽量多的前提下，尽量减少花费。 你的任务是帮助小美求出最优情况下的商品购买数量和花费的钱数。

输入： 第一行三个整数，以空格分开，分别表示N,X,Y。 接下来N行，每行两个整数，以空格分开，表示一个的原价和折扣价。 1≤N≤100, 1≤X≤5000, 1≤Y≤50，每个商品原价和折扣价均介于[1,50]之间。

动态规划？没了个贪心过了18的用例。

第五题：

现在有若干节点。每个节点上有能量塔。所有节点构成一棵树。 某个节点u可以为和u距离不超过给定值的节点各提供一点能量。 此处距离的定义为两个节点之间经过的边的数量。特别的，节点u到本身的距离为零。 现在给出每个节点上的能量塔可以为多远的距离内的点提供能量。 小美想要探究每个节点上的能量值具体是多少。你的任务是帮助小美计算得到，并依次输出。

输入描述：第一行一个整数N，表示节点的数量。 *接下来一行N个以空格分开的整数，依次表示节点1，节点2，…，节点N的能量塔所能提供能量的最远距离。 *接下来N-1行，每行两个整数，表示两个点之间有一条边。 1≤N≤500，节点上能量塔所能到达的最远距离距离不会大于 500.

e.g.

3

1 1 1

1 2

2 3

output: 2 3 2

没写完。本题不难，构造一个连接矩阵深度遍历应该就可以。