2024-03-09 美团笔试 430/500
- 第一题 100%（签到）
- 1e5长度的字符串，k次修改次数，最多可以让字符串有多少'M'，'T'字符
- 不是'M'或'T'的话改就行，直到k用完
- 第二题 100% （签到）
- 1e5长度的正整数数组，其中有部分元素为0，1e5次询问，每次给L和R，问0元素全部改成该区间范围内某元素后，数组的和最大、最小为多少
- 记一下0的数量，显然把0全变成L最小，变成R最大
- 第三题 100% （二维前缀和）
- 大小为200的01方阵，从1到n输出答案，答案为大小为i的方阵中01数量相等的方阵有多少
- 直接暴力会T，用二维前缀和记一下
- 第四题 30% （看评论区老哥解法学会了）
- 大小为1e5的正整数数组，有多少种删除区间的方案，使得剩下元素的乘积末尾0至少为k个
- 直接枚举区间范围暴力，能过30%
- 第五题 100% （离线 + 反向并查集）
- 编号为1e9的人，有1e5对朋友关系，朋友关系能够间接传递；1e5次询问，询问包含：1、删除一对直接朋友关系 2、询问两个人是否能通过朋友关系认识，对于2的询问输出Yes或No
- 并查集支持合并与栈形式的撤销合并操作，对于本题无序的删边，需要用到离线
- 最开始只合并操作中没有删除的边，然后从询问反着依次查询以及合并
- 一些边界条件：
- 可能会重复删除，记得只保存第一次删除的，同时，非直接关系需要忽略
- 保存边的时候要保存无向图，如{u, v}，应该保存{u, v}和{v, u}
- 点的大小为1e9，并查集数组需要用哈希表来存，预先把所有点存下来再初始化
，我思路感觉和你的一样呀🥺
腾讯二面448人在聊