A40890. 消除游戏本题总分：20 分【问题描述】在一个字符串 S 中，如果 S i = S ii 1 且 S i , S i+1 ，则称 S i 和 S i+1 为边缘字符。如果 S i , S ii 1 且 S i = S i+1，则 S ii 1 和 S i 也称为边缘字符。其它的字符都不是边缘字符。对于一个给定的串 S，一次操作可以一次性删除该串中的所有边缘字符（操作后可能产生新的边缘字符）。请问经…
填空题
困难
知识点
题目描述
消除游戏
本题总分：20 分
【问题描述】
在一个字符串 S 中，如果 S i = S ii 1 且 S i , S i+1 ，则称 S i 和 S i+1 为边缘
字符。如果 S i , S ii 1 且 S i = S i+1，则 S ii 1 和 S i 也称为边缘字符。其它的字符
都不是边缘字符。
对于一个给定的串 S，一次操作可以一次性删除该串中的所有边缘字符
（操作后可能产生新的边缘字符）。
请问经过 2
64 次操作后，字符串 S 变成了怎样的字符串，如果结果为空则
输出 EMPTY。
【输入格式】
输入一行包含一个字符串 S 。
【输出格式】
输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY。
【样例输入 1】
edda
【样例输出 1】
EMPTY
【样例输入 2】
sdfhhhhcvhhxcxnnnnshh
【样例输出 2】 s
试题 G: 消除游戏 10
第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 C 组
【评测用例规模与约定】
对于 25% 的评测用例，|S | ≤ 103 ，其中 |S | 表示 S 的长度；
对于 50% 的评测用例，|S | ≤ 104 ；
对于 75% 的评测用例，|S | ≤ 105 ；
对于所有评测用例，|S | ≤ 106，S 中仅含小写字母。
参考答案
#include <bits/stdc++.h>
using namespace std;
//char str = [1000010];
const long long pow264 = (long long)pow(2.0,64.0);
string str;
int del[1000010] = {0};
int del_len=0;
bool cmp(int a,int b)
{
return a<b;
}
int main()
{
long long i,j,k;
cin>>str;
for(k=0;k<pow264;k++)
{
// cout<<str<<"\n\n";
int have_erase = 0;
del_len = 0;
for(i=1;i<str.length()-1;i++)
{
if((str[i-1]==str[i])&&(str[i]!=str[i+1]))
{
del[del_len++] = i;
del[del_len++] = i+1;
have_erase = 1;
}
if((str[i-1]!=str[i])&&(str[i]==str[i+1]))
{
del[del_len++] = i-1;
del[del_len++] = i;
have_erase = 1;
}
}
sort(del,del+del_len+1,cmp);
while(del_len>=1)
{
cout<<del[del_len]<<"\n";
if(del[del_len]<str.length())
str.erase(del[del_len--],1);
else
del_len--;
}
if(!have_erase || str.length()<=1)
break;
}
if(str.length()>0)
cout<<str;
else
cout<<"EMPTY";
return 0;
}
上一题
下一题