广州番禺建设银行网站登录,推广策略图片,网站买空间,一个织梦两个网站【笔试】美团2024年春招第二场笔试#xff08;技术#xff09; 文章目录 T1 模拟T2 模拟T3 模拟#xff0c;快速幂/打表T4 众数、前缀和、树状数组T5 逆序对#xff0c;树状数组 T1 模拟
题目#xff1a;数组求和#xff0c;判断是否要减一个数 思路#xff1a;模拟即可…【笔试】美团2024年春招第二场笔试技术 文章目录 T1 模拟T2 模拟T3 模拟快速幂/打表T4 众数、前缀和、树状数组T5 逆序对树状数组 T1 模拟
题目数组求和判断是否要减一个数 思路模拟即可
//T1
//AC
#includebits/stdc.h
using namespace std;
typedef long long LL;int main() {int n; cinn;LL sum 0;for(int i 1; i n; i){LL x; cinx;sum x;}LL a, b; cinab;sum sum-a-b;coutsum\n;
}
T2 模拟
题目
1、所有字母都是小写。例如good 2、所有字母都是大写。例如APP 3、第一个字母大写后面所有字母都是小写。例如Alice给个字符串最少几次能合法
思路
最多四种情况判断一下即可
//T2
//AC
#includebits/stdc.h
using namespace std;
typedef long long LL;int main() {string s; cins;int sm 0;for(int i 0; i s.size(); i){if(islower(s[i])){sm;}}int bg s.size()-sm;int ans min(bg, sm);if(isupper(s[0])){ans min(ans, bg-1);}coutans\n;
}
T3 模拟快速幂/打表
题目数组每次操作将除了第 x 个元素的其余元素翻倍操作q次求最后的数组和。思路先假设每个数每次都翻倍维护每个数没有翻倍的次数最后除回去就行。
//T3
//AC
#includebits/stdc.h
using namespace std;
typedef long long LL;
const int maxn 1e510;
const LL mod 1e97;
LL a[maxn], v[maxn];
LL pows[maxn];
int main() {pows[0] 1;for(int i 1; i maxn; i){pows[i] pows[i-1]*2%mod;}int n, q; cinnq;for(int i 1; i n; i){cina[i];}LL fb q;while(q--){int xi; cinxi;v[xi];}LL ans 0;for(int i 1; i n; i){ans (ans (pows[fb-v[i]]*a[i]%mod))%mod;}coutans\n;
}
T4 众数、前缀和、树状数组
题目求数组的所有子数组的众数之和众数有多个时取小的那个。 输入 3 2 1 2 输出 9
思路1
取值只有1和2肯定要用起来。考虑对答案的贡献默认所有区间1因为至少1嘛。然后最多也就是2什么情况下会是2呢对于区间和区间长度*1.5的也就是2的个数超过区间一半的时候。暴力所有区间n^2然后前缀和O1区间和判断累加到这能拿70%其实也就是找2是众数的区间有多少个的情况
//T4-70%
#includebits/stdc.h
using namespace std;
typedef long long LL;
const int maxn 2e510;
LL a[maxn], s[maxn];
int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);LL n; cinn;LL ans 0;for(LL i 1; i n; i){cina[i];// a[i]--;// ans a[i];s[i] s[i-1]a[i];}// for(LL l 1; l n; l){// for(LL r l; r n; r){// LL sum s[r]-s[l-1];// LL c2 sum-(r-l1);// LL c1 (r-l1)-c2;// // for(int k l; k r; k){// // if(a[k]1)c1;// // else c2;// // }// if(c1c2)ans 1;// else ans 2;// }// }// 找出区间和比1.5倍区间长度要长的2或者说加1然后加全部区间个数ans (1n)*n/2;for(int len 1; len n; len){for(int i 1; ilenn; i){if((s[ilen-1]-s[i-1]) lenlen/2len%2)ans;}}coutans\n;// LL nn (1n)*n/2;// LL s1 0, s2 0;// for(int i 1; i n; i){// LL x; cinx;// if(x1)s1;// else s2;// }// coutnn*s2/s1\n;
}思路2
考虑区间枚举怎么优化考虑区间总个数一样换成求1是众数的的区间有多少个。把1和2换成-1和1。数组的众数是 1 等价于数组的和不小于 0此时只需要找出有多少个子数组的和不小于 0 剩下的就是众数2。 这里还是前缀和 前面有几个前缀和 ≤ 当前的前缀和。这里有点类似于求逆序对时候的做法用下标为前缀和权值为 1 的树状数组 统计某个取值范围内有多少个前缀和。
//T4-AC
#includebits/stdc.h
using namespace std;
typedef long long LL;
const LL maxn 2e510;
LL n, v[maxn*210];
void add(LL x, LL y){for(LL i x; i 2*maxn; i i(-i)){ // n- 2maxnv[i] y;}
}
LL query(LL x){LL res 0;for(LL i x; i 0; i - i(-i)){res v[i];}return res;
}
int main() {cinn;LL t 0, res 0;add(maxn, 1LL); //有负数需要转换一下for(LL i 1; i n; i){LL x; cinx;if(x1LL)t; else t--;res query(tmaxn);// coutres\n;add(tmaxn, 1LL);}LL cnt n*(n1)/2;// coutres\n;coutres2*(cnt-res)\n;
}
T5 逆序对树状数组
题目给你一个排列定义f(i)为a[i]取反后形成的数组的逆序对数量求f(1)到f(n)的值。 思路不难想到先来个原先的逆序对。 然后扫一遍过程中维护一下左右比当前数的大小关系推导一下公式算一下即可。
//T5
//AC
// 逆序对-l大于ai-r小于ail全部
// 逆序对l小于ai-r小于ai
// 排列ai-1 l小于air小于ai维护左边比ai小的数的个数
#include bits/stdc.h
using namespace std;
typedef long long LL;
const LL maxn 200010;
struct node{ LL v, p; }a[maxn];
bool cmp(node x, node y){return x.vy.v; }
LL n;
LL v[maxn], res[maxn];
void add(LL x, LL y){for(LL i x; i n; i i(-i)){v[i] y;}
}
LL query(LL x){LL res 0;for(LL i x; i 0; i - i(-i)){res v[i];}return res;
}
int main() {cinn;for(LL i 1; i n; i){cina[i].v; a[i].p i;}sort(a1,an1,cmp);LL ans 0;for(LL i n; i 1; i--){// couta[i].v\n;add(a[i].p,1);ans query(a[i].p-1);LL lmax query(a[i].p-1);LL lmin a[i].p-1-lmax;LL rmin a[i].v-1-lmin;res[a[i].p] lmin-rmin;}// coutans\n;for(LL i 1; i n; i){coutansres[i] ;}
}
// 64 位输出请用 prLLf(%lld)
