RdOI-R1 T2 序列 题解
Steven__Chen
·
·
个人记录
于是乎，这题就变成了：有一棵满二叉树$x$，节点数为$q$，对于一个节点$y$，你可以使$y$与其儿子交换位置。问如何使每个节点的值与其编号相等。
------------
转换题目后，思路就清晰多了。对于一个值与其编号不相等的节点$x_i$，我们可以先让它通过与父亲交换到达$x_i$和$x_{x_i}$的最近公共祖先处，再通过与儿子交换到达$x_{x_i}$节点处。为了在移动时不影响其它已经处理完并且编号大于自己的节点，我们应先从节点$x_q$处理，再处理节点$x_{q-1}$，……，最后处理节点$x_1$。
当然了，如果觉得求最近公共祖先麻烦，你也可以直接让$x_i$通过与父亲交换直接到达根节点处，然后再根据其二进制位，与儿子进行交换到达节点$x_{x_i}$处。这样做也是可行的。
代码如下：
``` cpp
#include<cstdio>
using namespace std;
int q, sequence[131073], log_2[131073], log2s = 1, log2c, f[131073], m;//sequence是序列x,log_2是节点x_i在满二叉树中的层数，f[i]代表i在满二叉树中的编号。
int RdOImin(int x, int y)//min函数。
{
return x > y ? y : x;
}
int LCA(int x, int y)//求最近公共祖先,函数内部是用二分实现的。
{
int l = 1, r = RdOImin(log_2[x], log_2[y]), mid, lastl = 0, lastr = 0;
while (l < r)
{
mid = (l + r) >> 1;
if (((x >> (log_2[x] - mid)) == (y >> (log_2[x] - mid))) && !(lastl == l && lastr == r) ) lastl = l, lastr = r, l = mid;
else lastl = l, lastr = r, r = mid - 1;
}
return x >> (log_2[x] - l);
}
inline int read()//快读函数。
{
int x = 0, f = 1; char c = getchar();
while(c > '9' || c < '0') { if(c == '-') f = -1; c = getchar(); }
while(c <= '9' && c >= '0') { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
void RdOIswap(int &x, int &y)//交换函数。
{
m = x, x = y, y = m;
}
int main()
{
q = read();
for (int i = 1; i <= q; i++)
{
sequence[i] = read();//读入序列x。
f[sequence[i]] = i;//完善引导数组。
}
for (int i = 1; i <= q; i++)//预处理log_2数组。
{
if (i == log2s)
log2s <<= 1, log2c++;
log_2[i] = log2c;
}
for (int i = q; i >= 1; i--)//逆序处理。
{
if (sequence[i] == i)//如果无需处理，跳过节点。
continue;
int node = LCA(f[i], i), p = f[i], way = (node << (log_2[i] - log_2[node])) ^ i, len = log_2[i] - log_2[node] - 1;//node是x_{f[i]}和x_i的最近公共祖先，p代表当前操作位置，way是二进制的引导项，当前位为0时，与左儿子交换，否则与右儿子交换，len是node与x_i的层数差距。
while (p != node)//node节点成为当前操作节点时，退出循环。
{
RdOIswap(sequence[p], sequence[p >> 1]);//交换p和它的父亲。
f[sequence[p >> 1]] = p >> 1, f[sequence[p]] = p;//更新f数组。
printf("%d %d\n", p >> 1, p);//输出操作。
p >>= 1;//更新当前操作节点。
}
while (p != i)//i成为当前操作节点时，退出循环。
{
int next = (way & (1 << len)) ? (p << 1) + 1 : p << 1;//p需要与next交换。
len--;
RdOIswap(sequence[p], sequence[next]);//交换节点p和next。
f[sequence[next]] = next, f[sequence[p]] = p;//更新f数组。
printf("%d %d\n", p, next);//输出操作。
p = next;//更新当前操作节点。
}
}
return 0;
}
```