Codeforces Round #786 (Div. 3)

A. Number Transformation

令\(a = 1\)，则\(b = \dfrac{y}{x}\)。

B. Dictionary

暴力预处理出完整的字典，然后用std::map存单词和下标的映射。

C. Infinite Replacement

如果\(t\)等于a，则答案为\(1\)。

否则，如果\(t\)包含a，则有答案为无穷大。

否则，\(s\)中的每个元素都有两种可能，替换或者不替换，即答案为\(2^n\)，其中\(n = |s|\)。

D. A-B-C Sort

先做了E，F才返回来做D。

对于\(n = 3\)，所有可能的结果有\(a_1a_2a_3\)和\(a_1a_3a_2\)。

对于\(n = 4\)，所有可能的结果有\(a_1a_2a_3a_4\)，\(a_1a_2a_4a_3\)，\(a_2a_1a_3a_4\)以及\(a_2a_1a_4a_3\)。

以此类推，发现题目所给的操作等价于：当\(n - i\)为偶数的时候，可以交换\(a_i\)和\(a_{i+1}\)。

对于满足条件的\(i\)，如果\(a_i > a_{i + 1}\)，就交换两元素的位置，否则不变。

然后看数组是否是非降序即可。

E. Breaking the Wall

被hack了，待更新。

可能的操作共有3种：

1. 只砸第\(i\)道墙。
2. 砸第\(i\)道墙和第\(i + 1\)道墙。
3. 拆第\(i\)道墙和第\(j\)道墙。

对于第一种操作，枚举每一道墙。可能砸倒了第\(i\)道墙，顺便把相邻的墙溅射倒了，这种情况会在第二种操作中考虑到。也可能第\(i\)道墙还没砸倒，相邻的墙就都倒了，代价为\(\max(a_{i - 1}, a_{i + 1})\)。\(O(n)\)枚举\(i\)即可。

对于第二种操作，假设砸第\(i\)道墙\(x\)次，第\(i + 1\)道墙\(y\)次，可以得到一个不等式方程组，解出来代价为\(\lceil \dfrac{a_{i} + a_{i + 1}}{3} \rceil\)。\(O(n)\)枚举\(i\)即可。

对于第三种操作，\(j\)的选择可以贪心选，共有4个候选：\(i - 1\)，\(i + 1\)，\(p(i - 2)\)，\(s(i + 2)\)。\(p(x)\)表示前\(x\)个元素中最小值所在下标，\(s(x)\)表示后缀。\(O(n)\)预处理前缀和后缀，然后再\(O(n)\)枚举\(i\)即可。

F. Desktop Rearrangement

记桌面上的图标数量为\(count\)。

由于行数和列数都是固定的，所以重排之后有图标的区域是可以直接算出来的。假设已经位于这个区域中的图标数有\(sum\)个，则还需要的操作数为\(count - sum\)。

将桌面上的位置按下面这种方式重新编号。

147 258 369 

重新编号之后，桌面重排之后图标的位置就会是一个前缀，然后就是单点修改+前缀的和问题了，直接树状数组搞定。

G. Remove Directed Edges

DAG上DP。

观察可得：最后的答案会是一条链。

假设\(dp_i\)表示以\(i\)为终点的链的最大长度。对于节点\(u\)，考虑和他相邻的点\(v\)是否拓展以\(u\)为终点的链。

因为是链，所以除了边\(u \rightarrow v\)以外，\(u\)的其他出边和\(v\)的其他入边都可以删去，所以如果\(outdeg_u > 1\)且\(indeg_v > 1\)的话，\(v\)就可以在\(u\)的基础上再拓展一。然后因为是DAG，所以对于\(v\)可能会有多个\(u\)，即\(dp_v = \max dp_{(u, v) \in E} dp_u + 1\)。

搞个拓扑排序，然后算DP即可。