題目傳送門

題目大意

你有一個空序列和 $N$ 個球。第 $i$ 個球 $(1\le i\le N)$ 的大小是 $2^{A_i}$。

計算 $N$ 操作后序列中剩余的球的個數。

你將進行 $N$ 次運算。

在第 $i$ 次操作中，你將第 $i$ 個球添加到序列的最右端，然后重復下面的步驟：

1. 如果序列中只有一個或更少的球，則結束操作。
2. 如果序列中最右邊的球和第二右邊的球大小不同，則結束操作。
3. 如果序列中最右邊的球和第二右邊的球大小相同，則拿出這兩個球，并在序列的最右端添加一個新球，其大小等于移除的兩個球的大小之和。然后回到步驟 1，重復上述過程。

計算 $N$ 操作后序列中剩余的球的個數。

解題思路

我們拿到題目一看，可以直接模擬，算法時間復雜度 $O(n)$。

首先定義一個 stack，為什么要定義一個棧呢？因為我們可以發現，每次操作都是從序列的最右端取出球，而不關最左端的球的事，所以我們可以將序列的最右端看成棧頂，而最左端可以看做是棧底，于是我們只需要在每次操作時，先將第 $i$ 個球入棧，再判斷棧的元素個數，然后連續兩次出棧，判斷兩球大小是否相同，最后確定是否將新球入棧即可。

大體思路如上所述，但是還有一個地方困住了一些選手，就是如題所述的第 $i$ 個球的大小為 $2^{A_i}$，但是 $0\le A_i\le 10^9$，那我們肯定不能直接算出 $2^{A_i}$ 的值，因為存不下這么大的數。我們不難想到在每次操作中只計算 $A_i$ 的值，但是這怎么計算呢？我們又得從題目進行分析，題目說了只有在最右端的兩球大小相同時才會添加一個大小為拿出的球的大小之和的球，也就是說我們每次計算時，只需要計算 $2\times 2^{B_k}$ （這里令 $B_k$ 為拿走的其中一個球的大小）的值就可以了。而 $2\times 2^{B_k}$ 就等于 $2^{B_k+1}$，所以在添加球的時候我們只需要入棧 $B_k+1$ 即可。

CODE:

#include <bits/stdc++.h>
using namespace std;
#define int long long
stack<int> s;
int a[200010];
signed main() {ios::sync_with_stdio(false);ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);int n;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++) {s.push(a[i]);while (1) {if (s.size() <= 1) {break;}int k = s.top();s.pop();int l = s.top();s.pop();if (k != l) {s.push(l);s.push(k);break;}s.push(l + 1);}}cout << s.size();return 0;
} 

總結

這道題目主要考察了大家能不能將題目描述轉化為棧的操作，總體來說較為簡單。