专栏文章

ARC 题目选记

TTom17
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip6oqwu
此快照首次捕获于
2025/12/03 07:02
3 个月前
此快照最后确认于
2025/12/03 07:02
3 个月前
查看原文

AT_arc085_c [ARC085E] MUL

完成情况：独立做出
特点：网络流，最大权闭合子图
题解。

AT_arc085_d [ARC085F] NRE

完成情况：未独立做出
原因：DP 时只想到对于下标作转移，想不到可以通过区间作转移。
做题经验：区间选择问题，先对区间左端点或右端点排序，分别从下标角度和区间角度设计 DP。
记住：右排左扫。
特点：线段树优化 DP
先转换，变为序列元素是 −1-1 或 11，找出若干个区间使得其并集的对应元素和最大。
DP。但是是从区间的角度 DP。
按右端点排序，从右端点较小的 DP 而来。
分类讨论前一个区间和这个区间有无交集，分别写两个式子转移。线段树优化。

AT_arc083_c [ARC083E] Bichrome Tree

完成情况：独立做出但 WA
原因：背包 DP 掌握不好。01 背包要讲究 倒序DP，防止滥用转移变为完全背包。
特点：树形 DP，背包 DP
染色与染色具体是什么色无关，所以我们不需要记录根的颜色这个状态。 就是说黑白颠倒也成立。
容易知道，树形 DP 过程中，我们只关心儿子的两种颜色对应权值的和分别是多少。
由于与根相同颜色的权值就是 XiX_i，所以对于某个结点 ii 的子树的一种染色方案，我们只关心子树与 ii 不同颜色的权值和，记作 ss。
后效性即为上述。进一步地，这些权值和种类可能很多，我们考虑剪掉某些种类。
我们把所有子树内的后效性看作二元组 {xy}{x}\brace{y}，就可以写作：
{X1s1,1},{X1s1,2},⋯{X2s1,1},{X2s1,2},⋯⋯\begin{aligned} &{{X_1}\brace{s_{1,1}}} , {{X_1}\brace{s_{1,2}}} , \cdots\\ &{{X_2}\brace{s_{1,1}}} , {{X_2}\brace{s_{1,2}}} , \cdots\\ &\cdots \end{aligned}
每一行选出若干个二元组，可以交换上下两个元素的值，使得上面元素的和 ≤Xcu\le X_{cu}，此时下面元素的和算作 cucu 的一个后效性。
然后我们发现：下面的和越小越优。
原因是无论怎么交换，要么 XX 在上面，那么下面的值作为下一次的值，肯定越小越好。要么 XX 在下面。那么这一次已经可以做到最优了，也是越小越好。
（我们其实是利用 XX 不变来论证选择最小的最优性。）
推导一下，就变为一个背包问题。

AT_arc082_c [ARC082E] ConvexScore

完成情况：未独立完成。
做题经验：形如 2x2^x 的计数，变为大小为 xx 的集合的所有子集贡献之和。
还要考虑其它集合的不变量，优化组合意义推导。
特点：凸包，计数
比较经典。套路适用范围可以借鉴。
对于每一个点集形成的凸包，其价值为
2∣被包含点集∣−∣凸包点集∣2^{|被包含点集|-|凸包点集|}
求贡献和。
什么叫 2x2^x 的和？这样理解，一个大小为 xx 集合，每个元素可以选或不选，方案数就为 2x2^x。
对于每一个不在凸包上但是被包含的点集都有 11 的贡献。
上面这句话很难描述。
我们加上：每一个凸包上点集与不在凸包上但是被包含的点集都有 11 的贡献。 就是形成凸包的点集。（因为凸包唯一，所以合法。）
所以变为全集减去不能形成凸包的点集。而不能形成凸包的点集满足集合内元素共线。（包括一/两个点形成的点集）
枚举即可。

AT_arc083_d [ARC083F] Collecting Balls

完成情况：未独立完成。
原因：未仔细审题。题目上明确表示有 2n2n 个球，但是我以为球的数量是不确定的，所以导致思考的方向有问题。
特点：基环树 DP
根据我们在 BSOI 2848 【5.24NOI模拟】城市建设 的经验，我们可以既可以把边看作点，也可以把点看作边。
矩阵常常和二分图形成双射。树和偶环基环树都是二分图。
根据鸽巢原理：每个机器人与每个球一一对应。
把每个点看作是对应二分图的连边，我们要确定每个球被哪一个机器人获取，相当于在给边定向。每个机器人只能获取一个球，那么说明每个点入度恰好为 11。
为什么说它是基环树森林？
  1. nn 条边 nn 个点的图，要么是基环树森林，要么必然存在一个连通块使得其边数 ≥\ge 点数。不存在定向方案。
  2. 手玩数据可知，一定不存在两个矩形拼在一起的情况。说明复杂环不是很行。
（不存在这种情况）
恰好，基环树入度为 11 的定向只有两种情况：环内顺时针和环内逆时针。环外的都指向了环中央。
定向完之后是求拓扑排序的数量。由于已经定向，那么偏序关系也很好描述，就是找到对应方向的第一个结点，并向其连边。可以证明其为内向生成树。

AT_arc096_d [ARC096F] Sweet Alchemy

特点：背包 DP 的特殊优化（复杂度优化到较小的值域上）
差分转为多重背包（注意 11 号点无限制，其他点最多选 dd 个）。
首先有一个假的贪心，直接贪心选择性价比最高的物品，能选则选。错误原因是，后面更优秀的方案，无法被前面贪心选择的方案替代。
考虑什么时候一定可以替代。考虑到每个物品的价值 ≤n\le n。 当前面选择的还剩 nn 种以上，后面选择的超过 nn 种时，直接将后面的物品用前面的物品表示。
发现这样构造方案即可：前面价值为 viv_i，后面价值为 jj。将 jj 物品减少 viv_i 个，将 ii 物品增加 vjv_j 个，这样一定合法。将后面物品往前移，性价比整体是往上移的，对应的物品所占容量变小，不劣。
考虑贪心会在哪里出现错误。考虑最优状态下，可能是在某一个后面的位置选得比较多，前面某个位置选的比较少。但是刚刚分析就可以得出，后面如果 ≥n\ge n 时，一定可以往前移而不劣。一直往前移，结束状态要么是前面达到限度了，要么后面 ≤n\le n 了。达到限度这种情况，贪心也可以得到最优状态。那我们实际上要考虑 ≤n\le n 这种情况。
贪心不能解决的最优状态，当且仅当元素选择小于等于 nn 时。 直接背包 DP，把 ≤n\le n 的情况的所有子问题最优态给算出来，然后全局最优态一定是从 ≤n\le n 的最优态拼上贪心得到的。
启示：
  1. 有时候 DP 和贪心不一定是互斥的，贪心贪不了的状态，可以转为先用 DP 钦定其某种子问题再加上另一部分的贪心。
  2. 背包考虑容量和价值，在较小的那一部分考虑，看看能否用一些其他技巧优化。
  3. 多重背包考虑二进制分组和单调队列优化。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...