2241302_mle.cc

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

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# include <algorithm>

using namespace std;

int len;
char ch, tmp[1000001], str[1000001], ans[1000001];
int flag, mark[28][1000011];

void dfs(int pos,int n)
{
	int i, p;

	ans[n] = tmp[pos];
	if(ans[n]=='.')
	{
		if(n==len-1)
			flag = 1;
		return ;
	}
	for(i = 1; i <= mark[tmp[pos]-'A'][0]; i++)
	{
		if(flag)
			return ;
		if(mark[tmp[pos]-'A'][i])
		{
			p = mark[tmp[pos]-'A'][i];
			mark[tmp[pos]-'A'][i] = 0;
			dfs(p-1,n+1);
			mark[tmp[pos]-'A'][i] = p;
		}
	}
}

void input()
{
	int i, j, t, no, pos;

	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",tmp);
		j = 0;
		for(i = 0; tmp[i] != '\0'; i++)
			if(tmp[i]<='9'&&tmp[i]>='0')
			{
				no = atol(&tmp[i]);
				no--;
				while(no--)
					str[j++] = ch;
				while(tmp[i]<='9'&&tmp[i]>='0')
					i++;
				i--;
			}
			else
			{
				if(tmp[i]=='.')
					pos = i;
				str[j++] = ch = tmp[i];
			}
			str[j] = '\0';
			strcpy(tmp,str);
			sort(tmp,tmp+j);
			memset(mark,0,sizeof(mark));
			for(i = 0; i < j; i++)
				if(str[i]=='.')
					mark[26][0]++,mark[26][mark[26][0]] = i+1;
				else
					mark[str[i]-'A'][0]++,mark[str[i]-'A'][mark[str[i]-'A'][0]] = i+1;
			len = strlen(str);flag = 0;
			dfs(pos,0);
			ans[len] = '\0';
			puts(ans);
	}
}

int main()
{
	input();
	return 1;
}