2297.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"set"
#include"functional"
#include"iostream.h"
#include"string.h"

using namespace std;

char atom[11][5],equation[300];
int m[20][20],at_num,mol_num;
int index[20][5];
__int64 ten[10];

int find(char *w)
{
	for(int i=0;i<at_num;i++)
		if(strcmp(w,atom[i])==0)break;
	if(i==at_num)strcpy(atom[at_num++],w);
	return i;
}

void input()
{
	int l,i,j,num,k;char w[5];
	while(cin.peek()=='\n')cin.get();

	cin.getline(equation,300);
	
	l=strlen(equation);
	
	at_num=0;mol_num=0;
	int sign=1;
	
	for(j=0;j<10;j++)
		m[0][j]=0;
	
	for(i=0;i<l;i++)
	{
		if(equation[i]=='+'||equation[i]=='=')
		{
			mol_num++;
			for(j=0;j<10;j++)
				m[mol_num][j]=0;
			
			if(equation[i]=='=')sign=-1;
		}

		else 
		{
			num=sign;
			w[0]=equation[i];w[1]='\0';
			if(equation[i+1]<='z'&&equation[i+1]>='a')
				w[1]=equation[i+1],w[2]='\0',i++;
			
			if(equation[i+1]<='9'&&equation[i+1]>='1')
				num*=equation[i+1]-'0',i++;
			j=find(w);
			m[mol_num][j]+=num;
		}
	}
	mol_num++;
	for(i=0;i<mol_num;i++)
	{
		for(k=0,j=0;j<at_num;j++)
			if(m[i][j]!=0)index[i][k++]=j;
		index[i][k]=-1;
	}

}

struct node
{
	int mol[11];
	int at[11];
	__int64 h;
};

struct cmp
{
	int operator()(node a,node b)const
	{
		return a.h<b.h;
	}
};

set<node,cmp> s;
set<node,cmp>::iterator iter;
int half;
node nd;

void fill(int k)
{
	int i;
	int *p=index[k];
	for(nd.mol[k]=1;nd.mol[k]<=9;nd.mol[k]++)
	{
		for(i=0;p[i]>=0;i++)
		{
			nd.at[p[i]]+=nd.mol[k]*m[k][p[i]];
			nd.h+=nd.mol[k]*m[k][p[i]]*ten[p[i]];
		}
		if(k==mol_num-1)
		{
			if(s.find(nd)==s.end())
			s.insert(nd);
		}
		else fill(k+1);
		
		for(i=0;p[i]>=0;i++)
		{
			nd.at[p[i]]-=nd.mol[k]*m[k][p[i]];
			nd.h-=nd.mol[k]*m[k][p[i]]*ten[p[i]];
		}
	}
}
bool check(int k)
{
	int i,*p=index[k];
	for(nd.mol[k]=1;nd.mol[k]<=9;nd.mol[k]++)
	{
		for(i=0;p[i]>=0;i++)
		{
			nd.at[p[i]]-=nd.mol[k]*m[k][p[i]];
			nd.h-=nd.mol[k]*m[k][p[i]]*ten[p[i]];
		}
		
		if(k==half-1)
		{
			if((iter=s.find(nd))!=s.end())
			{
				for(i=0;i<half;i++)
				{
					if(i)cout<<' ';
					cout<<nd.mol[i];
				}
				for(;i<mol_num;i++)
					cout<<' '<<iter->mol[i];
								
				cout<<endl;
				return 1;
			}
		}
		else if(check(k+1))return 1;
		
		for(i=0;p[i]>=0;i++)
		{
			nd.at[p[i]]+=nd.mol[k]*m[k][p[i]];
			nd.h+=nd.mol[k]*m[k][p[i]]*ten[p[i]];
		}
	}
	return 0;
}

int main()
{
	int t,i;
	ten[0]=1;
	for(i=1;i<10;i++)
		ten[i]=ten[i-1]*82;

	cin>>t;
	while(t--)
	{
		input();
		s.clear();
		half=mol_num/2;
		
		for(i=0;i<10;i++)
			nd.mol[i]=nd.at[i]=0;
		
		fill(half);
		
		for(i=0;i<10;i++)
			nd.mol[i]=nd.at[i]=0;
		
		if(!check(0))cout<<"IMPOSSIBLE"<<endl;
	}
	return 0;
}