牛客算法竞赛入门课第一节习题Part3（拼数~Selfish Grazing）

题意：

给定n个整数，拼出最大的数。

思路：

我们只考虑两个字符串的拼接的话，肯定是选择拼接后字典序大的拼接，拓展到n个也是一样的。

所以排序的时候就是按照拼接后的字典序从大到小排序。

代码：

题意：

二维矩阵的每个格子都有权值，问炸掉r*r的正方形可以获得的最大权值。

思路：

二维前缀和维护一下，然后枚举r*r的正方形，因为边长已经固定，只需要枚举左上角或右下角的点就可以。

要注意的是，本题并没有给出二维矩阵的大小，为了防止计算过程中的数组越界，要初始化边界x=r,y=r;

还有就是，因为本题是从0开始，为了防止越界，出现a[-1] [-1]的情况，可以将整个二维矩阵都往右下平移一下。

代码：

题意：

给定一个数轴，每次删除数轴上的某个区间的点，问最后剩下多少个点。

思路：

因为空间给的足够大，所以可以直接进行差分。

代码：

题意：

给出n个区间，求最大不相交区间数量（区间相交不包括端点）

思路：

贪心，将每个区间按照右端点从小到大排序（按照左端点也可以），枚举每个区间并且记录右端点的最小值tmp，如果本区间包含该点，直接跳过，否则就更新tmp并增加区间个数。

代码：