【NOIP1998】 三連擊 題解
文章轉載前需和原作者聯繫，否則追究法律責任
題目鏈接：//www.luogu.com.cn/problem/P1008
首先我們來分析一下題目。要求是枚舉三個數，比例為1:2:3，且各個數字由1-9組成。
我們採用枚舉的方式來進行這道題目。首先，數字滿足兩個條件（比例為1:2:3，且各個數字由1-9組成），我們只需要枚舉其中的一種條件，然後判斷第二種條件是否滿足即可。
舉例：枚舉數字比例1:2:3，然後進行判斷數位是否由1-9組成。程式碼框架：
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
for(int a=123;a<=333;a++){
b=2*a;c=3*a;
...
cout<<a<<' '<<b<<' '<<c<<endl;
}
}
最重要的是來判斷各個數位是否由1-9組成。此時，我們可以使用一個函數，叫做sprintf。
我們知道，printf函數可以向標準輸出輸出內容，例如：
假設a=2
printf("a=%d",a);
此時標準輸出會顯示：a=2
sprintf的用法和printf類似，因此，我們如果這樣寫：
sprintf(s,"a=%d",a);
如果s是一個C風格字元串，那麼s字元串將會變為：「a=2」。
是否發現了什麼？如果我們這樣寫：
sprintf(s,"%d%d%d",a,b,c);
那麼，如果a=123，b=456，c=789，那麼s將會變為：「123456789」。事實上，sprintf經常用於把數字轉為字元串。
這樣，我們把三個數連在了一起，這樣就可以從s[0]枚舉到s[9]，枚舉各個數字出現的個數即可。
完整程式碼如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
for(int a=123;a<=333;a++){
b=2*a;c=3*a;
char s[10];
sprintf(s,"%d%d%d",a,b,c);
int flag[10];
memset(flag,0,sizeof(flag));
for(int i=0;i<9;i++)
flag[s[i]-'0']++;//統計數字的個數
for(int i=1;i<=9;i++){
if(flag[i]!=1)goto next;//出現次數不為1則跳過
}
cout<<a<<' '<<b<<' '<<c<<endl;
next:
continue;
}
}
至於另一種解法，也就是只枚舉1-9的全排列，然後分段輸出三位數，這裡也簡單闡述一下。
枚舉全排列可以使用遞歸搜索的方法，框架大家都應該很清楚，我也不寫了。當然，也可以使用STL演算法庫的next_permutation函數，進行全排列的計算。
我們把全排列計算出後，就把9位分為三段，判斷比例是否為1:2:3。
程式碼如下：（使用next_permutation計算全排列）
註：總枚舉次數為9的階乘，也就是362880
#include<bits/stdc++.h>
using namespace std;
int s[9]={1,2,3,4,5,6,7,8,9};
int main(){
for(int i=0;i<362880;i++){
int a=s[0]*100+s[1]*10+s[2];
int b=s[3]*100+s[4]*10+s[5];
int c=s[6]*100+s[7]*10+s[8];
if((b==2*a) && (c==3*a)){
printf("%d %d %d\n",a,b,c);
}
next_permutation(s,s+9);
}
return 0;
}
