萌新袜子求助关于本题的线性做法（悬赏自提）

如题，我在做 QOJ9605（本题的线性空间版本）的时候发现了一种时空复杂度均为

\Theta(n)

的做法，询问 U 群后未能得到该做法的解释。

本题同时也是 https://ac.nowcoder.com/acm/contest/23218/F。

其中 Tony 老师的做法就是本做法。

QOJ9605 的提交记录按空间排序的前列也有。

CPP

int z=lowbit((~x[i])&(~y[i]));
x[i]=(x[i]/z+1)*z;
if(y[i]&z)y[i]|=z-1;
else y[i]=(y[i]/z+1)*z;
if(i>1) x[fa[i]]^=x[i],y[fa[i]]|=y[i];

还有另一份重写过的能做到本题最优解的代码。

CPP

int T, n, m, f[maxn], g[maxn], vis[maxn], ans; vec<int> e[maxn];
void dfs(int u, int fa) {
	vis[u] = 1;
	for (int v : e[u]) if (v != fa) dfs(v, u), f[u] ^= f[v], g[u] |= g[v];
	int x = (g[u] + 1) & ~g[u];
	f[u] &= -x, f[u] |= x; ++g[u];
}
void solve() {
	scanf("%d%d", &n, &m);
	rep(i, 1, n) f[i] = g[i] = vis[i] = 0, e[i].clear(); ans = 0;
	for (int i = 1, x, y; i <= m; i++) scanf("%d%d", &x, &y), e[x].pb(y), e[y].pb(x);
	rep(i, 1, n) if (!vis[i]) dfs(i, 0), ans ^= f[i];
	puts(ans ? "Alice" : "Bob");
}

大概是这样，其中

x

或者

f

是 SG 值，

y

或者

g

的含义本人未能得到解答。

求有没有博弈论大手子能给出一份解释或者说这个做法的题解链接/kel

萌新袜子求助关于本题的线性做法（悬赏自提）

讨论操作

回复

相关推荐

萌新袜子求助关于本题的线性做法（悬赏自提）