一种比较容易写的构造方案
考虑直接二进制拆分，发现在原排列的基础上，在开头填上更大的数，方案数+1，在末尾上填上更大的数，方案数*2，
直接按照填数从小到大顺序填入，长度为 logk + popcount(k)，期望得分91分
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 vector <int> construct_permutation(long long k) 6 { 7 stack <int> s; 8 for (long long x = k; x != 1; x >>= 1) s.push(x & 1); 9 deque <int> q; 10 for (int cnt = 0; !s.empty() ; s.pop()) 11 { 12 q.push_back(cnt++); 13 if (s.top()) q.push_front(cnt++); 14 } 15 vector <int> ans; 16 while (!q.empty()) ans.push_back(q.front()), q.pop_front(); 17 return ans; 18 }
发现如果已经有两次以上的+1操作，可以把原排列的前两位与前三位之间放入更大的数，方案数+3
可以把 *2 +1 *2 +1 变成 *2 *2 +3 ，可以通过该题
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 vector <int> construct_permutation(long long k) 6 { 7 stack <int> s; 8 for (long long x = k; x != 1; x >>= 1) s.push(x & 1); 9 10 deque <int> q; 11 bool pd = false; 12 for (int cnt = 0, s1 = 0; !s.empty(); s.pop()) 13 { 14 if (s1 > 3 && pd && s.top()) // *2 +1 *2 +1 -> *2 *2 +3 15 { // (now) *2 +1 16 q.pop_front(); --cnt; // del +1 17 q.push_back(cnt++); // add *2 18 int x = q.front(); q.pop_front(); 19 int y = q.front(); q.pop_front(); 20 q.push_front(cnt++); // +3 21 q.push_front(y); 22 q.push_front(x); 23 pd = false; 24 continue; 25 } 26 q.push_back(cnt++); 27 if (s.top()) q.push_front(cnt++), s1++, pd = true; 28 else pd = false; 29 } 30 31 vector <int> ans; 32 while (!q.empty()) ans.push_back(q.front()), q.pop_front(); 33 return ans; 34 }