This post is written in Chinese. Please consider using Google Translate

移动一根火柴可以分为两种情况：一是移动某一个数字上的一根火柴，使之变为另一个数字。二是两个数字，一个添加一根火柴，一个减少一根火柴。我们可以首先算出等式两边的代数和，然后枚举改变。每次改变后只需算出与原来数的差值，就可以在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#