\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

满足：

所以即需求

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} = \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

其中，

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

的期望操作数。

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} = \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} = f_{i-1,j-1}\oplus f_{i-1,j+1}

注意到，

可数学归纳法简单证明。

$O(N\log T)$

91629629

CF1455G Forbidden Value

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

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

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-10-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除

安全

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

暂无评论

十月杂题选做

十月杂题选做

十月杂题选做

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐