题目描述

将 $1, 2,\ldots, 9$ 共 $9$ 个数分成三组，分别组成三个三位数，且使这三个三位数的比例是 $A:B:C$，试求出所有满足条件的三个三位数，若无解，输出 No!!!。

//感谢黄小U饮品完善题意

输入格式

三个数，$A,B,C$。

输出格式

若干行，每行 $3$ 个数字。按照每行第一个数字升序排列。

样例 #1

样例输入 #1

1 2 3

样例输出 #1

192 384 576
219 438 657
273 546 819
327 654 981

提示

保证 $A

$\text{upd 2022.8.3}$：新增加二组 Hack 数据。

题解

关于三连击这道题目；

这里有三种解法

从经典的解法中套用模板：

#include
#include
void swap(char *a,char *b)
{char temp;temp = *a;*a = *b;*b = temp;	
}void  Allarrange(char *str,int k,int len)
{int i;if(k==len){static int s_i=1;printf("第%d种排列为:\t%s\n",s_i++,str);}else{for(i=k;i<=len;i++){swap(str+i,str+k);Allarrange(str,k+1,len);swap(str+i,str+k);}}
}int main()
{char str[10];printf("请输入排列的字符串："); gets(str);Allarrange(str,0,strlen(str)-1);return 0;
}

1. 回溯法；直接排列枚举；

#include
#include
using namespace std;
int cho[1000];
int used[1000];
int a,b,c;
bool ans=false;
int cons(int x){ //分成三份； 
int sum=0;
for(int i=3*x-2,j=2;i<=3*x;i++,j--){sum+=pow(10,j)*cho[i];
}
return sum;
}
void swap(int *a,int *b){int temp=*a;*a=*b;*b=temp;
}
void choice(int n){if(n==10&&cons(1)*b==cons(2)*a&&cons(2)*c==cons(3)*b){  //出口； cout<>a>>b>>c;for(int i=1;i<=9;i++)cho[i]=i;choice(1);if(!ans)cout<<"No!!!";return 0;

void choice(int n){if(n==10&&cons(1)*b==cons(2)*a&&cons(2)*c==cons(3)*b){  //出口； cout<

主要是交换位置；

2. 也是回溯法，变换一下形式；

void choice(int n){if(n==10&&cons(1)*b==cons(2)*a&&cons(2)*c==cons(3)*b){  //出口； cout<

同上；

3. next_permutation方法；

最简单的方法；

int main(){int a,b,c;cin>>a>>b>>c;for(int i=0;i<9;i++)s[i]=i+1;int t=0;do{
//	printf("%d %d %d\n",cons(1),cons(2),cons(3));if(cons(1)*b==cons(2)*a&&cons(2)*c==cons(3)*b){cout<

综上；是我关于初学排列枚举的一点收获：

4. 回溯可以解决绝大部分问题；

一般是从1->2.....->n;然后回栈；

5. for(int i=n;i<=9;i++){ swap(cho+i,cho+n); choice(n+1); swap(cho+i,cho+n); }

6. for(int i=1;i<=9;i++){ if(!used[i]){ cho[n]=i; used[i]=1; choice(n+1); used[i]=0; }

7. 递归的代码不理解很正常，先记下再说吧；