CF909D Colorful Points
ThomasNO1
·
·
题解
题目传送门
Solution
如果这道题用暴力，时间复杂度是 O(n^2) 的复杂度，无法通过这一道题，只能用 O(n) 左右的复杂度，此时 STL 库就起到了作用。
我们可以发现，这个字符串中的一些相同且两两相邻的字符可以组成一个块，像这样：
所以这些块，可以用一个 `vector` 来存储这些块。`vector` 则存储这一个 `pair<char,int>` 表示，一个以一个 `char` 类型的字符开头的的一个块的长度。而这个 `vector` 的属性是第 $i-1$ 次消除时，剩下的字符串所生成的新块。
我们可以发现，一个块，如果他是这个字符串中第一个块，那消除时，那只有这个块的最右边的那个字符才会和在这个字符的右边与它不同的字符抵消。同理，如果一个块是字符串中倒数第一个块，那消除时，那只有这个块的最左边的那个字符才会和在这个字符的左边与它不同的字符抵消。所以，首尾两个块在每一次抵消时，这个块的字符数量只会减 $1$，而在中间的块们，其首尾两位字符都会被抵消，所以，如果是在中间的块，那这个块的字符数量会减 $2$。
当一个块的字符数量 $\le 0$，那这个块为空，无用，循环直接调到下一次循环当中，不被加到下一层 `vector` 当中。如果这个块不为空，我们还要判断这一个块可不可以和前面一个的已被受消除的块合并，也就是如果这两个块的首字母相同，那就让前面一个的已被受消除的块的字符数量加上此时也被修改的块的字符数量。如果无法合并，也就是两个块的首字母不同，那就让此时的这块块加入到下一轮“淘汰赛”当中。
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 8;
vector<pair<char,int> > v[MAXN];//属性见上
char s[MAXN];
int main(){
scanf("%s",s);
int len = strlen(s),num = 0;
for(int i = 0;i < len;i++){//记录刚开始，每个块的首字母与块的大小。
if(i == 0){
num++;
continue;
}
if(s[i] != s[i - 1]) v[1].push_back({s[i - 1],num}),num = 1;
else num++;
}
v[1].push_back({s[len - 1],num});//注意，上一个循环中，并没有记录最后一个块的首字母和大小，所以注意这一处。
int I = 1;
while(v[I].size() > 1){//如果只有一个或根本没有块了，无法合并，退出
for(int i = 0;i < v[I].size();i++){//解析见上文
int number = v[I][i].second;
if(i == 0 || i == v[I].size() - 1)
number--;
else
number -= 2;
if(number <= 0)
continue;
if(!v[I + 1].empty()){
if(v[I + 1][v[I + 1].size() - 1].first ==
v[I][i].first) v[I + 1][v[I + 1].size() - 1].second += number;
else
v[I + 1].push_back({v[I][i].first,number});
}
else
v[I + 1].push_back({v[I][i].first,number});
}
I++;
}
printf("%d\n",I - 1);//刚开始不算
return 0;
}
```