「NOIP模拟赛」字符串
「题目描述」
现在给一个字符串，你要做的就是当这个字符串中存在两个挨着的字符是相同的时就将这两个字符消除。需要注意的是，当把这两个字符消除后，可能又产生一对新的挨着的字符是相同的。比如，初始的字符串是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之间。
题解
栈/链表模拟
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define pa pair<int,int> #define inf (1LL<<60) #define mod 1000000007 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char a[200005]; int n; int l[200005],r[200005]; void del(int x) { int L=l[x],R=r[x]; r[L]=R;l[R]=L; } int main() { //freopen("string.in","r",stdin); //freopen("string.out","w",stdout); scanf("%s",a+1);n=strlen(a+1); for(int i=0;i<n;i++)r[i]=i+1; for(int i=1;i<=n;i++)l[i]=i-1; for(int now=r[0];now;now=r[now]) { while(now&&a[now]==a[l[now]]) { int t=r[now]; del(l[now]);del(now); now=t; } } for(int now=r[0];now;now=r[now]) printf("%c",a[now]); puts(""); return 0; } |
Subscribe
计数器 9319902
OI 课件=>
OI 课件=>