1.求排列
题目描述
把1-n的所有排列按字典序排成一排,从中选择一个排列假设他是第Q个,返回倒数第Q个排列.
例如:1-2的所有排列为
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
若选择的排列是1, 2, 3, 则Q=1,应该输出3, 2, 1.
输入输出描述
输入描述:
第一行数字n,表示排列长度,
接下来一行n个数字,表示选出的排列. 1<n<300000
输出描述:
一行n个数字,表示返回的排列
示例
输入:
5
3 1 5 2 4
输出:
3 5 1 4 2
解题思路
嗯,调用prev_permutation()求得当前选择的排列是第j个排列,然后从最后一个排列往前取j个排列.得到要返回的排列.
代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> nums;
int v;
for(int i=0;i<n;i++){
cin >> v;
nums.push_back(v);
}
int j=0;
while(prev_permutation(nums.begin(), nums.end())){
j++;
}
for(int i=0;i<j;i++){
prev_permutation(nums.begin(), nums.end());
}
for(auto num:nums)
cout << num << " ";
cout << endl;
return 0;
}
大佬代码（奇技淫巧）
n = int(input())
array = [int(i) for i in input().split(' ')]
print(' '.join([str(n + 1 - array[i]) for i, item in enumerate(array)]))
2.数字环
题目描述
长度为n的数字数组a1,a2,.......,an,问是否能够使用n个数字构成一个环(首位连接),使得环中的每一个数字都小于它相邻的两个数字和(每个数字都必须使用且每个数字只能使用一次).
输入输出描述
输入描述:
第一行包含一个整数t(1<=t<=10),表示测试用例的组数
每个测试用例输入如下:
第一行一个整数n,表示数字的个数
第二行n个整数a1,a2,.......,用空格分隔.
3<=n<=10^5 , 1<=ai<=10^9
输出描述:
输出应该包含t行,对于每组样例,若能输出"YES",否则输出"NO".
示例
输入:
1
5
17 6 17 11 17
输出:
YES
解题思路
- 先对数组A排序
- 要使数组A满足首位连接构成环满足条件,将数组A排列成最有可能满足的情况,即每一个相邻数字尽量接近,排列后的数组用数组B保存. 具体方法见代码.
- 举例说明17 6 17 11 17
- 排序后为 6 11 17 17 17
- 最有可能满足条件排列 17 17 6 11 17
- 遍历数组B进行判断
代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int t,n;
cin >> t;
while(t--){
vector<int> numsA;
cin >> n;
int v;
for(int i=0;i<n;i++){
cin >> v;
numsA.push_back(v);
}
sort(numsA.begin(), numsA.end());
vector<int> numsB(numsA);
int left = (n-1)/2;
int right = (n-1)/2;
numsB[(n-1)/2] = numsA[0];
for(int i=1;i<n;i++){
if(i&1) numsB[++right] = numsA[i];
else numsB[--left] = numsA[i];
}
bool flag=true;
for(int i=0;i<n;i++){
if(numsB[(i-1+n)%n]+numsB[(i+1+n)%n]<=numsB[i]){
flag=false;
break;
}
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
3.字典序最小数组
题目描述
给一个包含n个整数a1,a2,......,an,你可以对数组执行任意次以下操作:
对于数组中的两个下标i,j(1<=i, j<=n),如果ai+aj为奇数,则可以交换ai,aj
求所有通过若干次操作得到的数组中,字典序最小的数组.
输入输出描述
输入描述:
第一行一个整数n,
第二行n个整数a1,a2,......,an,表示数组,用空格分隔.
输入保证1<=n<=10^5, 1<=ai<=10^9
输出描述:
n个整数,用空格分开,表示得到的字典序最小数组.
示例
输入:
10
53941 38641 31525 64784 29026 12199 83522 58200 64784 80987
输出:
12199 29026 31525 38641 53941 58200 64784 64784 80987 83522
解题思路
如果全部是奇数或者全部是偶数,则直接输出原数组,否则输出排序后的数组.
代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
vector<int> nums;
cin >> n;
int v;
int even_num = 0;
for(int i=0;i<n;i++){
cin>>v;
if(v%2) even_num++;
nums.push_back(v);
}
if(even_num!=n && even_num!=0){
sort(nums.begin(), nums.end());
}
for(auto num:nums)
cout << num << " ";
cout << endl;
return 0;
}
4.优秀序列
题目描述
给定01序列S,序列S是优秀的01序列,优秀的01序列定义如下:
1.如果序列S,T是优秀的,那么S+T也是优秀的,+是连接两个序列.
2.如果序列S是优秀的,则序列res(S)也是优秀的,res(S)被定义为按位翻转(0变1,1变0)并去掉前导0.例如res(1100101)="11010"
输入输出描述
输入描述:
第一行T表示有T组数据,
每组数据第一行是01序列S,第二行是01序列T.
1<=|S|, |T|<=1000,S,T不含前导0
输出描述:
对于每组数据输出"YES"或"NO".
示例
输入:
1
1100
110011
输出:
YES
解题思路
暂时不会,哭唧唧!
