题解
「CF750E」New Year and Old Subsequence-矩阵+线段树+dp
· ✏️ 1156 words · ☕ 3 mins read

定义一个数字串为“妙”的当且仅当:该串包含某一子序列为 $2017$ ,且不包含子序列 $2016$。

定义一个数字串的“丑值”为:该串至少删去几个字符,可以使得剩余串变“妙”;如果删去任意多个字符,均无法使该串变“妙”,则该串的“丑值”是 $-1$。

给定一个长度为 $n$ 的数字串 $s$ 。有 $q$ 次询问,每次询问用 $(l_i,r_i)$ 表示。对于每次询问,回答子串 $s[l_i…r_i]$ 的“丑值”。


「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$ 次操作。


「网络流 24 题」数字梯形-费用流
· ✏️ 735 words · ☕ 2 mins read

给定一个由 $n$ 行数字组成的数字梯形如下图所示。梯形的第一行有 $m$ 个数字。从梯形的顶部的 $m$ 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

分别遵守以下规则:

  1. 从梯形的顶至底的 $m$ 条路径互不相交;
  2. 从梯形的顶至底的 $m$ 条路径仅在数字结点处相交;
  3. 从梯形的顶至底的 $m$ 条路径允许在数字结点相交或边相交。

「网络流 24 题」软件补丁-最短路
· ✏️ 519 words · ☕ 2 mins read

某公司发现其研制的一个软件中有 $n$ 个错误,随即为该软件发放了一批共 $m$ 个补丁程序。每一个补丁程序都有其特定的适用环境,某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时,往往会加入另一些错误。

换句话说,对于每一个补丁 $i$ ,都有 $2$ 个与之相应的错误集合 $B_1(i)$ 和 $B_2(i)$ ,使得仅当软件包含 $B_1(i)$ 中的所有错误,而不包含 $B_2(i)$ 中的任何错误时,才可以使用补丁 $i$ 。补丁 $i$ 将修复软件中的某些错误 $F_1(i)$ ,而同时加入另一些错误 $F_2(i)$ 。另外,每个补丁都耗费一定的时间。

试设计一个算法,利用公司提供的 $m$ 个补丁程序将原软件修复成一个没有错误的软件,并使修复后的软件耗时最少。


「网络流 24 题」餐巾计划-费用流
· ✏️ 823 words · ☕ 2 mins read

一个餐厅在相继的 $n$ 天里,每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾。餐厅可以购买新的餐巾,每块餐巾的费用为 $P$ 分;或者把旧餐巾送到快洗部,洗一块需 $M$ 天,其费用为 $F$ 分;或者送到慢洗部,洗一块需 $n$ 天,其费用为 $S$ 分($S < F$)。

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 $n$ 天中餐巾使用计划,使总的花费最小。


「网络流 24 题」方格取数-二分图最大独立集
· ✏️ 678 words · ☕ 2 mins read

在一个有 $m \times n$ 个方格的棋盘中,每个方格中有一个正整数。

现要从方格中取数,使任意 $2$ 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。