[NOIP2004 普及組] 火星人
題目描述
人類終于登上了火星的土地并且見到了神秘的火星人。人類和火星人都無法理解對方的語言，但是我們的科學(xué)家發(fā)明了一種用數(shù)字交流的方法。這種交流方法是這樣的，首先，火星人把一個非常大的數(shù)字告訴人類科學(xué)家，科學(xué)家破解這個數(shù)字的含義后，再把一個很小的數(shù)字加到這個大數(shù)上面，把結(jié)果告訴火星人，作為人類的回答。
火星人用一種非常簡單的方式來表示數(shù)字――掰手指。火星人只有一只手，但這只手上有成千上萬的手指，這些手指排成一列，分別編號為 1 , 2 , 3 , ? 1,2,3,\cdots 1,2,3,?。火星人的任意兩根手指都能隨意交換位置，他們就是通過這方法計數(shù)的。
一個火星人用一個人類的手演示了如何用手指計數(shù)。如果把五根手指――拇指、食指、中指、無名指和小指分別編號為 1 , 2 , 3 , 4 1,2,3,4 1,2,3,4 和 5 5 5，當(dāng)它們按正常順序排列時，形成了 5 5 5 位數(shù) 12345 12345 12345，當(dāng)你交換無名指和小指的位置時，會形成 5 5 5 位數(shù) 12354 12354 12354，當(dāng)你把五個手指的順序完全顛倒時，會形成 54321 54321 54321，在所有能夠形成的 120 120 120 個 5 5 5 位數(shù)中， 12345 12345 12345 最小，它表示 1 1 1； 12354 12354 12354 第二小，它表示 2 2 2； 54321 54321 54321 最大，它表示 120 120 120。下表展示了只有 3 3 3 根手指時能夠形成的 6 6 6 個 3 3 3 位數(shù)和它們代表的數(shù)字：
| 三進制數(shù) | 代表的數(shù)字 |
|---|---|
| 123 123 123 | 1 1 1 |
| 132 132 132 | 2 2 2 |
| 213 213 213 | 3 3 3 |
| 231 231 231 | 4 4 4 |
| 312 312 312 | 5 5 5 |
| 321 321 321 | 6 6 6 |
現(xiàn)在你有幸成為了第一個和火星人交流的地球人。一個火星人會讓你看他的手指，科學(xué)家會告訴你要加上去的很小的數(shù)。你的任務(wù)是，把火星人用手指表示的數(shù)與科學(xué)家告訴你的數(shù)相加，并根據(jù)相加的結(jié)果改變火星人手指的排列順序。輸入數(shù)據(jù)保證這個結(jié)果不會超出火星人手指能表示的范圍。
輸入格式
共三行。
第一行一個正整數(shù)
N
N
N，表示火星人手指的數(shù)目（
1
≤
N
≤
10000
1 \le N \le 10000
1≤N≤10000）。
第二行是一個正整數(shù)
M
M
M，表示要加上去的小整數(shù)（
1
≤
M
≤
100
1 \le M \le 100
1≤M≤100）。
下一行是
1
1
1 到
N
N
N 這
N
N
N 個整數(shù)的一個排列，用空格隔開，表示火星人手指的排列順序。
輸出格式
N N N 個整數(shù)，表示改變后的火星人手指的排列順序。每兩個相鄰的數(shù)中間用一個空格分開，不能有多余的空格。
樣例 #1
樣例輸入 #1
5
3
1 2 3 4 5
樣例輸出 #1
1 2 4 5 3
提示
對于 30 % 30\% 30% 的數(shù)據(jù)， N ≤ 15 N \le 15 N≤15。
對于 60 % 60\% 60% 的數(shù)據(jù)， N ≤ 50 N \le 50 N≤50。
對于 100 % 100\% 100% 的數(shù)據(jù)， N ≤ 10000 N \le 10000 N≤10000。文章來源：http://www.zghlxwxcb.cn/news/detail-822879.html
noip2004 普及組第 4 題
代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-822879.html
#include <bits/stdc++.h>
using namespace std;
int N,M;
int mars[10010];//輸入的火星人數(shù)據(jù)
int arr[10010];//記錄的方案
bool st[10010] ;
int res=0;//方案個數(shù)
bool return0=false;
void dfs(int x) {
if(return0){//剪枝
return ;
}
if(x>N){
res++;
if(res==M+1){
return0=true;
for(int i=1;i<=N;i++){
printf("%d ",arr[i]);
}
}
return ;
}
for(int i=1;i<=N;i++){
if(!res){
i=mars[x];
}
if(!st[i]){
st[i]=true;
arr[x]=i;
dfs(x+1);
st[i]=false;
arr[x]=0;
}
}
}
int main(){
cin>>N>>M;
for(int i=1;i<=N;i++){
cin>>mars[i];
}
dfs(1);
return 0;
}
到了這里，關(guān)于題解 洛谷P1088 [NOIP2004 普及組] 火星人——【C/C++】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![洛谷P1059 [NOIP2006 普及組] 明明的隨機數(shù)](https://imgs.yssmx.com/Uploads/2024/02/558793-1.png)
![【洛谷 P1003】[NOIP2011 提高組] 鋪地毯 題解（數(shù)組+貪心算法）](https://imgs.yssmx.com/Uploads/2024/02/423482-1.png)
![【洛谷 P1328】[NOIP2014 提高組] 生活大爆炸版石頭剪刀布 題解（模擬+向量）](https://imgs.yssmx.com/Uploads/2024/02/696901-1.png)
![[NOIP2007 普及組] 紀(jì)念品分組](https://imgs.yssmx.com/Uploads/2024/02/632229-1.png)
