暴力枚举
算是我觉得相当简洁的一段代码了,思路简单好懂:
首先我们可以知道我们设要求的目标是target, 目标是找到三个数,使得target=a+b/c,可以考虑使用暴力解法
我是利用了next_permutation函数,将1~9的全排列给一个个搜出来,然后每次找到一种排列,就利用二重循环将该段排列分成三段,第一段得到a,第二段得到b,第三段得到c,然后进行判断即可
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10;
int cnt=0;
int num[9]={1,2,3,4,5,6,7,8,9};
int cal(int i,int j)
{
int res=0;
for(int k = i+1 ; k<=j ; k++)
{
res=res*10+num[k];
}
return res;
}
// 设target = a+b/c,
int main()
{
int target;
cin>>target;
// 枚举1~9的所有情况
do
{
for(int i = 0 ; i<9 ; i++) // 二重循环枚举组合
{
for(int j = i+1 ; j<9 ; j++)
{
int a = cal(-1,i);
int b = cal(i,j);
int c = cal(j,8);
if(target*c==a*c+b)cnt++; // 注意,由于c++是整除运算,因此我们用乘法来替代除法
}
}
}while(next_permutation(num,num+9));
cout<<cnt<<endl;
return 0;
}
第一次写题解,嘿嘿
佬太强了
大佬我也是这样写的,只不过是手搓的全排列,不知道为啥wa,能帮我看看吗?
我找到bug了,主要是你的cal函数写错了,你改成这样就ac了
怎么样,解决了吗
okok,谢谢大佬
你的dfsabc里面i不应该到7吗
我喜欢暴力解决此题
tql
挺好的 点赞
orz
太强了
点个赞
是真暴力,nb
大佬,可以讲讲这段代码的含义吗?没怎么看懂
将数组切成了三段,然后要将这三段组合成三个数字,这个函数就是将Num里的某段转换成一个数字
计算abc值的函数,传入两个隔板,隔板将数组分为三段,对应abc
每一段从i+1开始,到j结束