题解：CF1937A Shuffle Party

__bjxx0201__ · 2024-07-08 21:25:14 · 题解

题目大意

给你一个长度为 n 的整数序列，j 为 a_i 除本身之外最大的因数。会交换 a_i 和 a_j，求最后 1 是在哪一个位置。

思路

题目传送门

特别的，如果 n=1，直接输出 1。

对于接下来的数据，我们可以做一下模拟，模拟 n=4：

• 第一次：1 2 3 4（初始队列，不换）。
• 第二次：2 1 3 4（可发现仅有第 1 和第 2 个元素交换，1 换到了第 2 个位置）。
• 第三次：3 1 2 4（位置仍然和上一步的一样，但是其余的元素变换）。
• 第四次：3 4 2 1（位置乘以 2）。

我们可以看一下，一次 1 的位置为 1，之后，只有第 2 次、第 4 次变换了，为什么是这样呢？

由于对于每一次操作时，对于 a_i 而言，j 为 a_i 最大的除本身之外的因数，j\le \frac{1}{2}a_i，交换时，交换 a_i 和 a_j。所以，用最极端的方法，对于任意整数 a_i，直接换到某一个位置上，这个位置就是 2 一直乘上去的一个数字（可以表示为 2^k）。那么对于每一组数据，答案得到论证，就是最大的不大于 n 的 2 的整数次幂了。

参考代码：

#include <bits/stdc++.h>
#define int long long//注意，数据有可能会爆int，所以一定要用更大的范围。
using namespace std;
int t,a;
int er (int n) {//算出 2^n 的值。
    int ans=1;
    for (int i=1;i<=n;i++) ans*=2;
    return ans;
}
void calc (int n) {
    if (n==1) cout<<"1\n";
    else {
        int k=0;
        while (er (k)<=n) k++;
        cout<<er (k-1)<<"\n";
    }
}
inline int read () {int s=0,w=0;char c=getchar ();while (!isdigit (c)){w|=(c=='-');c=getchar ();}while (isdigit (c)) {s=(s<<1)+(s<<3)+(c^48);c=getchar ();}return w?-s:s;}
inline void write (int x) {if (x<0) putchar ('-'),x=-x;if (x>9) write (x/10);putchar (x%10|48);}
signed main() {
    cin>>t;
    while (t--) {
        cin>>a;
        calc (a);
    }
    return 0;
}