# CF1455

$(4/7)$

• 形式化的表示题意更容易发现突破口。
• 二维的问题考虑每维分开来考虑再用题目限制关联起来

# \texttt

题意：

定义一个数 $x$ 翻转函数 $f(x)$ 为把 $x$ 从低位到高为再写成一个数字并去掉前导零。求对于 $1\le x \le X$ ，求 $i\over f(f(i))$ 的取值种数。

题解：

发现只有最后有 $0$ 的翻过来翻回去后才会变，于是不难发现答案就是 $X$ 位数。

# \texttt

题意：

​ 初始站在数轴 $0$ 位置，第 $i$ 次操作可以选择向左走 $i$ 步或向右走 $1$ 步，求到正半轴 $x$ 所需最少步数。

题解：

​ 把正整数前缀和写出来，设第一个比 $x$ 大的前缀和为 $a$ ，这相当于是一直向左走步数，而我们要求的是在其中选择几步往右走。不难发现相当于是给 $a-(x+1)$ ，$x$ 是 $1...p$ 的中的一个数，发现 $a-x=1$ 时必须用 $p+1$ 步，因为找不到这样的一个 $x$ ，否则用 $p$ 步，即在这 $1+2+...+p$ 中选择一个反转。

# \texttt

题意：

​ $alice$ 和 $bob$ 玩游戏，每个人有体力值，击打一次球耗 $1$ 体力，谁不能击球就输掉这轮比赛，下一轮由胜者开局。开局必须打，初始 $alice$ 开局，每个人希望自己胜的尽可能多。

题解：

​ 发现后手占绝对优势，他能赢完自己体力次，于是输出 $a-1,b$

# \texttt

题意：

​ 给出一个序列 $x$ ，每次可以把序列中的一个 $>x$ 的数与 $x$ 交换， 问最少操作次数使整个序列升序。

题解：

​ 设交换的数为 $a_i$ ，则要求 $a_i>x,a_i> \max\limits_{j=1}^{i-1}a_j$ ，所以对于所有 $>x$ 的位置，都应该换，若前面有一个没换就不满足条件了。

​ 而还可以发现最后没有逆序的一段不需要换，于是把最后一个逆序的位置找出来，前面做一遍交换操作，最后扫一遍是否合法判断 $-1$

# \texttt

题意：

​ 四个点，求移动最小距离使之构成一个正方形。

题解：

​ 首先可以 $4!$ 枚举每个点最后是正方形的什么点，设 $a,b,c,d$ 分别成为正方形左上左下，右上右下点。

​ 然后把横纵坐标分开来考虑，以横坐标为例，由简单的初中数学可知，最终正方形的最左横坐标应该处于 $a_x,b_x$ 之间比较优，这样 $a,b$ 移动距离（横坐标）就是 $|a_x-b_x|$ 的了，如果不在这中间，则每偏离一个单位要多走 $2$ 步。类似的，我们还可以得出最右横坐标的取值，进一步得出正方形边长的取值区间，若与纵坐标的取值区间有交答案就是 ，前面这些加起来，否则就加上偏移量 $\times 2$

# \texttt

题意：

​ 给定一个字符串，对于第 $i$ 个字符， 操作 $L, R, U, D, O$ 分别表示与前 / 后一个字符交换，替换为字符集中前 / 后一个字符，不动，求原串依次对每个字符 $i$ 进行操作后，得到的字典序最小的字符串。

题解：
发现第 $i$ 步操作后只影响得到前 $i+1$ 个字符，于是用 $string$ 数组当 $dp$ 数组。设 $dp_{i}$ 表示第 $i$ 个操作前 $i + 1$ 个字符所对应的最小字符串，发现 $L,D,U,O$ 都很容易转移了，而 $R$ 可能影响到前面的东西。发现 $R$ 最多影响到 $i-2$ 位，还得是 $RL$ 的时候，于是多记录一维表示上一步操作是不是 $R$

# \texttt

题意：

G

题解：
在最开始加一个 $if \ 0$ ，发现我们可以构建一棵树。设 $dp_{u,j}$ 为 $u$ 的子树进去，出来后为 $j$ 的最小代价。使用线段树合并来转移。

​ 对于一个 $set$ ，有两种转移： 1. 在 $val$ 位置赋值为此时 $dp$ 数组最小值表示执行这条语句；2. 在除 $val$ 以外的位置加上 $cost$ 表示不执行这条语句。

​ 对于一个 $if$ 相当于开始一个新 $dp$ ，也就是新建一棵线段树，只在 $val$ 处为 $0$ ，其他为 $inf$