贸易建设网站,做美工需要参考的网站,积分商城平台,想做个网站推广下面是美团2024-03-16笔试真题#xff0c;进行了VP#xff0c;由于未参与评测#xff0c;故不保证正确性#xff0c;仅供参考。
第一题 小美点外卖 求和然后减去满减和红包即可。
#include bits/stdc.h
using namespace std;
using LL long long ;
int n, t, x,…下面是美团2024-03-16笔试真题进行了VP由于未参与评测故不保证正确性仅供参考。
第一题 小美点外卖 求和然后减去满减和红包即可。
#include bits/stdc.h
using namespace std;
using LL long long ;
int n, t, x, y;
LL ans;int main() {scanf(%d, n);while (n -- ) {scanf(%d, t);ans t;}scanf(%d%d, x, y);printf(%lld\n, ans - x - y);
}第二题 小美的合法单词 考虑三种情况分别需要的操作次数取最小值即可。
先扫描字符串s并用变量big和small分别统计字符串s中大写字母、小写字母的个数。
然后还要处理第一个字符是大写的情况
首先初始化变量ts.size()当第一个字符是大写字母时执行t t - 1 - small。减去1是因为去掉第一个大写字母然后再减去small这样得到的就是后面剩余的大写字符个数。
为什么是t-1-small而不是t-1-big呢举个例子s“AaaBbCD”此时big4small3。
若执行t-1-big则此时t的结果就是2那么答案为min{big, small, t} 2但显然答案应该是3将后面的B,C,D修改为小写。若执行t-1-small则此时t的结果就是3那么答案为min{big, small, t} 3这显然就是正确答案3将后面的B,C,D修改为小写。
说白了就是由于题目要求第一个字母大写后面所有字母都是小写。t-1-small就是将后面统计除了首位这个大写字母外剩余部分的大写字母个数而我们需要将这些大写字母个数就是我们需要修改为小写字母所需要的操作次数。
#include bits/stdc.h
using namespace std;int main() {string s;cin s;int big 0, small 0, t s.size();for (auto c : s) {if (c A c Z) big;else if (c a c z) small;}if (s[0] A s[0] Z) t t - 1 - small;printf(%d\n, min({small, big, t}));
}第三题 翻倍元素 统计每个元素最后翻倍的次数即可。
如下表
数组元素a[]翻倍次数times[]最终结果a[1]11 1 × 2 1 1\times 2^1 1×21a[2]21 2 × 2 1 2\times 2^1 2×21a[3]32 3 × 2 2 3\times 2^2 3×22a[4]42 4 × 2 2 4\times 2^2 4×22
因此最终结果为2、4、12、16答案即为24121634。
对于快速求 a b a^b ab显然可以使用快速幂。
#include bits/stdc.h
using namespace std;
const int N 1e5 10, MOD 1e9 7;
int a[N], times[N], n, m;int qmi(int a, int b) {int ans 1;while (b) {if (b 1) ans ans * a % MOD;a a * a % MOD;b 1;}return ans % MOD;
}int main() {scanf(%d%d, n, m);for (int i 1; i n; i) {scanf(%d, a[i]);times[i] m;}for (int i 1; i m; i) {int x;scanf(%d, x);-- times[x];}int ans 0;for (int i 1; i n; i) {ans (ans a[i] * qmi(2, times[i]) % MOD) % MOD;}printf(%d\n, ans);
}第四题 小美的众数 首先需要观察到元素 a i a_i ai只有1和2这两种取值。由于它的数值只有1和2所以记录一个前缀和。如果说当前值是1就前缀和加1如果说当前值是2就前缀和减1。即我们定义数组 s i s_i si表示区间 [ 1 , i ] [1,i] [1,i]中元素1和元素2的被标记为1和-1之后的前缀和。
对于一个前缀和 s i s_i si来说它前面有多少个 s j s_j sj的值比 s i s_i si小就说明1的个数会大于等于2的个数那么这些数量的区间众数必然是元素1。 i i i减去这些区间的数量也就是剩下的区间数量众数就是2了。
对于如何求一个前缀和 s i s_i si来说它前面有多少个 s j s_j sj的值比 s i s_i si小这可以用树状数组来求解。
为什么要加偏移量OFFSET n1呢
这是因为数组s[]取值有可能是负数这是由于将元素1和元素2的被标记为1和-1导致的最坏情况下s[]取值可能是 − n -n −n。但是我们知道树状数组下标是从1开始的不能是1的故我们加上偏移量n1使得保证树状数组的下标是正确从1开始。
如何理解query(s[i] OFFSET) (i - query(s[i] OFFSET)) * 2这个式子呢
query(s[i] OFFSET)其实完整写法是query(s[i] OFFSET) * 1它求解的是如果当前区间 [ 1 , i ] [1,i] [1,i]中的众数是元素1的话那么就求这些子区间中众数1的总和。(i - query(s[i] OFFSET)) * 2它求解的是如果当前区间 [ 1 , i ] [1,i] [1,i]中的众数是元素1的话那么就求这些子区间中众数1的总和。当前有 i i i个元素其中众数是元素1的个数有query(s[i] OFFSET)个那么众数是元素2的个数就为(i - query(s[i] OFFSET))。然后求这些子区间中众数2的总和即可。
#include bits/stdc.h
const int N 2e5 10;
using LL long long ;
int a[N], s[N], tr[N * 2], n;inline int lowbit(int x) {return x -x;
}void modify(int x, int k) {for (int i x; i 2 * n 10; i lowbit(i)) tr[i] k;
}LL query(int x) {LL ans 0;for (int i x; i; i - lowbit(i)) ans tr[i];return ans;
}int main() {scanf(%d, n);int OFFSET n 1; // 偏移量防止下标是负数使得下标从1开始for (int i 1; i n; i) scanf(%d, a[i]);modify(0 OFFSET, 1); // 边界初始化LL ans 0;for (int i 1; i n; i) {if (a[i] 1) s[i] s[i - 1] 1;else s[i] s[i - 1] - 1;// query(s[i] OFFSET) * 1计算出如果1是众数时的和// (i - query(s[i] OFFSET)) * 2计算出如果2是众数时的和ans query(s[i] OFFSET) (i - query(s[i] OFFSET)) * 2;modify(s[i] OFFSET, 1);}printf(%lld, ans);
}第五题 小美的逆序对 本题可以考虑使用树状数组来求逆序对。
我们可以先对原数组求一遍逆序对。对于第 i i i个数字它在变为最小的数字后在它之前的所有比它小的数字都会和它组成逆序对在它之后所有比它小的数字会由原本构成逆序对转变成不构成逆序对。设在它左侧比它小的数字的个数为cnt那么在它右侧比它小的数字的个数就是x - 1 - cnt。因此当元素x取反后它左侧这cnt个数字就比x大增加了cnt个逆序对然后它右侧这x-1-cnt个数字就比x大减少了x-1-cnt个逆序对。由此逆序对的增量就是x - (x - 1 - cnt)个。考虑原本的逆序对数目s则第 i i i个数字取反后的逆序对数目为s x - (x - 1 - cnt)。
#include bits/stdc.h
const int N 2e5 10;
using LL long long ;
int t[N], tr[N], n;inline int lowbit(int x) {return x -x;
}void modify(int x, int k) {for (int i x; i n; i lowbit(i)) tr[i] k;
}LL query(int x) {LL ans 0;for (int i x; i; i - lowbit(i)) ans tr[i];return ans;
}int main() {scanf(%d, n);LL s 0;for (int i 1; i n; i) {int x;scanf(%d, x);s query(n) - query(x);// cnt表示x左侧比x小的元素个数, x - 1 - cnt表示x右侧比x小的元素个数LL cnt query(x - 1);t[i] cnt - (x - 1 - cnt);modify(x, 1);}for (int i 1; i n; i) printf(%lld , s t[i]);
}
