十月杂题选做

十月杂题选做

CF1254

P3147 [USACO16OPEN]262144 P

的右端点。

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$ 的数量。

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 的权值的差。

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

$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

满足：

所以即需求

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. 创世纪

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

表示当前点选/不选的最大值。

考虑非树边 $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}$

有转移：

其中，

其中 $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

的期望操作数。

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$ 的方案数：

的方案数，转移：

可以前缀和优化。

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

177961978

P4804 [CCC2016] 生命中的圆

段的状态，转移：

注意到，

可数学归纳法简单证明。

$O(N\log T)$

91629629

CF1455G Forbidden Value

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

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

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