网站开发地图板块浮动,账号权重查询,建设主题网站的顺序一般是,河南国安建设集团有限公司网站文章目录 T1 小美的升序数组T2 小美的子序列T3 小美的数组T4 小美的元素删除T5 题目忘了#xff08;不确定是不是这个题面#xff09; 23秋招#xff0c;美团笔试5#xff08;技术#xff09; 2023 美团笔试题 0902#xff0c;咋都是牛客月赛原题呀#xff08;
时间不确定是不是这个题面 23秋招美团笔试5技术 2023 美团笔试题 0902咋都是牛客月赛原题呀
时间2023.09牛客补题 补题2
T1 小美的升序数组
小美在 n 行 m 列的本子上写了许多字母她会在每一行中找出一个字母然后组成一个字符串。 小美想知道组成的字符串中是否存在至少一个字符串包含“meituan”子序列。
补题
//AC
#include iostream
#include bits/stdc.h
using namespace std;
const int maxn 1e510;
int a[maxn], b[maxn];
int main() {int n; cinn;int ok 1;for(int i 1; i n; i){cina[i];b[i-1] a[i]-a[i-1];if(i2 a[i]a[i-1])ok 0;}for(int i 2; i n; i){if(b[i]b[i-1])ok 0;}if(ok1)coutYes\n;else coutNo\n;
}
T2 小美的子序列
小美拿到了一个数组。她每次可以进行如下操作之一
选择一个元素使其乘以 2。选择一个元素使其除以 2向下取整。
小美希望第一个元素变成所有元素的最大值。请你判断小美最少需要操作多少次?
补题
//T2-AC
#include iostream
#include bits/stdc.h
using namespace std;
const int maxn 1e510;
string a[1010];
int main() {int n, m; cinnm;for(int i 0; i n; i)cina[i];string spmeituan; 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(cur7)break;}if(cur7)coutYES\n;else coutNO\n;
}
T3 小美的数组
小美拿到了一个数组。她每次可以进行如下操作之一
选择一个元素使其乘以 2。选择一个元素使其除以 2向下取整。
小美希望第一个元素变成所有元素的最大值。请你判断小美最少需要操作多少次?
//T3-AC
#include iostream
#include bits/stdc.h
using namespace std;
const int maxn 1e510;
int a[maxn];
int main() {int n; cinn;int mx 0;for(int i 1; i n; i){cina[i];mx max(mx, a[i]);}int t a[1], cc 0;while(t mx){t * 2; cc;}// coutcc\n;int c2 0;for(int i 2; i n; i){while(a[i]a[1]){c2;a[i] / 2;}}coutmin(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 1e510;
const int mod 1e97;
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; cinnk;cout0\n;// coutmod-1\n;// setintse;// for(int i 1; i n; i){// cina[i];// se.insert(a[i]);// }// sort(a1,an1);// 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)coutres\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;// coutres\n;// cout(n-k-1)*(n-k)%mod/2\n;// else cout8\n;// if(n-k2){// while(1);// int rc 0;// for(int i 1; i n; i){// for(int j 1; j n; j){// if(ij)continue;// if(a[i]%a[j]0 || a[j]%a[i]0){// rc;// }// }// }// coutrc/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为末尾时的贡献累加上去即可。
#includebits/stdc.h
using namespace std;
const int maxn 2010, mod 1e97;
int a[maxn], dp[maxn][maxn];
int main(){int n, k; cinnk;for(int i 1; i n; i) cina[i];sort(a1, an1);for(int i 1; i n; i) {dp[i][1] 1; //选1个方案数1for(int j 1; j i; j){ //暴力枚举前1-iif(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;}coutres\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 1e510;
int a[maxn];
int main() {int n; cinn;coutn/2\n;// mapint,intmp;// int res 0;// setintss;// setpairint,intse;// for(int i 1; i n; i){// cina[i];// if(ss.size()0)ss.insert(a[i]);// for(int x : ss){// pairint,intp make_pair(min(x,a[i]), max(x,a[i]));// if(se.count(p)){// continue;// }else{// se.insert(p);// break;// }// }// // mp[a[i]];// }// coutse.size()\n;// int res 0;// vectorpairint,int vc(mp.begin(), mp.end());// for(int i 0; i vc.size(); i){// if(vc[i].second0)continue;// for(int j i; j vc.size(); j){// if((vc[j].second0 vc[i].second0 i!j ) || (vc[i].second2)){// vc[i].second--;// vc[j].second--;// // coutvc[i].first vc[j].first\n;// res;// }// if(vc[i].second0)break;// }// }// coutres\n;
}
