消除游戏(第十三届蓝桥杯省赛C++C组 , 第十三届蓝桥杯省赛PythonA/B/研究生组)

简介: 消除游戏(第十三届蓝桥杯省赛C++C组 , 第十三届蓝桥杯省赛PythonA/B/研究生组)

在一个字符串 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;
}
相关文章
|
3天前
|
定位技术 C++ Windows
第一人称射击游戏 C++控制台版(未完成)
第一人称射击游戏 C++控制台版(未完成)
第一人称射击游戏 C++控制台版(未完成)
|
3天前
|
C++
C++小练习:猜数游戏
C++小练习:猜数游戏
|
10天前
|
存储 人工智能 C++
【PTA】L1-093 猜帽子游戏(C++)
【PTA】L1-093 猜帽子游戏(C++)
10 1
|
25天前
|
数据安全/隐私保护 C++
小唐开始刷蓝桥(九)2012年第三届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(九)2012年第三届C/C++ B组蓝桥杯省赛真题
|
26天前
|
算法 测试技术 C++
小唐开始刷蓝桥(八)2013年第四届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(八)2013年第四届C/C++ B组蓝桥杯省赛真题
|
26天前
|
算法 C++ 数据格式
小唐开始刷蓝桥(七)2014年第五届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(七)2014年第五届C/C++ B组蓝桥杯省赛真题
|
26天前
|
算法 C++
小唐开始刷蓝桥(六)2015年第六届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(六)2015年第六届C/C++ B组蓝桥杯省赛真题
|
26天前
|
算法 C++
小唐开始刷蓝桥(五)2016年第七届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(五)2016年第七届C/C++ B组蓝桥杯省赛真题
|
26天前
|
存储 人工智能 算法
小唐开始刷蓝桥(四)2017年第八届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(四)2017年第八届C/C++ B组蓝桥杯省赛真题
|
26天前
|
机器学习/深度学习 存储 人工智能
小唐开始刷蓝桥(三)2018年第九届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(三)2018年第九届C/C++ B组蓝桥杯省赛真题

热门文章

最新文章