标签 SPOJ 下的文章
- 首页
- 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$。