XOR-gun (位运算，思维，区间暴力)

lovesickman

已于 2022-07-13 16:53:48 修改

阅读量222

点赞数 1

分类专栏： codeforces 文章标签：算法

于 2022-07-13 16:44:45 首次发布

本文链接：https://blog.csdn.net/hacker__man/article/details/125767441

版权

codeforces 专栏收录该内容

12 篇文章

订阅专栏

XOR-gun (位运算，思维，区间暴力)

题面翻译

给定一个长为 $2\leq n \leq10^5$ 的不降序列，每次操作可以任选相邻的两个数，并将这两个数替换为两个数按位异或的结果，现在需要破坏序列的不降，求最少操作次数，无解输出 $- 1$

输出格式

Print a single integer — the minimum number of steps needed. If there is no solution, print $- 1$

样例 #1

样例输入 #1

4
2 5 6 8

样例输出 #1

样例 #2

样例输入 #2

3
1 2 3

样例输出 #2

-1

样例 #3

样例输入 #3

5
1 2 4 6 20

样例输出 #3

非常巧妙的思维题。

自己想的时候，想了10分钟发现没有任何切入点；

既然题目要求改变序列单调性，那么可以假设 $a_1,a_2,a_3 ...$ ，

是把 $\bigoplus a_2 > a_3$ 还是 $a_2 \bigoplus a_3$ ? 都可以；

考虑异或定义，发现，如果存在连续的3个数，他们二进制表示的最高位在同一位，那么有 $a_2 \bigoplus a_3$

所以每位二进制最多有两个连续的数相邻，又因为序列是不降的， $a[i]\le 10^{9}$ , 所以最多有 30 * 2 == 60 个数，如果 $n > 60$ 那么只要 1 次操作即可。

对于 $\le 60$ ，先判断1次操作可不可以，然后暴力。因为要对连续的数合并，类似区间dp，枚举分界点，维护前缀异或和，当出现非不降情况时维护答案即可。

int a[N];
void solve(){
	cin>>n;
	if(n>60){
		puts("1");
	}
	map<int,int>mp;
	fo(i,1,n){
		cin>>a[i];
	}
	fo(i,1,n){
		int x = a[i];
		int cnt = 0;
		while(x){
			cnt++;
			x>>=1;
		}
		mp[cnt]++;
	}
	bool flag=0;
	for(auto c:mp){
		if(c.second>=3){
			flag=1;
			break;
		}
	}
	if(flag){
		puts("1");
	}
	else{
		fo(i,1,n){
			a[i] ^= a[i-1];
		}
		int ans = n;
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				for(int k=i;k<j;k++){
					int x = a[k]^a[i-1];
					int y = a[j]^a[k];
					if(x>y){
						ans = min(ans,j-i-1);
					}
				}
			}
		}
		if(ans == n){
			puts("-1");
		}
		else
		cout<<ans<<endl;
	}
}