ARC 题目选记

· · 个人记录

AT_arc085_c [ARC085E] MUL

完成情况：独立做出

特点：网络流，最大权闭合子图

题解。

AT_arc085_d [ARC085F] NRE

完成情况：未独立做出

原因：DP 时只想到对于下标作转移，想不到可以通过区间作转移。

做题经验：区间选择问题，先对区间左端点或右端点排序，分别从下标角度和区间角度设计 DP。

记住：右排左扫。

特点：线段树优化 DP

先转换，变为序列元素是 -1 或 1，找出若干个区间使得其并集的对应元素和最大。

DP。但是是从区间的角度 DP。

按右端点排序，从右端点较小的 DP 而来。

分类讨论前一个区间和这个区间有无交集，分别写两个式子转移。线段树优化。

AT_arc083_c [ARC083E] Bichrome Tree

完成情况：独立做出但 WA

原因：背包 DP 掌握不好。01 背包要讲究 倒序DP，防止滥用转移变为完全背包。

特点：树形 DP，背包 DP

染色与染色具体是什么色无关，所以我们不需要记录根的颜色这个状态。 就是说黑白颠倒也成立。

容易知道，树形 DP 过程中，我们只关心儿子的两种颜色对应权值的和分别是多少。

由于与根相同颜色的权值就是 X_i，所以对于某个结点 i 的子树的一种染色方案，我们只关心子树与 i 不同颜色的权值和，记作 s。

后效性即为上述。进一步地，这些权值和种类可能很多，我们考虑剪掉某些种类。

我们把所有子树内的后效性看作二元组 {x}\brace{y}，就可以写作：

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

每一行选出若干个二元组，可以交换上下两个元素的值，使得上面元素的和 \le X_{cu}，此时下面元素的和算作 cu 的一个后效性。

然后我们发现：下面的和越小越优。

原因是无论怎么交换，要么 X 在上面，那么下面的值作为下一次的值，肯定越小越好。要么 X 在下面。那么这一次已经可以做到最优了，也是越小越好。

（我们其实是利用 X 不变来论证选择最小的最优性。）

推导一下，就变为一个背包问题。

AT_arc082_c [ARC082E] ConvexScore

完成情况：未独立完成。

做题经验：形如 2^x 的计数，变为大小为 x 的集合的所有子集贡献之和。

还要考虑其它集合的不变量，优化组合意义推导。

特点：凸包，计数

比较经典。套路适用范围可以借鉴。

对于每一个点集形成的凸包，其价值为

2^{|被包含点集|-|凸包点集|}

求贡献和。

什么叫 2^x 的和？这样理解，一个大小为 x 集合，每个元素可以选或不选，方案数就为 2^x。

对于每一个不在凸包上但是被包含的点集都有 1 的贡献。

上面这句话很难描述。

我们加上：每一个凸包上点集与不在凸包上但是被包含的点集都有 1 的贡献。 就是形成凸包的点集。（因为凸包唯一，所以合法。）

所以变为全集减去不能形成凸包的点集。而不能形成凸包的点集满足集合内元素共线。（包括一/两个点形成的点集）

枚举即可。

AT_arc083_d [ARC083F] Collecting Balls

完成情况：未独立完成。

原因：未仔细审题。题目上明确表示有 2n 个球，但是我以为球的数量是不确定的，所以导致思考的方向有问题。

特点：基环树 DP

根据我们在 BSOI 2848 【5.24NOI模拟】城市建设 的经验，我们可以既可以把边看作点，也可以把点看作边。

矩阵常常和二分图形成双射。树和偶环基环树都是二分图。

根据鸽巢原理：每个机器人与每个球一一对应。

把每个点看作是对应二分图的连边，我们要确定每个球被哪一个机器人获取，相当于在给边定向。每个机器人只能获取一个球，那么说明每个点入度恰好为 1。

为什么说它是基环树森林？

  2. 手玩数据可知，一定不存在两个矩形拼在一起的情况。说明复杂环不是很行。

（不存在这种情况）

恰好，基环树入度为 1 的定向只有两种情况：环内顺时针和环内逆时针。环外的都指向了环中央。

定向完之后是求拓扑排序的数量。由于已经定向，那么偏序关系也很好描述，就是找到对应方向的第一个结点，并向其连边。可以证明其为内向生成树。

AT_arc096_d [ARC096F] Sweet Alchemy

特点：背包 DP 的特殊优化（复杂度优化到较小的值域上）

差分转为多重背包（注意 1 号点无限制，其他点最多选 d 个）。

首先有一个假的贪心，直接贪心选择性价比最高的物品，能选则选。错误原因是，后面更优秀的方案，无法被前面贪心选择的方案替代。

考虑什么时候一定可以替代。考虑到每个物品的价值 \le n。 当前面选择的还剩 n 种以上，后面选择的超过 n 种时，直接将后面的物品用前面的物品表示。

发现这样构造方案即可：前面价值为 v_i，后面价值为 j。将 j 物品减少 v_i 个，将 i 物品增加 v_j 个，这样一定合法。将后面物品往前移，性价比整体是往上移的，对应的物品所占容量变小，不劣。

考虑贪心会在哪里出现错误。考虑最优状态下，可能是在某一个后面的位置选得比较多，前面某个位置选的比较少。但是刚刚分析就可以得出，后面如果 \ge n 时，一定可以往前移而不劣。一直往前移，结束状态要么是前面达到限度了，要么后面 \le n 了。达到限度这种情况，贪心也可以得到最优状态。那我们实际上要考虑 \le n 这种情况。

贪心不能解决的最优状态，当且仅当元素选择小于等于 n 时。 直接背包 DP，把 \le n 的情况的所有子问题最优态给算出来，然后全局最优态一定是从 \le n 的最优态拼上贪心得到的。

启示：

  1. 有时候 DP 和贪心不一定是互斥的，贪心贪不了的状态，可以转为先用 DP 钦定其某种子问题再加上另一部分的贪心。

  2. 背包考虑容量和价值，在较小的那一部分考虑，看看能否用一些其他技巧优化。

  3. 多重背包考虑二进制分组和单调队列优化。

ARC214B Missing Number in Graph / ARC214C - Divide into 4 Teams

非常可爱的两道结论题。

这充分说明，做出来不是最优态，最优的是如何快速地做出来。

比如说 B 题，可以用数据结构维护，但是结论不需要数据结构，那么就会在这里优化时间。

比如 C 题，如果没有一定的思维，那么就是做不出来的。

ARC214B Missing Number in Graph

先找一棵生成树。令 x 为 1 号结点的权值，自然可以得到其它点的权值。每个点就点权形如 x\oplus p_i。希望取一个合适的 x 使得 \{x\oplus p_i\} 这个集合为 \{0,1,\cdots,n\}\backslash\{b\}。

观察一下，异或具有唯一性。即 x\oplus A=B 的 x 恰好有一个。

如何知道缺了哪一个元素？

由于唯一性，所以当 b 不同时，\{0,1,\cdots,n\}\backslash\{b\} 的异或总和都互不相同。所以用 \{x\oplus p_i\} 的异或和即可知道。

当 n 为偶数时，x 抵消掉，所以此时直接可以知道剩下了哪一个值。

当 x 为奇数时，我们先钦定某个 b 合法，那么就可以算出 x 的一个合法的值。根据群理论，我们将 x 异或上 1，那么这个 \{x\oplus p_i\} 的元素不会超过 n（因为 n 是奇数）并且缺失元一定会发生改变（异或的唯一性）所以一定有两个以上的解。

根据群理论，如果 n 的后 k 位都是 1，那么任意一个合法 x 异或上 0 到 2^k-1 的整数都是合法解。且如果 k 最大为 k_{\max} 那么解恰有 2^{k_{\max}} 个。

所以这道题可以这样描述：

当确定一种方案时，如果存在另一种 b 使其合法，那么就必定是 \{0,1,\cdots,n\}\backslash\{b_1\} 到 \{0,1,\cdots,n\}\backslash\{b_2\} 的异或映射。断言一定是通过 b_1\oplus b_2 映射得到的。

如果不是，那么 b_1 映射到了一个 >n 的数上。根据异或的对称性，那么这个 >n 的数会映射会 b_1，矛盾。

那么就是 $\{0,1,\cdots,n\}$ 到 $\{0,1,\cdots,n\}$ 的映射。考虑异或的旋转性，对其二进制分组后，其每块的相对顺序不会发生改变，否则就对齐不了。所以一定是块内旋转。而最小块长和后缀 $1$ 数量有关。所以如此。 总结：异或具有 - 唯一性：$x$ 通过 $A$ 异或为 $B$ 的只有一个。 - 对称性：$x$ 通过 $A$ 异或到 $y$，那么 $y$ 也通过 $A$ 异或到 $x$。 - 旋转性：考虑每一段 $p\times 2^k+[0,2^k-1]$，其再异或上一个 $x$ 后其还是一个连续段。 ### [ARC214C - Divide into 4 Teams](https://atcoder.jp/contests/arc214/tasks/arc214_c) 三种方法。 第一种是生成函数的做法。 等价于求 $\displaystyle [x^0y^0]\prod_{i=1}^n(x^{P_i}+y^{P_i}+x^{-P_i}+y^{-P_i})$。（这里先不考虑一个集合为空的情况。） 考虑一个式子太难处理，能否拆分成两个的乘积？ 考虑共轭？注意有 $(x^{-P_i}+y^{-P_i})x^{P_i}y^{P_i}=x^{P_i}+y^{P_i}$。或者写成 $\displaystyle \frac{1}{x^{P_i}}+\frac{1}{y^{P_i}}=\frac{x^{P_i}+y^{P_i}}{x^{P_i}y^{P_i}}$。最终可以得到 $\displaystyle [x^0y^0]\prod_{i=1}^n(x^{P_i}+y^{P_i})(1+{x^{-P_i}y^{-P_i}})$。 后面一项要求 $x,y$ 次数相等，前面一项要求和为全部。所以只能是总和的一半。（如果没有这个也可以做，就是后面直接求，前面只记录 $x$ 的次数，最后用全体减去 $y$ 的次数即可。） 第二种用生成函数但是中途改为改变坐标系。 等价于求 $\displaystyle [x^0y^0]\prod_{i=1}^n(x^{P_i}+y^{P_i}+x^{-P_i}+y^{-P_i})$。然后可以变为斜坐标系。就是求 $\displaystyle [x^0y^0]\prod_{i=1}^n(x^{P_i}y^{P_i}+x^{-P_i}y^{P_i}+x^{P_i}y^{-P_i}+x^{-P_i}y^{-P_i})$。你发现 $x$ 和 $y$ 互相独立，那么直接为其平方。 第三种观察法。 注意到 $A$ 和 $C$，$A$ 和 $D$ 加和都为全部。而 $A,B,C,D$ 也是任选，所以答案为其平方。 就是说，怎么取化式子，使得每一部分的结构更为简单（第一种），每一部分对称使得其互相独立（第二种），同时独立的刻画两个不同的集合（第三种）。