CodeForces - 1457D XOR-gun(位运算+暴力)

题目链接：点击查看

题目大意：给出一个长度为 n 的非降序列，现在可以执行数次操作：选择相邻的两个位置将其替换成异或和，更具体的，每次操作可以选择一个位置 i ，满足 1 <= i < n，令 a[ i ] = a[ i ] xor a[ i + 1 ] 并删除掉 a[ i + 1 ]，问最少需要操作多少次才能使得整个序列不再非降

题目分析：假设 b[ i ] 为 a[ i ] 最高位的那个 1，比较显然的是，如果存在 b[ i - 1 ] == b[ i ] == b[ i + 1 ] 时，答案为 1，因为此时只需要将 a[ i ] 与 a[ i + 1 ] 进行一次操作后，就能得到 a[ i - 1 ] > a[ i ] ，即满足了条件

考虑如果没有连续的三个位置的最高位相同，那么最坏情况肯定是两两成对，换句话说 b 数组依次为 1 , 1 , 2 , 2 , 3 , 3 ... log( mmax ) , log( mmax )，此时如果再多一个数字，因为要满足初始的序列非降，所以不难看出无论插在哪里一定会出现 b[ i - 1 ] == b[ i ] == b[ i + 1 ] 的情况，又回到了第一种情况，换句话说如果整个序列的长度大于 log( mmax ) * 2 了，那么答案一定为 1，这是一个很重要的剪枝

上面剪枝的阈值可以设置为大于 60 的任意一个数，而对于小范围的数直接暴力即可，再考虑一下答案会在哪些地方出现：

选择一段区间 [ l , r ]，将整个区间进行异或，最后得到的答案与 a[ l - 1 ] 和 a[ r + 1 ] 比较

选择两段相邻的区间 [ i , j ] 和 [ j + 1 , k ] ，将两段区间分别异或然后比较大小

情况一可以 n^2 暴力，情况二可以 n^3 暴力

代码：
 

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int a[N],sum[N];int main() { #ifndef ONLINE_JUDGE // freopen("data.ans.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",a+i);sum[i]=sum[i-1]^a[i];}if(n>60)return 0*puts("1");int ans=inf;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){int num=sum[j]^sum[i-1];if((i>1&&num<a[i-1])||(j<n&&num>a[j+1]))ans=min(ans,j-i);}for(int i=1;i<=n;i++)//[i,j][j+1,k]for(int j=i+1;j<=n;j++)for(int k=j+1;k<=n;k++){int num1=sum[j]^sum[i-1];int num2=sum[k]^sum[j];if(num1>num2)ans=min(ans,k-i-1);}if(ans==inf)puts("-1");elseprintf("%d\n",ans);return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1457D XOR-gun(位运算+暴力)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。