下面是美團(tuán)2024-03-16筆試真題，進(jìn)行了VP，由于未參與評測，故不保證正確性，僅供參考。

第一題 小美點(diǎn)外賣

求和然后減去滿減和紅包即可。

#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);
}

第二題 小美的合法單詞

考慮三種情況分別需要的操作次數(shù)，取最小值即可。

先掃描字符串s，并用變量big和small分別統(tǒng)計(jì)字符串s中大寫字母、小寫字母的個(gè)數(shù)。

然后還要處理第一個(gè)字符是大寫的情況：

首先初始化變量t=s.size()，當(dāng)?shù)谝粋€(gè)字符是大寫字母時(shí)，執(zhí)行t = t - 1 - small。減去1是因?yàn)槿サ舻谝粋€(gè)大寫字母，然后再減去small，這樣得到的就是后面剩余的大寫字符個(gè)數(shù)。

為什么是t-1-small而不是t-1-big呢？舉個(gè)例子：s=“AaaBbCD”，此時(shí)big=4，small=3。

• 若執(zhí)行t-1-big，則此時(shí)t的結(jié)果就是2，那么答案為min{big, small, t} = 2，但顯然答案應(yīng)該是3（將后面的B,C,D修改為小寫）。
• 若執(zhí)行t-1-small，則此時(shí)t的結(jié)果就是3，那么答案為min{big, small, t} = 3，這顯然就是正確答案3（將后面的B,C,D修改為小寫）。

說白了就是由于題目要求第一個(gè)字母大寫，后面所有字母都是小寫。t-1-small就是將后面統(tǒng)計(jì)除了首位這個(gè)大寫字母外剩余部分的大寫字母個(gè)數(shù)，而我們需要將這些大寫字母個(gè)數(shù)就是我們需要修改為小寫字母所需要的操作次數(shù)。

#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}));
}

第三題 翻倍元素

統(tǒng)計(jì)每個(gè)元素最后翻倍的次數(shù)即可。

如下表：

數(shù)組元素a[]	翻倍次數(shù)times[]	最終結(jié)果
a[1]=1	1	$1\times 2^1$
a[2]=2	1	$2\times 2^1$
a[3]=3	2	$3\times 2^2$
a[4]=4	2	$4\times 2^2$

因此最終結(jié)果為2、4、12、16，答案即為2+4+12+16=34。

對于快速求$a^b$顯然可以使用快速冪。

#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);
}

第四題 小美的眾數(shù)

首先需要觀察到元素$a_i$只有1和2這兩種取值。由于它的數(shù)值只有1和2，所以記錄一個(gè)前綴和。如果說當(dāng)前值是1就前綴和加1，如果說當(dāng)前值是2，就前綴和減1。即我們定義數(shù)組$s_i$表示區(qū)間$[1,i]$中元素1和元素2的被標(biāo)記為+1和-1之后的前綴和。

對于一個(gè)前綴和$s_i$來說，它前面有多少個(gè)$s_j$的值比$s_i$小，就說明，1的個(gè)數(shù)會大于等于2的個(gè)數(shù)，那么這些數(shù)量的區(qū)間，眾數(shù)必然是元素1。$i$減去這些區(qū)間的數(shù)量，也就是剩下的區(qū)間數(shù)量，眾數(shù)就是2了。

對于如何求一個(gè)前綴和$s_i$來說，它前面有多少個(gè)$s_j$的值比$s_i$小，這可以用樹狀數(shù)組來求解。

為什么要加偏移量OFFSET = n+1呢？

這是因?yàn)閿?shù)組s[]取值有可能是負(fù)數(shù)（這是由于將元素1和元素2的被標(biāo)記為+1和-1導(dǎo)致的），最壞情況下s[]取值可能是$?n$。但是我們知道樹狀數(shù)組下標(biāo)是從1開始的，不能是<1的，故我們加上偏移量n+1，使得保證樹狀數(shù)組的下標(biāo)是正確從1開始。

如何理解query(s[i] + OFFSET) + (i - query(s[i] + OFFSET)) * 2這個(gè)式子呢？

• query(s[i] + OFFSET)其實(shí)完整寫法是query(s[i] + OFFSET) * 1，它求解的是如果當(dāng)前區(qū)間$[1,i]$中的眾數(shù)是元素1的話，那么就求這些子區(qū)間中眾數(shù)1的總和。
• (i - query(s[i] + OFFSET)) * 2，它求解的是如果當(dāng)前區(qū)間$[1,i]$中的眾數(shù)是元素1的話，那么就求這些子區(qū)間中眾數(shù)1的總和。當(dāng)前有$i$個(gè)元素，其中眾數(shù)是元素1的個(gè)數(shù)有query(s[i] + OFFSET)個(gè)，那么眾數(shù)是元素2的個(gè)數(shù)就為(i - query(s[i] + OFFSET))。然后求這些子區(qū)間中眾數(shù)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;	// 偏移量，防止下標(biāo)是負(fù)數(shù)，使得下標(biāo)從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計(jì)算出如果1是眾數(shù)時(shí)的和// (i - query(s[i] + OFFSET)) * 2計(jì)算出如果2是眾數(shù)時(shí)的和ans += query(s[i] + OFFSET) + (i - query(s[i] + OFFSET)) * 2;modify(s[i] + OFFSET, 1);}printf("%lld", ans);
}

第五題 小美的逆序?qū)?/h3>

本題可以考慮使用樹狀數(shù)組來求逆序?qū)Α?/p>

我們可以先對原數(shù)組求一遍逆序?qū)?。對于?span id="ieo6y2aa" class="katex--inline">$i$個(gè)數(shù)字，它在變?yōu)樽钚〉臄?shù)字后，在它之前的所有比它小的數(shù)字都會和它組成逆序?qū)?#xff0c;在它之后所有比它小的數(shù)字會由原本構(gòu)成逆序?qū)D(zhuǎn)變成不構(gòu)成逆序?qū)?。設(shè)在它左側(cè)比它小的數(shù)字的個(gè)數(shù)為cnt，那么在它右側(cè)比它小的數(shù)字的個(gè)數(shù)就是x - 1 - cnt。因此當(dāng)元素x取反后，它左側(cè)這cnt個(gè)數(shù)字就比x大，增加了cnt個(gè)逆序?qū)?#xff0c;然后它右側(cè)這x-1-cnt個(gè)數(shù)字就比x大，減少了x-1-cnt個(gè)逆序?qū)ΑＳ纱四嫘驅(qū)Φ脑隽烤褪?code>x - (x - 1 - cnt)個(gè)。考慮原本的逆序?qū)?shù)目s，則第$i$個(gè)數(shù)字取反后的逆序?qū)?shù)目為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左側(cè)比x小的元素個(gè)數(shù), x - 1 - cnt表示x右側(cè)比x小的元素個(gè)數(shù)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]);
}

---