【泛做】简单题选做·第二弹

感觉自己真的是菜成一团…

感觉自己其实是地地道道的「empiricist」而不是「innovators」,也就是自己似乎并不具有「Pioneering thinking」。但为什么,为什么我想从事的一切恰恰都需要「Pioneering thinking」呢…?

可能是人越缺少什么,就越向往什么吧?但是这怎么解释,我之前还不明白自己缺少什么的时候,怀抱着的对那片天空的无限憧憬呢?

人总是喜欢问没有答案的问题。因为求索总是让人感觉自己还切切实实活着在这个世界上啊。

Hide your skill from your clumsiness, make you fast in slowly.

本文共计 15 道题。

UVA1407 Caves

给定一棵 $n$ 个节点、边带权的树。$q$ 次询问,每次给定一个 $x$ ,询问从根出发走多少个点,满足走过的边权和 $<x$ 且经过的点最多。点可以重复经过,但只会被计算一次。

$n\leq 500,q\leq 10^5,x\leq 5\cdot 10^8$ 。

一个比较基础的思想是背包,但这时空显然不是背包能做的。这个地方考虑,点数只有 $500$,也就是至多只能走 $500$ 个点。于是就考虑把状态定义到点上,即 $f_{x,j}$ 表示以 $x$ 为根走了 $j$ 个不同的点的最小代价。注意到由于可以重复经过,所以多记一维 $0/1$ ,即 $f_{x,j,0/1}$ 表示以 $x$ 为根走了 $j$ 个不同的点,最终没回到/回到了 $i$ 的最小代价。考虑转移:

其中第二个转移表达的是这条路径的终点是否在以 $y$ 为根的子树内。注意转移的时候要倒序枚举 $j$ ,保证当前转移不重复。

发现 $f_{root}$ 显然是单调的,于是回答询问时二分即可。复杂度 $O(n^2+q\log n)$ 。因为好像有证明,这种东西的复杂度是 $O(n^2)$ 的…

BZOJ4160 Exclusive Access 2

给出 $n$ 个点 $m$ 条边的无向图,定向得到有向无环图,使得最长路最短。

$1\leq n ≤ 15, 1\leq m ≤ 100$ .

大概是 $\rm dilworth$ 定理的应用,考虑 $\rm dilworth$ 定理:

令 $(X,≤)$ 是一个有限偏序集,并令 $m$ 是反链的最大长度。则 $X$ 可以被划分成 $m$ 个但不能再少的链。 即:链的最少划分数 $=$ 反链的最长长度.。

同时也存在对偶定理:

令 $(X,≤)$ 是一个有限偏序集,并令 $r$ 是其最长链的大小。则 $X$ 可以被划分成 $r$ 个但不能再少的反链。

也就是:

偏序集能划分成的最少的全序集个数等于最大反链的元素个数

其中「全序集」指的是这样的一个偏序集 $(Y,\leq )$ ,改偏序集内部所有元素两两均可比。反链则指的是这样一个偏序集 $(Z,\leq )$ ,改偏序集内部所有元素两两均不可比

换言之,假设给原图定向,那么根据 dilworth 定理,最长链的长度就是最小的独立集的大小,其中「独立集」的定义为原无向图中距离大于 $1$ 的两个点可以组成一个独立集(不考虑连通性),因为只要两者没有边相连,两者的关系就是「不可比」。

于是这东西就可以状压了。$f_{s}$ 表示 $s$ 集合中最少有多少个独立集。这东西就可以先预处理一下每个 $s$ 是否是独立集,然后 $3^n$ 暴力 $dp$ 即可。

POJ3735 Training little cats

现在给你一个长度为 $n$ 的序列,开始这个序列都是 0。对这个序列一共有三种操作:

操作 1:输入一个 $x$,把 $x$ 位置上的值 $+1$ 。

操作 2:输入一个 $x$ 一个 $y$,交换 $x$,$y$ 位置上的值。

操作 3:输入一个 $x$,把 $x$ 位置上的值变成 $0$ 。

我们接着对这个序列进行 $k$ 次操作。

我们把这 $k$ 次操作叫做一轮,现在这个 $k$ 个操作进行了 $m$ 轮。

输出最后的序列。

$1\leq n\leq 100,1\leq k\le 10^4,1\leq m\leq 10^9$ 。

…矩阵快速幂神题 sto

考虑一开始把这个空的序列记作一个 $n+1$ 维向量 $A:[1,0,0\cdots,0]$ 。其中第一维留空赋值为 $1$ ,$2\sim n+1$ 分别代表序列的第 $1\sim n$ 号元素。

那么考虑由于 $m$ 比较大,但是每次操作都是一样的,于是启发要用矩阵快速幂。

考虑三个操作,以下默认右乘转移矩阵 $T$ 、位置 $p,q$ 都是原序列右移一位的位置。

1、位置 $p$ 的数 $+1$ 。

考虑对于 $n+1$ 阶单位矩阵

考虑如何使得乘上这个矩阵的某个变形之后,位置 $p$ 实现 $+1$ 。考虑矩阵运算的本质是 $c_{i,j}=\sum_{k}a_{i,k}\cdot b_{k,j}$ ,那么 $A’_{1,p}=\sum _{i=1}^{n+1}A_{1,i}\cdot T_{i,p}$ ,因为 $A_{1,1}$ 恒定为 $1$ ,所以可知应该让 $T_{1,p}=1$ 实现 $+1$ 的功能。比如 $p=2$ :

2、交换位置 $p,q$ 的数。

还是考虑 $n+1$ 阶单位矩阵。观察矩阵乘法本质,$A’_{1,q}=\sum_{i=1}^{n+1}A_{1,i}T_{i,q}$ ,那么一方面要让之前 $q$ 位置的数消失,一方面又要让 $A’_{1,q}=A_{1,p}$ ,于是应该让 $T_{q,q}=0,T_{p,q}=1$ 。 即如果 $p=1,q=2$ ,则应该是:

3、位置 $p$ 的数清零。

…$T_{p,p}=0$ 就好了。

注意到上面都是单独进行一个操作的情况。如果出现多个操作冗杂在一起,那么一方面可以建 $k$ 个转移矩阵,每次新的转移矩阵要乘上之前的矩阵,这样复杂度就是 $O(n^3k+n^3\log m)$ 。有点爆炸。

注意到可以把这 $k$ 次操作都放到一个转移矩阵里面,第 $2,3$ 操作就要相应发生改变,$2$ 操作就需要对换 $T$ 的 $p$ 列和 $q$ 列,$3$ 操作则需要把 $p$ 这一列全部清零。这样复杂度就是 $O(nk+n^3\log m)$ 了, 可以通过本题。

但其实 $n$ 可以出到 $2000$。注意到本题中最多只有 $O(n)$ 个不为零的位置。所以只需要对这些位置做矩阵乘法即可。复杂度变成了 $O(nk+n^2\log m)$ 。

哦,poj 上多组数据,那没事了(

UVA1437 String painter

给定一个串 $s$ 和一个目标串 $t$。每次可以将 $s$ 的连续一段刷成一个同一个字符。求最少多少次操作使得 $s$ 变成 $t$ 。

$1\leq |s|,|t|\leq 500$ 。

一开始的错误思路:考虑如果两个对应位置的字符相同,那么就可以把这对字符删掉不需要管,剩下的 $s$ 就可以看做空串。对这个进行 $dp$ ,$f_{i,j}$ 表示刷好了区间 $[i,j]$ 内字符的最小代价,每次转移考虑如果 $i$ 和 $j$ 相同就从 $f_{i+1,j}$ 或者 $f_{i,j-1}$ 转移过来之类的…反正很乱很乱很乱…

写了一发之后发现挂了。理了理思路,发现首先有个错误的点,即不一定「删掉不管」是最优的,可能相同的字符会先被覆盖然后再涂上。所以这个思路本来就是错的。之后再考虑,以 $1$ 为步长转移本身没有道理,因为转移时枚举一个子状态,要枚举一个可能存在的确定量。

所以设 $f_{i,j}$ 表示一个空串的 $[l,r]$ 刷成 $t[l…r]$ 的最少代价。转移时考虑枚举一个和 $l$ 或 $r$ 同色的端点 $k\in[l,r]$ 分成两个子问题即可。之后考虑如何把 $s$ 刷成 $t$ 。设 $g_i$ 表示 $s[1…i]$ 刷成 $t[1…i]$ 的最小代价。考虑比起一个空串,$s$ 中可能存在某些与 $t$ 对应相等的位置。这时只要 chkmax(g[i], g[i - 1]) 即可。为了保证转移全面,直接枚举断点转移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (int i = 1 ; i <= n ; ++ i) f[i][i] = 1 ;
for (int len = 1 ; len < n ; ++ len)
for (int i = 1 ; i <= n - len ; ++ i){
j = i + len ; f[i][j] = f[i][j - 1] + 1 ;
for (int k = i ; k <= j - 1 ; ++ k)
if (t[j] == t[k])
chkmin(f[i][j], f[k + 1][j - 1] + f[i][k]) ;
}
for (int i = 1 ; i <= n ; ++ i){
g[i] = f[1][i] ;
chkmin(g[i], s[i] == t[i] ? g[i - 1] : P) ;
for (int k = 1 ; k <= i ; ++ k)
chkmin(g[i], g[k - 1] + f[k][i]) ;
}
//为什么总是学不会?

UVA1427 Parade

有一个由 $n+1$ 条横向路和 $m+1$ 条竖向路构成的网格图,每条横向路有一个高兴值和经过的时间。

现在想从网格的最下方走到最上方,求能得到的最大的高兴值是多少。

走路有限制:不能多次经过同样的路,也不会从下往上走。另外,在每条横向路上所花的时间不能超过 $k$ 。

$1\leq n\leq 100,1\leq m\le 10^4$ 。

一开始想的是直接暴力 $dp$,枚举每一行的每个出发点(即从上一行转移过来的点),考虑向左走一定是走一个包含当前点的最大子段和,向右也是。然后一开始觉得这个思路很有道理,但有点疑惑:我把 $n$ 和 $m$ 读反了,导致我以为这个做法是 $n^2m$ 没准可以卡过去的…后来发现是 $m^2n$ …虽然 $n^2m$ 也必定过不去就是了。

后来想了想,大概可以定义一个比较靠谱的状态。$f_{i,j}$ 表示到达了 $(i,j)$ 的最大高兴值。那么每次转移可以定向,从右边或者从左边。注意到由于存在 $k$ 的限制,决策区间具有单调性。所以可以用单调队列优化掉一个 $m$ 。

好像很简单的样子…但是不能一眼 A 就是罪过吧…

UVA11795 Mega Man’s Mission

洛克人最初只有一种武器 “Mega Buster”(这种武器可以消灭特定的一些机器人),你需要按照一定的顺序消灭 n 个其他机器人。每消灭一个机器人你将会得到他的武器(也可能没有得到武器),而这些武器可以消灭特定的机器人。你的任务是计算出消灭所有机器人的顺序总数。注意:一个机器人的武器可能可以消灭自己,但这对最终答案没有影响,因为必须先消灭这个机器人才能够得到他的武器。

$1\leq n\leq 16$ 。

其实是很水的题…只是记录一个坑点。遇到这种求顺序总数的时候,我大脑总会选择性宕机…准确来说,显然这题是要预处理一个 $g_s$ 表示杀死 $s$ 中的怪物后可以获得那些武器。然后考虑 $f_s$ 表示杀死 $s$ 中的怪兽的顺序总数。对于 $f$ 的转移,我一开始是想的是要首先枚举每个元素,再去枚举这个元素第几个出现合法,但是这就需要再记一个其他元素的顺序,然后就爆炸了。

这也反映了自己并没有理解认真理解 $dp$ 子问题重叠的本质。考虑如何简化子问题。发现无论以什么顺序转移,最后一个加进去的元素是固定的(感性理解)。或者换句话说我们并不关心某个元素 $x$ 在集合内第几个出现,这些状态都可以合并到集合较小时 $x$ 最后一个加入的状态。所以只需要枚举最后一个元素+判断合法性即可。

菜成一坨,GGGGGGGGG。

UVA1625 Color Length

输入两个长度分别是 $n$ 和 $m$ 的颜色序列,要求按顺序合并成同一个序列,即每次可以把一个序列开头的颜色放到新序列的尾部。

记 $L(c)$ 为关于颜色 $c$ 和合并之后的排列的一个函数,定义如下:

你的任务是找一种合并方式,使得所有 $L(c)$ 的总和最小。

$1\leq n,m\leq 5000$ 。

考虑朴素的状态当然是 $f_{i,j}$ 表示 $A$ 合并到位置 $i$,$B$ 合并到位置 $j$ 的最小总和…等下,似乎这东西并不可以很好的转移,因为考虑对于每个前驱状态,并不是很好记录每个颜色第一出现的位置,同时也不好维护最后出现的位置,根本没法转移。

考虑一个 trick,提前计算贡献。即虽然其余的都很麻烦,但是可以比较方便地知道有哪些颜色一定没有合并完。所以可以每次转移时,计算还没有合并完的贡献。这样做本质上是把贡献分摊到每个元素上面。因为考虑这种转移,对于每个终止状态,并不关心前面代价转移的形式,只关心代价转移的结果。

于是就预处理一个 $g_{i,j}$ 表示 $A$ 合并到位置 $i$,$B$ 合并到位置 $j$ 时有多少个字母还没有闭合。剩下的 $nm$ 转移即可。

UVA1218 Perfect Service

一个网络中有 $n$ 个节点,由 $n-1$ 条边连通,每个节点是服务器或者客户端。如果节点 $u$ 是客户端,就意味着 $u$ 所连接的所有点中有且仅有一台服务器。求最少要多少台服务器才能满足要求。

$1\leq n\leq 10^6$ 。

这题比较水,主要是整理一下,给自己提个醒。如果设 $f_{x,0/1}$ 表示 $x$ 当根不选/选自己的话,注意到会出现 $f_{son_x,0}$ 没法转移到 $f_{x,1}$ 这种情况,因为不知道 $son_{son_x}$ 选没选。这种定义状态的方式就过于模糊。

于是考虑因为难以记儿子,所以记父亲。$f_{x,0/1/2}$ 分别表示「$x$ 和 $fa_x$ 都没选」、「$x$ 选了 $fa_x$ 不管(因为选不选都不引起冲突)」、「$x$ 没选 $fa_x$ 选了」,于是就是:

注意到,其中 $f_{x,1}$ 这个状态,本质上是两个状态的合并。可以考虑分裂成 $f_{x,3/4}$ 表示 $x$ 选了 $fa_x$ 选没选,发现被转移的时候,两者转移是一样的。所以就可以简并成一个状态。

UVA12099 The Bookcase

有 $n$ 本书,每本书有一个高度 $h_i$ 和一个宽度 $w_i$。 现在要构建一个 $3$ 层的书架,你可以选择将 $n$ 本书放在书架的哪一层。设 $3$ 层高度(每层书的最大高度)之和为 $h$,书架总宽度为 $w$,要求 $h×w$ 尽量小。

$3\le n\leq 70,1\leq h_i\leq 300,1\leq w_i\le 30$ 。

本质上是要最优化两样东西,宽度和高度。所以不妨让其中一个变得有序,所以考虑先按照 $h_i$ 把所有书降序排序。

考虑如何设计状态。发现如果某一层有最高的那本书,那么无论怎么放书,这一层的高度都不会再受影响;同时,把每一层的高度和宽度都记下来是没有必要的,于是可以记某一维为某个确切数值时另一维的最小值。具体的,$f_{i,j,k}$ 表示考虑了前 $i$ 本书,第二层的宽度为 $j$,第三层宽度为 $k$ 时,第二层、第三层的最小高度和。此处记宽度为状态是因为一方面高度和宽度是对称的,另一方面宽度的数据范围显然比高度要小。

考虑转移。首先应该定一个顺序,比如第二层高度应该大于第三层,那么此时转移有:

其中第三个决策当且仅当第二层已经有了一本书。

考虑这样 $dp$ 的复杂度,似乎是 $O(n\cdot \left(\sum w_i\right)^2)$ ,有点爆炸。考虑如何剪枝:

1、$j+k\leq \sum_{t=1}^iw_t$ 。

2、$\sum_{t=1}^iw_t-j-k+30\geq j,j+30\geq k$。

其中第一可行性个比较好理解,第二个最优性剪枝是在说,因为 $\max\{w_i\}\leq 30$,所以如果高层的宽度比低层的宽度 $+30$ 还要大,那么不妨将几本书放到低层,可知这样放一定不会使结果更劣。

这么一波剪枝之后似乎就跑的飞快了…似乎是要滚一下第一维的样子。

大概转移and初始赋值这些会有一点细节的样子吧。

UVA10559 Blocks

有 $n$ 个带有颜色的方块,没消除一段长度为 $x$ 的连续的相同颜色的方块可以得到 $x^2$ 的分数,让你用一种最优的顺序消除所有方块使得得分最多。

$1\leq n\leq 200$ 。

大概是比较神仙的 $dp$ 了吧…

第一感觉肯定就是 $f_{l,r}$ 嘛,但是这么做的话本质上就变成贪心了,因为可能转移时,$f_{l,k}$ 和 $f_{k,r}$ 是消掉中间一部分,再合并起来的模式。注意到,对于一段 $i,j$,假设 $i<q<j$ 满足 $q\sim j$ 同色,$i<o<p<q$ 满足 $o\sim p$ 与 $q\sim j$ 同色,那么一种决策就是把这两段合并。但是注意到可能还会存在一个区间 $i<s<t<o$ 满足 $s\sim t$ 和 $o\sim p$ 同色。

于是这就启发(个鬼,这怎么可能想得出来)要多记一维状态 $d$,即 $f_{l,r,d}$ 表示 $l\sim r$ 的这段区间内,区间右侧还有 $d$ 个元素和 $r$ 同颜色时的最大得分。这样每次就以「和右端点颜色相同的颜色段」为子决策进行转移。那么需要枚举每次有多少个块和右端点一起删掉,在这基础枚举一个和右端点同色的、靠左的点进行转移,表示右端点所在的同色段暂时先不删,加入继续向左延伸的长同色段的一部分。

复杂度的话,状态是 $O(n^3)$ 的,然后我这种写法好像很迷幻,我觉得应该是 $n^5$ 但不知道为什么测出来极限数据(即所有颜色都相同)时运算量在 $n^4$ 量级 …剪枝是要剪的,每次只关心和 $r$ 同色的元素就好了。

好的,我又重新写了一下测了一下,觉得应该把访问记忆化结果也算 $1$ 次运算。发现 $100$ 个相同的颜色放在一起,这么写的运算量大概是 $258712510\approx2.6\cdot 10^8$,大概 $1s$ 内是可以跑出来结果的(uoj custom test 900ms左右)。$200$ 个颜色相同的就已经是紫荆花之恋那题跑不出来的程度了(即 $14s$ 以内跑不出来,只能本地测试),似乎足足要 $1\min+$,大概是 $8136350020\approx8\cdot 10^9$ 的运算量中间可执行文件还一度被系统给 kill 掉了

然后…然后我就加了一个好像很牛逼的剪枝,大概就是判断一下 $l\sim r$ 这一整段是不是同色,如果是的话就直接算完了返回即可。发现这样之后极端数据就应该是只有两种颜色然后左右交替这种,就可以在 $370\sim400ms$ 左右跑出来但似乎应该还是过不了,因为极限可以有15组数据,每组都这个速度肯定跑不进3s鸭

然后发现这个某个区间是否同色可以预处理,然后就预处理了一下,发现一组快的话只需要 $320ms$ 左右了…

然后又改了一下,发现可以稍微贪一下,「枚举每次有多少个块和右端点一起转移走」显然是最大的那个快最好了。但这并没有快…

删了点重复计算和冗杂判断…发现大概是稳定在 $320ms$ 左右了…

…发现自己是个弟弟,如果要把右边和左边合并的话,那肯定是全都一起合并最优。所以现在大概是真正的 $O(n^4)$ 算法了?一组大概是 $200ms$ 左右了…人艰不拆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//版本1 最大点 400ms
bool check(int l, int r){
for (int i = r, j = lst[r] ; i >= l ; j = lst[j], i = lst[i])
if (i != j + 1) return 0 ; return 1 ;
}

int solve(int l, int r, int t){
if (l > r) return f[l][r][t] = 0 ;
if (f[l][r][t]) return f[l][r][t] ;
if (l == r) return f[l][r][t] = (t + 1) * (t + 1) ;
if (check(l, r)) return f[l][r][t] = (t + r - l + 1) * (t + r - l + 1) ;//剪枝 1
for (int i = r ; i >= l && base[i] == base[r] ; -- i){
chkmax(f[l][r][t], solve(l, i - 1, 0) + (t + r - i + 1) * (t + r - i + 1)) ;
for (int j = lst[i] ; j >= l ; j = lst[j])
if (base[j] == base[r])
chkmax(f[l][r][t], solve(j + 1, i - 1, 0) + solve(l, j, r - i + 1 + t)) ;
}
return f[l][r][t] ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//版本2 最大点 320- ms
int solve(int l, int r, int t){
if (l > r) return f[l][r][t] = 0 ;
if (f[l][r][t]) return f[l][r][t] ;
if (l == r) return f[l][r][t] = (t + 1) * (t + 1) ;
if (g[r] <= l) return f[l][r][t] = (t + r - l + 1) * (t + r - l + 1) ;
chkmax(f[l][r][t], solve(l, g[r] - 1, 0) + (t + r - g[r] + 1) * (t + r - g[r] + 1)) ;
for (int i = r ; i >= g[r] ; -- i){
register int pq = t + r - i + 1 ;
for (int j = lst[i] ; j >= l ; j = lst[j])
chkmax(f[l][r][t], solve(j + 1, i - 1, 0) + solve(l, j, pq)) ;
}
return f[l][r][t] ;
}

int main(){
cin >> T ; Q = T ;
while (T --){
n = qr() ;
memset(f, 0, sizeof(f)) ;
memset(buc, 0, sizeof(buc)) ;
memset(lst, 0, sizeof(lst)) ;
printf("Case %d: ", Q - T) ;
for (int i = 1 ; i <= n ; ++ i)
lst[i] = buc[base[i] = qr()], buc[base[i]] = i ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = i ; j >= 1 ; -- j)
if (base[i] == base[j]) g[i] = j ; else break ;
cout << solve(1, n, 0) << '\n' ;
}
}
1
2
3
4
5
6
7
8
9
10
11
//版本3 200- ms 左右 此时根本不需要判整段是否相同
int solve(int l, int r, int t){
if (l > r) return f[l][r][t] = 0 ;
if (f[l][r][t]) return f[l][r][t] ;
if (l == r) return f[l][r][t] = (t + 1) * (t + 1) ;
//if (g[r] <= l) return f[l][r][t] = (t + r - l + 1) * (t + r - l + 1) ;
chkmax(f[l][r][t], solve(l, g[r] - 1, 0) + (t + r - g[r] + 1) * (t + r - g[r] + 1)) ;
for (int j = lst[g[r]] ; j >= l ; j = lst[j])
chkmax(f[l][r][t], solve(j + 1, g[r] - 1, 0) + solve(l, j, (t + r - g[r] + 1) )) ;
return f[l][r][t] ;
}

UVA1380 A Scheduling Problem

给定一棵树,pks把其中某些边改成了有向边。现在要求把所有边都改成有向边,求最长链的长度最小值。

$1\leq n\leq 200$ 。

考虑首先,对于这种带方向性的计算链长,在树上一般都是要分成两部分做。于是不妨令 $f_i$ 表示从 $i$ 开始,到 $i$ 子树中的某个点结束的最长链,令 $g_i$ 表示到 $i$ 结束,起点是子树内某个点的最长链。然后开始分类讨论,设当前点为 $x$ :

1、如果对于某个 $x$ ,该点与所有儿子的连边均为有向边,那么:

那么就是比较朴素的转移。

2、如果存在某个 $y\in son(x)$ ,$(x,y)$ 是无向边,那么:

那自然是再分类讨论这条边重定向成 $x\to y$ 还是 $y\to x$ 。但…这样做毕竟是 $2^{\mathrm{count}(son(x))}$ 的,如果一棵树全都是无向边那人就没了。

考虑观察一点更深刻的性质。发现如果对于某个 $y$ ,被定向成了 $y\to x$ ,那么考虑对于其他 $g_z<g_y$ 的 $(x,z)$ 未定向的 $z\in son(x)$ ,一定是要定向成 $z\to x$ 的。原因是,定向成 $z\to x$ 对当前没有任何贡献,因为边不带权,且 $y$ 转移过来一定更优;同时 $z\to x$ 对另一边的 $f$ 的转移没有任何贡献。综上,这样做一定不会使得结果更劣。

那么就可以考虑,一开始用 vector<int> 将所有无向边连接的儿子给 push_back 进来。对于 $f$ 和 $g$ 分别处理。这个地方需要注意到题目中有个定理:

假如 $\rm G$ 是一棵树,那么需要的天数是 $k$ 或 $k+1$ 。$k$ 满足:$k$ 是 $\rm G$ 中所有链中一条链能包含的最多顶点数。

链的定义:在一条路径 $ P=(x_1, x_2, …, x_k)$中 ,对于任意的 $i=1,2,…,k-1$,总有一条从 $x_i$ 指向 $x_{i+1}$ 的有向边。

但其实这个定理也可以没有用。因为只需要在外层套一个二分就好了。·

这提示我们只关心最长链是否 $>k$,而不关心是否真的被最小化了。也就是说,我们致力于保证 $f$ 和 $g$ 是最优的,但是不用考虑 $f$ 和 $g$ 怎么合并——因为这个地方,可能会出现最优化 $g$ 和 $f$ 的时候,对于一条无向边被用了两次。但这并不重要,因为可能存在这么一个局面, $f_x$ 此时没有被最优化,$g_x$ 也没有被最优化,但是 $f_x+g_x\leq k$ 并且两者的决策不相交——这就可以保证至少在 $x$ 这里 $k$ 是合法的。那么就考虑在排完序扫两遍的过程中记录贡献即可。

注意一个问题,由于这个状态记录的不是子树的最大值(当然也可以多记一个这个),所以如果中有以某点为根,路径长度 $>k$ 的,需要将这个信息向上传导。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
bool read_in(){
int u, v ; char w ;
res = cnt = ans = 0 ;
bool ret = 0 ; n = 0 ;
memset(fa, 0, sizeof(fa)) ;
memset(head, 0, sizeof(head)) ;
while (std :: cin >> u){
if (!u) return ret ;
ret = 1, n = std :: max(u, n) ;
while (scanf("%d%c", &v, &w) && v){
fa[v] = u ; n = std :: max(n, v) ;
if (w == 'd') add_e(u, v, 2), add_e(v, u, 1) ;
else if (w == 'u') add_e(u, v, 1), add_e(v, u, 2) ;
else add_e(u, v, 0), add_e(v, u, 0) ;
}
}
return ret ;
}
void dfs(int x, int fa, int len){
ans = std :: max(ans, len) ;
for (int k = head[x] ; k ; k = next(k))
if (to(k) != fa && val(k) == 2) dfs(to(k), x, len + 1) ;
}

bool comp_f(const int & x, const int & y){ return f[x] < f[y] ; }
bool comp_g(const int & x, const int & y){ return g[x] < g[y] ; }

bool do_dp(int x, int fa){
// cout << x << '\n' ;
f[x] = g[x] = 0 ;
int F, G, df, dg ;
for (int k = head[x] ; k ; k = next(k)){
if (to(k) != fa){
if (!do_dp(to(k), x)) return 0 ;
if (!val(k)) son[x].p_b(to(k)) ;
else if (val(k) > 1)
f[x] = std :: max(f[x], f[to(k)] + 1) ;
else g[x] = std :: max(g[x], g[to(k)] + 1) ;
}
}
F = f[x] ; G = g[x] ;
if (son[x].empty()) return (bool)(F + G <= ans) ;
f[x] = ans + 1 ; suf[son[x].size()] = 0 ;
std :: sort(son[x].begin(), son[x].end(), comp_f) ;
for (int i = son[x].size() - 1 ; i >= 0 ; -- i)
suf[i] = std :: max(suf[i + 1], g[son[x][i]]) ;
// debug(suf, 0, n) ;
if (F + suf[0] + 1 <= ans) f[x] = F ;
for (int i = 0 ; i < son[x].size() ; ++ i){
dg = std :: max(G, suf[i + 1] + 1) ;
df = std :: max(F, f[son[x][i]] + 1) ;
if (df + dg <= ans) f[x] = std :: min(f[x], df) ;
}
g[x] = ans + 1 ; suf[son[x].size()] = 0 ;
std :: sort(son[x].begin(), son[x].end(), comp_g) ;
for (int i = son[x].size() - 1 ; i >= -1 ; -- i)
suf[i] = std :: max(suf[i + 1], f[son[x][i]]) ;
// debug(suf, 0, n) ;
if (G + suf[0] + 1 <= ans) g[x] = G ;
for (int i = 0 ; i < son[x].size() ; ++ i){
df = std :: max(F, suf[i + 1] + 1) ;
dg = std :: max(G, g[son[x][i]] + 1) ;
if(df + dg <= ans) g[x] = std :: min(g[x], dg) ;
}
// cout << x << " " << F << " " << G << " " << f[x] << " " << g[x] << '\n' ;
return (bool)(f[x] <= ans || g[x] <= ans) ;
}
int main(){
while (read_in()){
for (int i = 1 ; i <= n ; ++ i){
if (!fa[i]) root = i ;
dfs(i, 0, 0) ; son[i].clear() ;
}
// cout << ans << '\n' ;
/*
for (int i = 1 ; i <= cnt ; ++ i)
cout << to(i) << " " << val(i) << '\n' ;
*/
res = do_dp(root, 0) ; //return 0 ;
//cout << f[i] << " " << g[i] << '\n' ;
// for (int i = 1 ; i <= n ; ++ i)
// if (f[i] + g[i] > ans){ res = 1 ; break ; }
// cout << i << " " << f[i] << " " << g[i] << '\n' ;
cout << (res ? ans + 1 : ans + 2) << '\n' ;
}
return 0 ;
}

UVA12170 Easy Climb

给出一堆山的高度 $h_i$ ,给定一个数 $d$ 。除了 $h_1,h_n$ 之外,可以任意修改山的高度,设改完之后山的高度是 $h’$,那么修改的代价是 $|h-h’|$ 。求使得任意两座相邻山峰的之间高度差得绝对值不超过 $d$ 的最小修改代价。

$1\leq n\leq 100,0\leq h_i\leq 10^9$ 。

orz又是性质题,好烦啊怎么一直不会

考虑暴力怎么做。$f_{i,v}$ 表示把 $i$ 改成了 $v$ 后前 $i$ 座山彼此之间合法的最小代价和。你发现这个 $v$ 大概是没法直接转移的…

于是考虑一个深刻的性质。对于一个 $1<i<n$ , $h_i$ 一定会被改成 $\max\{h_{i-1},h_{i+1}\}-d$ 或者 $\min\{h_{i-1},h_{i+1}\}+d$ 两者之一,如果一开始就满足性质就不用改,否则如果不满足就一定要去凑最近那个边界。类似的,考虑如果 $h_i ‘=h_{i+1}+d$ ,那么 $h_{i+1}’$ 就应该是关于 $h_{i}’$ 或者 $h_{i+2}$ 的一个带有常数个 $\mp d$ 的答案。那么这也就证明了,最终每座山都会变成某个 $h_p+q\cdot d$ 的形式,其中 $p\in [1,n]\cap\mathbb{Z_+}$,$q\in[-n,n]\cap\mathbb Z$ 。那么状态数就变成了 $O(n)\cdot O(n^2)=O(n^3)$ 个。考虑转移:

发现可以对 $x$ 这一维用单调队列。于是复杂度 $O(n^3)$ 。如果实现不精细可能会多一个 $\log$ 。注意到可以一开始把所有可能的 $x$ 值排序后存起来,这样就可以避免 map 或者 set 的滥用。

UVA1228 Integer Transmisson

在一个仿真网络中传输一个 $n$ 比特的非负整数 $k$。各比特从左到右传输,第 $i$ 个比特的发送时刻为 $i$ 。每个比特的网络延迟总是为 $0\sim d$ 之间的整数(因此从左到右第 $i$ 个比特的到达时刻为 $i\sim i+d$ 之间)。若同时有多个比特到达,实际收到的顺序任意。

求实际收到的整数有多少种 ,以及它们的最小值和最大值。

例如,$n=3$,$d=1$,$k=2$ (二进制为010)实际收到的整数的二进制可能是 001(1),010(2) 和 100(4)。

$1\leq n\leq 64,0\leq d\leq n,0\leq k\leq 2^n $。

最小值和最大值都显然可以贪心。考虑求方案数。比较直接的想法就是设 $f_{i,j}$ 表示考虑前 $i$ 个 $0$ 和前 $j$ 个 $1$ 后,组成整数的方案数。但是转移并不知道要怎么转移,因为可能上一个 $0/1$ 的出现时间不确定,导致无法判定当前在整个数最右边插入 $0/1$ 是否合法。

然后就需要洞见一个比较深刻的性质了。考虑如果希望凑出某个数 $w$ ,那么对于任意时刻,最右边那位(指被收到的最右边那一位)必然可以没有延迟 。因为即使延迟了,结果也不会更优(即也不会存在没延迟拼不出来,只有延迟才能拼出来的情况)。证明的话比较简单,因为「若同时有多个比特到达,实际收到的顺序任意」,所以如果某个比特延后至 $>$ 最右边的数接收的时间,就可以调整成等于然后重排。

于是就可以知道,假设第 $i$ 位的发送时间是 $t_i$,那么考虑如何从 $f_{i,j}$ 转移到 $f_{i+1,j}$ 和 $f_{i,j+1}$ 。观察到本质上是要求插入一个新的 $1$ 或者新的 $0$ 。那么考虑假设第 $i+1$ 个 $0$ 的发送时间是 $t_0$ ,第 $j+1$ 个 $1$ 的发送时间是 $t_1$ ,那么如果为了让 $0$ 能够被尽早接收到,就需要满足 $t_0\leq t_1+d$ ,同理如果是想要 $1$ 能够尽量早到,就需要 $t_1\leq t_0+d$ 。于是转移时判断一下即可。复杂度 $O(n^2)$ 。

代码懒得写了

UVA1628 Pizza Delivery

你是一个披萨店的老板,有一天突然收到了 $n$ 个客户的订单。

你所在的小镇只有一条笔直的大街,其中位置 $0$ 是你的披萨店,第 $i$ 个客户所在的位置为 $p_i$,如果你选择给第 $i$ 个客户送餐,他将会支付你 $e_i-t_i$ 元。其中 $t_i$ 是你到达他家的时刻。

当然,如果你到的太晚,使得 $e_i-t_i<0$ 。你可以路过他家但是不能进去给他送餐,免得他反过来找你要钱。

最大化收益。

$n \leq 100$ 。

考虑对于这种每秒代价递增的问题,一般都是代价提前计算。但是这题也不是最朴素的这类问题,因为存在可以放弃某些位置的情况。

然后就是比(我)较(又)神(不)仙(会)的状态设计环节。首先是,根据题面可知不用全部送餐,所以要把「准备送餐给ta」的人数 $k$ 放到状态里面。同时如果定义「选了某个区间内的全部数」作为状态,显然是不合适的。于是设 $f_{i,j,k,0/1}$ 表示不考虑区间 $[i,j]\cap\mathbb {Z_+}$ 内的元素,还要给 $k$ 个人送餐,当前位于 $i(0)$ 还是 $j(1)$ 的最小代价。那么最后答案就是

考虑转移。发现对于一个 $f_{i,j,k,0/1}$ 而言,必然是由一个包含 $[i,j]$ 的更大的区间 $[l,r]$ 通过切分得来的,同时为了每次只转移走一个子问题,需要 $r=j$ 或者 $l=i$ 的更大区间。于是考虑每次只转移一个点,故转移为:

然后就刷表就好了?

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int len = n - 1 ; len ; -- len)
for (int k = 0 ; k <= n - len ; ++ k)
for (int i = 1, j = i + len ; j <= n ; ++ i, ++ j){
//cout << i << " " << j << '\n' ;
for (int p = i + 1 ; p <= j ; ++ p){
chkmax(f[p][j][k + 1][0], f[i][j][k][0] + val[i] - (k + 1) * abs(pos[p] - pos[i])) ;
chkmax(f[p][j][k + 1][1], f[i][j][k][0] + val[i] - (k + 1) * abs(pos[j] - pos[i])) ;
}
for (int q = j - 1 ; q >= i ; -- q){
chkmax(f[i][q][k + 1][1], f[i][j][k][1] + val[j] - (k + 1) * abs(pos[j] - pos[q])) ;
chkmax(f[i][q][k + 1][0], f[i][j][k][1] + val[j] - (k + 1) * abs(pos[j] - pos[i])) ;
}
}

这东西看似是 $n^4$ 的,实际上跑得很快(

UVA12105 Bigger is Better

用不超过 $n$ 根火柴摆出一个尽量大的、能被 $m$ 整除的数。

$1\leq n\leq 100,1\leq m\leq 3000$ 。

大概是个套路?遇到这种被 $m$ 整除余几的,大概需要在 $\bmod m$ 的余数之间来回转移。

然后可能是因为脑子抽了,一开始设计的状态是 $f_{i,j}$ 表示用了 $i$ 根火柴,模 $m$ 余 $j$ 时可以拼出来的最大的数,然后发现最多可以有 $50$ 位,但是 __int128 也只是大概 $36\cdot 10^{36}$ 多一点,不足以记下所有可行的的数字。

然后又尝试用 string ,写了一会儿才意识到 string 自定义的比较函数是按字典…当然也可以写一个大整数类,似乎最多只会带一个 50 的常数

然后考虑这么设计不行,就只能去最小化贡献,然后手动构造了。考虑 $g_{i,j}$ 表示如果想要凑出从高到低的 $i$ 位,$\bmod m$ 余 $j$ 时最少需要用多少根火柴。转移和第一个转移…基本上差不多,刷就对了。然后考虑从第一位开始贪心地凑,注意判几次合法性就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
int n, m ;
ll f[N][M], ans ;
int num[10] = {6, 2, 5, 5, 5, 5, 6, 3, 7, 6} ;

int main(){
while (cin >> n){
if (!n) return 0 ; ans = -1 ;
cin >> m ; memset(f, -1, sizeof(f)) ;
for (int i = 0 ; i <= 9 ; ++ i) f[i % m][num[i]] = i ;
for (int j = 2 ; j <= n ; ++ j){
for (int k = 0 ; k <= 9 ; ++ k){
for (int i = 0 ; i < m ; ++ i)
chkmax(f[((i * 10) + k) % m][j + num[k]], f[i][j] * 10 + k) ;
}
}
for (int i = 2 ; i <= n ; ++ i)
chkmax(ans, f[0][i]) ; cout << ans << '\n' ;
}
return 0 ;
}*/

int n, m, T ;
int pw[N], ans[N], f[N][M] ;
int num[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6} ;

int main(){
while (cin >> n){
if (!n) return 0 ;
memset(f, 63, sizeof(f)) ;
int l = 1, r = n, mid, res = 0 ;
printf("Case %d: ", ++ T), cin >> m ;
memset(ans, 0, sizeof(ans)) ; f[0][0] = 0 ;
for (int i = 0 ; i <= n ; ++ i)
for (int j = 0 ; j < m ; ++ j)
if (f[i][j] != 0x3f3f3f3f)
for (int k = 0 ; k <= 9 ; ++ k)
chkmin(f[i + 1][(j * 10 + k) % m], f[i][j] + num[k]) ;
for (res = n + 1 ; f[res][0] > n ; -- res) ;
int p = 0, cost = n ; pw[1] = 1 ; //cout << res << '\n';
for (int i = 2 ; i <= res ; ++ i) pw[i] = pw[i - 1] * 10 % m ;
for (int i = 1 ; i <= res ; ++ i)
for (int j = 9 ; j >= 0 ; -- j){
int t = j * pw[res - i + 1] % m ;
if (num[j] + f[res - i][((m - p - t) % m + m) % m] <= cost){
cost -= num[j] ; (p += t) %= m ; ans[i] = j ; break ;
}
}
//cout << res << '\n' ;
int q = 1 ; while (!ans[q] && q < res) ++ q ;
for (int i = q ; i <= res ; ++ i) printf("%d", ans[i]) ;
if (!res) puts("-1") ; else puts("") ;
}
return 0 ;
}

注意几个细节:

1、最后数字的位数不具有可二分性,所以还是枚举吧。

2、注意可能存在前导 $0$ ,需要删掉。

总结

其实学到了许多吧?自己基础一点也不好,所以其实是把别人很早之前付出的努力,再重新付出了一遍。很遗憾,这些题目里面还是有不少无不太会做的题目…

感谢兔队的教导可以让我安心学下去:藏巧于拙,寓快于慢。只要努力,就一定会比昨天的我更优秀吧?

不过,努力和选择同样重要。希望在接下来越来越紧张的时间里面,我可以想清楚自己到底要做些什么题、要学习一些什么知识吧。加油吧!