P8376 [APIO2022] 排列

一种比较容易写的构造方案

考虑直接二进制拆分，发现在原排列的基础上，在开头填上更大的数，方案数+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 }