Beyond the Void
BYVoid
NOI 2003 木棒遊戲
本文正體字版由OpenCC轉換

移動一根火柴可以分爲兩種情況:一是移動某一個數字上的一根火柴,使之變爲另一個數字。二是兩個數字,一個添加一根火柴,一個減少一根火柴。我們可以首先算出等式兩邊的代數和,然後枚舉改變。每次改變後只需算出與原來數的差值,就可以在O(1)時間更新和。總的時間複雜度爲O(N^2)。

看似不難的一道題,本身其實也不難,難就難在初始化上。建議先把每個數字能變成的數字先寫出,然後寫道程序的常量中,這點十分容易錯。

/* 
 * Problem: NOI2003 stickgame
 * Author: Guo Jiabao
 * Time: 2009.5.22 13:16
 * State: Solved
 * Memo: 搜索 初始化
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001;
const int C1[10]={2,0,1,1,0,0,2,0,0,2};
const int R1[10][2]={ {6,9},{0,0},{3},{2},{0,0},{0,0},{0,9},{0,0},{0,0},{0,6} };
const int Ex1[10][10][2]=
{
//		  0		  1		  2		  3		  4		  5		  6		  7		  8		  9
/* 0 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{ 8, 5},{ 8, 1},{ 8, 0},{ 8, 3},} ,
/* 1 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{ 7, 1},{ 7, 0},{-1,-1},} ,
/* 2 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},} ,
/* 3 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{ 9, 5},{-1,-1},{ 9, 0},{ 9, 3},} ,
/* 4 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},} ,
/* 5 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{ 6, 5},{-1,-1},{ 6, 0},{ 9, 5},} ,
/* 6 */	{{ 5, 8},{-1,-1},{-1,-1},{ 5, 9},{-1,-1},{ 5, 6},{-1,-1},{-1,-1},{ 8, 6},{-1,-1},} ,
/* 7 */	{{ 1, 8},{ 1, 7},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},} ,
/* 8 */	{{ 0, 8},{ 0, 7},{-1,-1},{ 0, 9},{-1,-1},{ 0, 6},{ 6, 8},{-1,-1},{-1,-1},{ 9, 8},} ,
/* 9 */	{{ 3, 8},{-1,-1},{-1,-1},{ 3, 9},{-1,-1},{ 5, 9},{-1,-1},{-1,-1},{ 8, 9},{ 3, 8},} ,
};
const int Ex2[10][10][2]=
{
//		  0		  1		  2		  3		  4		  5		  6		  7		  8		  9
/* 0 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},} ,
/* 1 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},} ,
/* 2 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},} ,
/* 3 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{ 9, 9},{-1,-1},} ,
/* 4 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},} ,
/* 5 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{ 9, 6},{ 6, 3},} ,
/* 6 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{ 8, 5},} ,
/* 7 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},} ,
/* 8 */	{{-1,-1},{-1,-1},{-1,-1},{ 9, 9},{-1,-1},{ 6, 9},{-1,-1},{-1,-1},{-1,-1},{-1,-1},} ,
/* 9 */	{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1},{ 3, 6},{ 5, 8},{-1,-1},{-1,-1},{ 8, 3},} ,
};
using namespace std;
char Str[MAXN];
int elem[MAXN],N,E,S[2],bel[MAXN],len;
int L[MAXN],R[MAXN];
bool sgn[MAXN];
void init()
{
	freopen("stickgame.in","r",stdin);
	freopen("stickgame.out","w",stdout);
	scanf("%s",Str);
	sgn[N=1]=true;
	for (char *p=Str;*p!='#';p++)
	{
		++len;
		if (*p=='-') sgn[N+1]=false;
		if (*p=='+' || *p=='=') sgn[N+1]=true;
		if (*p=='=')
			E=N;
		if (*p=='+' || *p=='-' || *p=='=')
		{
			R[N]=len-2;
			L[++N]=len;
		}
		else
		{
			elem[N] = elem[N] * 10 + (*p-'0');
			bel[len-1] = N;
		}
	}
	L[1]=0;
	R[N]=len-1;
}
bool replace(int k,int p)
{
	int a,b,i,v=0,delta;
	b=bel[k];
	for (i=L[b];i<=R[b];i++)
	{
		a=Str[i] - '0';
		if (i==k) a=p;
		v = v * 10 + a;
	}
	delta = v - elem[b];
	if (!sgn[b]) delta = -delta;
	if (b <= E)
		return S[0] + delta == S[1];
	else
		return S[1] + delta == S[0];
}
bool exchange(int k1,int k2,int n1,int n2)
{
	int i,b1,b2,a,v1=0,v2=0,d1,d2;
	b1=bel[k1];b2=bel[k2];
	for (i=L[b1];i<=R[b1];i++)
	{
		a=Str[i] - '0';
		if (i==k1) a=n1;
		v1 = v1 * 10 + a;
	}
	for (i=L[b2];i<=R[b2];i++)
	{
		a=Str[i] - '0';
		if (i==k2) a=n2;
		v2 = v2 * 10 + a;
	}
	d1 = v1 - elem[b1];
	if (!sgn[b1]) d1 = -d1;
	d2 = v2 - elem[b2];
	if (!sgn[b2]) d2 = -d2;
	if (b1<=E && b2<=E)
		return S[0] + d1 + d2 == S[1];
	else if (b1 >E && b2>E)
		return S[0] == S[1] + d1 + d2;
	else if (b1<=E && b2>E)
		return S[0] + d1 == S[1] + d2;
	else
		return S[0] + d2 == S[1] + d1;
}
bool solve()
{
	int i,j,k,a,b,na,nb;
	for (i=1;i<=E;i++)
		S[0] += elem[i] * (sgn[i]?1:-1);
	for (i=E+1;i<=N;i++)
		S[1] += elem[i] * (sgn[i]?1:-1);
	for (i=0;i<len;i++)
	{
		if (Str[i]>='0' && Str[i]<='9')
		{
			a=Str[i]-'0';
			for (k=0;k<C1[a];k++)
				if (replace(i,R1[a][k]))
				{
					Str[i]=R1[a][k] + '0';
					return true;
				}
		}
	}
	for (i=0;i<len-1;i++)
	{
		if (Str[i]>='0' && Str[i]<='9')
		{
			a=Str[i]-'0';
			for (j=i+1;j<len;j++)
			{
				if (Str[j]>='0' && Str[j]<='9')
				{
					b=Str[j]-'0';
					na=Ex1[a][b][0]; nb=Ex1[a][b][1];
					if (na!=-1 && exchange(i,j,na,nb))
					{
						Str[i] = na+'0';
						Str[j] = nb+'0';
						return true;
					}
					na=Ex2[a][b][0]; nb=Ex2[a][b][1];
					if (na!=-1 && exchange(i,j,na,nb))
					{
						Str[i] = na+'0';
						Str[j] = nb+'0';
						return true;
					}
				}
			}
		}
	}
	return false;
}
int main()
{
	init();
	if (solve())
	{
		for (char *p=Str;*p!='#';p++)
			putchar(*p);
		printf("#n");
	}
	else
		printf("Non");
	return 0;
}
<h2><span class="mw-headline">木棒遊戲 </span></h2>

【問題描述】

這是一個很古老的遊戲。用木棒在桌上拼出一個不成立的等式,移動且只移動一根木棒使得等式成立。現在輪到你了。

<a class="image" title="Image:Stickgame1.gif" href="http://www.ruvtex.cn/wiki/Image:Stickgame1.gif"><img src="http://www.ruvtex.cn/mw/images/d/d9/Stickgame1.gif" alt="Image:Stickgame1.gif" width="556" height="122" /></a>

【任務】

從文件讀入一個式子(該式子肯定是一個不成立的等式)。

如果移動一根木棒可以使等式成立,則輸出新的等式,否則輸出No。

【說明和限制】
<ol>
    <li>式子中的數可能是正數或負數,運算符號只會出現加號和減號,並且有且僅有一個等號,不會出現括號、乘號或除號,也不會有++,--,+-或-+出現。</li>
    <li>式子中不會出現8個或8個以上的連續數字(數的絕對值小於等於9999999)。</li>
    <li>你只能移動用來構成數字的木棒,不能移動構成運算符(+、-、=)的木棒,所以加號、減號、等號是不會改變的。移動前後,木棒構成的數字必須嚴格與圖2中的0~9相符。</li>
    <li>從文件讀入的式子中的數不會以0開頭,但允許修改後等式中的數以數字0開頭。</li>
</ol>
<a class="image" title="Image:Stickgame2.gif" href="http://www.ruvtex.cn/wiki/Image:Stickgame2.gif"><img src="http://www.ruvtex.cn/mw/images/a/a5/Stickgame2.gif" alt="Image:Stickgame2.gif" width="556" height="122" /></a>

【輸入數據】

從文件中讀入一行字符串。該串中包括一個以“#”字符結尾的式子(ASCII碼35),式子中沒有空格或其他分隔符。輸入數據嚴格符合邏輯。字符串的長度小於等於1000。

注意:“#”字符後面可能會有一些與題目無關的字符。

【輸出數據】

將輸出結果存入文件,輸出僅一行。

如果有解,則輸出正確的等式,格式與輸入的格式相同(以“#”結尾,中間不能有分隔符,也不要加入多餘字符)。此時輸入數據保證解是唯一的。

如果無解,則輸出“No”(N大寫,o小寫)。

【輸入樣例1】

1+1=3#

【輸出樣例1】

1+1=2#

【輸入樣例2】

1+1=3+5#

【輸出樣例2】

No

【輸入樣例3】

11+77=34#

【輸出樣例3】

17+17=34#

上次修改時間 2017-05-22

相關日誌