模拟祖玛游戏（串）（一）

模拟祖玛游戏（串）（一）

时间： 1ms        内存：1M

描述：

给出只包含0~5的数字字符串（长度小于20），为便于测试，该字符串由玩家输入。由玩家输入一个字符（0~5）和插入位置，若插入字符后形成3个或3个以上的相同字符串，则消去，余下部分连接，直到所有字符都被消去，此时输出：You win！。

输入：

若输入：2003

玩家输入：0 1

玩家输入：2 1

玩家输入：2 1

玩家输入：3 1

玩家输入：3 1

输出：

输出：23

输出：223

输出：3

输出：3 3

输出：You win!

示例输入：

1122334455

5 8

4 6

3 4

2 2

1 1

示例输出：

11223344

112233

1122

11

You win!

提示：

参考答案（内存最优[752]）：

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
	char date;
	struct node *link;
	struct node *before;
}SNode,*SNodePtr;
SNodePtr creat(){
	char c;
	SNodePtr head=NULL,p,q;
	while((c=getchar())!='\n'){
		p=malloc(sizeof(SNode));
		p->date=c;
		if(head==NULL){
			head=q=p;
			head->before=NULL;
		}
		else{
			q->link=p;
			p->before=q;
			q=p;
		}
	}
	q->link=NULL;
	return head;
}
int main(){
	SNodePtr head,p,q,r;
	char c,d,i;
	head=creat();
	while(head!=NULL){
		int sum=0;
		p=head;
		getchar();
		scanf("%c %c",&c,&d);
		for(i=49;i<d;i++)
			p=p->link;
		q=p;
		while(1){
			if(q->date!=c)
				break;
			else
				sum++;
			if(q==head)
				break;
			q=q->before;
		}
		r=p->link;
		while(1){
			if(r==NULL)
				break;
			if(r->date!=c)
				break;
			else
				sum++;
			r=r->link;
		}
		if(sum>=2){
			if(q->date==c){
				head=r;
				if(r!=NULL)
					r->before=NULL;
			}
			else
				q->link=r;
		}
		else{
			q=malloc(sizeof(SNode));
			q->date=c;
			q->link=NULL;
			q->link=p->link;
			q->before=p;
			if(p->link!=NULL)
				q->link->before=q;
			p->link=q;
		}
		for(p=head;p!=NULL;p=p->link)
			printf("%c",p->date);
		if(head!=NULL)
			printf("\n\n");
		getchar();
	}
	printf("You win!\n");
}

参考答案（时间最优[0]）：

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
	char date;
	struct node *link;
	struct node *before;
}SNode,*SNodePtr;
SNodePtr creat(){
	char c;
	SNodePtr head=NULL,p,q;
	while((c=getchar())!='\n'){
		p=malloc(sizeof(SNode));
		p->date=c;
		if(head==NULL){
			head=q=p;
			head->before=NULL;
		}
		else{
			q->link=p;
			p->before=q;
			q=p;
		}
	}
	q->link=NULL;
	return head;
}
int main(){
	SNodePtr head,p,q,r;
	char c,d,i;
	head=creat();
	while(head!=NULL){
		int sum=0;
		p=head;
		getchar();
		scanf("%c %c",&c,&d);
		for(i=49;i<d;i++)
			p=p->link;
		q=p;
		while(1){
			if(q->date!=c)
				break;
			else
				sum++;
			if(q==head)
				break;
			q=q->before;
		}
		r=p->link;
		while(1){
			if(r==NULL)
				break;
			if(r->date!=c)
				break;
			else
				sum++;
			r=r->link;
		}
		if(sum>=2){
			if(q->date==c){
				head=r;
				if(r!=NULL)
					r->before=NULL;
			}
			else
				q->link=r;
		}
		else{
			q=malloc(sizeof(SNode));
			q->date=c;
			q->link=NULL;
			q->link=p->link;
			q->before=p;
			if(p->link!=NULL)
				q->link->before=q;
			p->link=q;
		}
		for(p=head;p!=NULL;p=p->link)
			printf("%c",p->date);
		if(head!=NULL)
			printf("\n\n");
		getchar();
	}
	printf("You win!\n");
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。