美团2026年春招第一场笔试【技术方向】个人题解

整体难度应该是低于去年。

题目一

给定区间 ，求其中因子个数为奇数的整数个数。数据范围为 。

解答

因子一般成对出现，只有完全平方数会留下一个未配对的平方根，因此只有完全平方数的因子个数为奇数。

设

则答案为

如果按平方根枚举实现，复杂度是 ；直接用上式计算可做到 。

题目二

已知数列满足

且当 时，

现有 次询问，每次给出一个 ，要求输出 ，其中 。

解答

设 ，预处理 即可。

维护最近 项的窗口和

则有

这样每次转移都是 ，总复杂度为 。

题目三

给定一个无向图，支持 次操作：

• 1 x：删除编号为 的边；
• 2 x：查询点 所在连通块中的最大点权。

其中点权定义为

数据规模为 。

解答

这类“删边 + 连通块查询”适合离线倒序处理。先把所有会被删除的边标记掉，建出所有操作执行完后的最终图；然后从最终图出发，用并查集维护每个连通块的最大点权。

倒序扫描询问：

1. 遇到 2 x，直接输出 所在连通块的最大点权；
2. 遇到 1 x，把第 条边加回。反向过程中边只会增加，因此两个端点的度数只会变大；更新这两个点的点权后，再用并查集合并两个连通块，并维护块内最大值即可。

总复杂度为