/*
這個代碼運行的時間長主要是因為每次枚舉之后都要重新計算一下和的值！
如果要快的話，應該在dfs，也就是枚舉的過程中計算出前邊的數值（這種方法見第二個代碼），直到最后，這樣不必每一次枚舉都要從頭再算一遍值！
*/
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 7 char ch[20]; 8 char sign[3]={'+', '-', '.'}; 9 int n, cnt; 10 int num[20]; 11 int signNum[200]; 12 13 void dfs(int u){ 14 if(u==n){ 15 if(signNum['+']==n-1 || signNum['+']+signNum['.']==n-1 || signNum['.']==n-1 || signNum['-']==n-1) return; 16 for(int i=1; i<n; ++i){ 17 num[i]=i; 18 if(ch[i]=='.'){ 19 int s=i, v=i; 20 while(i<n && ch[i]=='.'){ 21 if(i+1>9) 22 s=s*100+(++i); 23 else s=s*10+(++i); 24 } 25 if(s>10000) return ;//非得加上這句話....然后就幸運的過了！ 26 num[v]=s; 27 --i; 28 } 29 } 30 num[n]=n; 31 int s=num[1]; 32 for(int i=1; i<n; ++i) 33 if(ch[i]!='.'){ 34 if(ch[i]=='+') s+=num[i+1]; 35 else s-=num[i+1]; 36 } 37 if(s==0){ 38 ++cnt; 39 if(cnt<=20){ 40 for(int i=1; i<n; ++i) 41 printf("%d %c ", i, ch[i]); 42 printf("%d\n", n); 43 } 44 } 45 return; 46 } 47 for(int i=0; i<3; ++i){ 48 ch[u]=sign[i]; 49 ++signNum[sign[i]]; 50 dfs(u+1); 51 --signNum[sign[i]]; 52 } 53 } 54 55 int main(){ 56 while(scanf("%d", &n)!=EOF){ 57 cnt=0; 58 dfs(1); 59 printf("%d\n", cnt); 60 } 61 return 0; 62 }
?
/*
清晰的思路，清晰的代碼.....T^T!
*/
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 char sign[3]={'+', '-', '.'}; 7 int n, cnt; 8 char ch[20]; 9 int dir[2]={10, 100}; 10 11 12 //pre記錄的是'+' 或者是 '-'的左邊的運算值， nowI記錄的是其右邊的值 13 void dfs(char chPre, int pre, int nowI, int cur){ 14 if(cur==n){ 15 int s=-1; 16 if(chPre=='+') 17 s=pre+(nowI*dir[cur/10]+cur); 18 else if(chPre=='-') 19 s=pre-(nowI*dir[cur/10]+cur); 20 //如果chPre=='.' 說明整個式子中不存在運算符號+或者-， 那最終的結果一定不是0 21 if(s==0){ 22 ++cnt; 23 if(cnt<=20){ 24 for(int i=1; i<n; ++i) 25 printf("%d %c ", i, ch[i]); 26 printf("%d\n", n); 27 } 28 } 29 return ; 30 } 31 for(int i=0; i<3; ++i){ 32 ch[cur]=sign[i]; 33 if(ch[cur]!='.'){ 34 if(chPre=='+') 35 dfs(ch[cur], pre+(nowI*dir[cur/10]+cur), 0, cur+1); 36 else if(chPre=='-') 37 dfs(ch[cur], pre-(nowI*dir[cur/10]+cur), 0, cur+1); 38 else dfs(ch[cur], pre*dir[cur/10]+cur, 0, cur+1); 39 } 40 else{ 41 //之前出現了運算符，當前不是運算符 42 if(chPre=='+' || chPre=='-')//一直累計nowI的值 43 dfs(chPre, pre, nowI*dir[cur/10]+cur, cur+1); 44 else //如果之前沒有出現過運算符+或者-，一直累計pre的值 45 dfs(chPre, pre*dir[cur/10]+cur, 0, cur+1); 46 } 47 } 48 } 49 50 int main(){ 51 while(scanf("%d", &n)!=EOF){ 52 cnt=0; 53 dfs(' ', 0, 0, 1); 54 printf("%d\n", cnt); 55 } 56 return 0; 57 }
?
