2019年3月

Description

题目链接:UOJ 336

曾经有一款流行的游戏,叫做Infinity Loop,先来简单的介绍一下这个游戏:

游戏在一个 $n \times m$ 的网格状棋盘上进行,其中有些小方格中会有水管,水管可能在方格某些方向的边界的中点有接口,所有水管的粗细都相同,所以如果两个相邻方格的公共边界的中点都有接头,那么可以看作这两个接头互相连接。水管有以下 $15$ 种形状:

游戏开始时,棋盘中水管可能存在漏水的地方。

形式化地:如果存在某个接头,没有和其它接头相连接,那么它就是一个漏水的地方。

玩家可以进行一种操作:选定一个含有非直线型水管的方格,将其中的水管绕方格中心顺时针或逆时针旋转 $90$ 度。

直线型水管是指左图里中间一行的两种水管。

现给出一个初始局面,请问最少进行多少次操作可以使棋盘上不存在漏水的地方。如果无法达成目标,输出 $-1$。

数据范围:$1 \le n \times m \le 2000$。

- 阅读剩余部分 -

Description

题目链接:CodeChef GERALD07

大厨有一个无向图 $G$。顶点从 $1$ 到 $n$ 标号,边从 $1$ 到 $m$ 标号。

大厨有 $q$ 对询问 $L_i, R_i$。对于每对询问,大厨想知道当仅保留编号 $X$ 满足 $L_i \le X \le R_i$ 所在的边时,图 $G$ 中有多少了连通块。

注意数据可能包含自环和重边!

本题有 $T$ 组数据。

数据范围:$1 \le T \le 10 ^ 3$,$1\le n, m, q \le 2\times 10 ^ 5$,$1\le L_i \le R_i \le M$,所有的 $n, m, q$ 的和均不超过 $2\times 10 ^ 5$。

- 阅读剩余部分 -

Description

题目链接:SPOJ 16580

给定一棵 $n$ 个节点的树,每个点都有一个黑白颜色和一个点权 $w_i$。接下来进行 $m$ 次操作,操作分为如下 $2$ 种:

  • 0 u:询问和点 $u$ 相连的所有点中的最大点权,两个点 $u, v$ 是相连的当且仅当两者路径(包括 $u, v$)上的点颜色相同。
  • 1 u:反转点 $u$ 的颜色(黑色变成白色,白色变成黑色)。
  • 2 u w:将点 $u$ 的点权修改为 $w$。

数据范围:$1\le n, m\le 10 ^ 5$,$\vert w_i\vert \le 10 ^ 9$。

- 阅读剩余部分 -

Description

题目链接:SPOJ 16549

给定一棵 $n$ 个节点的树,初始状态所有点都是黑色的。接下来有 $m$ 个操作,操作分为如下 $2$ 种:

  • 0 u:询问有多少个点和 $u$ 连通,两个点是连通的当且仅当 $u, v$ 的路径上(包括 $u, v$)的点的颜色都是相同的。
  • 1 u:反转点 $u$ 的颜色(黑色变成白色,白色变成黑色)。

数据范围:$1\le n, m\le 10 ^ 5$。

- 阅读剩余部分 -

Description

题目链接:SPOJ 2939

给定一棵 $n$ 个节点的树,初始状态所有点都是黑色的。接下来进行 $q$ 次操作,操作分为以下 $2$ 种:

  • 0 i:反转点 $i$ 的颜色(黑色变成白色,白色变成黑色)。
  • 1 v:询问 $\min\{\text{dist}(u, v)\}$,其中点 $u$ 必须是白点,两个点可以相同。显然如果点 $v$ 是白色的,那么答案一定是 $0$。特殊地,如果树上不存在白点,那么输出 $-1$。

数据范围:$1\le n, q\le 10 ^ 5$。

- 阅读剩余部分 -

Description

题目链接:SPOJ 2666

给定一棵 $n$ 个节点的数,第 $i$ 条边的边权为 $c_i$,初始状态所有的点都是白色的。接下来要进行 $q$ 次操作,操作问题如下 $2$ 种:

  • C a:反转点 $a$ 的颜色(白色变成黑色,黑色变成白色)。
  • A:询问 $\max\{\text{dist(a, b)}\}$,其中 $a, b$ 都是白点(两个点可以相同)。这意味着,只要树上存在白点,则答案一定是非负整数。如果不存在白点则输出 They have disappeared.

数据范围:$1\le n, q\le 10 ^ 5$,$-10 ^ 3\le c_i \le 10 ^ 3$。

- 阅读剩余部分 -