EOJ2859 表达式的个数

http://acm.cs.ecnu.edu.cn/problem.php?problemid=2859

简单dfs。但花了比较大的精力去处理不添加符号的情况，求出所有的情况复杂度大概是8*3^8，最后用map匹配完成

dfs遍历时存下添加符号的方法，到最终再计算处理会比较清晰。用hash可能更快。

 1 #include<map>
 2 #include<cmath>
 3 #include<queue>
 4 #include<cctype>
 5 #include<cstdio>
 6 #include<string>
 7 #include<cstdlib>
 8 #include<cstring>
 9 #include<iostream>
10 #include<algorithm>
11 using namespace std;
12 int op[10];
13 int n;
14 map<int,int> m;
15 int cal(){
16     int ans=1,t;
17     for(int i=1;i<=8;){
18         int j;
19         if(op[i])t=0;            
20         else t=1;                //对数字1后面无符号的特殊处理
21         for(j=i+1;j<=9;j++){
22             t=t*10+j;
23             if(op[j])break;
24         }
25         if(op[i])ans+=op[i]*t;
26         else ans=t;                //对数字1后面无符号的特殊处理
27         i=j;
28     }    
29     return ans;
30 }
31 void dfs(int depth){
32     if(depth==9){
33         op[depth]=1;    //为cal做准备（实际无意义）
34         int ans=cal();
35         m[ans]++;        //finished
36         return ;
37     }
38     for(int i=0;i<3;i++){
39         if(i==0)op[depth]=1;        //遍历三种方法，op的赋值方法完全是为了cal写起来方便
40         else if(i==1)op[depth]=-1;
41         else op[depth]=0;
42         dfs(depth+1);
43     }
44 }
45 int main(){
46     dfs(1);
47     while(scanf("%d",&n)!=EOF){
48         printf("%d\n",m[n]);
49     }
50     return 0;
51 }

View Code

hash 版本：

dfs思路清晰，代码略难看。

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <string>
  4 #include <string.h>
  5 #include <stdlib.h>
  6 #define M 7001
  7 #define MAX 0x3f3f3f3f
  8 using namespace std;
  9 typedef struct
 10 {
 11     int n, cnt, next;    
 12 }E;
 13 E edge[7000];
 14 int ie;
 15 int hash[7001];
 16 
 17 const int a[10] = {1,2,3,4,5,6,7,8,9};
 18 int sign;
 19 int sum;
 20 int ans;
 21 
 22 int search(int n)
 23 {
 24     int x = n%M;
 25     int p = hash[x];
 26     while(p)
 27     {
 28         if(edge[p].n == n)
 29             return p;
 30         p = edge[p].next;
 31     }
 32     return 0;
 33 }
 34 
 35 void add(int n)
 36 {
 37     int p;
 38     if(p = search(n))
 39         edge[p].cnt ++;
 40     else
 41     {
 42         int x = n%M;
 43         edge[ie].n = n;
 44         edge[ie].cnt = 1;
 45         edge[ie].next = hash[x];
 46         
 47         hash[x] = ie++;
 48     }
 49 }
 50 
 51 void dfs(int depth)    //dfs(depth)表示，符号加在a[depth]前。 
 52 {
 53     if(depth == 9)
 54     {
 55         ans += sign * sum;
 56         //printf("%d\n", ans);
 57         add(ans + MAX);        //散列。 
 58         ans -= sign * sum;
 59         return ;
 60     }
 61     int tsum = sum, tsign = sign;
 62     // +
 63     ans += sign * sum;
 64     sign = 1;
 65     sum = a[depth];
 66     dfs(depth+1);
 67     sign = tsign;
 68     sum = tsum;
 69     ans -= sign * sum;
 70     
 71     // -
 72     tsum = sum, tsign = sign;
 73     ans += sign * sum;
 74     sign = -1;
 75     sum = a[depth];
 76     dfs(depth+1);
 77     sign = tsign;
 78     sum = tsum;
 79     ans -= sign * sum;
 80     
 81     //不加符号
 82     tsum = sum;
 83     sum = sum*10 + a[depth];
 84     dfs(depth+1);
 85     sum = tsum;    
 86     
 87 }
 88 
 89 int main()
 90 {
 91     //freopen("testin.txt", "r", stdin);
 92     //freopen("testout.txt", "w", stdout);
 93     
 94     memset(hash, 0, sizeof(hash));
 95     ie = 1;
 96     sum = 1;
 97     ans = 0;
 98     sign = 1;
 99     dfs(1);
100     
101     int x;
102     while(scanf("%d", &x) != EOF)
103     {
104         int p;
105         if(p = search(MAX + x))
106             printf("%d\n", edge[p].cnt);
107         else
108             printf("0\n");
109     }    
110     return 0;
111 }

View Code