标签 SPOJ 下的文章

「SPOJ 16607」IE1 - Sweets

题目链接：SPOJ 16607

John 有 $n$ 个水果罐子，每个罐子都装有不同种类的糖果，第 $i$ 个罐子里有 $m_i$ 个糖果。John 决定吃一些糖果，并且打算至少吃 $a$ 个，至多吃 $b$ 个，求一共有多少种吃法。答案对 $2004$ 取模。

数据范围：$1 \le n \le 10$，$0 \le a \le b \le 10 ^ 7$，$0 \le m_i \le 10 ^ 7$。

「SPOJ 220」Relevant Phrases of Annihilation

题目链接：SPOJ 220

你是 Byteland 的国王，你的特工刚刚截获了 $n$ 条敌方的加密信息 $s_i$。你请来的密码学家声称他只能解密文本中最重要的部分，这个文字片段在所有信息中至少出现 $2​$ 次且不相交。你需要求出这个文字片段的最长长度。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 10$，$1 \le n \le 10$，$2 \le \lvert s_i \rvert \le 10 ^ 4$。

「SPOJ 16580」QTREE7 - Query on a tree VII

题目链接：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$。

「SPOJ 16549」QTREE6 - Query on a tree VI

题目链接：SPOJ 16549

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

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

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

「SPOJ 2939」QTREE5 - Query on a tree V

题目链接：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$。

「SPOJ 2666」QTREE4 - Query on a tree IV

题目链接：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$。

「SPOJ 2798」QTREE3 - Query on a tree again!

题目链接：SPOJ 2798

给定一棵 $n$ 个节点的树，初始状态每个节点都是白色的。接下来有 $q$ 次操作，操作分为如下 $2$ 种：

• 0 i：反转节点 $i$ 的颜色（白色变成黑色，黑色变成白色）。
• 1 v：询问从节点 $1$ 到 $v$ 的有向路径上第一个黑点。如果没有黑点则输出 $-1$。

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

「SPOJ 913」QTREE2 - Query on a tree II

题目链接：SPOJ 913

给定一棵 $n$ 个节点的树，第 $i$ 条边有边权 $c_i$，需要支持如下 $2$ 种操作：

• DIST a b：询问点 $a$ 和 $b$ 之间的边权和。
• KTH a b k：询问点 $a$ 到 $b$ 的有向路径的第 $k$ 个点的标号。

询问以 DONE 结束。

本题有 $T$ 组数据。

数据范围：$1\le T\le 25$，$1\le n\le 10 ^ 4$，$1\le c_i\le 10 ^ 5$。

「SPOJ 375」QTREE - Query on a tree

题目链接：SPOJ 375

给定一棵 $n$ 个节点的树，边按照输入顺序编号为 $1$ 到 $n - 1$，每条边都有一个权值 $c_i$。需要对这棵树进行若干次操作，操作分为 $2$ 种：

• CHANGE i t：将第 $i$ 条边的权值 $c_i$ 修改为 $t$。
• QUERY a b：询问从节点 $a$ 到 $b$ 的路径上的边权最大值。

询问以 DONE 结束。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 20$，$1 \le n \le 10 ^ 4$，$1 \le c_i, t \le 10 ^ 6$。

「SPOJ 10628」COT - Count on a Tree

题目链接：SPOJ 10628

你有一棵 $n$ 个节点的树，节点从 $1$ 到 $n$ 编号。每个点都有一个权值 $a_i$。现在有 $m$ 个询问，每个询问形如：

• u v k：求节点 $u,v$ 之间的路径上的第 $k$ 小权值。

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