題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)長度為 n 的非降序列，現(xiàn)在可以執(zhí)行數(shù)次操作：選擇相鄰的兩個(gè)位置將其替換成異或和，更具體的，每次操作可以選擇一個(gè)位置 i ，滿足 1 <= i < n，令 a[ i ] = a[ i ] xor a[ i + 1 ] 并刪除掉 a[ i + 1 ]，問最少需要操作多少次才能使得整個(gè)序列不再非降

題目分析：假設(shè) b[ i ] 為 a[ i ] 最高位的那個(gè) 1，比較顯然的是，如果存在 b[ i - 1 ] == b[ i ] == b[ i + 1 ] 時(shí)，答案為 1，因?yàn)榇藭r(shí)只需要將 a[ i ] 與 a[ i + 1 ] 進(jìn)行一次操作后，就能得到 a[ i - 1 ] > a[ i ] ，即滿足了條件

考慮如果沒有連續(xù)的三個(gè)位置的最高位相同，那么最壞情況肯定是兩兩成對，換句話說 b 數(shù)組依次為 1 , 1 , 2 , 2 , 3 , 3 ... log( mmax ) , log( mmax )，此時(shí)如果再多一個(gè)數(shù)字，因?yàn)橐獫M足初始的序列非降，所以不難看出無論插在哪里一定會(huì)出現(xiàn) b[ i - 1 ] == b[ i ] == b[ i + 1 ] 的情況，又回到了第一種情況，換句話說如果整個(gè)序列的長度大于?log( mmax ) * 2 了，那么答案一定為 1，這是一個(gè)很重要的剪枝

上面剪枝的閾值可以設(shè)置為大于 60 的任意一個(gè)數(shù)，而對于小范圍的數(shù)直接暴力即可，再考慮一下答案會(huì)在哪些地方出現(xiàn)：

選擇一段區(qū)間 [ l , r ]，將整個(gè)區(qū)間進(jìn)行異或，最后得到的答案與 a[ l - 1 ] 和 a[ r + 1 ] 比較

選擇兩段相鄰的區(qū)間 [ i , j ] 和 [ j + 1 , k ] ，將兩段區(qū)間分別異或然后比較大小

情況一可以 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; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1457D XOR-gun(位运算+暴力)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。