首页 > 搜索 > DFS搜索 > HDU 3325-Arithmetically Challenged-DFS-[解题报告]HOJ
2014
03-16

HDU 3325-Arithmetically Challenged-DFS-[解题报告]HOJ

Arithmetically Challenged

问题描述 :

Challenge 24 is a popular mathematics game used in many grade schools. In each game, contestants are given a card with four positive integers i1, i2, i3, i4 on it, and the first one who can use all of these numbers and any combination of the four basic arithmetic operations to get 24 wins. Each of the numbers i1, i2, i3, i4 must be used exactly once. Division can be used only if the divisor evenly divides the dividend (i.e., you can perform 6/2 but not 6/4). For example, if the card contains the numbers 7, 2, 5 and 1, possible solutions are (7-2)*5-1 or (7+1)*(5-2). Hmmm . . . this sounds like a source of a good programming problem.

Write a program that determines the longest consecutive sequence of integers that can be obtained by different ways of arithmetically combining the four integers. For example, with 7, 2, 5 and 1 the longest consecutive sequence is -18 to 26 (yes, we’re allowing final results to be negative). The "+" and "-" operators must be used as binary operators, not as unary signs.

输入:

Each test case will consist of a single line containing the four, not necessarily distinct, positive integers, none of which will exceed 100. A line containing four 0’s will terminate input.

输出:

Each test case will consist of a single line containing the four, not necessarily distinct, positive integers, none of which will exceed 100. A line containing four 0’s will terminate input.

样例输入:

7 2 5 1
8 15 38 3
0 0 0 0

样例输出:

Case 1: -18 to 26
Case 2: 150 to 153

#include<iostream>
 #include<stdio.h>
 #include<math.h>
 #include<algorithm>
 #include<string.h>
 #include<string>
 #include<ctime>
 #include<queue>
 #include<list>
 #include<map>
 #include<set>
 #define INF 999999999
 #define MAXN 100000
 using namespace std;
 int b[10],mark[10],a[10],arr[MAXN+1],pos;
 set<int> ss;
 
 //针对6种运算情况进行计算
 int fenjie(int a,int b,int p)
 {
     if(p==0)
         return a+b;
     else if(p==1)
         return a-b;
     else if(p==5)
         return a*b;
     else if(p==3)
     {
         if(!b||a%b!=0)
             return INF;    //当遇到除法则先判断除数是否为0,这是必要的,不然会RE
         return a/b;
     }
     else if(p==4)
     {
         if(!a||b%a!=0)
             return INF;    //同上
         return b/a;
     }
     else if(p==2)
         return b-a;
 }
 
 void baoli()
 {
     int i,j,k,temp2,sum1,sum2,sum3;
     for(i=0;i<6;i++)
     {
         if((sum1=fenjie(a[b[0]],a[b[1]],i))==INF)   //1.非法时候进行处理
             continue;
         for(j=0;j<6;j++)
         {
             if((sum2=fenjie(sum1,a[b[2]],j))==INF)  //2
                 continue;
             for(k=0;k<6;k++)
             {
                 if((sum3=fenjie(sum2,a[b[3]],k))!=INF)  //3
                     ss.insert(sum3);
                 //1 2 3 是对前6种可能得暴力枚举
                 
                 //最后一种([email protected])@([email protected])的处理
                 if((temp2=fenjie(a[b[2]],a[b[3]],k))==INF)
                     continue;
                 if((sum3=fenjie(sum1,temp2,j))==INF)
                     continue;
                 ss.insert(sum3);
             }
         }
     }
 }
 
 //dfs对数组进行全排列
 void dfs(int s)   
 {
     int i;
     if(s>=4)
     {
         baoli();
     }
     else
     {
         for(i=0;i<4;i++)
         {
             if(!mark[i])
             {
                 mark[i]=1;
                 b[s]=i;
                 dfs(s+1);
                 mark[i]=0;
             }
         }
     }
 }
 int main()
 {
     int sb=1;
     while(~scanf("%d%d%d%d",&a[0],&a[1],&a[2],&a[3]))
     {
         if(a[0]+a[1]+a[2]+a[3]==0)
             break;
         int i;
         memset(mark,0,sizeof(mark));
         pos=0;
         ss.clear();
         dfs(0);
         while(!ss.empty())
         {
             arr[pos++]= * ss.begin();
             ss.erase(ss.begin());
         }
         int maks=0,cnt=0,ed=0;
         for(i=1;i<pos;i++)
         {
             if(arr[i]==arr[i-1]+1)
                 cnt++;
             else
                 cnt=0;
             if(maks<=cnt)
             {
                 maks=cnt;
                 ed=arr[i];
             }
         }
         printf("Case %d: %d to %d\n",sb++,ed-maks,ed);
     }
     return 0;
 }

参考:http://www.cnblogs.com/crazyapple/archive/2013/04/08/3008726.html


,
  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  3. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  4. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧