**题意:

     给你一个数字串,让你在里面添加一个=和若干个+,使等式成立.

思路:
**

lmax最大是15,直接暴搜,无压力,关键是判重,要在答案的时候判重,一开始在进队列之前判的,各种wa,哎!后来才发现如果在之前判断就不能得到当前什么符号都不加,而下一个有符号了,判重我用的是map,随意什么只要别爆内存就行,水搜索竟然调了2个小时,丢脸啊…

#include
#include
#include
#include

typedef struct
{
int** mk[16]; char str[16]; int nowid ,deng; }NODE;

NODE xin ,tou; int nn;
map<__int64 ,__int64>mark**;

bool** MK(NODE aa) { __int64 sum = 0; for(int i = 0 ;i <= nn ;i ++)
sum = sum * 10 + aa.mk[i]; if(mark[sum]) return 1;
mark[sum] = 1; return 0**;
}

bool** ok(NODE tou) { if(tou.deng) { int l ,r;
l = r = 0; int sum = 0; int mki; for(int i = 0 ;tou.mk[i] != 2 ;i ++) { if(tou.mk[i] == 1) {
l += sum;
sum = tou.str[i] - 48; } else {
sum = sum * 10 + tou.str[i] - 48; }
mki = i; }
l += sum;
sum = 0; for(int i = mki + 1;i <= nn ;i ++) { if(tou.mk[i] == 1) {
r += sum;
sum = tou.str[i] - 48; } else {
sum = sum * 10 + tou.str[i] - 48; } }
r += sum; return l == r && !MK(tou); } return 0**;
}

int** BFS() {
memset(xin.mk ,0 ,sizeof(xin.mk));
nn = strlen(xin.str) - 1;
xin.nowid = 0;
xin.deng = 0;
queue<NODE>q;
q.push(xin); int ans = 0;
mark.clear(); while(!q.empty()) {
tou = q.front();
q.pop(); if(ok(tou))
ans ++; if(tou.nowid == nn) continue; if(!tou.deng)// =
{
xin = tou;
xin.deng = 1;
xin.nowid = tou.nowid + 1;
xin.mk[xin.nowid] = 2;
q.push(xin); }

  //+  
  xin **=** tou**;**  
  xin**.**deng **=** tou**.**deng**;**  
  xin**.**nowid **=** tou**.**nowid **+** 1**;**  
  xin**.**mk**\[**xin**.**nowid**\] =** 1**;**  
  q**.**push**(**xin**);**

  //  
  xin **=** tou**;**  
  xin**.**deng **=** tou**.**deng**;**  
  xin**.**nowid **=** tou**.**nowid **+** 1**;**  
  xin**.**mk**\[**xin**.**nowid**\] =** 0**;**  
  q**.**push**(**xin**);  

}
return** ans**;
}

int main ()
{
while(~scanf(**"%s" *,xin.str) &&* strcmp("END" ,xin.str)) {
printf("%d\n" ,BFS()); } return 0; }