【捞】【APIO2022 T3】排列（构造，DP）

题面

源自洛谷

题目背景

本题只支持 C++ 提交，提交时不需要包含 perm.h 头文件，只需要将附件中的 perm.h 中的内容粘贴到代码的开头即可。

题目描述

法老们利用行星的引力来加速飞船。假设飞船将依次以 p [ 0 ] , p [ 1 ] , … , p [ n − 1 ] p[0], p[1],dots , p[n - 1] p[0],p[1],…,p[n−1] 的轨道速度飞掠 n n n 颗行星。飞掠每颗行星时，法老科学家可以选择是否利用它来加速飞船。为了节省能量，当飞船以轨道速度 p [ i ] p[i] p[i] 飞掠一颗行星并完成加速后，它将不能再在以轨道速度 p [ j ] < p [ i ] p[j] < p[i] p[j]

科学家已经确认，总共有 k k k 种方案来选择行星对飞船进行加速，但是他们弄丢了轨道速度的记录信息（甚至包括 n n n 的大小）。不过他们记得 ( p [ 0 ] , p [ 1 ] , … , p [ n − 1 ] ) (p[0], p[1],dots , p[n - 1]) (p[0],p[1],…,p[n−1]) 是 0 , 1 , … , n − 1 0, 1,dots , n - 1 0,1,…,n−1 的一个排列。这里的排列是包含从 0 0 0 到 n − 1 n - 1 n−1 每个整数恰好一次的序列。 你的任务是找出一个长度尽量小且符合要求的排列 ( p [ 0 ] , p [ 1 ] , … , p [ n − 1 ] ) (p[0], p[1],dots , p[n - 1]) (p[0],p[1],…,p[n−1])。

你要对 q q q 艘不同的飞船来解决该问题。对每艘飞船 i i i，你会得到一个整数 k i k_i ki​，表示选择行星加速飞船的不同方案数。你的任务是找出长度 n n n 足够小的轨道速度序列，使得从中恰好可以选出 k i k_i ki​ 个轨道速度递增的行星子序列。

实现细节

你要实现以下函数：

int[] construct_permutation(int64 k)

• k k k 是应有的递增子序列的数量。
• 该函数要返回有 n n n 个元素的数组，每个元素是 0 0 0 到 n − 1 n - 1 n−1 之间（包括 0 0 0 和 n − 1 n - 1 n−1）的数。
• 返回的数组必须是恰好有 k k k 个递增子序列的合法排列。
• 该函数总共被调用 q q q 次。每次调用被视为一个独立的场景。

输入格式

评测程序示例按以下格式读取输入：

• 第 1 1 1 行： q q q。
• 第 2 + i 2+i 2+i 行（ 0 ≤ i ≤ q − 1 0le ile q-1 0≤i≤q−1）： k i k_i ki​。

输出格式

评测示例程序对每个 k i k_i ki​ 打印一行，包含对应 construct_permutation 调用的返回值。如果出错则打印错误信息。

样例 #1 样例输入 #1

2
3
8

样例输出 #1

2
1 0
3
0 1 2

提示 例子 例 1 1 1

考虑以下调用：

construct_permutation(3)

该函数应该返回一个恰好有 3 3 3 个递增子序列的排列。一种可能的答案是 [ 1 , 0 ] [1,0] [1,0]，它的递增子序列有 [ ] [] []（空的子序列）、 [ 0 ] [0] [0] 和 [ 1 ] [1] [1]。

例 2 2 2

考虑以下调用：

construct_permutation(8)

该函数应该返回一个恰好有 8 8 8 个递增子序列的排列。一种可能的答案是 [ 0 , 1 , 2 ] [0,1,2] [0,1,2]。

约束条件

• 1 ≤ q ≤ 100 1le qle 100 1≤q≤100。
• 2 ≤ k i ≤ 1 0 18 2le k_ile 10^{18} 2≤ki​≤1018（对所有 0 ≤ i ≤ q − 1 0le ile q-1 0≤i≤q−1）。

子任务

1. （ 10 10 10 分） 2 ≤ k i ≤ 90 2le k_ile 90 2≤ki​≤90（对所有 0 ≤ i ≤ q − 1 0le ile q-1 0≤i≤q−1）。如果你给出的所有排列长度至多为 90 90 90 且结果正确，你将获得 10 10 10 分，否则获得 0 0 0 分。
2. （ 90 90 90 分）没有额外的约束条件。对该子任务，令 m m m 为你在所有场景中给出的排列的最大长度，则你的得分按下表来计算：

条件	得分
m ≤ 90 mle 90 m≤90	90 90 90
90 < m ≤ 120 90 < mle 120 90	90 − m − 90 3 90-dfrac{m-90}{3} 90−3m−90​
120 < m ≤ 5000 120 < mle 5000 120	80 − m − 120 65 80-dfrac{m-120}{65} 80−65m−120​
m > 5000 m > 5000 m>5000	0 0 0

题解

其实这题我之前写过，虽然是弱化版(但是 K 更大？)，但是我用的是 m ≤ 90 mleq90 m≤90 的做法。

原博客，因为元素不重复一定更优，所以输出的也是排列

当初最终复杂度没说清。

由于对连续段的处理，使得一段连续 x x x 个 1 1 1 的操作次数其实是 ≤ log ⁡ x leqlog x ≤logx ，这个数据均摊下近似于 O ( 1 ) O(1) O(1) 了。最坏情况应该是接近 01 循环。所以总长度是跑不满的 3 2 log ⁡ K frac{3}{2}log K 23​logK 。果然是跑不到 90 的。

另外，原题 ≤ 98 leq 98 ≤98 ，存在用三进制过掉的做法。但我也就是听大佬们这么一说，完全不懂怎么做呢。放在这题也能过个 90+ 吧。

CODE

代码真的很短

// #include "perm.h"
#include
#include
#include
#include
#include
#include
using namespace std;
#define LL long long

LL dp[105];
int a[105];
LL hb,mx,L;
LL ct[105];
int mp(LL x) {
	for(int i = 0;i <= mx;i ++) if(ct[i] == x) return i;
	return -1;
}
void addbot(int ad) {
	for(int i = 1;i <= L;i ++) if(a[i] > ad) a[i] ++;
	mx ++;
	for(int i = mx;i > ad+1;i --) swap(ct[i],ct[i-1]);
	a[++ L] = ad+1; ct[ad+1] = ct[ad];
	for(int i = ad+1;i <= mx;i ++) ct[i] += ct[ad];
	return ;
}
vector construct_permutation(LL K) {
	L = 0;
	vector rs;
	memset(a,0,sizeof(a));
	memset(ct,0,sizeof(ct));
	memset(dp,0,sizeof(dp));
	hb = 62,mx = 0;
	ct[0] = 1ll;
	while(!(K & (1ll<= 0;i --) {
		if(K & (1ll<
			LL tm = 1ll;
			while(i > 0 && (K & (1ll<<(i-1)))) {
				i --; tm = tm<<1ll|1ll;
			}
			for(LL tmp = tm;tm > 0ll;tmp = min(tmp,tm)) {
				tmp = tm;
				int add = 0;
				while((add=mp(tmp)) < 0) tmp >>= 1ll;
				LL tmc = tmp;
				while(tmc > 0) {
					a[++ L] = ++ mx; ct[mx] = ct[mx-1]<<1ll;
					tm >>= 1ll;
					tmc >>= 1ll;
				}
				addbot(add);
			}
		}
		else {
			a[++ L] = ++ mx;
			ct[mx] = ct[mx-1]<<1ll;
		}
	}
	for(int i = 1;i <= L;i ++) {
		rs.push_back(a[i]-1);
	}
	return rs;
}