洛谷 火星人
内容纲要

[NOIP2004 普及组] 火星人

题目描述

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为 1,2,3,4 和 5 ,当它们按正常顺序排列时,形成了 5 位数 12345 ,当你交换无名指和小指的位置时,会形成 5 位数 12354 ,当你把五个手指的顺序完全颠倒时,会形成 54321 ,在所有能够形成的 120 个 5 位数中, 12345 最小,它表示 1 ; 12354 第二小,它表示 2 ; 54321 最大,它表示 120 。下表展示了只有 3 根手指时能够形成的 6 个 3 位数和它们代表的数字:

三进制数 代表的数字
123 1
132 2
213 3
231 4
312 5
321 6

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指,科学家会告诉你要加上去的很小的数。你的任务是,把火星人用手指表示的数与科学家告诉你的数相加,并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

输入格式

共三行。
第一行一个正整数 N ,表示火星人手指的数目( 1 <= N <= 10000 )。
第二行是一个正整数 M ,表示要加上去的小整数( 1 l<= M <= 100 )。
下一行是 1 到 N 这 N 个整数的一个排列,用空格隔开,表示火星人手指的排列顺序。

输出格式

N 个整数,表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开,不能有多余的空格。

样例 #1

样例输入 #1

5
3
1 2 3 4 5

样例输出 #1

1 2 4 5 3
#include <bits/stdc++.h>
using namespace std;

// 创建二维数组是为了方便记录每个数是否被选中
vector<vector<int>> mars(10001, vector<int>(2, 1));
int N, M;
int flag = 0;
// 递归函数
void DFS(int x)
{
    // 递归结束条件
    if (x > N)//如果已经满足在初始设定的位置上,则开始计算次数
    {
        flag++;
        if(flag == M + 1)//如果次数满足要求,则输出
        {
            for (int j = 1; j <= N; j++)
                cout << mars[j][0] << " ";
            exit(0);//结束递归直接退出
        }
    }
    for (int i = 1; i <= N; i++)
    {
        if(flag == 0)
        //递归的顺序是从第一位开始的,这一步是为了直接跳到要求的数
        //再此基础上进行递归
            i = mars[x][0];
        if (mars[i][1])
        {
            mars[i][1] = 0;
            mars[x][0] = i;
            DFS(x + 1);
            mars[i][1] = 1;
        }
    }
}

int main()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        cin >> mars[i][0];
    DFS(1);
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇