Solve

NOI2003木棒游戏

题目解答

我是使用朴素的方法做的(高深的我不会)，首先找到火柴棒间的对应关系，比如移动一根火柴可以将8变为0，等等，然后分为两种情况枚举：

  1. 本身变动
  2. 两个数字一起变动

当然这样枚举必定要TLE，所以先把整个式子提取出来(所以程序很长 ,其实后来我也有点看不懂了。。。)，这样变动数字进行计算的时候就不用每次把整个式子都算了

运行情况

NOI 2003

程序清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include<iostream>
#include<cstring>
#include<cctype>
using namespace std;

#define fin cin
#define fout cout

typedef long long int64;

char shizi[1001],fh[600],num[600][10];
bool rel1[10][10],rel2[10][10],rel3[10][10],fuh1=false,fuh2=false;
int64 cnum[600],cheng[10]={0,1,10,100,1000,10000,100000,1000000,10000000,100000000};
int len,f,mid1,tsz[1001][2];//tsz is the num's position.
inline bool check()
{
       int64 fl=cnum[1],fr=cnum[mid1];
       if(fuh1) fl=-fl;
       if(fuh2) fr=-fr;
       for(int i=2;i<=mid1-1;i++)
       {
         if(fh[i-1]=='+')
           fl+=cnum[i];
         else
           fl-=cnum[i];
       }
       for(int i=mid1;i<=len;i++)
       {
         if(i-1<=f)
         if(fh[i-1]=='+')
           fr+=cnum[i+1];
         else
           fr-=cnum[i+1];
       }
       if (fr==fl) 
           return true;
       return false;
}
inline int work()
{
       int64 temp=0,tj1=0,tem2=0,li=strlen(shizi),tj2=0,ttem2=0;
       char tem,ttem;
       //state 1
       for(int i=0;i<li;i++)
       if(isdigit(shizi[i]))
       {
           temp=shizi[i]-'0';
           for(int j=0;j<=9;j++)
           if(rel1[temp][j])
           {
             tem=num[tsz[i][0]][tsz[i][1]];
             num[tsz[i][0]][tsz[i][1]]=j+'0';
             tj1=strlen(num[tsz[i][0]]);
             tem2=cnum[tsz[i][0]];
             cnum[tsz[i][0]]=0;
             for(int k=0;k<tj1;k++)
               cnum[tsz[i][0]]+=(num[tsz[i][0]][k]-'0')*(cheng[tj1-k]);
             if(check()) 
             {
               shizi[i]=j+'0';
               fout<<shizi<<'#';
               return 0;
             }
             num[tsz[i][0]][tsz[i][1]]=tem;
             cnum[tsz[i][0]]=tem2;
           }
       }
       //state 2
       for(int i=0;i<li;i++)
       if(isdigit(shizi[i]))
         for(int j=1;j<li;j++)
         if((isdigit(shizi[j]))&&(i!=j))
         {
         for(int i1=0;i1<=9;i1++)
           if(rel2[shizi[i]-'0'][i1])
           for(int j1=0;j1<=9;j1++)
             if(rel3[shizi[j]-'0'][j1])
             {
             tem=num[tsz[i][0]][tsz[i][1]];
             num[tsz[i][0]][tsz[i][1]]=i1+'0';
             tj1=strlen(num[tsz[i][0]]);
             tem2=cnum[tsz[i][0]];
             cnum[tsz[i][0]]=0;
             for(int k=0;k<tj1;k++)
               cnum[tsz[i][0]]+=(num[tsz[i][0]][k]-'0')*(cheng[tj1-k]);
             ttem=num[tsz[j][0]][tsz[j][1]];
             num[tsz[j][0]][tsz[j][1]]=j1+'0';
             tj2=strlen(num[tsz[j][0]]);
             ttem2=cnum[tsz[j][0]];
             cnum[tsz[j][0]]=0;
             for(int k=0;k<tj2;k++)
               cnum[tsz[j][0]]+=(num[tsz[j][0]][k]-'0')*(cheng[tj2-k]);
             if(check()) 
             {
               shizi[i]=i1+'0';
               shizi[j]=j1+'0';
               fout<<shizi<<'#';
               return 0;
             }
             num[tsz[i][0]][tsz[i][1]]=tem;
             cnum[tsz[i][0]]=tem2;
             num[tsz[j][0]][tsz[j][1]]=ttem;
             if(tsz[i][0]!=tsz[j][0])//important
               cnum[tsz[j][0]]=ttem2; 
             }
         }
       //special
       fout<<"No";
}
inline void init();
int main()
{
    init();
    work();
    return 0;
}
inline void init()
{
       fin.getline(shizi,1000,'#');
       for(int i=0;i<=9;i++) 
         for(int j=0;j<=9;j++)
         {
           rel1[i][j]=false;
           rel2[i][j]=false;
           rel3[i][j]=false;
         }
    int i=0;
       while(i<strlen(shizi)) 
       {
         if(i!=0) i++;
         if((i==0)&&(!isdigit(shizi[0]))) 
         {
           fuh1=true;
           i++;
         }
         if(isdigit(shizi[i]))
         {
           int j=0;
           len++;
           while (isdigit(shizi[i]))
           {
             tsz[i][0]=len;
             tsz[i][1]=j;
             num[len][j]=shizi[i];
             i++;
             j++;
           }
           j=strlen(num[len]);
           for(int k=0;k<j;k++)
             cnum[len]+=(num[len][k]-'0')*(cheng[j-k]);
         }
         if(shizi[i]=='=') 
         {
           mid1=len+1;
           if(shizi[i+1]=='-') 
           {
             fuh2=true;
             i++;
           }
         }
           else 
           if(isgraph(shizi[i]))
                {
                  f++;
                  fh[f]=shizi[i];
                }
       }
       //state 1
       rel1[0][6]=true;rel1[6][0]=true;
       rel1[0][9]=true;rel1[9][0]=true;       
       rel1[9][6]=true;rel1[6][9]=true;
       rel1[3][2]=true;rel1[2][3]=true;
       rel1[3][5]=true;rel1[5][3]=true;
       //state 2
       rel2[0][8]=true;rel3[8][0]=true;
       rel2[9][8]=true;rel3[8][9]=true;
       rel2[6][8]=true;rel3[8][6]=true;
       rel2[5][6]=true;rel3[6][5]=true;
       rel2[1][7]=true;rel3[7][1]=true;
       rel2[3][9]=true;rel3[9][3]=true;
       rel2[5][9]=true;rel3[9][5]=true;
}

注意事项

注意优化。本题目只要稍加思索可以想到两种比较好的优化方式(均为数学分析优化)，不过以我现在的水平还不行，况且我对着比较bug的测试数据调了很长时间才把负数问题解决(测试数据的答案没有换行 (>-<)导致我一直以为我不对)，恳请大牛不吝赐教。

难易等级

Medium (NOI the 1st)