Browsed by
Month: 2019年5月

ICPC2019 西安邀请赛 H. Minecraft

ICPC2019 西安邀请赛 H. Minecraft

一个 $N \times M \times H$ 的 $Minecraft$ 世界,每次操作将一个对角为 $(x_1, y_1, z_1)$ 和 $(x_2, y_2, z_2)$ 的长方体区域全部变为石头,问每次询问后石头区域的联通块数量和非石头区域的联通块数量。

ICPC2019 西安邀请赛 E.Tree

ICPC2019 西安邀请赛 E.Tree

给你一个 $n$ 个点的树,每个点上有一堆共 $a_i$ 个石子。三种操作:

1. 将从 $1$ 到 $x$ 路径上的每个点与 $t$ 取与
2. 将从 $1$ 到 $x$ 路径上的每个点与 $t$ 取或
3. 将从 $1$ 到 $x$ 路径上的每个点再加上一堆 $t$ 大小的石子堆做 $Nim$ 游戏,问是否先手必胜。

ICPC2019 西安邀请赛 J.And And And

ICPC2019 西安邀请赛 J.And And And

给你一个 $n$ 个节点的树,每条边上有一个权值 $w$ ,定义 $E(u, v)$ 为路径 $u$ 到 $v$ 的点集集合, $X(u, v)$ 为路径 $u$ 到 $v$ 的所有边的权值的异或和。问

$$\sum\limits_{u=1}^{n}{\sum\limits_{v=1}^{n}{\sum\limits_{u’ \in E(u, v)}{\sum\limits_{v’ \in E(u, v)}{[u < v][u′ < v′][X(u′, v′) = 0]}}}}$$

Codeforces 1156F Card Bag

Codeforces 1156F Card Bag

有 $n$ 个卡片,每个卡片上的数字为 $a_i$ 。每次等概率从这对卡里面抽出一个卡,假设 $x$ 为本次抽出来的卡片, $y$ 为上一次抽出的卡片,那么如果 $x < y$ 那么你就输了;如果 $x = y$ 你就获胜;如果 $x > y$ 那么比赛会继续。问你获胜的概率为多少。