首页 > 搜索 > BFS搜索 > HDU 1868 Consecutive sum-Hash表-[解题报告] C++
2013
12-23

HDU 1868 Consecutive sum-Hash表-[解题报告] C++

Consecutive sum

问题描述 :

Every body knew that 15 = 1+2+3+4+5 = 4+5+6 = 7+8. Now give you a number N, tell me how many ways to represent N as a sum of consecutive positive integers. For example, 15 have 3 ways to be found.

输入:

Each line will contain an signed 32-bits integer N. Process to end of file.

输出:

For each case, output the answer in one line.

样例输入:

15
1050

样例输出:

3
11

据说这题的数据不是很强,直接bfs+hash判重即可过。

这里我打算拿它练习一下双广搜索。

用了两个队列,分别从始态和终态进行bfs。

队列中保存的是每一个状态,每一个状态是用一个一维数组保存的。

hash时,把它转化成一个9位的整数,质数取余,拉链法判重。

hash表开成两维的,分别储存两个队列的搜索结果,同时还保存搜到每一个状态所用的step。

每当向hash表的一维里插入新状态时,判断在另一维的这个位置是否已经访问到,如果已经访问到,则说明相遇了,输出两个step之和即为结果。

其实双广用一个队列也可以实现,注意把两种状态用标记区分开即可。

另外,这题还有两点有注意的地方:

1.如果初状态和末状态的逆序数的奇偶性不同,则无解,直接输出-1。证明方法网上有。

2.如果初状态与末状态一样,直接输出0。不要再用双广,双广的话输出结果会是2(显然)。

双广时,两个队列交替进行扩展,且每次要扩展一层(一圈一圈的向外扩展,直到两个圈相遇)。第一次相遇,获得的一定是最短的路径了。

代码如下:

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>

    #define PRIME 455809
    using namespace std;

    struct node
    {
        node(unsigned int t)
        {
            s=t;
            next=NULL;
        }
        unsigned int s;
        int step;
        node *next;
    };
    node *hashtable[460000][2];
    struct State
    {
        int map[10];
        int pos;
        int step;
    } states,statee;

    void hinsert(State s,bool ty)
    {
        unsigned int i,st=0;
        for(i=1; i<=9; i++)
            st=st*10+s.map[i];
        node *f=new node(st);
        f->step=s.step;
        f->next=hashtable[st%PRIME][ty];
        hashtable[st%PRIME][ty]=f;
    }
    bool exist(State s,bool ty,int &res)
    {
        unsigned int i,st=0;
        for(i=1; i<=9; i++)
            st=st*10+s.map[i];
        node *f=hashtable[st%PRIME][ty];
        while(f)
        {
            if(f->s==st)
            {
                res=f->step;
                return true;
            }
            f=f->next;
        }
        return false;
    }
    int transfer(State t,queue <State>&Q,bool ty)
    {
        State s;
        int res;
        s=t;
        if((s.pos-3)>0)
        {
            swap(s.map[s.pos],s.map[s.pos-3]);
            s.step++;
            s.pos-=3;
            if(exist(s,!ty,res))
            {
                return (s.step+res);
            }
            if(!exist(s,ty,res))
            {
                Q.push(s);
                hinsert(s,ty);
            }
        }
        s=t;
        if(s.pos+3<10)
        {
            swap(s.map[s.pos],s.map[s.pos+3]);
            s.step++;
            s.pos+=3;
            if(exist(s,!ty,res))
            {
                return (s.step+res);
            }
            if(!exist(s,ty,res))
            {
                Q.push(s);
                hinsert(s,ty);
            }
        }
        s=t;
        if((s.pos+1)%3!=1)
        {
            swap(s.map[s.pos],s.map[s.pos+1]);
            s.step++;
            s.pos+=1;
            if(exist(s,!ty,res))
            {
                return (s.step+res);
            }
            if(!exist(s,ty,res))
            {
                Q.push(s);
                hinsert(s,ty);
            }
        }
        s=t;
        if((s.pos-1)%3!=0)
        {
            swap(s.map[s.pos],s.map[s.pos-1]);
            s.step++;
            s.pos-=1;
            if(exist(s,!ty,res))
            {
                return (s.step+res);
            }
            if(!exist(s,ty,res))
            {
                Q.push(s);
                hinsert(s,ty);
            }
        }
        return 0;
    }

    queue<State>Qs;
    queue<State>Qe;
    int reversenum(State a)
    {
        int res=0;
        for(int i=1; i<=9; i++)
        {
            if(a.map[i]==0)continue;
            for(int j=i-1; j>=1; j--)
            {
                if(a.map[j]>a.map[i])res++;
            }
        }
        return res;
    }
    bool prejudge(State a,State b)
    {
        int t1=reversenum(states);
        int t2=reversenum(statee);
        if((t1+t2)%2!=0)
        {
            printf("-1\n");
            return true;
        }
        bool tflag=0;
        for(int i=1; i<=9; i++)
        {
            if(a.map[i]!=b.map[i])
            {
                tflag=1;
                break;
            }
        }
        if(!tflag)
        {
            printf("0\n");
            return true;
        }
        else return false;
    }
    int main()
    {
        int tcases;
        scanf("%d",&tcases);
        while(tcases--)
        {
            memset(hashtable,0,sizeof(hashtable));
            for(int i=1; i<=9; i++)
            {
                scanf("%d",&states.map[i]);
                if(states.map[i]==0)states.pos=i;
            }
            statee.step=0;
            for(int i=1; i<=9; i++)
            {
                scanf("%d",&statee.map[i]);
                if(statee.map[i]==0)statee.pos=i;
            }
            states.step=0;

            hinsert(states,0);
            hinsert(statee,1);
            if(prejudge(states,statee))continue;

            bool endflag=0;
            while(!Qs.empty())Qs.pop();
            while(!Qe.empty())Qe.pop();
            Qs.push(states);
            Qe.push(statee);
            while(!Qs.empty()||!Qe.empty())
            {
                int ns=Qs.size(); //这个是处于同一层的状态的数量
                int ne=Qe.size();
                if(ns<ne||ne==0) //选择元素个数较少的队列进行扩展
                {
                    for(int i=0; i<ns; i++)//扩展s队列。一次扩展一层,这是双广正确性(得到最优解)的重要保证
                    {
                        State cur;
                        cur=Qs.front();
                        Qs.pop();
                        int res=transfer(cur,Qs,0);
                        if(res)
                        {
                            printf("%d\n",res);
                            endflag=1;
                            break;
                        }
                    }
                }
                else
                {
                    for(int i=0; i<ne; i++)
                    {
                        State cur;
                        cur=Qe.front();
                        Qe.pop();
                        int res=transfer(cur,Qe,1);
                        if(res)
                        {
                            printf("%d\n",res);
                            endflag=1;
                            break;
                        }
                    }
                }
                if(endflag)break;
            }
        }
        return 0;
    }

解题报告转自:http://blog.csdn.net/zhuang19922011/article/details/8520862


,
  1. This write-up presents the gentle in which we can notice the fact. this is extremely wonderful one and gives in depth info.

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。