CF1257E/F

E

给出三个序列共n个元素，每个元素值为1~n且不重

一次可以把一个元素换到另一个序列中，求最少操作次数使得三个序列（可为空）分别排序后并在一起为1~n顺序

题解

(伪)神仙题

随便dp，依次考虑每个数放在那里

由于要保证最终的顺序，所以放的序列的编号要单调

f[i][0/1/2]，第i个放在0/1/2的最小操作数

code

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
using namespace std;

int a[200002];
int f[200002][3];
int n,n1,n2,n3,i,j,k,l,ans,Ans;

int main()
{
//	freopen("e.in","r",stdin);
	
	scanf("%d%d%d",&n1,&n2,&n3);n=n1+n2+n3;
	fo(i,1,n1) scanf("%d",&j),a[j]=0;
	fo(i,1,n2) scanf("%d",&j),a[j]=1;
	fo(i,1,n3) scanf("%d",&j),a[j]=2;
	
	memset(f,127,sizeof(f));
	
	f[0][0]=f[0][1]=f[0][2]=0;
	fo(i,0,n-1)
	{
		fo(j,0,2)
		{
			fo(k,j,2)
			f[i+1][k]=min(f[i+1][k],f[i][j]+(k!=a[i+1]));
		}
	}
	
	printf("%d
",min(min(f[n][0],f[n][1]),f[n][2]));
}

F

n个数，求一个x（x<=2^30-1）使得每个ai xor x二进制下一的个数相同

ai<=2^30-1

题解

折半，每边15位

设n个数最终1的个数为x，i的前15位异或后1的个数为ci

那么后15位的个数分别为x-c1,x-c2,x-c3...x-cn

差分一下变成c1-c2,c2-c3,c3-c4...，刚好与前15位的差分c2-c1,c3-c2,c4-c3...成相反数关系

处理出一边的情况，把序列取反哈希后丢到map里，再枚举另一边判断即可

code

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <map>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define mod 1145141919810ll
using namespace std;

int a[101];
int b[101];
int n,i,j,k,l,x,s1,s2;
map<long long,int> hs;
map<long long,int> :: iterator I;
long long s;

int get(int x)
{
	int s=0;
	
	while (x)
	{
		++s;
		x^=x&-x;
	}
	
	return s;
}

int main()
{
//	freopen("f.in","r",stdin);
	
	scanf("%d",&n);
	fo(i,1,n)
	scanf("%d",&a[i]),b[i]=a[i]&32767,a[i]=a[i]>>15;
	
	fo(x,0,32767)
	{
		s=1;
		fo(i,1,n)
		{
			s1=get(a[i]^x);
			
			if (i>1)
			s=(s*233+(s1-s2+233))%mod;
			
			s2=s1;
		}
		
		hs.insert(map<long long,int>::value_type(s,x));
	}
	
	fo(x,0,32767)
	{
		s=1;
		fo(i,1,n)
		{
			s1=get(b[i]^x);
			
			if (i>1)
			s=(s*233+(s2-s1+233))%mod;
			
			s2=s1;
		}
		
		I=hs.find(s);
		if (I!=hs.end())
		{
			printf("%d
",(*I).second*32768+x);
			return 0;
		}
	}
	
	printf("-1
");
}