题解：CF1682B AND Sorting

· · 题解

题目传送门 CF原题链接

题目主意：

这道题是关于位操作和排序算法的组合问题。我们首先了解一下题目的要求。

题目给出了一个初始未排序的数组 p = p_1, p_2, \ldots, p_n，它包含从 0 到 n-1 的整数，每个数字恰好出现一次。我们需要找出一个最大的非负整数 X，使得通过执行特定的操作，数组 p 可以被排序。这个操作如下：
选择数组中两个索引 i 和 j（1 \le i < j \le n），使得元素 p_i 和 p_j 在二进制表示下按位与的结果为 X，即 p_i \operatorname{and} p_j = X。然后交换这两个元素。

题目要求：

目标是找到最大的这样的 X 值，使得可以通过有限次这样的操作将数组排序。

首先，为了方便叙述，我们定义一个函数 f(i)，表示在数组 p 中与 p_i 进行按位与操作能得到的最大 X 值，即 f(i) = \max_{j>i} \{ p_i \operatorname{and} p_j \}。对于给定的数组 p，我们首先遍历一次数组，计算所有元素的 f(i) 值。然后，我们再遍历一次数组，对于每一个元素 p_i，检查是否存在某个 p_j（j > i）使得 f(i) = f(j)。如果存在，那么我们可以用这两个元素进行交换，且 X = f(i)。否则，我们将当前的 f(i) 值作为新的 X 值。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
int p[maxn];
int t = 0,n = 0,tmp = -1;
int main() {
    cin >> t;
    while(t--){ 
        cin >> n;
        for(int i = 0;i < n;i++){//用0开始，1试过过不去 
            cin >> p[i];
            if(i != p[i] && tmp == -1){ //如果p[i]不等于它的位置（i）且未被赋值 
                tmp = p[i];
            }else if(i != p[i]){
                tmp = tmp & p[i]; 
            }
        }
        printf("%d\n",tmp);//输出 
        tmp = -1;//记得要清0
    }
    return 0;
}