2024-03-09 美团笔试 430/500

第五题 全部打印Yes怒骗3分

第四题预先计算所有 2 因子和 5 因子的数量，然后计算出一个 maximum delete 2 和 5（最多能删除的个数）。然后你 for 循环，维护一个前缀的 2 因子的数量和 5 因子的数组。对这个数组做二分可以找到对于当前索引 i 往左最多能删除的区间长度，ans += 这个区间长度即可。注意维护下数组就行了。

只a两个能进面吗....麻了

T4 顺手重写了下大概是这样

第四题想用滑动窗口做，剩二十分钟没写完，太久没写题了第三题改bug改疯了

不知道为什么前两题一样的写法 为啥只有 40 和16的通过率

第四题我是先全部乘起来，然后动态规划一个个除掉，但只过了30%，感觉可能是数组里有0的原因，最后来不及改了

第二题不知道为啥怎么改都是30%..

佬，能看看为啥我的并查集只能过3个样例吗，我思路感觉和你的一样呀🥺

2题16.777（golang，int）是什么鬼...离谱哎

A了四道加第五道dfs骗了百分之10，第四道我是算每个数的2和5的因子个数的前缀和。然后再双指针遍历以每个i结尾的删除区间

我想问哪里可以找到这期的java答案？

m

第四题o(n)双指针： #include <bits> using namespace std; typedef long long ll; const int N=100010; int a[N],n,k; int s1[N],s2[N],a1[N],a2[N]; ll res; bool check(int i,int j) { int cnt1=s1[j]-s1[i-1],cnt2=s2[j]-s2[i-1]; int lft=min(s1[n]-cnt1,s2[n]-cnt2); return lft>=k; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>k; for(int i=1;i<=n;i++) { int x,t; cin>>x; t=x; while(x%2==0) a1[i]++,x/=2; x=t; while(x%5==0) a2[i]++,x/=5; } for(int i=1;i<=n;i++) { s1[i]=a1[i]+s1[i-1]; s2[i]=a2[i]+s2[i-1]; } for(int j=1,i=1;j<=n;j++) { while(i<=j&&!check(i,j)) i++; res+=j-i+1; } cout<<res><<"\n"; return 0; }</res></bits>

T5啥叫离线处理？学习一下

第四题可以使用回溯：找子集-过滤有已删除元素的子集

410，只骗到了10分，悲

有没有朋友能提供第5题的代码参考一下，并查集忘得差不多了

第五题只能弗洛伊德骗分个10了每次查找都复制一边二维数组然后重新弗洛伊德，结局就是爆内存