首页 > 其他分享 >Codeforces Round 888 (Div. 3)F(异或小技巧)

Codeforces Round 888 (Div. 3)F(异或小技巧)

时间:2023-07-26 09:57:17浏览次数:42  
标签:aj rr int ll 888 Codeforces ai 异或

题意:给你一个数组长度为n的a数组,要求a数组的值为非负整数,再给你一个k,a的值全小于2的k次方,找到一个小于a的k次方的值x,再从a中找到两个值,让他们 (ai⊕x)&(aj⊕x)最小

结论:n个数的最小异或对的答案就是排序后最小的相邻异或和

思路:(ai⊕x)&(aj⊕x)的最高位为1,可以把它先转换成二进制
例如:
0010 2
0100 4
0100 4
0100 4
0101 5
0110 6
1001 9
1010 10
1110 14
我们知道异或是相同为0,不同为1,与是有0为0,所以我们要先让(ai⊕x)和(aj⊕x)位数尽可能为1,而(ai⊕aj)为1的位数我们是没有办法改变的,(ai⊕aj)为1则(ai⊕x)&(aj⊕x)为0,所以我们要找最小的异或对,这个时候就用到上面的结论了,然后找到异或对后就是构造x,x就是i,j的同一位数全为0则x这一位为1,否则为0

点击查看代码
const int N = 1e6 + 10;
int n,m,k;
struct now{
	int u;
	int v;
}a[N];
bool cmp(now ll,now rr)
{
	if(ll.u == rr.u)
	return ll.v < rr.v;
	return ll.u < rr.u;
}
void solve()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i ++)
	{
		cin >> a[i].u;
		a[i].v = i;
	}
	sort(a+1,a+n+1,cmp);
	int l = 0,r = 0,num = 1e18;
	for(int i = 2;i <= n;i ++)//找最小异或对
	{
		int w = a[i].u ^ a[i-1].u;
		if(w < num)
		{
			num = w;
			l = i-1;
			r = i;
		}
	}
	int cnt = 1,ans = 0;
	for(int i = 0;i < m;i ++)//二进制枚举位数,比对该位是否为相同为0
	{
		cnt = 1 << i;
		int xx = a[l].u&cnt;
		int yy = a[r].u&cnt;
		if(xx==0&&yy==0)
		{
			ans += cnt;
		}
	}
	cout << a[l].v << ' ' << a[r].v << ' ' << ans << '\n';
}

标签:aj,rr,int,ll,888,Codeforces,ai,异或
From: https://www.cnblogs.com/ljmxmu/p/17581651.html

相关文章

  • 【题解】Educational Codeforces Round 150(CF1841)
    赛时过了A-E,然后就开摆了,为什么感觉C那么无厘头[发怒][发怒]排名:25thA.GamewithBoard题目描述:Alice和Bob玩游戏,他们有一块黑板。最初,有\(n\)个整数\(1\)。Alice和Bob轮流操作,Alice先手。轮到时,玩家必须在棋盘上选择几个(至少两个)相等的整数,擦除它们,然后写一个......
  • Codeforces 1852A Ntarsis' Set 题解
    题目传送门:Codeforces1852ANtarsis'Set题意给定一个集合,里面初始有\(1,2,3...10^{1000}\),告诉你每天会拿掉其中的第\(a_1,a_2,a_3...a_n\)个,询问这样的\(k\)天之后剩下的最小的数是多少。分析思考如果\(x\)在这天没有被删掉,那么哪些被删掉的位置会对它产生什么......
  • Codeforces Round 886 (Div. 4) D - H
    D.BalancedRoundProblem-D-Codeforces双指针,贪心题意:​ 给出\(n\)个数,我们可以删去其中若干个数,使得删完后的数重新排列任意相邻的数之差绝对值不超过\(k\),输出最小删去数的个数思路:​ 很明显可以先将给出的数组进行排序。对于排序后的数组,我们可以将其分为若干个相邻......
  • CodeForces 725F Family Photos
    洛谷传送门CF传送门不错的贪心题。我们考虑一对照片只有一张的情况。那么先后手会按照\(a+b\)降序取。因为若\(a_i+b_i\gea_j+b_j\),变形得\(a_i-b_j\gea_j-b_i\)且\(b_i-a_j\geb_j-a_i\),所以对于双方先取\(i\)一定是不劣的。回到原题,如果\(a_{i......
  • Codeforces Round 887 (Div. 2) A-D
    CodeforcesRound887(Div.2)A.Desorting题意:给出一个数组,可以进行任意次以下操作:选择一个i对于数组中的a[1],a[2],...,a[i]全部+1a[i+1]...a[n]全部-1,问最小使得数组变得无序的操作是多少次Solution直接找相邻的两个数的最小的差值即可voidsolve(){ intn;cin>>n......
  • Educational Codeforces Round 71 (Rated for Div. 2)
    EducationalCodeforcesRound71(RatedforDiv.2)A-ThereAreTwoTypesOfBurgers思路:价格高的优先取#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128typedefpair<int,int>PII;typedefpair<string,int&......
  • 题解 Codeforces Round 887 (Div 1+Div 2) / CF1853AB,CF1852ABCD
    下大分!悲!Div1只过了1A!!!但还是补完整场Div2吧。A.Desortinghttps://codeforces.com/problemset/problem/1853/Aproblem用操作:\([1,i]++,[i+1,n]--\),使得数组不单调不降,求最小操作次数。\(n\leq10^5\)。solution操作等同于在差分数组上选出\(i\),做\(c_1:=c_1+1,c_i:......
  • Codeforces Round #887 Div.2 A-E
    CodeforcesRound#887Div.2一定要手玩哦前言:一定要手玩,一定要手玩!我今早一手玩发现C很TM简单,如果赛时我能切C说不定直接上1800.。。。时隔多年,我的CodeforcesRating(1718)再次超越了@cqbzlhy(1674)!!!赛时错误:B题出得太慢了->劣于pzj半小时。%%%pzjC没有手玩,瞪眼半天......
  • Codeforces Round #885 数学专场
    妙,我只能说妙。今天补DEF发现除了F诡秘的杨辉三角,我都能独立做出来。但为什么我感觉DE难度不如C!!!!A题意:一个人站在\((x,y)\)处,而其他人分别在\((x_1,y_1)\dots(x_n,y_n)\),每一次这个人先移动一步到上下左右四个格子,然后其他\(n\)个人再移动一步,求是否永远这个人与其他人不......
  • Codeforces Round 887 (Div. 2)记录
    A.Desorting如果有$a_1\leqa_2\leq\ldots\leqa_{n-1}\leqa_n$,则称长度为$n$的数组$a$已排序。Ntarsis有一个长度为$n$的数组$a$。他可以对数组进行一种操作(0次或多次):-选择一个索引$i$($1\leqi\leqn-1$)。-将$1$加到$a_1,a_2,\ldots,a_i$。-用$a_{......