带分数
题目 带分数
思路分析
这是第4届倒数第二题 可以纯暴力写（暴力杯名不虚传）
枚举出1~9的全排列 再枚举各个全排列在abc的划分
123456789 是全排列的一种
要把它枚举出 a:1 b:2 c:3456789 ……这样的各种情况 用双指针 i左边a ij中间b j右边c
纯暴力
首先全排列问题可以用第二题的递归写 也可以next_permutation
结果递归3270ms stl3272ms 可见以后全排列问题就用stl自带算法了
把单词记住 permutation 变化组合 / 排列
y总提供了一种优化
https://www.acwing.com/solution/content/38879/
其实可以说成是递归套上递归 先递归出a的答案（在叶子结点） 然后在a的叶子结点处递归出c的所有答案 最后看枚举出的ac是否与b满足一些关系
代码实现
3270 ms
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int num[N];
bool used[N];
int target;
int res;
int calc(int l,int r){
int ans=0;
for(int i=l;i<=r;i++)
ans=ans*10+num[i];
return ans;
}
void dfs(int u){
if(u==10){
//a最少占1位 最多占7位（bc至少各一位）
for(int i=1;i<=7;i++){
//ij中间是b b最少是第二位 最多是第8位（给ac各留一位）
for(int j=i+1;j<=8;j++){
int a=calc(1,i);
int b=calc(i+1,j);
int c=calc(j+1,9);
if(a*c+b==c*target){
res++;
}
}
}
return;
}
//全排列
for(int i=1;i<=9;i++){
if(!used[i]){
used[i]=true;
num[u]=i;
dfs(u+1);
used[i]=false;
}
}
}
int main()
{
cin>>target;
dfs(1);
cout<<res<<endl;
return 0;
}
3272 ms
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int num[N];
int target;
int calc(int l,int r){
int ans=0;
for(int i=l;i<=r;i++)
ans=ans*10+num[i];
return ans;
}
int main()
{
cin>>target;
for(int i=1;i<=9;i++)
num[i]=i;
int res=0;
do{
for(int i=1;i<=7;i++)
{
//ij中间是b b最少是第二位 最多是第8位（给ac各留一位）
for(int j=i+1;j<=8;j++)
{
int a=calc(1,i);
int b=calc(i+1,j);
int c=calc(j+1,9);
if(a*c+b==c*target)
res++;
}
}
}while(next_permutation(num+1,num+1+9));
cout<<res<<endl;
return 0;
}
1179 ms
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int had_use[N],ever[N];
int ans=0;
int n;
bool check(int a,int c)
{
int b = n * c - a * c;//把公式整理一下，然后先把b计算出来
if(!a || !b || !c)
return false;
//因为我们要对这个判断是否出现的数组进行修改，但是原数组又不能变化，所以我们额外开一个数组进行使用，这样就可以达到判断且不会改变原数组的目的
memcpy(ever,had_use,sizeof had_use);
while(b)
{
int t=b%10;//取它的每一位，用来更新一下用过的数字
b/=10;//删掉这个已经被选中的数
if(!t || ever[t])
return false;
ever[t]=1;
}
for(int i=1;i<=9;i++)//遍历一下，判断每个数
if(!ever[i])
return false;
return true;
}
void dfs_c(int x,int a,int c)//x表示我们已经用了多少个数字
{
if(x>=10)
return;//如果我们把10个数字都用了的话，那就直接return了
if(check(a,c))
ans++;//如果满足要求，那我们判断一下a,c是否符合题目要求，如果符合，那么答案++
for(int i=1;i<=9;i++)//否则的话我们把c从1到9全部枚举一遍
{
if(!had_use[i])
{
had_use[i]=1;
dfs_c(x+1,a,c*10+i);//如果这个数没用过，那么我们就把它放在c的后面,继续dfs下一层
had_use[i]=0;
}
}
}
void dfs_a(int x,int a)
{
if(a>=n)
return;
if(a)
dfs_c(x,a,0);//如果说a是满足情况的，那么我们就枚举一下c,后面那个0表示c的大小
for(int i=1;i<=9;i++)//枚举一下当前这个位置可以用哪些数字
if(!had_use[i])
{
had_use[i]=1;
dfs_a(x+1,a*10+i); //如果这个数没有被用过，那么我们就加上它，并且dfs下一层
had_use[i]=0;//恢复现场，回溯一下
}
}
int main()
{
cin>>n;
dfs_a(0,0);//第一个0表示我们已经用了多少个数字,后面那个0表示我们当前的a是多少
cout<<ans;
return 0;
}
💬 评论