2646183_ac_31ms_872k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define INIT (tree *)malloc(sizeof(tree))

using namespace std;

int n;

typedef struct node 
{
	int len, ape;
	char word[101];
	struct node *l, *r;
}tree;

tree *root;
int mark;

void insert(char tmp[],int len)
{
	if (mark)
	{
		mark = 0;
		root = INIT;
		strcpy(root->word,tmp);
		root->len = len;
		root->ape = 1;
		root->l = root->r = NULL;
	} 
	else
	{
		tree *p, *q;

		p = root;
		q = INIT;
		q->l = q->r = NULL;
		q->len = len;q->ape = 1;
		strcpy(q->word,tmp);
		while (p)
		{
			int v = strcmp(p->word,tmp);
			if (v>0)
			{
				if (p->l)
				{
					p = p->l;
				} 
				else
				{
					p->l = q;
					return ;
				}
			}
			else
				if (v<0)
				{
					if (p->r)
					{
						p = p->r;
					} 
					else
					{
						p->r = q;
						return ;
					}
				} 
				else
				{
					p->ape++;
					return ;
				}
		}
	}
}

int Find(char tmp[])
{
	tree *p;

	p = root;
	while (p)
	{
		int v = strcmp(p->word,tmp);
		if (v<0)
		{
			p = p->r;
		} 
		else
		{
			if (v>0)
			{
				p = p->l;
			} 
			else
			{
				return p->ape;
			}
		}
	}
	return 0;
}

int main()
{
	int i, t, cas, m, l;
	char tmp[101];

	//freopen("sin","r",stdin);
	//freopen("res","w",stdout);
	scanf("%d",&t);
	cas = 1;
	while (t--)
	{
		mark = 1;
		printf("Scenario #%d:\n",cas++);
		scanf("%d",&n);
		for (i = 0; i < n; i++)
		{
			scanf("%s",tmp);
			l = strlen(tmp);
			if (l>2)
			{
				sort(&tmp[1],&tmp[1]+l-2);
			}
			insert(tmp,l);
		}
		scanf("%d",&m);
		int ans;
		char ch;

		for (i = 0; i < m; i++)
		{
			ans = 1;
			scanf("%s",tmp);
			while (1)
			{	
				l = strlen(tmp);
				if (l>2)
				{
					sort(&tmp[1],&tmp[1]+l-2);
				}
				ans *= Find(tmp);
				while ((ch=getchar()))
				{
					if (ch=='\n')
					{
						goto ed;
					}
					if (ch!=' ')
					{
						tmp[0] = ch;
						scanf("%s",&tmp[1]);
						break;
					}
				}
			}
ed:
			;
			printf("%d\n",ans);
		}
		printf("\n");
		root->ape = 0;
	}
	return 0;
}