【笔试】美团2023年秋招第5场笔试（后端数开软件方向）

文章目录 T1 小美的升序数组T2 小美的子序列T3 小美的数组T4 小美的元素删除T5 题目忘了（不确定是不是这个题面） 23秋招，美团笔试5（技术）

2023 美团笔试题 0902，咋都是牛客月赛原题呀（

时间：2023.09，牛客补题， 补题2

T1 小美的升序数组

小美在 n 行 m 列的本子上写了许多字母，她会在每一行中找出一个字母，然后组成一个字符串。 小美想知道，组成的字符串中是否存在至少一个字符串包含“meituan”子序列。

补题

//AC #include <iostream> #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; int a[maxn], b[maxn]; int main() { int n; cin>>n; int ok = 1; for(int i = 1; i <= n; i++){ cin>>a[i]; b[i-1] = a[i]-a[i-1]; if(i>=2 && a[i]<=a[i-1])ok = 0; } for(int i = 2; i < n; i++){ if(b[i]>=b[i-1])ok = 0; } if(ok==1)cout<<"Yes\n"; else cout<<"No\n"; } T2 小美的子序列

小美拿到了一个数组。她每次可以进行如下操作之一：

选择一个元素，使其乘以 2。选择一个元素，使其除以 2，向下取整。

小美希望第一个元素变成所有元素的最大值。请你判断小美最少需要操作多少次?

补题

//T2-AC #include <iostream> #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; string a[1010]; int main() { int n, m; cin>>n>>m; for(int i = 0; i < n; i++)cin>>a[i]; string sp="meituan"; int cur = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(a[i][j]==sp[cur]){ cur++; break; } } if(cur==7)break; } if(cur==7)cout<<"YES\n"; else cout<<"NO\n"; } T3 小美的数组

小美拿到了一个数组。她每次可以进行如下操作之一：

选择一个元素，使其乘以 2。选择一个元素，使其除以 2，向下取整。

小美希望第一个元素变成所有元素的最大值。请你判断小美最少需要操作多少次?

//T3-AC #include <iostream> #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; int a[maxn]; int main() { int n; cin>>n; int mx = 0; for(int i = 1; i <= n; i++){ cin>>a[i]; mx = max(mx, a[i]); } int t = a[1], cc = 0; while(t < mx){ t *= 2; cc++; } // cout<<cc<<"\n"; int c2 = 0; for(int i = 2; i <= n; i++){ while(a[i]>a[1]){ c2++; a[i] /= 2; } } cout<<min(cc, c2)<<"\n"; } T4 小美的元素删除

小美有一个数组，她希望删除 k 个元素，使得剩余的元素两两之间互为倍数关系。你能告诉小美有多少种删除方案吗? 由于答案过大，请对1e9+ 7取模。

补题

//T4-45% #include <iostream> #include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 1e5+10; const int mod = 1e9+7; int a[maxn]; int C(int n, int m){ int sum = 1; for(int i = 1; i <= n; i++)sum *= i; for(int i = 1; i <= n-m; i++)sum /= i; for(int i = 1; i <= m; i++)sum /= i; return sum; } signed main() { int n, k; cin>>n>>k; cout<<0<<"\n"; // cout<<mod-1<<"\n"; // set<int>se; // for(int i = 1; i <= n; i++){ // cin>>a[i]; // se.insert(a[i]); // } // sort(a+1,a+n+1); // int res = 0; // for(int i = 1; i <= n; i++){ // if(a[i]==1){ // // res++; // continue; // } // int t = a[i]*a[i], rc = 2; // while(se.count(t)){ // t *= a[i]; rc++; // } // if(rc >= n-k){ // res += C(rc, n-k); // } // } // if(res!=0)cout<<res<<"\n"; // int res = 1; // for(int i = 1; i <= n; i++)res *= i; // for(int i = 1; i <= n-k; i++)res /= i; // for(int i = 1; i <= k; i++)res /= i; // cout<<res<<"\n"; // cout<<(n-k-1)*(n-k)%mod/2<<"\n"; // else cout<<8<<"\n"; // if(n-k==2){ // while(1); // int rc = 0; // for(int i = 1; i <= n; i++){ // for(int j = 1; j <= n; j++){ // if(i==j)continue; // if(a[i]%a[j]==0 || a[j]%a[i]==0){ // rc++; // } // } // } // cout<<rc/2<<"\n"; // return 0; // } } //AC // 1、两两为倍数 & 元素互不相等，所以排序后，后一个元素都是前一个元素的倍数 // 2、最大数为1e9, 而最小倍数为2，所以序列的长度最多为31（可以建图，当然也可以不建，暴力也行，或者大于31时输出0拿部分分） // 3、删除k个不好考虑，考虑最后保留的，也就是选出n-k个。 // dp[i][k], 以i元素为末尾元素，且前排累计挑选k个的方案数，最后答案就是每个元素为末尾，都选出n-k个的方案数累加。 // 转移：暴力枚举1-i，找出当前在集合里的元素j，对于所有元素j为末尾，依次选出1~(n-k)个时的方案都可以作为i为末尾时的贡献，累加上去即可。 #include<bits/stdc++.h> using namespace std; const int maxn = 2010, mod = 1e9+7; int a[maxn], dp[maxn][maxn]; int main(){ int n, k; cin>>n>>k; for(int i = 1; i <= n; i++) cin>>a[i]; sort(a+1, a+n+1); for(int i = 1; i <= n; i++) { dp[i][1] = 1; //选1个方案数1 for(int j = 1; j < i; j++){ //暴力枚举前1-i if(a[i]%a[j]==0){ //a[j]可以作为以a[i]为末尾元素的集合中的元素（或者说a[i]可以加到a[j]后面） for(int kk = 2; kk <= n-k; kk++){ // 依次选出2~(n-k)个时的方案，先把a[i]选上去，所以从2开始 dp[i][kk] += dp[j][kk-1]; // 贡献累加 dp[i][kk] %= mod; } } } } int res = 0; for(int i = 1; i <= n; i++){ //以每个元素为末尾，都选出n-k个的方案数累加 res = (res + dp[i][n-k])%mod; } cout<<res<<"\n"; return 0; } T5 题目忘了（不确定是不是这个题面）

小美的彩虹糖

小美有很多的彩虹糖，每颗彩虹糖都有一个颜色，她每天可以吃两颗彩虹糖，如果今天吃的彩虹糖组合是之前没吃过的组合，则小美今天会很高兴。

例如，小美有 6 颗彩虹糖，颜色分别是[1,1,4,5,1,4] 。

小红第一天吃一组颜色为 1和4 的彩虹糖，小美会很高兴；

第二天吃一组颜色为 4 和 1的彩虹糖，小美不会很高兴;

第三天小美吃一组颜色为 1和 5 的彩虹糖，小美会很高兴，此时小美共有 2 天很高兴。

小美想知道，她最多有几天会很高兴。

//T5-AC #include <iostream> #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; int a[maxn]; int main() { int n; cin>>n; cout<<n/2<<"\n"; // map<int,int>mp; // int res = 0; // set<int>ss; // set<pair<int,int>>se; // for(int i = 1; i <= n; i++){ // cin>>a[i]; // if(ss.size()==0)ss.insert(a[i]); // for(int x : ss){ // pair<int,int>p = make_pair(min(x,a[i]), max(x,a[i])); // if(se.count(p)){ // continue; // }else{ // se.insert(p); // break; // } // } // // mp[a[i]]++; // } // cout<<se.size()<<"\n"; // int res = 0; // vector<pair<int,int> > vc(mp.begin(), mp.end()); // for(int i =0; i < vc.size(); i++){ // if(vc[i].second==0)continue; // for(int j = i; j < vc.size(); j++){ // if((vc[j].second>0 && vc[i].second>0 && i!=j ) || (vc[i].second>=2)){ // vc[i].second--; // vc[j].second--; // // cout<<vc[i].first<<" "<<vc[j].first<<"\n"; // res++; // } // if(vc[i].second==0)break; // } // } // cout<<res<<"\n"; }