美团算法笔试

整体难度应该是低于去年。 题目一 给定区间 ，求其中因子个数为奇数的整数个数。数据范围为 。 解答 因子一般成对出现，只有完全平方数会留下一个未配对的平方根，因此只有完全平方数的因子个数为奇数。 设  则答案为  如果按平方根枚举实现，复杂度是 ；直接用上式计算可做到 。 题目二 已知数列满足  且当  时，  现有  次询问，每次给出一个 ，要求输出 ，其中 。 解答 设 ，预处理  即可。 维护最近  项的窗口和  则有  这样每次转移都是 ，总复杂度为 。 题目三 给定一个无向图，支持  次操作：  1 x：删除编号为  的边； 2 x：查询点  所在连通块中的最大点权。  其中点权定义...

记录一下😀😀T1 求l~r间因数为奇数的个数，考虑到因数只能成对出现，但是平方数是不会成对出现的T2 什么机器学习题……不会T3 每个节点求最大权重的第一个祖先节点，树上构造单调栈，dep从小到大 + 权重从大到小；回溯就再开一个栈记录T4 q次询问 + 修改，询问联通集中最大权重，修改为删除边；离线做法，把q次询问反过来做，然后跑带权重的并查集

这两天陆陆续续开始做笔试了，但是感觉这跟hot100不沾边吧，完全没思路目前就做了携程美团米哈游的，我报的java但是米哈游选择题还都是cpp（qwq）完全不懂qwq感觉拼尽全力也就能过一两题甚至一题都没过......但是hot100确实刷了啊然后马上就是多多和小红书还有蚂蚁，我问问这难度这么高是必须要全a才能进面吗，还是说占比不高qwq

选择题大模型不会算法题第二题一直超时，卡在百分之四十的通过率，后面试着光输入并打印常数也超时最后十分钟灵机一动换成 c++ 过了第三题直接跳了