在一个字符串 S 中，如果 Si=Si−1 且 Si≠Si+1，则称 Si 和 Si+1 为边缘字符。
如果 Si≠Si−1 且 Si=Si+1，则 Si−1和 Si 也称为边缘字符。
其它的字符都不是边缘字符。
对于一个给定的串 S，一次操作可以一次性删除该串中的所有边缘字符（操作后可能产生新的边缘字符）。
请问经过 2^64 次操作后，字符串 S 变成了怎样的字符串，如果结果为空则输出 EMPTY。
输入格式
输入一行包含一个字符串 S。
输出格式
输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY。
数据范围
对于 25% 的评测用例，|S|≤10^3，其中 |S|表示 S的长度；
对于 50% 的评测用例，|S|≤10^4；
对于 75% 的评测用例，|S|≤10^5；
对于所有评测用例，|S|≤10^6，S 中仅含小写字母。
输入样例1：
edda
输出样例1：
EMPTY
输入样例2：
sdfhhhhcvhhxcxnnnnshh
输出样例2：
s
思路：题目就是模拟删除符合边缘字符条件的字符
先看暴力的做法就是两层遍历，那么o（n^2）就会TLE，观察题目，暴力的两层循环是有很多冗余的判断次数，其实每次只需要判断被删除的字符左右两边的字符就行。
这里用两个vector数组w，q，分别代表待删和备选。因为长度总共为n，所以时间复杂度为3n。
带有注释的代码：
#include <iostream> #include <algorithm> #include <cstring> #include <vector> using namespace std; const int N = 1000010; int l[N], r[N]; // 左右邻接关系数组 char s[N]; // 输入的字符串 vector<int> q, w; // 辅助队列 q 用于存储待处理的节点，w 用于存储需要插入的节点 int n; // 字符串长度 bool st[N]; // 记录节点是否已经处理过 // 插入节点到待处理队列 void insert(int k) { if (!st[k]) { st[k] = true; w.push_back(k); } } // 根据条件筛选待删除节点 void filter_del() { w.clear(); for (int k : q) { int a = l[k], b = k, c = r[k]; // 满足条件1：a和b相同，b和c不同，且c不是边界标记# if (s[a] == s[b] && s[b] != s[c] && s[c] != '#') { insert(b); insert(c); } // 满足条件2：a和b不同，b和c相同，且a不是边界标记# else if (s[a] != s[b] && s[b] == s[c] && s[a] != '#') { insert(a); insert(b); } } } int main() { // 读取输入字符串 cin >> s + 1; n = strlen(s + 1); // 处理字符串的边界情况 s[0] = s[n + 1] = '#'; // 初始化左右邻接数组和待处理队列 for (int i = 1; i <= n; ++i) { l[i] = i - 1, r[i] = i + 1; q.push_back(i); } r[0] = 1, l[n + 1] = n; // 循环处理，直到没有待处理节点 while (true) { filter_del(); if (w.empty()) break; q.clear(); for (int k : w) { int a = l[k], b = k, c = r[k]; // 将未处理的左侧节点加入待处理队列，且不重复加入相同的节点 if (!st[a] && a && (q.empty() || q.back() != a)) q.push_back(a); // 将未处理的右侧节点加入待处理队列 if (!st[c] && c != n + 1) q.push_back(c); // 更新左右邻接关系，将节点b从链表中删除 r[a] = c, l[c] = a; } } // 输出结果 if (r[0] == n + 1) cout << "EMPTY"; else { for (int i = r[0]; i != n + 1; i = r[i]) { cout << s[i]; } } return 0; }
