十月杂题选做

CF1254

P3147 [USACO16OPEN]262144 P

注意到答案一定很小,设 $f_{i,j}$ 表示左端点为 $j$,能合并出数字 $i$ 的右端点。
$$
f_{i,j}=f_{i-1,f_{i-1,j}}
$$
88502520

ARC097D Monochrome Cat

需要遍历的点一定是在最小的包含白点的连通块内。

剩余的树上每个点都必须经过。因此除了起点与终点之间路径上的边会被经过恰好一次以外,其余所有边都会被经过恰好两次。

不妨先设所有边都经过了两次,若无修改每个点颜色即为初始颜色异或度数奇偶性,只需在其为白时进行一次修改操作。

然后考虑起点与终点之间的路径,它的影响是让路径上的点(包含起点但不包含终点)都被少经过一次。

容易发现,原本为白操作次数减 $2$,原本为黑色操作次数不变。

于是类似找树的直径即可。

88504488

P4183 [USACO18JAN]Cow at Large P

设 $g_i$ 为 $i$ 到最近叶子的距离。

如果 $u$ 为根,$d_i\ge g_i$ 则 $i$ 子树内仅需贡献 $1$ 即可拦截 $u$,注意到如果 $i$ 的父节点 $f_i$ 能拦截 $u$ 则没必要动用 $i$,所以我们令 $d_i\ge g_i \land d_{f_i}< g_{f_i}$。

考虑点分治,根据分治重心我们可以划分成一个点及若干子树。

考虑每个子树对子树外的贡献,以及分治重心对所有子树的贡献。

注意一下一开始钦定的限制条件,不然可能重复计算。

88502426

P6931 [ICPC2017 WF]Mission Improbable

考虑俯视图限制显然是有数的则至少要有 $1$;主视图、侧视图限制即为每行每列的最大值仍然保留。

贪心地保留每行每列的一个最大值,其余的全削减至 $1$。

注意到可以有一个数同时占行列的最大值的情况。

于是跑一次二分图匹配即可。

88937221

AGC024B Backfront

顺序显然可以随意移,最后剩下必须连续,求最长上升子序列即可。

35588799

CF1481E Sorting Books

预处理出每种颜色的最左最右位置,即求最多保留多少不移动。

设 $f_i$ 表示 $[i,n]$ 中最多有多少无需移动,$s_{i,j}$ 表示 $[j,n]$ 中,颜色为 $i$ 的数量。

$$
f_i = \max \begin{cases}
f_{i+1} & 1\leq i < n\
s_{a_i,i} & i \not = l_{a_i}\
s_{a_i,i} + f_{r_{a_i} + 1} & i=l_{a_i}
\end{cases}
$$

106631440

P5779 [CTSC2001]聪明的学生

几个结论:

  1. 如果两个相等,则另一个一定为其之和。
  2. 另两个人中较大者未能在相应的回合猜出,则其可能猜中。
  3. 最大的人一定先猜到。

设 $f_{i,a,b,c}$ 表示 $a,b,c$ 数,在第 $i$ 次是否能猜中。转移根据结论 1,2,3 即可。

89498503

CF536D Tavas in Kansas

首先从 $s,t$ 分别跑一次最短路,容易发现答案仅与其相对大小有关,因此先离散化。

容易将其抽象成一个表格,其中第 $i$ 号点位于 $(d_{s,i},d_{t,i})$,权值为 $p_i$,两人分别从 上/左 取若干 行/列。

注意到 $n\leq 2\times 10^3$,考虑 dp,设 $f_{k,i,j}$ 表示在各自最优策略下当前小 X/小 Y 先手,剩余的点为 $(i,j)$ 及其右下角范围,小 X 的权值与小 Y 的权值的差。

发现其实没必要枚举每个人取到哪一行/列进行转移,只需要一行行一列列转移时注意是否要交给对方即可。

$$
\begin{aligned}
&f_{0,i,j}\leftarrow \max { f_{0,i+1,j} , f_{1,i+1,j}}+S(i,j,i,c_1) \quad [\exists p\in [i,j,i,c_1]]\
&f_{1,i,j}\leftarrow \min { f_{0,i,j+1} , f_{1,i,j+1}}-S_{i,j,c_0,j} \quad[\exists p\in [i,j,c_0,j]]
\end{aligned}
$$

$O(N^2)$。

159692208

ARC102D Revenge of BBuBBBlesort!

被操作的点仅可能是 $a_i=i$ 的点。

显然相邻且均满足 $a_i=i$ 的两个位置无法操作,所以原序列可分为若干交替是否满足 $a_i=i$ 的子串。

每个子任务单独考虑,必须满足 $a_i$ 在可交换的区间内且需要交换的数最长下降子序列长度不能超过 $2$。

90297746

P3685 [CERC2016]不可见的整数 Invisible Integers

考虑设 $f_{S,x,xi,y,yi}$ 表示已满足的限制的状态 $S$,从右往左正在满足的是 $x$,满足到 $xi$ 位,从左往右正在满足的是 $y$,满足到 $yi$ 位,最少的元素个数。

不妨从左向右考虑,对于所有向右得到的序列 $i$,若能接在 $y$ 后面,则满足 $y$ 的剩余部分可以被 $i$ 覆盖,于是之后只需要考虑 $i$ 即可。

对于 $x$,若已被填满,对于所有向左得到的序列 $i$,若可以接上,则满足 $i$ 的接入部分可以被 $x$ 覆盖,于是之后考虑 $i$ 的剩余部分即可。

90346563

P5957 [POI2017]Flappy Bird

设 $x$ 为上升步数,$y$ 为下降步数,则从起点 $(0,0)$ 到终点 $(a,b)$ 满足:
$$
\begin{cases}
x+y=a\
x-y=b
\end{cases}
$$
所以即需求 $y_{\min}$,对于每根柱子求出范围即可。

90332163

CF1340C Nastya and Unexpected Guest

设 $f_{i,j}$ 表示第 $i$ 秒到达第 $j$ 个绝对安全至少经过多少个周期。

转移的边仅有相邻两个,于是直接 01-BFS。

$O(mg)$

176863749

CF778D Parquet Re-laying

操作可逆,考虑将起始状态与结束状态转移到一个中间的状态。

不妨设长为偶数,设构造中间状态所有地砖都是横的。

能旋转就旋转,发现一定可以转到。

176863439

P5956 [POI2017]Podzielno

容易发现 $X$ 是 $B-1$ 的倍数的充要条件是 $X$ 的各位之和是 $B-1$ 的倍数。

注意到 $a_i\ge 1$,所以只需要删除一个数即可,剩余的数从大到小排列。

注意不用删数的情况。

90466898

P5847 [IOI2005]mea

容易将 $S_{n+1}$ 用 $S_n$ 表示。

根据 $S_i\leq S_{i+1}$,可列出不等式,即可容易解得 $S_i$ 取值范围。

最终 $S_1$ 最后范围即为答案。

注意无解输出 $0$。

90469236

CF429C Guess the Tree

爆搜。

首先判掉叶子节点过少的情况,爆搜的话按照子节点数多的从大往小先摆着,之后的点考虑连到之前的点中。

可以证明这个是能过的。

176992784

P1330 封锁阳光大学

每个连通块单独考虑,分别黑白染色,取黑白中数量较小即可。

90701973

CF436E Cardboard Box

对于每个关卡,分成两类:

  • $2a_i\leq b_i$:将选两个点拆成 $a_i$ 与 $b_i-a_i$,有 $a_i < b_i - a_i$。
  • $2a_i > b_i$:另外单独考虑,按照 $b_i$ 排序,此时一定先选两个更优。

一类点直接拆散按从小到大排序选即可。

考虑枚举选一类点 $i$ 个,则剩余 $m-i$ 个点填二类点分 $m-i$ 的奇偶性判断:

  • $m-i$ 为偶数:恰好选前 $(m-i)/2$ 个两个即可。
  • $m-i$ 为奇数:选 $(m-i-1)/2$ 个两个,再加上一个一个;或选 $(m-i+1)/2$ 个两个,再将其中一个两个转为一个。

显然奇数情况记前/后缀最小/大值即可。

177110807

AcWing 359. 创世纪

在一内向基环树森林上选若干点,使每个点必有一个儿子没选,求权值和最大。

设 $f_{u,0/1}$ 表示当前点选/不选的最大值。
$$
f_{u,0} = \sum_{v\in subtree_u} \max{f_{v,0},f_{v,1}}
$$

$$
f_{u,1} =(\sum_{v\in subtree_u} \max{f_{v,0},f_{v,1}}) - (\min_{v\in subtree_u}\max {0,f[v][1]-f[v][0]} )+ 1
$$

考虑非树边 $x\rightarrow y$,有两种情况:

  • 不选 $y$,则 $x$ 无限制。
  • 选 $y$,对 $x$ 无影响,可直接将 $x\rightarrow y$ 断开。

两者取最大即可。

18236699

P2664 树上游戏

对于每个点,每种颜色,其单独答案贡献可转化为 $n-siz_{x,c}$。

其中 $siz_{x,c}$ 代表从点 $x$ 出发,不经过颜色 $c$ 的点,所构成的连通块大小。

考虑对于所有 $siz$,均挂在深度最小的节点上,之后树上差分统计即可。

若碰到与当前颜色相同的点,之后该子树将失效,贡献更新。

注意根节点父亲颜色应设为“全彩”,特殊考虑即可。

90681495

CF916E Jamie and Tree

首先求 $u,v$ 在以 $r$ 为根意义下的 lca 即为 lca(u,v)、lca(u,r)、lca(v,r) 中深度最大的点,证明不难通过讨论 $u,v$ 是否在 $r$ 子树内求得。

其次求点 $x$ 在以 $r$ 为根意义下的子树。

  • $x$ 即为 $r$:则即为整棵树。
  • $x$ 是 $r$ 的子树 或 $x$ 不是 $r$ 的祖先:则即为 $x$ 的子树。
  • 其他情况:即为 $x$ 的子节点中子树包含 $r$ 的子树。

177124474

CF432E Square Tiling

按顺序从上到下从左到右贪心,首先对该格子的限制一定是上下左右四个格子,显然该格子一定染最小的与其不同的颜色。

接下来考虑是否向右下拓展:注意到向外拓展一层的几个条件:

  • 上一行对应列点必须与其不同色。
  • 不能已经被染过不同颜色。
  • 上一行对应列点不能与其相差超过 $1$。
  • 上一行对应列点不能与其均不为 A

177130361

CF1343F Restore the Permutation by Sorted Segments

暴力枚举第一个数,再将所有限制中包含该数的删掉该数,显然从删过的限制之中会产生一个只剩一个元素的限制,于是其为第二个数。

再将所有限制中包含第二个数的删掉,循环该步骤即可。

最后判一下是否合法。

177263802

CF553D Nudist Beach

二分答案,check 先把所有都标记为能选,再将所有不合法的点依次剔除。

可以证明这一定最优。

177266621

The 2022 ICPC Asia Regionals Online Contest (I)

经过一定分析可以发现合法数很少,写个爆搜+剪枝把所有答案先跑出来,查询二分即可。

$O(?X+Q\log X)$

56740

Petrozavodsk Winter 2020. Day 8. Almost Algorithmic Contest. Problem C. StalinSort Algorithm

很容易设出一个简单的 DP,设 $f_{i}$ 表示当前子序列结尾为 $a_i$,且保证最终一定含 $a_i$,长度最大值。

设 $g_{i,j} = \min { j> i \land a_j > a_i}$。

有转移:
$$
f_j \leftarrow f_i + 1
$$
其中,$j\in [g_i,g_{g_i}) \land a_j > a_i$。

其中 $a_j>a_i$ 限制,直接按 $a_i$ 从小到大枚举即可。

线段树辅助转移。

特别注意,初始合法的点仅为 $[1,g_1]$。

$O(n\log n)$

56884

2021“MINIEYE杯”中国大学生算法设计超级联赛(6). Problem 1007. Power Station of Art

每个连通块独立,分别考虑。

根据提示,容易想到按图是否为二分图分类。

若该连通块为二分图,将该图黑白染色,两图的左黑+右白、右黑+左白数量相等,容易证明这是充要的。

若该连通块不为二分图,即其必含奇环,注意到变换之和为偶数,故黑、白点奇偶性相同,且权值集合相同,容易证明这是充要的。

56887

京都大学プログラミングコンテスト 2021. Problem F. One Yen Coin

只需要考虑 $1\times x+ 5\times y$ 即可。

贪心地想,容易发现每次只会选一个物品。

综合上述,一个代价为 $a_i$ 的物品价值为 $5\lceil \frac {a_i}5\rceil-a_i$,其新代价为 $\lceil \frac {a_i} 5\rceil$,而总新容量为 $\lfloor \frac m5\rfloor$,初始答案为 $m\bmod 5$。

注意到价值很小,可以将价值放到状态里,设 $f_{i,j}$ 表示考虑所有代价 $\leq i$ 的物品,获得价值为 $j$,所需要的最小代价。

显然其满足决策单调性,将所有代价为 $i$ 的物品抽出来排序求前缀和,转移即可。

$O(n\log n)$

56896

ABC163F path pass i

至少一个点颜色为 $k$,显然可以转化为求不含颜色 $k$ 的路径。

对于一个大小为 $s$ 的连通块,若其均不含颜色 $k$,贡献即为 $\frac {s(s+1)}2$。

对于每个点颜色 $c_x$,只需求其所有儿子的子树中不包含 $c_x$ 的连通块大小之和即可。

注意考虑与根节点颜色不同的点在根部分的答案。

35854775

CF1754E Wish I Knew How to Sort

不妨设有 $K$ 个应该是 $0$ 的位置被放到 $1$,设 $f_i$ 表示有 $i$ 个应是 $0$ 被放到 $1$ 的期望操作数。
$$
f_i=f_{i-1} + \frac {n(n-1)}{2i^2}
$$
177581574

CF1754F The Beach

显然将其转化为空位的移动,注意到最后两个相邻的空位一定会由不同的点转移过来。所以直接将所有空位丢入起点,一起跑一遍最短路即可。

注意建图是单向边。

177594371

CF1732D2 Balance (Hard version)

不妨先看 Easy Version,没有删除操作。

容易发现直接对每个询问记忆化答案,暴力往上跳复杂度是对的。

加入删除操作,考虑对每个询问跳过的点记下来,删除的话就对所有经过该点的询问打个标记。之后若询问到有标记的点,则输出标记中的最小值即可,插入的时候把对应标记删除。

这个感性理解一下,复杂度大概也是对的,因为每个询问跳的点必定是已经有过的点,所以点数是 $O(N)$ 的,总复杂度大概是两个 $\log$ 级别?
177713494

CF1732E Location

分块,对于整块修改只需暴力枚举 $\gcd$ 更新答案即可,显然这同约数一样可提前预处理。

$O(\frac nk+ K\gcd)$

177713521

CF223E Planar Graph

取一个极远的点为根,任意建一棵树。

一次询问的答案即为出环的边数-入环的边数,分别对每个点相邻两条边算贡献,注意到环内的点一定在其极角排序后一段连续的区间内。因此直接做前缀和查询即可。

注意贡献有正有负且环上点必须按照同种顺序排序,叉积判断即可。

177955681

CF1188C Array Beauty

先对 $a$ 排序,考虑转化为计算 $\min \ge c$ 的方案数:

设 $f_{i,j}$ 表示前 $i$ 个数,选了 $j$ 个,且最后一个选了 $a_i$ 的方案数,转移:
$$
f_{i,j} = \sum_{a_j-a_k \ge c} f_{k,j-1}
$$
可以前缀和优化。

而 $\min \leq \frac V {k-1}$,所以总复杂度 $O(kn)$。

177961978

P4804 [CCC2016] 生命中的圆

设 $f_{i,j}$ 表示第 $i$ 轮,第 $j$ 段的状态,转移:
$$
f_{i,j} = f_{i-1,j-1}\oplus f_{i-1,j+1}
$$
注意到,$f_{i,j} = f_{i-2^k,j-2^k}\oplus f_{i-2^k,j+2^k}$。

可数学归纳法简单证明。

$O(N\log T)$

91629629

CF1455G Forbidden Value

设 $f_i$ 表示 $x=i$ 时的最小花费。对于题目的嵌套,显然可以看作合并操作。

对于 set,$f_y = \min f_i, f_i +=v \ (i\not =y)$。

动态开点线段树+线段树合并即可。

177991542