uva-10400-搜索
2024-08-31 08:02:44
题意:题意很简单,就是输入数字,对数字进行加减乘除,然后能不能得到最后的数字.
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 ;
}
最新文章
- IIS中启用ASP并连接Access数据库的解决办法
- ThinkPHP真正疑难问题笔记
- 【剑指offer】出现次数超过一半的数字
- [Ajax系列]Ajax介绍
- php5调用web service
- 应用python编写简单新浪微博应用(一)
- Android线程消息通信(一)
- css3 web字体记
- Balsamiq Mockups
- python装饰实现线程同步
- 不用jquery等框架实现ajax无刷新登录
- 201521123008《Java程序设计》第10周学习总结
- 《Python网络编程》学习笔记--使用谷歌地理编码API获取一个JSON文档
- vue 开发环境搭建
- Electorn(桌面应用)自动化测试之Java+selenium实战例子
- python基础自学 第一天
- Python实现工厂模式
- git push 和 pull 时 免密执行的方法
- R read.table 一个问题的解决
- Kangax 的 ES7 兼容性表格