Many CF games in succession are stuck in xor questions and sent in different ways. I have to make up for the handling skills in this area
Codeforces is a little slow to access, so the title link of Luogu is hung
CF1605D Treelabeling
E and s are playing a game. E is first and S is second.
Give a tree with \ (n \) nodes, and the value of the node contains each value in \ ([1,n] \).
E selects a point randomly and occupies it (point \ (u \)), S can only select the point adjacent to this point and not occupied (point \ (v \)), and these two points meet \ (u ⊕ v ≤ \ min(u,v) \)
\(⊕ \) is an XOR operation
Now give the tree to E. e wants to rearrange the values of nodes (the shape of the tree remains unchanged, but the values of nodes are exchanged) to achieve this purpose:
Maximize the number of points that can be selected in the first round. After selecting this point, E must win.
Win: if your opponent has no way to go, you will win
\(u~{\rm xor}~v\le \min(u,v) \) obviously needs to be handled. It is easy to find that it is equivalent to the highest 1 of \ (u \) and \ (V \).
Taking \ (n=7 \) as an example, we divide the values of nodes into groups according to the highest order: \ (\ {1 \}, \ {2,3 \}, \ {4,5,6,7 \} \)
Notice the fact that a tree is a bipartite graph. Because you can do secondary dyeing. Take \ (n=7 \) with \ (3,4 \) points on both sides as an example
Fill one side of \ (3 \) points with \ (\ {1 \}, \ {2,3 \} \), and \ (\ {4,5,6,7 \} \) naturally corresponds to the other side
Then we found that no matter which point we choose, the other party will lose
This construction is universal, because the size of the divided group is a pile of integer powers of 2, and there must be no more than \ (\ dfrac n2 \) points on one side, which can be exactly filled by binary splitting
#include<stdio.h>
const int N=200010;
int T,n,cnt,x,y,m[2],a[N],b[N],last[N],v[2][N];
struct node { int y,pre; }E[N<<1];
void dfs(int x,int f,int c) { // dyeing
v[c][++m[c]]=x;
for (int i=last[x]; i; i=E[i].pre)
if (E[i].y!=f) dfs(E[i].y,x,!c);
}
void fill(int x) { // Fill, x is the color with fewer points
for (int i=1,j=0; i<=m[x]; i<<=1)
if (m[x]&i) {
for (int k=0; k<i; ++k)
a[v[x][++j]]=i+k,b[i+k]=1;
}
x=(!x);
for (int i=1,j=1; i<=m[x]; ++i)
if (!a[v[x][i]]) {
while (b[j]) ++j;
a[v[x][i]]=j,++j;
}
}
int main(){
scanf("%d",&T);
while (T--) {
scanf("%d",&n),cnt=m[0]=m[1]=0;
for (int i=1; i<=n; ++i)
a[i]=b[i]=last[i]=0;
for (int i=1; i<n; ++i)
scanf("%d%d",&x,&y),
E[++cnt]={y,last[x]},last[x]=cnt,
E[++cnt]={x,last[y]},last[y]=cnt;
dfs(1,0,0),fill(m[0]>m[1]);
for (int i=1; i<=n; ++i) printf("%d ",a[i]);
putchar('\n');
}
}
CF1615D X(or)-mas Tree
Given a weighted tree with \ (n(2\le n\le2\times10^5) \) points, the weights of some edges have been determined, while others have not been determined (represented by \ (- 1 \).
Now there are \ (m(1\le m\le2\times10^5) \) pieces of information, indicating whether the weight xor and popcount on the path from \ (u_i \) to \ (v_i \) are odd or even.
Try to construct such a tree, or output no solution.
First, notice popcount. For this thing, each binary bit is equivalent, so we can try to press a number directly into a bit 0 / 1
The most direct idea is to decompose the binary system and xor put each bit together. The result is \ ({\ rm popcount}(x)\bmod 2 \).
After a brief observation, it seems that this operation is very correct. Now the problem turns to:
For a tree, the edge weight is 0 / 1, and some edge weights are unknown. Give the weight xor sum on \ (m \) paths, and try to construct a qualified tree.
At that time, I didn't think of it here, and then I sent it, rating-=114514
In fact, there is only one simple technique to consider: difference / prefix sum on the tree.
Randomly select a root node \ (root \), and make \ (a_i \) represent the weight xor sum on the path from \ (I \) to \ (root \).
Then the sum of the weights XOR on the path from \ (u \) to \ (V \) is \ (a_ ~ {\ RM xor} ~ a_v \).
Correctness: obviously, the path from \ ({\ rm LCA}(u,v) \) to \ (root \) goes twice, and the contribution offsets itself.
It's a well-known trick. I haven't heard about it until now / youl
Then, what each message gives is actually a relationship between \ (a_u=a_v \) and \ (a_ \ ne a_v \), and the edges with known weights are the same
And \ (a_i \) has only two values of 0 / 1
Write a weighted search set and it's gone
#include<stdio.h>
const int N=200010;
int T,f,n,m,u[N],v[N],w[N],a[N],fa[N];
int find(int x) {
if (fa[x]==x) return x;
int t=fa[x]; fa[x]=find(t),a[x]^=a[t];
return fa[x];
}
int _union(int x,int y,int z) { //Weighted concurrent search set
z=(__builtin_popcount(z)&1);
int fx=find(x),fy=find(y);
fa[fy]=fx,a[fy]=(a[x]^a[y]^z);
return a[fx];
}
int work() {
scanf("%d%d",&n,&m),f=0;
for (int i=1; i<=n; ++i) fa[i]=i,a[i]=0;
for (int i=2; i<=n; ++i) {
scanf("%d%d%d",u+i,v+i,w+i);
if (~w[i]) f|=_union(u[i],v[i],w[i]);
}
while (m--) {
scanf("%d%d%d",u+1,v+1,w+1);
if (~w[1]) f|=_union(u[1],v[1],w[1]);
}
for (int i=1; i<=n; ++i) find(i); //Run path compression
return f;
}
int main() {
scanf("%d",&T);
while (T--) if (!work()) {
puts("YES");
for (int i=2; i<=n; ++i)
printf("%d %d ",u[i],v[i]),
printf("%d\n",(~w[i])?w[i]:(a[u[i]]^a[v[i]]));
}
else puts("NO");
return 0;
}
CF1625D Binary Spiders
Select some numbers from the sequence \ (\ {a_n \} \), so that any logarithm \ (x,y \) satisfies \ (x~{\rm xor}~y\ge k \).
Give any scheme that meets the requirements and selects the most number, or output no solution.
Consider 01 trie.
Obviously, the higher and different numbers are independent of each other. The higher bit here refers to the binary bits above \ ({\ rm highbit}(k) \).
At most two numbers can be selected from a group with the same higher order. Just judge with 01 trie.
Pay attention to details.
#include<stdio.h>
#include<ctype.h>
#include<algorithm>
#include<map>
#define rep(i,l,r) for (int i=l; i<=r; ++i)
#define add(x) ans[++m]=x
const int N=300010;
int n,m,cnt,k,hb,x,y,f,a[N],ans[N],T[N<<5][2];
void ins(int x) { // [01 trie board] insert
x&=(1<<hb)-1;
for (int i=hb-1,p=0; ~i; --i) {
int &t=T[p][(x>>i)&1];
t||(t=(++cnt)),p=t;
}
}
int qry(int x) { // [01 trie board] query the maximum XOR sum (one number is x)
int s=0; x&=(1<<hb)-1;
for (int i=hb-1,p=0; ~i; --i) {
int t=(x>>i)&1;
if (T[p][!t]) s|=(1<<i),p=T[p][!t];
else p=T[p][t];
}
return s;
}
std::map<int,int>mp;
int read() {
int x=0; char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x;
}
int main() {
n=read(),k=read();
if (!k) {
printf("%d\n",n);
rep(i,1,n) printf("%d ",i);
return 0;
}
rep(i,1,n) mp[a[i]=read()]=i;
std::sort(a+1,a+n+1);
hb=32-__builtin_clz(k); printf("%d\n",hb);
rep(i,1,n) if ((y=a[i]>>hb)==x) {
if (f) continue;
int t=qry(a[i]);
if (t>=k) add(a[i]),add(a[i]^t),f=1; //Choose two
ins(a[i]);
}
else {
if (cnt&&!f) add(a[i-1]); //Choose one
rep(i,0,cnt) T[i][0]=T[i][1]=0;
f=0,cnt=0,ins(a[i]),x=y;
}
if (cnt&&!f) add(a[n]);
if (m<=1) return puts("-1"),0;
printf("%d\n",m);
rep(i,1,m) printf("%d ",mp[ans[i]]);
return 0;
}
CF1628C Grid Xor
Give a grid of \ (n \ times, n \), and there is a number \ (a_{i,j} \) at each point
Definition \ (B {I, J} = a {I-1, J} ~ {\ RM XOR} ~ a {I, J-1} ~ {\ RM XOR} ~ a {I, j + 1} ~ {\ RM XOR} ~ a {I + 1, J} \)
That is, the exclusive or sum of the upper, lower, left and right adjacent numbers. If it is on the edge, it will not be counted as the number crossing the boundary (or it is considered that there is a circle of 0 around the periphery)
Give \ (b \) and find the XOR sum of all numbers in \ (a \).
There are many ways to solve the magic construction problem, but I didn't expect any of them. / kk
Here is a method
Let \ (f {I, J} \) represent the number of times \ (a {I, J} \) participates in XOR. We just need to select some appropriate elements in \ (b \) and XOR them so that all \ (f_{i,j} \) are odd.
Let's scan the grid from top left to bottom right. If the current \ (f {I, J} \) is even, select \ (B {I + 1, J} \) and update the four \ (f \) values it can affect
It sounds violent. It seems that we only guarantee that the \ (f_{i,j} \) of the first \ (n-1 \) line is odd, but this construction is indeed correct
The proof needs to consider one thing: select some \ (b_{1,j} \) arbitrarily in the first line, and there must be a solution for the last \ (n-1 \) line.
Consider this option:
..X..... .X.X.... X.X.X... .X.X.X.. ..X.X.X. ...X.X.X ....X.X. .....X..
An X-matrix with an inclination of \ (45 \) degrees is constructed.
Each Are just adjacent to an even number of X.
For all positions marked with X, if \ (b_{i,j} \) is not selected, it is selected instead; If yes, change to No.
If one feasible solution is transformed as above, another feasible solution will be obtained, and the selection of the number of specific positions in the first row will change (in the figure it is \ (b_{1,3} \))
The problem must have a solution. Through appropriate transformation, we can make the first line in the case of arbitrary selection, and there is still a feasible solution.
In short, it means that you can choose the first line blindly. Anyway, you can find a solution later
Then we find that the scheme of the second line after the first line is selected blindly is certain, because when \ (f {1, J} \) is an even number, you must select \ (B {2, J} \) to remedy, and vice versa
Then the second row is also determined, and so on. All rows can be selected
According to the previous proof, this seemingly disorderly selection method must be a feasible solution
The code is very simple
code#include<stdio.h>
#define rev(x) x=(!x)
const int N=1010;
int T,n,ans,a[N][N]; bool f[N][N];
int main() {
scanf("%d",&T);
while (T--) {
scanf("%d",&n),ans=0;
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
scanf("%d",&a[i][j]),
f[i][j]=0;
for (int i=2; i<=n; ++i)
for (int j=1; j<=n; ++j)
if (!f[i-1][j])
ans^=a[i][j],
//rev(f[i-1][j]),
rev(f[i][j-1]),
rev(f[i][j+1]),
rev(f[i+1][j]);
printf("%d\n",ans);
}
return 0;
}