十月杂题选做

十月杂题选做

yzxoi

2022-10-19 (Updated: 2022-10-19)

oi

杂题选做

CF1254 P3147 [USACO16OPEN]262144 P

的右端点。

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

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{align}&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{align}

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

原文地址：https://cloud.tencent.com/developer/article/2146524