1. 小红的文章匹配
小红书的第 i 篇文章有一个点赞数 ai 。小红认为，如果两篇不同的文章满足：点赞数通过位异或运算恰好得到 k ，那么这两篇文章是相似文章，
即ai xor aj=k 。现在小红收集到了 n 篇文章的点赞数，请帮助她计算出有多少对 (i,j) 是相似文章。输入描述
第一行输入两个整数n，k(1≤n≤,0≤k≤)代表文章总数与相似文章判断值。第二行输入 n 个整数 a1,a2,...,an(0≤ai≤) 代表每篇文章的点赞数。
两数之异或
int main(int argc, char *argv[]) {
int n,k;
cin>>n>>k;
//异或是可逆的，相当于两数之和
unordered_map<int,int> m;
int res = 0;
for(int i=0;i<n;i++){
int num;
cin>>num;
if(m.count(num^k)) res+=m[num^k];
m[num]++;
}
cout<<res;
return 0;
}
2. 魔法阅览室
思维题
int w(int a,int b,int c)
{
if (a>x || b>y || c>z) return 0;
return (x-a+1)*(y-b+1)*(z-c+1);
}
int main()
{
int T;
cin>>T;
while (T--)
{
cin>>x>>y>>z>>k;
if (x>y) swap(x,y);
if (y>z) swap(y,z);
if (x>y) swap(x,y);
long long ans=0;
for (int i=1; i<=x; i++)
for (int j=i; j<=y; j++)
{
int t=k/i/j;
if (t<j) break;
if (i*j*t!=k) continue;
int s=max(w(t,i,j),w(t,j,i));
int ss=max(w(i,t,j),w(j,t,i));
int sss=max(w(i,j,t),w(j,i,t));
ans+=max(s,max(ss,sss));
}
cout<<ans<<endl;
}
return 0;
}
3. 小红的树上询问
小红有一棵由 n 个节点、 n - 1 条无向边构成的树，每条边的权值为 wi。定义树上两个点 (u,v) 的权值为，从 u 到 v 的简单路径上，全部边权的异或和，特别的，当 u 和 v 为同一个点时，权值为 0 。
小红会提出 q 次询问，每次询问要求计算有多少个点到节点 u 的权值恰好为 k 。树是指这样的一张图，其上的任意两个点都连通，且不存在环。
简单路径是指两个节点之间的一条路径，其不包含任何重复的节点。也就是说，在简单路径上，每个节点只能出现一次。
有点类似换源dp，但实际上根据异或性质直接哈希转换即可
int main(int argc, char *argv[]) {
int n,q;
cin>>n>>q;
vector<vector<pair<int,int>>> graph(n+1);
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
graph[u].push_back({v,w});
graph[v].push_back({u,w});
}
unordered_map<int,int> m;//表示所有点到点1异或距离的个数
m[0] = 1;
vector<int> dis(n+1);//所有点到点1的异或距离
function<void(int,int)> f = [&](int u,int p)->void{
for(auto e:graph[u]){
if(e.first==p) continue;
dis[e.first] = dis[u]^e.second;
m[dis[e.first]]++;
f(e.first,u);
}
};
f(1,-1);//从1节点,计算所有节点到1节点的异或距离,同时计数所有的异或距离个数
for(int i=0;i<q;i++){
int u;
long long k;
cin>>u>>k;
long long target = k^dis[u];
if(m.count(target)) cout<<m.count(target)<<endl;
else cout<<0<<endl;
}
}