Codeforces Round #614 简要题解
Div1 Div2 从一月份一直咕到现在的一场比赛 /kel ConneR and the A.R.C. Markland-N 暴力往两边找即可。 代码 JOE is on TV! 显然每次淘汰掉刚好一个人是最好的。 答案即为 $\sum_{i=1}^n\frac{1}{i}$。 代码 NEKO's Maze Game 维护每个格子是否是岩浆，当一个格子改变时维护一下上下两格都是岩浆的列数即...
M_sea 发布的文章
- 首页
- M_sea
AGC028E High Elements
AtCoder 分析 因为要字典序最小，所以可以贪心，从前往后确定所有位，每位尽量填 $0$。 为了方便，我们把是 $p$ 中的前缀最大值的前缀最大值称作“旧的“，不是 $p$ 中前缀最大值的前缀最大值称作”新的“。 首先有一个结论：如果一个 $s$ 合法，那么 $x,y$ 两个序列中一定有一个序列的前缀最大值全都是旧的。 证明可以这样考虑：如果 $x,y$ 中都有一个新的前缀最大值，那么我...
CF1344D Résumé Review
Codeforces Luogu 分析 对 $f_i(x)=x(a_i-x^2)$ 求二阶导可以发现它是凸的，那么每次选一个 $\Delta y$ 最大的放一定是最优的。 我们二分最小的 $\Delta y$，对每个函数二分（或者直接解一元二次方程）找到它被加的次数，判断是否 $\leq k$ 即可。 这样子最后可能并不能达到 $k$，把还没加的部分选加到 $\Delta y$ 最大的那些上...
AGC027F Grafting
AtCoder 分析 先考虑如果有一个点没有被操作过该怎么做。 我们把这个点作为根，在两棵树上分别 DFS 一遍，那么如果有解的话答案一定是在两棵树上父节点不同的点数。 现在的问题在于如何判无解。首先如果 A 中一个点不要被操作但它的父节点要被操作，那么一定是无解的。否则，考虑到 A 中一个点的父节点要在它之后被操作，B 中一个点的父节点要在它之前被操作，这样子就有若干个偏序关系，我们只需要...
ARC077F SS
AtCoder 分析 设 $T$ 为 $S$ 减去 $S$ 的最长 border 后缀后得到的串。 如果 $|T|$ 是 $|S|$ 的约数，那么操作得到的串依次是 可以发现，$s_i=s_{i-1}+s_{i-2}$。 那么串长增长的速度是指数级别的，所以我们可以直接暴力地算出前若干个这样的串中每个字符的个数，询问时把 $[1,r]$ 拆成若干个这样的串相接再加上不是一个完整的 $S$ ...
CF528E Triangles 3000
Codeforces Luogu 分析 考虑三角形的面积公式：$S_{\triangle ABC}=\frac{1}{2}\left(\vec{OA}\times\vec{OB}+\vec{OB}\times\vec{OC}+\vec{OC}\times\vec{OA}\right)$，其中 $ABC$ 是逆时针顺序。 于是可以枚举一条直线 $l_i$，然后枚举另一条直线 $l_j$，计算它...
CF163E e-Government
Codeforces Luogu 分析 建 AC 自动机，那么暴力就是把匹配到的位置全部加 $1$，然后把每个在集合中的串的 fail 树上子树和加起来。 我们转化一下，先把在集合中的串对应的位置加 $1$，然后累加匹配到的每个节点到根链上的和。这样子可以直接树链剖分维护。 再转化一下，把每个点的点权设成到根链上的和，这样子修改时修改子树权值，询问时直接询问单点即可。可以用树状数组维护。 代...
CF520E Pluses everywhere
Codeforces Luogu 分析 考虑每个数 $a_i$ 的贡献。枚举长度可以得到 预处理 $a_i$ 的前缀和即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==============================...
CF107D Crime Management
Codeforces Luogu 分析 不难想到 DP。设 $dp_{i,a_1,a_2,\cdots}$ 表示前 $i$ 个字符，字符 $c_j$ 的出现次数模 $m_j$ 等于 $a_j$ 时的方案数。转移枚举在后面填的字符即可。 因为 $\prod m_i\leq 123$，所以后面的状态至多只有 $123$ 种，因此直接矩阵快速幂即可。 实现时需要把后面的状态压成一个数。我的做法是压...