https://ac.nowcoder.com/acm/contest/11254/F
一道标准的搜索题。
注意题目有坑点,其他按照搜索即可。
我的写法中包含两层搜索+精度的控制。
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <stack>
#include <algorithm>
#include <map>
#include <stdio.h>
using namespace std;
struct node
{
vector<int>line;
};
vector<node>ans;
stack<int>tmp;
double mm;
int aaaa =0 ;
void dfsans(vector<double> &now,int chu)
{
if(now.size()==1&&abs(now[0]-mm)<0.00001&&chu>0) {aaaa++;return ;}
if(now.size()==1&&abs(now[0]-mm)<0.00001) {aaaa=-1000000;return ;}
if(now.size()==1) return ;
vector<double> nex;
for (size_t i = 0; i < now.size()-1; i++)
{
nex.push_back(now[i]);
}
int t;
for (size_t i = 0; i < now.size() && aaaa >=0 ; i++)
{
for (size_t j = 0; j < now.size() && aaaa >=0; j++)
{
if (i==j)
{
continue;
}
nex[0] = now[i] + now[j];t=1;
for (size_t k = 0; k < now.size(); k++)
{
if (k!=i && k!=j)
{
nex[t] =now[k];
t ++;
}
}
dfsans(nex,chu);
nex[0] = now[i] - now[j];
dfsans(nex,chu);
nex[0] = now[i] * now[j];
dfsans(nex,chu);
if(now[j] !=0 )
{
nex[0] = now[i] / now[j];
int a = now[i];
int b = now[j];
if( a==now[i] && b==now[j] && (a%b!=0) )
dfsans(nex,chu+1);
else
dfsans(nex,chu);
}
}
}
return ;
}
void findans()
{
vector<double>compute;
stack<int> ttmp = tmp;
while (ttmp.size()>0)
{
compute.push_back(ttmp.top());
ttmp.pop();
}
aaaa =0 ;
dfsans(compute,0);
if(aaaa>0)
{
ttmp = tmp;
struct node ansline;
while (ttmp.size()>0)
{
ansline.line.push_back(ttmp.top());
ttmp.pop();
}
sort(ansline.line.begin(),ansline.line.end());
ans.push_back(ansline);
}
}
void dfs(int step)
{
if(step==0)
{
findans();
return;
}
for (size_t i = 1; i <= 13; i++)
{
tmp.push(i);
dfs(step-1);
tmp.pop();
}
}
bool cmp(node &a,node &b)
{
for (size_t i = 0; i < a.line.size(); i++)
{
if(a.line[i]<b.line[i]) return true;
if(a.line[i]>b.line[i]) return false;
}
return true;
}
int main()
{
int n,m,i,j,k,l;
scanf("%d",&n);
scanf("%d",&m);
mm = m;
dfs(n);
j=0;
map<int,bool>maps;
for (size_t i = 0; i < ans.size(); i++)
{
k=0;
for (size_t j = 0; j < ans[i].line.size(); j++)
{
k*=13;
k+=ans[i].line[j];
}
if(maps[k] == 0)
j++;
maps[k] =1;
}
printf("%lu\n",maps.size());
for (size_t i = 0; i < ans.size(); i++)
{
k=0;
for (size_t j = 0; j < ans[i].line.size(); j++)
{
k*=13;
k+=ans[i].line[j];
}
if(maps[k] == 0)
continue;
maps[k] = 0 ;
for (size_t j = 0; j < ans[i].line.size(); j++)
{
printf("%d ",ans[i].line[j]);
}
printf("\n");
}
return 0;
}```