uva-10400-搜索

　　题意：题意很简单,就是输入数字,对数字进行加减乘除,然后能不能得到最后的数字.

wa了很多次,memcpy(dst,src,sizeof(dst))才对,最后一个参数写错,最后一个参数是要拷贝的字节数目.

跑了5s多,这应该是我提交的代码运行最长的一次.

#include <string>

#include<iostream>

#include<map>

#include<memory.h>

#include<vector>

#include<algorithm>

#include<queue>

#include<vector>

#include<stack>

#include<math.h>

#include<iomanip>

#include<bitset>

#include"math.h"

namespace cc

{

    using std::cout;

    using std::endl;

    using std::cin;

    using std::map;

    using std::vector;

    using std::string;

    using std::sort;

    using std::priority_queue;

    using std::greater;

    using std::vector;

    using std::swap;

    using std::stack;

    using std::queue;

    using std::bitset;

    constexpr int N = ;

    constexpr int MAXN = ;

    constexpr int MINN = -;

     string NO = "NO EXPRESSION";

     constexpr int MAXP = ;

     int vis[MAXP][N];

     int n;

    int number[MAXP+];

     class  Node

     {

     public:

         int level;

         int curNum;

         int steps[MAXP+];

     };

     queue<Node>q;

     int flag = ;

     Node bfs()

     {

         while (!q.empty())

         {

             Node node = q.front();

             q.pop();

             int level = node.level;

             int curNum = node.curNum;

             int nextLevel = level+;

             int nextNum = ;

             for (int i=;i<;i++)

             {

                 if (i == )

                 {

                     //+

                     nextNum = number[nextLevel] + curNum;

                 }

                 else if (i == )

                 {

                     //-

                     nextNum = curNum - number[nextLevel];

                 }

                 else if (i == )

                 {

                     //*

                     nextNum = curNum * number[nextLevel];

                 }

                 else if (i==&&number[nextLevel]!=&&curNum % number[nextLevel] == )

                 {

                     // /

                     nextNum = curNum / number[nextLevel];

                 }

                 if (nextNum > MAXN || nextNum < MINN)

                     continue;

                 if (vis[nextLevel][nextNum + MAXN] == )

                     continue;

                 vis[nextLevel][nextNum + MAXN] = ;

                 Node newNode;

                 newNode.curNum = nextNum;

                 newNode.level = nextLevel;

                 memcpy(&(newNode.steps),&(node.steps),sizeof(node.steps));

                 newNode.steps[nextLevel] = i;

                 if (nextLevel == n - )

                 {

                     //final number

                     if (number[n-] == nextNum)

                     {

                         flag = ;

                         return newNode;

                     }

                     continue;

                 }

                 q.push(newNode);

             }

         }

         Node errorNode;

         errorNode.curNum = ;

         return errorNode;

     }

    void solve()

    {

        int cases;

        cin >> cases;

        while (cases--)

        {

            cin >> n;

            flag = ;

            while (!q.empty())

                q.pop();

            memset(vis,,sizeof(vis));

            n++;

            for (int i=;i<n;i++)

            {

                cin >> number[i];

            }

            if (n==)

            {

                if (number[] == number[])

                    cout << number[] << "=" << number[] << endl;

                else

                    cout << NO << endl;

                continue;

            }

            Node node;

            node.curNum = number[];

            node.level = ;

            node.steps[node.level] = -;

            q.push(node);

            node = bfs();

            if (flag == )

            {

                cout << NO << endl;

                continue;

            }

            cout << number[];

            for (int i=;i<n-;i++)

            {

                if (node.steps[i] == )

                    cout << "+";

                else if (node.steps[i] == )

                    cout << "-";

                else if (node.steps[i] == )

                    cout << "*";

                else

                    cout << "/";

                cout << number[i];

            }

            cout << "=" << number[n - ] << endl;

        }

    }

};

int main()

{

#ifndef ONLINE_JUDGE

    freopen("d://1.text", "r", stdin);

#endif // !ONLINE_JUDGE

    cc::solve();

    return ;

}