美团笔试-3.18_美团 字典序最小的回文

1、捕获敌人

小美在玩一项游戏。该游戏的目标是尽可能抓获敌人。
敌人的位置将被一个二维坐标 (x, y) 所描述。
小美有一个全屏技能，该技能能一次性将若干敌人一次性捕获。
捕获的敌人之间的横坐标的最大差值不能大于A，纵坐标的最大差值不能大于B。
现在给出所有敌人的坐标，你的任务是计算小美一次性最多能使用技能捕获多少敌人。
输入描述
第一行三个整数N,A,B，表示共有N个敌人，小美的全屏技能的参数A和参数B。
接下来N行，每行两个数字x,y，描述一个敌人所在的坐标。
1 ≤ N ≤ 500，1 ≤ A , B ≤ 1000，1 ≤ x , y ≤ 1000
输出描述
一行，一个整数表示小美使用技能单次所可以捕获的最多数量。
样例输入
3 1 1
1 1
1 2
1 3
样例输出
2

实现（55%）

本题相当于给定一个矩形区域，需要使用矩形区域框出最多数量的敌人。考虑使用循环遍历每一个节点，而后再次进行二重循环遍历剩余的每一个节点，我们需要确保一开始的节点为当前举行区域的左上角，而后统计当前区域中的敌人个数。

总结

考虑到数据量不大，可以直接构建二维矩阵用于记录每个坐标上是否有敌人，最终只需要遍历二维矩阵寻找在一个矩形区域中能够获得敌人的最大数量即可。值得注意的是，可能会出现多个敌人有着相同坐标的情况，因此不能单纯将矩阵的值设置为 1 。同时为了方便求解区间和，可以使用前缀和进行进一步优化。

int g[N][N];

int main() {
   
    int n, a, b;
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) {
   
        int x, y;
        cin >> x >> y;
        g[x][y]++;
    }
    for (int i = 1; i <= 1000; i++) {
   
        for (int j = 1; j <= 1000; j++) {
   
            g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int i = 1; i <= 1000; i++) {
   
        for (int j = 1; j <= 1000; j++) {
   
            ans = max(ans, g[i][j] - g[max(0, i - a - 1)][j] - g[i][max(0, j - b - 1)] + g[max(0, i - a - 1)][max(0, j - b - 1)]);
        }
    }
    cout << ans << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2、彩带

题目描述：
小美现在有一串彩带，假定每一厘米的彩带上都是一种色彩。
因为任务的需要，小美希望从彩带上截取一段，使得彩带中的颜色数量不超过K种。
显然，这样的截取方法可能非常多。于是小美决定尽量长地截取一段。
你的任务是帮助小美截取尽量长的一段，使得这段彩带上不同的色彩数量不超过K种。
输入描述
第一行两个整数N,K，以空格分开，分别表示彩带有N厘米长，你截取的一段连续的彩带不能超过K种颜色。
接下来一行N个整数，每个整数表示一种色彩，相同的整数表示相同的色彩。
1 ≤ N , K ≤ 5000，彩带上的颜色数字介于 [ 1 , 2000 ] 之间。
输出描述
一行，一个整数，表示选取的彩带的最大长度。
样例输入
8 3
1 2 3 2 1 4 5 1
样例输出
5

实现（AC）

利用数组记录彩带上的每一种颜色，利用哈希集合控制彩带的类型以及数量。我们一次遍历每一个节点，探索从他开始最多能访问几种颜色。在探索过程中利用哈希集合判断当前颜色是否以获得并及时更新哈希表的大小，若哈希表大小超出范围则立刻终止。最终计算并更新当前的最大长度。

int main(