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

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

题目一

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

解答

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

则答案为

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

题目二

已知数列满足

且当 时,

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

解答

,预处理 即可。

维护最近 项的窗口和

则有

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

题目三

给定一个无向图,支持 次操作:

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

其中点权定义为

数据规模为

解答

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

倒序扫描询问:

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

总复杂度为

#美团笔试#
全部评论

相关推荐

(码风很屎别在意~)1.很简单直接都是一个数字就行#include <bits/stdc++.h>using namespace std;#define endl '\n';void solve() {int n;cin >> n;vector<int> v(n + 1);for(int i = 1; i <= n; i++) {cin >> v[i];cout << (n + 1) - v[i] << " \n"[i == n];}}int main() {ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int t;cin >> t;while(t--) {solve();}}2.只用算平方就行了,直接暴力。如下#include <bits/stdc++.h>using namespace std;#define endl '\n';bool cal(int x) {int tot = 0;for(int i = 1; i * i <= x; i++) {if(x / i * i == x)tot += 2;}if(tot % 2)return false;else return true;}void solve() {int l, r;cin >> l >> r;int lmin = sqrt(l);int ans = 0;lmin = lmin * lmin == l ? lmin : lmin + 1;if(lmin == 1)ans++, lmin++;for(int i = lmin; i * i <= r; i++) {if(cal(i * i))ans++;}cout << ans;}int main() {ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int t;t = 1;while(t--) {solve();}}3.稍微推一下公式就行,题解如下#include <bits/stdc++.h>using namespace std;#define endl '\n';#define int long longint mod = 1e9 + 7;const int N = 1e6 + 10;int a[N];void solve() {int k, q;cin >> k >> q;for(int i = 1; i <= k; i++) {a[i] = 1;}a[k + 1] = k ;int tot = k;for(int i = k + 2; i <= 1000000; i++) {tot = ((tot + a[i - 1])  - a[i - k - 1]);a[i] = tot % mod;}while(q--) {int x;cin >> x;cout << a[x] % mod << endl;}}signed main() {ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int t;t = 1;while(t--) {solve();}}
一起聊美团
点赞 评论 收藏
分享
评论
1
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务