题解：P17750 「RSOI-2C」异或 / xor
Portuguese
·
·
题解
题目传送门
这是本蒟蒻的第一篇题解，不喜勿喷。
思路：
判断所有数最高位是否一致。若不一致，原图连通，答案 0；若全部相同，只需修改一个数，把它改成小于 2^k 的最大数或大于等于 2^{k+1} 的最小数，取最小修改代价。n=1 直接输出 0。
复杂度：
### AC Code:
```cpp
//P17750
#include<bits/stdc++.h>
using namespace std;
int getbit(int x)
{
if(x==0) return -1;
int res=0;
while(x>>=1) res++;
return res;
}
int a[100005];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
if(n==1)
{
cout<<0;
return 0;
}
int bit=getbit(a[0]);
bool f=1;
for(int i=0;i<n;i++)
{
if(getbit(a[i])!=bit)
{
f=0;
break;
}
}
if(!f)
{
cout<<0;
return 0;
}
int p=1;
for(int i=0;i<bit;i++) p*=2;
int ans=1e18;
for(int i=0;i<n;i++)
{
int c1=a[i]-(p-1);
int c2=p*2-a[i];
ans=min(ans,min(c1,c2));
}
cout<<ans;
return 0;
}
```
~~求过。~~