学步园

题目描述

现在给一个字符串，你要做的就是当这个字符串中存在两个挨着的字符是相同的时就将这两个字符消除。需要注意的是，当把这两个字符消除后，可能又产生一对新的挨着的字符是相同的。比如，初始的字符串是abcddc，dd是两个挨着的相同的字符，当把"dd"消除后，得到的字符串是abcc，这时cc又是两个挨着的相同的字符，所以又应该把cc消除。重复以上操作直到剩下的串中不存在两个挨着的字符是相同的为止，输出最终剩下的串。另外需要注意的是，多对相同字符的消除顺序是不会对答案产生影响的，可以证明最后他们都会达到唯一的结果，比如，对于初始字符串adccdeed，无论是adccdeed->addeed->aeed->ad还是adccdeed->adccdd->adcc->ad，最终的输出结果都是ad。

输入

输入文件名：string.in
输入的第一行，包含一个字符串，为初始字符串，所有的字符均为小写字母。

输出

输出文件名：string.out
输出为一行，包含一个字符串，为执行多次消除操作后最终剩下的字符串。

输入样例

adccdeed

输出样例

ad

数据范围

对于100%的数据，字符串的长度在1到200000之间。

题解

话说第一反应是链表，其实是栈。不过鉴于我写链表经常写跪，所以就当链表练手了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define inf 1<<30
using namespace std;
int n;
char ch[200005];
struct lian{int v,nx,pre;} a[200010];
void init()
{
	scanf("%s",ch+1);
	n=strlen(ch+1);
	int i;
	for(i=1;i<=n;i++)
	   {a[i].v=ch[i]-'a'+1;
	    a[i].pre=i-1;
	    a[i-1].nx=i;
	   }
	a[0].v=inf; a[n+1].v=-inf;
	a[n].nx=n+1; a[n+1].pre=n;
}
void work()
{
	int l=1,r,z,y;
	while(l<=n)
	   {if(a[l].v!=a[a[l].nx].v)
	       {l=a[l].nx; continue;}
	    while(a[l].v==a[a[l].nx].v)
	       {r=a[l].nx;
		    z=a[l].pre; y=a[r].nx;
		    a[z].nx=y; a[y].pre=z;
		    l=z; r=y;
		   }
	   }
	l=a[0].nx;
	while(l<=n)
	   {printf("%c",(char)a[l].v-1+'a');
	    l=a[l].nx;
	   }
}
int main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	init(); work();
	return 0;
}