大孩小孩的博客

ICPC2019 西安邀请赛 E.Tree

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

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

给你一个 $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]}}}}$$

给你一棵 $n$ 个节点的树，其中有 $m$ 个点是特殊点。至少选择一个特殊点，问有多少种选法，满足任何两个选中的特殊点之间距离不超过 $k$。

给你一个字符串 $c$ ，你可以将其中的 ‘*’ 换成任意的字符，你需要最大化字符串 $s$ 和 $t$ 在其中出现的次数的差值。

给你一个长度为 $n$ 的排列 $p$ ，问满足 $p_l + p_r = \max \limits_{i = l}^{r} p_i$ 的连续子序列 $p[l, r]$ 有多少种。

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

给你一个 $n$ 个节点的树，每条边上有权值 $0$ 或 $1$ 。问经过权值为 $1$ 的边之后不通过权值为 $0$ 的有向路径共有多少种。

给你一个 $n$ 行 $m$ 列的棋盘，从 $(1, 1)$ 走到 $(n, m)$ ，有 $k$ 个点不能经过，每次可以向上向右或者向斜上方走。问有多少走法可以走出棋盘。结果对 $59393$ 取模。

给你一个长度为 $n$ 的数列 $a$ ，保证对于所有 $1 \leq i \leq n$ 有 $a_i \leq x$ 成立，定义 $f(l, r)$ 为删除所有满足 $l \le a_i \le r$ 的数之后所剩下的数列。问使得这个数列为不下降序列的 $l, r$ 共有多少对。

你需要购买 $n$ 个物品，每个需要购买 $k_i$ 个。你每天会获得 $1 \ burle$，每个物品价值 $2 \ burles$，有 $m$ 个促销活动，其中 $d_i$ 天 $t_i$ 物品价格会变成 $1 \ burle$，问最少多少天收集齐所有的物品。