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)\)
\(A.l2=mp[val].first,r2=mp[val].second;\)
\(B.l2=mp[val].first,r2=mp[val].second-1;\)
\(C.l2=mp[val].first+1,r2=mp[val].second-1;\)
\(D.l2=mp[val].first+1,r2=mp[val].second;\)
\(A.cout<<l1<<" "<<l2-1<<" "<<r1+1<<" "<<r2<<endl;\)
\(B.cout<<l1<<" "<<l2-1<<" "<<r2+1<<" "<<r1<<endl;\)
\(C.cout<<l1<<" "<<r1-1<<" "<<l2+1<<" "<<r2<<endl;\)
\(D.cout<<l1<<" "<<r1-1<<" "<<l2<<" "<<r2<<endl;\)
标签：wedge,val,一个,sum,int,l2,mp From： https://www.cnblogs.com/Diamondan/p/17680712.html