CF514 题解

CF514A题解

题目大意

给定一个数，对于其每一位数字 $t$ ，你可以将他改为 $9-t$ 或者保持不变。问通过若干次此操作，可以得到的最小正数是多少（也不能有前导零）。

考虑对每一位分别贪心，若转换后值变小了就转换，反之则不变。记得要特判首位是否是 $0$ ，如果是 $0$ 就变回 $9$，这样就能去除前导零以及保证答案是正数。

CF514B题解

题目大意

有n个恐怖分子在站在一个平面上，每个恐怖分子都有一个位置坐标位置 $(x,y)$ 。现在有一个激光武器要用来消灭这些恐怖分子，这个武器所在的位置是 $(x_0,y_0)$ ，激光武器每发射一次，就可以消灭一条直线上的所有恐怖分子。现在，你的任务是计算最少要发射多少次激光，才可以消灭所有的恐怖分子。

题解

计算每个恐怖分子到 $(x_0, y_0)$ 的直线斜率，装进数组里，sort，unique，得出答案。

由于我使用分数来表示斜率，所以需要特判 $\Delta x=0$ 和 $\Delta y=0$ 的情况：

如果 $\Delta x=0$ 和 $\Delta y=0$就不管。
如果 $\Delta x=0$，就令 $\Delta y=1$ (反正都是在一条直线上)；
反之若$\Delta y=0$ 就令 $\Delta x=1$ 。

这样做就避免了分数比大小的时候 0 和一个负数比大小出现问题。

CF514C题解

题目大意

给出 $n$ 个已知字符串，$m$ 次询问，每次询问给出一个字符串，问上面 $n$ 个字符串中是否有一个字符串满足恰好有一个字母不同于询问的字符串。$n, m \le 3 \times 10^5$，其中所有字符串的字符属于{'a','b','c'}，且输入总长度 $\le 6 \times 10^5$。

题解

字典树模板，秒了。

我们注意到输入总长度 $\le 6 \times 10^5$ 。因此字典树节点个数一定不会超过 $6 \times 10^5$（考虑最坏情况下每个字符串的每个字符都是一个节点），总查询时间复杂度也如此。

字典树上的插入我就不说了，大家可以参考 OI-Wiki 字典树。这里我重点分析如何查找。考虑 dfs，枚举当前字符的两种情况：跟查询字符串的对应位置是否相同；若不同，则后面必须都是相同（匹配）的，在 dfs 的时候传参 tag 来记录这件事。

CF514D题解

题目大意

一共有 $N$ 个敌人，每个敌人有 $M$ 个属性值，当一个敌人的所有属性值都 $\le 0$ 的时候，这个敌人就被打败了。

我们每次操作可以选一种属性值进行攻击，使得所有敌人的这个属性的值都 $-1$. 我们最多可以进行 $K$ 次操作。

求最多可以干掉多少个连续的人，只需输出这种时候的具体操作（每一种属性用了多少次操作）。

题解

观察题解题目不难发现，若将连续一个区间的所有人的某一个属性全部降到 $\le 0$ 需要的操作次数，应是区间中该属性的最大值。求区间最值很容易想到使用单调队列实现滑动窗口。

维护 $m$ 个单调队列，每个单调队列记录相同区间 $[l,r]$ 中对应属性的最大值。枚举右端点 $r$，若 $m$ 个属性的区间最大值加起来大于 $k$，就将左端点 $l$ 右移；直到最大值之和小于等于 $k$，且区间长度大于 $0$,就是一种可行方案，更新答案即可。

CF514E题解

题目大意

有一个无限大的有根树，树上的每一个节点都有 $n$ 个子节点（$1 \leq n \leq 10^5$），任意一个节点它的第 $i$ 个子节点之间的距离为 $d_i$（$1 \leq d_i \leq 100$）。

给出一个数 $x$（$0 \leq x \leq 10^9$），求有多少个节点到根节点的距离小于等于 $x$，输出答案对 $10^9+7$ 取模后的结果。

题解

我们容易发现，单独拿出任意一棵子树，他们的结构完全相同，因此答案也相同。我们记对于每一棵子树，到根节点距离小于等于 $x$ 的节点个数为 $dp_x$. 由此，我们枚举每棵子树，再考虑当前节点算1个，容易写出状态转移方程： $$ dp_x=1+\sum_{i=1}^{n}{dp_{x-d_i}} $$ 我们设 $t_x=\sum_{i=1}^{100}{[d_i==x]}$ ，于是上式可以写成 $$ dp_x=1+\sum_{i=1}^{100}{dp_{x-i}t_i} $$

时间复杂度 $O(10^{11})$ ，是一种没有前途的算法。

考虑到这个式子是一种常系数齐次线性递推，可以考虑使用矩阵快速幂进行优化。我们设 $1\times (n+1)$ 的状态矩阵 $A_{i}$： $$ \begin{bmatrix} 1&dp_{i-99}&dp_{i-98}&\ldots&dp_{i-1}&dp_{i} \end{bmatrix} $$ 上面的递推公式对应出 $n+1$ 阶的操作矩阵 $Op$： $$ \begin{bmatrix} 1&0&0&\cdots&0&1\\ 0&0&0&&0&1\\ 0&1&0&&0&1\\ 0&0&1&&0&1\\ &\vdots&&\ddots&&\\ 0&0&0&\cdots&1&1 \end{bmatrix} $$ 有关其计算步骤，可以从OI-Wiki 矩阵乘法上学习矩阵乘法，由其定义得到。我们有 $A_i=A_{i-1}\times Op$

由 $dp_0=1$ 得到初始状态矩阵 $A_0$： $$ \begin{bmatrix} 1&0&0&\cdots &0&1 \end{bmatrix} $$

我们对操作矩阵进行指数为 $x$ 的快速幂，再使初始状态矩阵与之相乘。即$A_x=A_0\times {Op}^{x}$ ，取 $A_x$ 的最后一列，就是答案。