各省省选
「SCOI2005」骑士精神-搜索
· ✏️ 577 words · ☕ 2 mins read

在一个 $5 \times 5$ 的棋盘上有 $12$ 个白色的骑士和 $12$ 个黑色的骑士, 且有一个空位。在任何时候一个骑士都能按照骑士的走法(它可以走到和它横坐标相差为 $1$ ,纵坐标相差为 $2$ 或者横坐标相差为 $2$ ,纵坐标相差为 $1$ 的格子)移动到空位上。 给定一个初始的棋盘,怎样才能经过移动变成如下目标棋盘: 为了体现出骑士精神,他们必须以最少的步数完成任务。


「JSOI2010」满汉全席-2-SAT
· ✏️ 488 words · ☕ 1 mins read

题意过长,概括如下:

你有 $n$ 种食材,评委 $m$ 个要求,你需要加工这 $n$ 种食材,每种从"汉式(h)“或者"满式(m)“中选择一种。每个要求用两个形如 $\text{h} x$ 或者 $\text{m}x$ ( $x$ 为一个 $1 \sim n$ 的正整数),意为第 $x$ 道菜需要用用"汉式(h)“或者"满式(m)“来进行加工,每个要求中的两个条件必须至少满足一个,每种食材最多只能用一种方式来加工。

请你判断存不存在一个合法的方式。


「HNOI2010」平面图判定-2-SAT
· ✏️ 574 words · ☕ 2 mins read

若能将无向图 $G=(V, E)$ 画在平面上使得任意两条无重合顶点的边不相交,则称 $G$ 是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图,图中存在一个包含所有顶点的环,即存在哈密顿回路。


「SDOI2014」数表-数论
· ✏️ 834 words · ☕ 2 mins read

有一张 $n \times m$ 的数表,其第 $i$ 行第 $j$ 列( $1 \le i \le n$, $1 \le j \le m$ )的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$ ,计算数表中不大于 $a$ 的数之和。


「AHOI2013」联通图-线段树分治+并查集
· ✏️ 748 words · ☕ 2 mins read

给定一个 $n$ 个点 $m$ 条边的无向连通图 $G$ 和若干个小集合 $S$,每个小集合包含 $c(1 \le c \le 4)$ 条边,对于每个集合,你需要确定将集合中的边删掉后改图是否保持联通。

集合间的询问相互独立。


「HAOI2017」八纵八横-线段树分治+线性基
· ✏️ 1518 words · ☕ 4 mins read

Anihc 国有 $n$ 个城市,这 $n$ 个城市从 $1$ ~ $n$ 编号,$1$ 号城市为首都。城市间初始时有 $m$ 条高速公路,每条高速公路都有一个非负整数的经济影响因子,每条高速公路的两端都是城市(可能两端是同一个城市),保证任意两个城市都可以通过高速公路互达。

Anihc 国正在筹划「八纵八横」的高铁建设计划,计划要修建一些高速铁路,每条高速铁路两端也都是城市(可能两端是同一个城市),也都有一个非负整数的经济影响因子。国家还计划在「八纵八横」计划建成之后,将「一带一路」扩展为「一带一路一环」,增加「内陆城市经济环」即选择一条从首都出发沿若一系列高铁与高速公路走的路径,每条高铁或高速公路可以经过多次,每座城市也可以经过多次,最后路径又在首都结束。令「内陆城市经济环」的 GDP 为依次将这条路径上所经过的高铁或高速公路的经济影响因子异或起来(一条路经过多次则会被计算多次)。

现在 Anihc 在会议上讨论「八纵八横」的建设计划方案,他们会不断地修改计划方案,希望你能实时反馈对于当前的「八纵八横」的建设计划的方案「内陆城市经济环」的最大是多少。

初始时,八纵八横计划中不包含任何—条高铁,有以下三种操作:

  • Add x y z :在计划中给在城市 $x$ 和城市 $y$ 之间建设一条高铁,其经济影响因子为 $z$ ,如果这是第 $k$ 个 Add 操作,则将这条高铁命名为 $k$ 号高铁。

  • Cancel k :将计划中的 $k$ 号高铁取消掉,保证此时 $k$ 号高铁一定存在。

  • Change k z :表示将第 $k$ 号高铁的经济影响因子更改为 $z$ ,保证此时 $k$ 号高铁一定存在。


「FJOI2015」火星商店问题-线段树分治+可持久化Trie
· ✏️ 1075 words · ☕ 3 mins read

有 $n$ 个商店,每个商店都有一个特殊商品,每个人在任何时间都可以买。第一天可能没有进货,有若干次询问,而之后的每天,都有一次进货和若干次询问,每次进货都是某个商店进了某个编号的货,每次询问都是询问在编号为 $l$ 到 $r$ 的商店中,在 $d$ 天内进的货的编号异或 $x$ 的最大值。


「SDOI2017」数字表格-数论
· ✏️ 637 words · ☕ 2 mins read

Doris 刚刚学习了 fibnacci 数列,用 $f[i]$ 表示数列的第 $i$ 项,那么: $f[0] = 0,f[1] = 1,f[n] = f[n - 1] + f[n - 2](n \geq 2)$ 。

Doris 用老师的超级计算机生成了一个 $n \times m$ 的表格,第 $i$ 行第 $j$ 列的格子中的数是 $f[\gcd(i, j)]$,其中 $\gcd(i, j)$ 表示 $i$ 与 $j$ 的最大公约数。

Doris 的表格中共有 $n \times m$ 个数,她想知道这些数的乘积是多少。

这些数的乘积实在是太大了,所以 Doris 只想知道乘积对 $1000000007$ 取模后的结果。


「SDOI2017」树点涂色-LCT+树链剖分
· ✏️ 1080 words · ☕ 3 mins read

Bob 有一棵 $n​$ 个点的有根树,其中 $1​$ 号点是根节点。Bob 在每个节点上涂了颜色,并且每个点上的颜色不同。

定义一条路径的权值是,这条路径上的点(包括起点和终点)共有多少种不同的颜色。

Bob 可能会进行这几种操作:

  • 1 x,把点 $x$ 到根节点的路径上的所有的点染上一种没有用过的新颜色;
  • 2 x y,求 $x$ 到 $y$ 的路径的权值;
  • 3 x,在以 $x$ 为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。

Bob 一共会进行 $m$ 次操作。


「BJOI2014」大融合-LCT
· ✏️ 662 words · ☕ 2 mins read

小强要在 $N$ 个孤立的星球上建立起一套通信系统。这套通信系统就是连接 $N$ 个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻,一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量。

现在,你的任务就是随着边的添加,动态的回答小强对于某些边的负载的询问。


「SCOI2016」美味-可持久化线段树
· ✏️ 721 words · ☕ 2 mins read

一家餐厅有 $n$ 道菜,编号 $1,\dots,n$ ,大家对第 $i$ 道菜的评价值为 $a_i(1 \leq i \leq n)$。有 $m$ 位顾客,第 $i$ 位顾客的期望值为 $b_i$,而他的偏好值为 $x_i$ 。因此,第 $i$ 位顾客认为第 $j$ 道菜的美味度为 $b_i\ \text{XOR}\ (a_j+x_i)$ ,$\text{XOR}$ 表示异或运算。

第 $i$ 位顾客希望从这些菜中挑出他认为最美味的菜,即美味值最大的菜,但由于价格等因素,他只能从第 $l_i$ 道到第 $r_i$ 道中选择。请你帮助他们找出最美味的菜。


「ZJOI2008」骑士-基环树+dp
· ✏️ 733 words · ☕ 2 mins read

每个骑士都有且仅有一个自己最厌恶的骑士(当然不是他自己),他是绝对不会与自己最厌恶的人一同出征的。

请你从所有的骑士中选出一个骑士军团,使得军团内没有矛盾的两人(不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况),并且使得这支骑士军团最具有战斗力。

为了描述战斗力,我们将骑士按照 $1$ 至 $n$ 编号,给每名骑士一个战斗力的估计,一个军团的战斗力为所有骑士的战斗力总和。


「JSOI2008」球形空间产生器-高斯消元
· ✏️ 487 words · ☕ 1 mins read

有一个球形空间产生器能够在 $n$ 维空间中产生一个坚硬的球体。现在,你被困在了这个 $n$ 维球体中,你只知道球面上 $n+1$ 个点的坐标,你需要以最快的速度确定这个 $n$ 维球体的球心坐标,以便于摧毁这个球形空间产生器。

提示:给出两个定义:

  1. 球心:到球面上任意一点距离都相等的点。
  2. 距离:设两个n为空间上的点A, B的坐标为$(a_1, a_2, \cdots , a_n)$ , $(b_1, b_2, \cdots , b_n)$,则 AB 的距离定义为:$dist = \sqrt{ \sum_{i=1}^{n}(a_i - b_i)^2 }$

「HNOI2007」梦幻岛宝珠-背包dp
· ✏️ 1251 words · ☕ 3 mins read

给你 $N$ 颗宝石,每颗宝石都有重量 $w_i$ 和价值 $v_i$。要你从这些宝石中选取一些宝石,保证其总重量不超过 $W$ ,且总价值最大。

请你输出最大的总价值。