C. Anu Has a Function(位运算&思维)

布满荆棘的人生 2021-07-17 02:39 372阅读 0赞

[题目][Link 1]

思路：对于两个二进制数f(x,y)=x|y-y 举两个例子 x 11101 y 10100 f(x,y)=01001 x 111111 y 1010 f(x,y)=110101 我们可以发现f(x,y)结果就是将y中的对应二进制为一的地方如果x中相对应的也为1则将x相应位置变为0，剩下的x就是结果。而对于一个序列我们将对序列第一个元素进行(n-1)次这种“相减”运算，可以发现对于一个序列我们只要确定了第一个元素的值，其他后面的元素无论怎样排序结果都相同。如此我们只需先将每个元素所有位的二进制数存储一遍求个总和，如果存储的某位上>=2，则必有两个元素都有在这个位上是1，最终结果在此位上会相减为0。所以只有某个位是1，才能够保存下来，那么我们只需找到存储中最大的位上是1的元素即可（由二进制的性质所有后面的位数相加的值不可能比前面的大），细节见代码。

Code:

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #include<bitset>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int lst[Max];
    int Mod = 1e9 + 7;
    
    
    int main()
    { 
    	FAST;
    	int n;cin >> n;
    	map<int, int> ma;
    	for (int i = 1;i <= n;i++)
    	{ 
    		int g, t = 0;cin >> g;lst[i] = g;
    		while (g)
    		{ 
    			if (g % 2)ma[t]++;
    			g /= 2;t++;
    		}
    	}
    	int f = -1;
    	for (int i = 35;i >= 0;i--)if (ma[i] == 1) { 
    		f = i;break;
    	}
    	if (f == -1)for (int i = 1;i <= n;i++)cout << lst[i] << " ";
    	else
    	{ 
    		int q=0;
    		for (int i = 1;i <= n;i++)
    		{ 
    			int g = lst[i], t = 0;
    			while (g)
    			{ 
    				if (g % 2==1 && t == f)
    				{ 
    					q = i;break;
    				}
    				g /= 2;t++;
    			}
    			if (q)break;
    		}
    		int k = lst[1];lst[1] = lst[q];lst[q] = k;
    		for (int i = 1;i <= n;i++)cout << lst[i] << " ";
    	}
    	cout << endl;
    }

[Link 1]: https://codeforces.ml/contest/1300/problem/C