【洛谷 P1088】[NOIP2004 普及组] 火星人 题解(全排列+向量)

简介: **火星人问题摘要:**NOIP2004普及组竞赛中的题目,涉及火星人用手指的排列表示数字。人类需计算火星人数字与给定数值之和的新排列。给定火星人手指数N(≤10000),加上的数M(≤100),以及初始排列,要求输出新排列。30%的数据中N≤15,60%的数据中N≤50。使用`next_permutation`函数找到第M个排列。样例:N=5, M=3, 初始排列1 2 3 4 5,输出1 2 4 5 3。

[NOIP2004 普及组] 火星人

题目描述

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言,但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的,首先,火星人把一个非常大的数字告诉人类科学家,科学家破解这个数字的含义后,再把一个很小的数字加到这个大数上面,把结果告诉火星人,作为人类的回答。

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手,但这只手上有成千上万的手指,这些手指排成一列,分别编号为 $1,2,3,\cdots$。火星人的任意两根手指都能随意交换位置,他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为 $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 \le N \le 10000$)。
第二行是一个正整数 $M$,表示要加上去的小整数($1 \le M \le 100$)。
下一行是 $1$ 到 $N$ 这 $N$ 个整数的一个排列,用空格隔开,表示火星人手指的排列顺序。

输出格式

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

样例 #1

样例输入 #1

5
3
1 2 3 4 5

样例输出 #1

1 2 4 5 3

提示

对于 $30\%$ 的数据,$N \le 15$。

对于 $60\%$ 的数据,$N \le 50$。

对于 $100\%$ 的数据,$N \le 10000$。

noip2004 普及组第 4 题

思路

输入一个排列,输出接下来的第m个排列。

AC代码

#include <iostream>
#include <algorithm>
#include <vector>
#define AUTHOR "HEX9CF"
using namespace std;

int main()
{
   
    int n, m;
    vector<int> v;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
   
        int t;
        cin >> t;
        v.push_back(t);
    }
    for (int i = 0; i < m; i++)
    {
   

        next_permutation(v.begin(), v.end());
    }
    vector<int>::iterator it1 = v.begin();
    for (; it1 != v.end(); it1++)
    {
   
        if (it1 != v.begin())
        {
   
            cout << " ";
        }
        cout << *it1;
    }
    cout << endl;
    return 0;
}
目录
相关文章
【洛谷 P1036】[NOIP2002 普及组] 选数 题解(深度优先搜索+判断质数+枚举子集)
**NOIP2002普及组选数问题**:给定$n$个整数和一个整数$k$,需找出所有$k$个数的组合,计算它们的和为素数的种类数。输入包含$n$和$k$,以及$n$个整数;输出是符合条件的组合数。例如,对于输入`4 3`和数组`[3, 7, 12, 19]`,输出为`1`。代码使用递归枚举子集并检查质数的方法。
397 0
|
12月前
Threejs创建天空和太阳
这篇文章讲解了如何使用Three.js中的Sky组件来创建真实的天空与太阳效果,包括调整天空的颜色、太阳的位置以及实现大气散射等技巧。
429 3
|
11月前
|
UED 开发者 容器
鸿蒙next版开发:ArkTS组件通用属性(图像效果)
在HarmonyOS 5.0中,ArkTS提供了丰富的图像效果属性,如阴影、灰度、高光、饱和度、对比度、图像反转、叠色、色相旋转等,极大丰富了用户界面的表现力。本文详细解读这些属性并提供示例代码。
521 1
|
JavaScript
vue项目中使用vue-router进行路由配置及嵌套多级路由
该文章详细说明了如何在Vue项目中配置和使用vue-router进行单页面应用的路由管理,包括设置嵌套路由和实现多级路由导航的示例。
vue项目中使用vue-router进行路由配置及嵌套多级路由
|
12月前
|
Python
蓝桥杯常用函数基础 | 模块及常用内置函数
蓝桥杯常用函数基础 | 模块及常用内置函数
|
存储 Java 数据库
基于全志H713 Android 11:给TvSettings添加default.xml默认值
本文介绍了在全志H713 Android 11平台上为TvSettings应用添加HDMI CEC功能的默认设置值的方法,通过修改SettingsProvider的源码和配置文件来实现默认值的设置,并提供了详细的步骤和测试结果。
481 0
基于全志H713 Android 11:给TvSettings添加default.xml默认值
|
机器学习/深度学习 人工智能
【洛谷 P1028】[NOIP2001 普及组] 数的计算 题解(递推)
在NOIP2001普及组的数的计算题目中,给定自然数`n`,需构造遵循特定规则的合法数列。合法序列始于`n`,新元素不超过前一项的一半。任务是找出所有这样的数列数量。例如,当`n=6`时,合法序列包括`6`, `6,1`, `6,2`, `6,3`, `6,2,1`, `6,3,1`。程序通过动态规划求解,当`i`为奇数时,`a[i] = a[i - 1]`;为偶数时,`a[i] = a[i - 1] + a[i / 2]`。代码中预处理数组`a`并输出`a[n]`作为答案。输入`n`后,程序直接计算并打印合法数列个数。
192 0
|
算法
【洛谷 P1003】[NOIP2011 提高组] 铺地毯 题解(数组+贪心算法)
**NOIP2011 提高组问题:铺地毯** 在第一象限的颁奖典礼场地,有$n$张地毯按编号顺序铺设。需找出覆盖特定点$(x, y)$的最上方地毯编号。输入包括地毯坐标和点坐标,输出地毯编号或-1表示未覆盖。 样例:给定3张地毯,点$(2,2)$被第3张地毯覆盖,输出3;另一样例点$(4,5)$未被覆盖,输出-1。 $30\%$数据$n\leq2$,$50\%$数据坐标$\leq100$,$100\%$数据$n\leq10^4$,坐标$\leq10^5$。 解决方法:从下到上遍历地毯,更新覆盖点的地毯编号。 AC代码略。
185 0
|
机器学习/深度学习 存储
【洛谷 P1028】[NOIP2001 普及组] 数的计算 题解(递归)
**NOIP2001普及组数的计算**:给定自然数\( n \),构造数列,新数不超过序列最后一项一半。求合法数列个数。输入\( n \)(\(1 \leq n \leq 10^3\))。样例:输入6,输出6。递归解决,代码中定义函数`f`实现递归计算,总和存储在`cnt`中,最后输出。
147 0
【洛谷 P1002】[NOIP2002 普及组] 过河卒 题解(递归+记忆化搜索)
`NOIP2002`普及组的过河卒问题是一个棋盘路径计数挑战。卒从$(0,0)$出发到$(n,m)$,只能向下或向右移动,马在$(c1,c2)$固定,控制某些点。任务是计算不受马阻挡的路径数。输入是目标和马的位置,输出是路径总数。使用动态规划和记忆化搜索避免重复计算,样例输入$(6,6,3,3)$输出$6$。代码中定义了$f(x,y)$计算$(x,y)$处的路径数,利用边界条件和递推关系计算。
206 0