P7973 [KSN2021] Binary Land题目描述给定一张NNN个点的图每个点有权值AiA_iAi​和价值BiB_iBi​。两个点x,yx,yx,y之间存在一条无向边当且仅当Ax xor Aymax⁡(Ax,Ay)A_x\text{ xor }A_y\max(A_x,A_y)Ax​xorAy​max(Ax​,Ay​)。你需要对于i1,2,⋯ni1,2,\cdots ni1,2,⋯n依次求出点iii所在连通块中所有点的价值和。输入格式第一行输入一个正整数NNN。第二行输入NNN个正整数AiA_iAi​。第三行输入NNN个正整数BiB_iBi​。输出格式输出NNN行第iii行包含一个整数代表点iii所在连通块中所有点的价值和。输入输出样例 #1输入 #13 2 1 1 20 30 10输出 #160 60 60输入输出样例 #2输入 #24 5 4 4 5 10 20 30 40输出 #210 20 30 40输入输出样例 #3输入 #35 1 2 1 7 11 20 10 30 100 100输出 #360 60 60 200 200说明/提示【数据范围】本题采用捆绑测试。Subtask 18 points只存在一组数据满足N8N8N8A[6,39,11,63,3,39,1,43]A[6,39,11,63,3,39,1,43]A[6,39,11,63,3,39,1,43]B[4,8,3,7,9,1,2,2]B[4,8,3,7,9,1,2,2]B[4,8,3,7,9,1,2,2]。Subtask 213 points保证N≤200N \leq 200N≤200。Subtask 310 points保证N≤2000N \leq 2000N≤2000。Subtask 44 points保证A1A2⋯AnA_1A_2\cdotsA_nA1​A2​⋯An​。Subtask 57 points保证存在非负整数kkk使得Ai2kA_i2^kAi​2k。Subtask 619 pointsAi≤212−1A_i\leq 2^{12}-1Ai​≤212−1。Subtask 739 points无特殊限制。对于所有数据1≤N≤1051 \leq N \leq 10^51≤N≤1051≤Ai≤230−11 \leq A_i \leq 2^{30}-11≤Ai​≤230−11≤Bi≤1091 \leq B_i \leq 10^91≤Bi​≤109。C实现#includebits/stdc.h#definelllonglong#defineMOD998244353usingnamespacestd;structpx{ll a,b,uid;booloperator(constpxb)const{returnab.a;}}a[100005];ll ans[100005],f[100005],sum[100005],cv[100005],n;vectorllh[30];llfind(ll x){returnxf[x]?x:f[x]find(f[x]);}voidmerge(ll a,ll b){if(find(a)find(b))return;sum[find(b)]sum[find(a)];cv[find(b)]|cv[find(a)];f[find(a)]find(b);}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(ll i1;in;i)cina[i].a;for(ll i1;in;i)cina[i].b,a[i].uidi;sort(a1,a1n);for(ll i1;in;i){f[i]i;sum[i]a[i].b;ll cnt0,now1;while(now*2a[i].a)now*2,cnt;cv[i]now;for(ll jcnt;j0;--j)if(((a[i].aj)1)0){for(autoit:h[j])merge(it,i);h[j].clear();}for(ll jcnt;j0;--j)if((cv[find(i)]j)1)h[j].emplace_back(find(i));}for(ll i1;in;i)ans[a[i].uid]sum[find(i)];for(ll i1;in;i)coutans[i]\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容