一个出的题

Diamondan / 2023-09-05 / 原文

T20
题意：在$2^{k+1}$ 个$[0,4^{k})$内的整数，请求出任意两个不交非空区间使得其异或和相等，无解输出$-1$
考虑生日悖论，每次随机一个区间，给他插进 map 里面，
期望随机根号值域级别（也就是 $2^{k}$），就会出现相同的异或和
部分小数据随机化效果不好，考虑暴力
code

#include<bits/stdc++.h>
#include<random>
#define endl "\n"
#define pii pair<int,int>
#define mk make_pair
#define int long long
using namespace std;
int inline read() {
	int ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')
		f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		ans=ans*10+ch-'0';
		ch=getchar();
	}
	return ans*f;
}
mt19937 rnd(19260817);
int rad(int x,int y){
	return rnd()%(y-x+1)+x;
}
int n,m,k;
const int N=1e6+5;
int a[N],sum[N];
map<int,pii > mp;
int main() {
	int T;
	cin>>T;
	srand(19260817);
	while(T--)
	{
		cin>>k;
		for(int i=1;i<=(1<<(k+1));i++)
		a[i]=read();
		for(int i=1;i<=(1<<(k+1));i++)
		sum[i]=sum[i-1]^a[i];
		if(k==0)
		{
			cout<<"1 1 2 2\n";
			continue;
		}
		if(k==1)
		{
			for(int l1=1;l1<=3;l1++)
			for(int r1=l1;r1<=3;r1++)
			for(int l2=r1+1;l2<=4;l2++)
			for(int r2=l2;r2<=4;r2++)
			if( ① )
			{
				cout<<l1<<" "<<r1<<" "<<l2<<' '<<r2<<endl;
				goto q123;
			}
			q123:
				continue;
		}
		mp.clear();
		int flg=0;
		while(1)
		{
			int l=rad(0,(1<<(k+1))),r=rad(0,(1<<(k+1)));
			if(l==r) continue;
		        if(l>r) swap(l,r);
                        int val= ② ;
			if(mp.find(val)==mp.end()) mp[val]=③;
			else if(mp.find(val)!=mp.end()&&mp[val].first!=l&&mp[val].second!=r)
			{
				int l1=l+1,r1=r;
                                int ④
				if(l1>l2) swap(l1,l2),swap(r1,r2);
				if(l2>r1) cout<<l1<<" "<<r1<<" "<<l2<<' '<<r2<<endl;
				else if(r2<r1) ⑤
				else cout<<l1<<' '<<l2-1<<' '<<r1+1<<" "<<r2<<endl;
				break;
			}
			flg++;
			if(flg>=(1<<(k+5)))
			{
				puts("-1");
				break;
			}
		}
	}
	return 0;
}

程序中①~⑤应该填写:
1.
$A.(sum[l1]\wedge sum[r1])==(sum[l2]\wedge sum[r2])$

$B.(sum[l1]\wedge sum[r1+1])==(sum[l2]\wedge sum[r2+1])$

$C.(sum[l1-1]\wedge sum[r1])==(sum[l2-1]\wedge sum[r2])$

$D.(sum[l1-1]\wedge sum[r1+1])==(sum[l2-1]\wedge sum[r2+1])$

$A.mp.find(sum[r]\wedge sum[l]) == mp.end()$

$B.mp.find(sum[r]\wedge sum[l-1]) == mp.end()$

$C.mp.find(sum[r+1]\wedge sum[l]) == mp.end()$

$D.mp.find(sum[r+1]\wedge sum[l-1]) == mp.end()$

$A.mk(l,r)$

$B.mk(l-1,r)$

$C.mk(l,r+1)$

$D.mk(l-1,r+1)$