这一题要利用xor的性质：if x^y=z, then x=y^z。
所以可以分别枚举a^b和c^d的值，并记录对应的值有多少种组合。之后遍历a^b的所有值，查找在c^d中，值为(a^b)^K的有多少种组合，相乘即可。
查找可以通过先排序，然后二分查找实现。
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include<ctype.h> #include<map> #include<time.h> #include<set> #include<bitset> #include<sstream> using namespace std; //Google APAC2017 Practice Round Problem B. Robot Rock Band const int maxn=1010; int T; int N; long long K; long long robert[4][maxn]; vector<pair<long long,long long> >axor[2];//the number of combination might exceed int long long ans=0; void calxor(int type) { int aidx=0; if(type==0) aidx=0; else if(type==2) aidx=1; map<long long,int>mp; mp.clear(); // cout<<"haha"<<endl; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { long long tmp=robert[type][i]^robert[type+1][j]; // cout<<tmp<<endl; if(mp[tmp]==0) { axor[aidx].push_back(make_pair(tmp,1)); mp[tmp]=axor[aidx].size();//start from 1 } else { axor[aidx][mp[tmp]-1].second++; } } } } bool cmp(pair<long long,int>a, pair<long long,int>b) { if(a.first==b.first) { return a.second<b.second; } return a.first<=b.first; } long long binary(long long goal) { int low=0; int high=axor[1].size()-1; int mid=(low+high)/2; bool find=false; while(low<=high) { mid=(low+high)/2; if(axor[1][mid].first<goal) { low=mid+1; } else if(axor[1][mid].first>goal) { high=mid-1; } else if(axor[1][mid].first==goal) { find=true; break; } } if(find==true) { return axor[1][mid].second; } else { return -1; } } int main() { freopen("B-large-practice.in","r",stdin); freopen("B-large-practice.out","w",stdout); scanf("%d",&T); for(int ca=1;ca<=T;ca++) { memset(robert,0,sizeof(robert)); memset(axor,0,sizeof(axor)); ans=0; scanf("%d %lld",&N,&K); for(int i=0;i<4;i++) { for(int j=0;j<N;j++) { scanf("%lld",&robert[i][j]); } } // if(ca!=10) continue; calxor(0); // cout<<"here"<<endl; calxor(2); sort(axor[1].begin(),axor[1].end(),cmp); // for(int i=0;i<axor[0].size();i++) cout<<axor[0][i].first<<" "<<axor[0][i].second<<" "; // cout<<endl; // for(int i=0;i<axor[1].size();i++) cout<<axor[1][i].first<<" "<<axor[1][i].second<<" "; // cout<<endl; for(int i=0;i<axor[0].size();i++) { long long goal=K^axor[0][i].first; // cout<<i<<" "<<goal<<endl; long long tmp=binary(goal); // cout<<tmp<<endl; if(tmp!=-1) { ans+=axor[0][i].second*tmp; } } printf("Case #%d: %lld\n",ca,ans); } return 0; }
