NOIP2004蟲食算---C2021bjw

首先看一下題目:

所謂蟲食算，就是原先的算式中有一部分被蟲子啃掉了，需要我們根據剩下的數字來判定被啃掉的字母。來看一個簡單的例子：

43#98650#45

+　　 8468#6633

--------------------------------- 　　　

44445506978

其中#号代表被蟲子啃掉的數字。

根據算式，我們很容易判斷：第一行的兩個數字分别是5和3，第二行的數字是5。

現在，我們對問題做兩個限制：

首先，我們隻考慮加法的蟲食算。這裡的加法是N進制加法，算式中三個數都有N位，允許有前導的0。

其次，蟲子把所有的數都啃光了，我們隻知道哪些數字是相同的，我們将相同的數字用相同的字母表示，不同的數字用不同的字母表示。

如果這個算式是N進制的，我們就取英文字母表午的前N個大寫字母來表示這個算式中的0到N-1這N個不同的數字：但是這N個字母并不一定順序地代表0到N-1)。

輸入資料保證N個字母分别至少出現一次。

BADC

• CBDA

DCCC

上面的算式是一個4進制的算式。很顯然，我們隻要讓ABCD分别代表0123，便可以讓這個式子成立了。

你的任務是，對于給定的N進制加法算式，求出N個不同的字母分别代表的數字，使得該加法算式成立。輸入資料保證有且僅有一組解。

這道題是NOIP2004的一道搜尋題，巧妙利用了大量剪枝，初始化處理，并且将搜尋順序倒過來以提高搜尋速度。

這是一道非常經典的搜尋題目，隻要掌握了它的方法基本就可以掌握整個深搜的所有優化技巧。

接下來上代碼：

//這道題的關鍵在于從右至左進行計算，其次在Dfs中，如果J從0開始，那大數就越靠前，如果将大數放在低位上，那麼進位的可能性就越大
#include <cstdio>
#include <cstdlib>
#include <cstring>

bool Used [ 95 ] = {  };
int V [ 95 ] = {  } , N = 0 , Cnt = 0 , Tmp = 0 , Jw = 0 , A1 = 0 , A2 = 0 , B1 = 0 , B2 = 0, C1 = 0 , C2 = 0;
char A [ 30 ] = {  } , B [ 30 ] = {  } , C [ 30 ] = {  } , D [ 30 ] = {  };

void Init (  )//預處理
{
	for ( int I = N - 1; I >= 0; I -- )
	{
		if ( ! Used [ A [ I ] ] )//如果A[I]沒有沒使用過
		{
			Used [ A [ I ] ] = 1;//标記為使用過
			D [ ++ Cnt ] = A [ I ];//将A[I]存入D數組中
		}
		if ( ! Used [ B [ I ] ] )//如果B[I]沒有沒使用過
		{
			Used [ B [ I ] ] = 1;//标記為使用過
			D [ ++ Cnt ] = B [ I ];//将B[I]存入D數組中
		}
		if ( ! Used [ C [ I ] ] )//如果C[I]沒有沒使用過
		{
			Used [ C [ I ] ] = 1;//标記為使用過
			D [ ++ Cnt] = C [ I ];//将B[I]存入D數組中
		}
	}
	memset ( Used , 0 , sizeof ( Used ) );//清零，友善下次使用
	memset ( V , -1 , sizeof ( V ) );//清-1，友善下次使用
}
int Ok (  )//判斷輸出條件
{
	for ( int I = N - 1; I >= 0; I -- )
	{
		Tmp = V [ A [ I ] ] + V [ B [ I ] ] + Jw;
		if ( Tmp % N != V [ C [ I ] ] )//如果兩加數與進位相加不等于和return 0
		{
			return 0;
		}
		Jw = Tmp / N;
	}
	if ( Jw )//如果有進位，不滿足條件return 0
	{
		return 0;
	}
	return 1;
}
int Check (  )//剪枝
{
	for ( int I = N - 1; I >= 0; I -- )
	{
		if ( V [ A [ I ] ] > -1 && V [ B [ I ] ] > -1 && V [ C [ I ] ] >-1 )//三個數都有值
		{		
			if ( ( V [ A [ I ] ] + V [ B [ I ] ] ) % N != V [ C [ I ] ] && ( V [ A [ I ] ] + V [ B [ I ] ] + 1 ) % N != V [ C [ I ] ] )//如果相加不等于和并且加上進位也不等于和 ,那麼這個式子不可能成立,不在這一枝上繼續搜尋
			{
				return 0;
			}
		}
		if ( V [ A [ I ] ] > -1 && V [ B [ I ] ] > -1 && V [ C [ I ] ] == -1 )//隻有兩個加數有值
		{
			C1 = ( V [ A [ I ] ] + V [ B [ I ] ] ) % N;
			C2 = ( V [ A [ I ] ] + V [ B [ I ] ] + 1 ) % N;//考慮進位
			if ( Used [ C1 ] && Used [ C2 ] )//如果相加的值被占用并且加上進位也被占用,那麼這個式子不可能成立,不在這一枝上繼續搜尋
			{
				return 0;
			}
		}
		if ( V [ A [ I ] ] > -1 && V [ B [ I ] ] == -1 && V [ C [ I ] ] > -1 )//隻有A加數與和
		{
			B1 = ( V [ C [ I ] ] - V [ A [ I ] ] + N ) % N;//可能不夠減，是以加上N
			B2 = ( V [ C [ I ] ] - V [ A [ I ] ] - 1 + N ) % N;//借位也要考慮
			if ( Used [ B1 ] && Used [ B2 ] )//如果相減的值與減去借位的值都被占用,那麼這個式子不可能成立,不在這一枝上繼續搜尋
			{
				return 0;
			}
		}
		if ( V [ A [ I ] ] == -1 && V [ B [ I ] ] > -1 && V [ C [ I ] ] > - 1 )//隻有B加數與和
		{
			A1 = ( V [ C [ I ] ] - V [ B [ I ] ] + N ) % N;//可能不夠減，是以加上N
			A2 = ( V [ C [ I ] ] - V [ B [ I ] ] - 1 + N ) % N;//借位也要考慮
			if ( Used [ A1 ] && Used [ A2 ] )//如果相減的值與減去借位的值都被占用,那麼這個式子不可能成立,不在這一枝上繼續搜尋
			{
				return 0;
			}
		}
	}
	return 1;
}
void Print (  )//輸出
{
	for ( int I = 65; I < N + 64; I ++ )//保證最後沒有空格,雖然考試時忽略格式,但平常最好養成好習慣
	{
		printf ( "%d " , V[I] );
	}
	printf ( "%d" , V [ N + 64 ] );
	exit(0);//結束整個程式
}
void Dfs ( int I )//深搜 
{
	if ( I > N )//如果所有字母都有值
	{
		if ( Ok (  ) )//如果滿足題目條件
		{
			Print (  );//輸出
		}
		return;
	}
	for (int J = N - 1; J >= 0; J -- )//循環給每個字母指派 
	{
		if ( Used [ J ] )//如果這個值被占用
		{
			continue;//尋找下一個值
		}
		V [ D [ I ] ] = J;//沒有被占用，把這個值賦給這個字母
		Used [ J ] = 1;//把這個值變為沒有被占用
		if ( ! Check (  ) )//如果不符合條件，剪枝，不在這一枝上搜尋
		{
			V [ D [ I ] ] = -1;//回溯并跳出
			Used [ J ] = 0;
			continue;
		}
		Dfs ( I + 1 );//繼續搜尋
		V [ D [ I ] ] = -1;//回溯
		Used [ J ] = 0;
	}
}
int main()
{
	scanf ( "%d\n" , &N );//輸入N
	gets ( A );//輸入A數組
	gets ( B );//輸入B數組
	gets ( C );//輸入C數組
	Init ( );//預處理
	Dfs ( 1 );//深搜
	return 0;
}