洛谷 P1092 虫食算

题目链接 https://www.luogu.org/problemnew/show/P1092

已经是第三遍做了，终于记住搜索的方法了。

思路就是从低位向高位搜索，如果多于1个数未知，就枚举，1个数未知就算出来，全部已知就检查是否满足加法。

这样裸搜应该能拿到90分，接下来考虑剪枝。

每填完一位检查高位，如果三个数都已知，那么如果在无论有无进位的情况下都不能成立，则是不成立的情况。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 using namespace std;
  5 bool flg,b[33];
  6 int n,a[30],s[4][30];
  7 
  8 void dfs(int pos,int jin)//ËÑË÷µ½posÎ»£¬ÓÐjinµÄ½øÎ» 
  9 {
 10     if(flg)
 11         return ;
 12     
 13     if(pos<0&&jin==0)
 14     {
 15         flg=1;
 16         for(int i=0;i<n;i++)
 17         {
 18             printf("%d",a[i]);
 19             if(i==n-1)
 20                 printf("
");
 21             else
 22                 printf(" ");
 23         }
 24         return ;
 25     }
 26     
 27     int cnt=0;
 28     for(int i=1;i<=3;i++)
 29         if(a[s[i][pos]]==-1)
 30             cnt++;
 31     
 32     if(cnt==0)
 33     {
 34         for(int i=pos-1;i>=0;i--)
 35         {
 36             int ct=0;
 37             for(int j=1;j<=3;j++)
 38                 if(a[s[j][i]]==-1)
 39                     ct++;
 40             if(ct==0)
 41             {
 42                 int tmp=a[s[1][i]]+a[s[2][i]];
 43                 if(tmp%n!=a[s[3][i]]&&(tmp+1)%n!=a[s[3][i]])
 44                     return ;
 45             }
 46         }
 47         int tmp=a[s[1][pos]]+a[s[2][pos]]+jin;
 48         if(tmp%n==a[s[3][pos]])
 49             dfs(pos-1,tmp/n);
 50     }
 51     
 52     else if(cnt==1)
 53     {
 54         if(a[s[1][pos]]==-1)
 55         {
 56             int tmp=a[s[3][pos]]-jin-a[s[2][pos]];
 57             if(tmp>=0&&tmp<n)
 58                 a[s[1][pos]]=tmp;
 59             else
 60                 a[s[1][pos]]=tmp+n;
 61             if(!b[a[s[1][pos]]])
 62             {
 63                 b[a[s[1][pos]]]=1;
 64                 dfs(pos,jin);
 65                 b[a[s[1][pos]]]=0;
 66             }
 67             a[s[1][pos]]=-1;
 68         }
 69         else if(a[s[2][pos]]==-1)
 70         {
 71             int tmp=a[s[3][pos]]-jin-a[s[1][pos]];
 72             if(tmp>=0&&tmp<n)
 73                 a[s[2][pos]]=tmp;
 74             else
 75                 a[s[2][pos]]=tmp+n;
 76             if(!b[a[s[2][pos]]])
 77             {
 78                 b[a[s[2][pos]]]=1;
 79                 dfs(pos,jin);
 80                 b[a[s[2][pos]]]=0;
 81             }
 82             a[s[2][pos]]=-1;
 83         }
 84         else
 85         {
 86             int tmp=a[s[1][pos]]+a[s[2][pos]]+jin;
 87             if(tmp>=0&&tmp<n)
 88                 a[s[3][pos]]=tmp;
 89             else
 90                 a[s[3][pos]]=tmp-n;
 91             if(!b[a[s[3][pos]]])
 92             {
 93                 b[a[s[3][pos]]]=1;
 94                 dfs(pos,jin);
 95                 b[a[s[3][pos]]]=0;
 96             }
 97             a[s[3][pos]]=-1;
 98         }
 99     }
100     
101     else
102     {
103         for(int i=1;i<=3;i++)
104             if(a[s[i][pos]]==-1)
105             {
106                 for(int j=n-1;j>=0;j--)
107                     if(!b[j])
108                     {
109                         a[s[i][pos]]=j,b[j]=1;
110                         dfs(pos,jin);
111                         a[s[i][pos]]=-1,b[j]=0;
112                     }
113                 break;
114             }
115     }
116 }
117 
118 int main()
119 {
120     scanf("%d",&n);
121     for(int i=1;i<=3;i++)
122     {
123         char ch[33];
124         scanf("%s",ch);
125         for(int j=0;j<n;j++)
126             s[i][j]=ch[j]-'A';
127     }
128     memset(a,-1,sizeof(a));
129     
130     dfs(n-1,0);
131     return 0;
132 }

View Code