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$ 种，因此直接矩阵快速幂即可。 实现时需要把后面的状态压成一个数。我的做法是压...
CF527E Data Center Drama
Codeforces Luogu 分析 这个“所有边的出入度都是偶数”可以想到欧拉回路。可以发现只要造一张边数最小且为偶数的欧拉图出来，然后把欧拉回路上的边依次正向、反向定向即可。 这个很容易造，我们只要把相邻度数为奇数的点两两之间连一条边即可。练完之后边数可能是奇数，再连一个自环即可。显然这样子边数是最小的。 代码 // =================================...
洛谷3643 [APIO2016]划艇
Luogu LOJ 分析 一个显然的想法是设 $dp_{i,j}$ 表示前 $i$ 个学校，第 $i$ 个学校派了 $j(j\neq 0)$ 艘划艇的方案数，然而第二维高达 $10^9$。 可以想到把所有端点离散化一下（这里改成左闭右开区间会方便一些），$dp_{i,j}$ 的定义改为前 $i$ 个学校，第 $i$ 个学校派的划艇数在第 $j$ 个区间中的方案数。 考虑转移。我们枚举一个 $...
洛谷4769 [NOI2018]冒泡排序
Luogu LOJ 分析 先考虑什么样的排列是满足条件的。冷静分析一下，达到下界当且仅当排列中没有长度 $\geq 3$ 的下降子序列，因为如果有的话一定有一个元素需要移过目标位置再移回来，从而不能达到下界。 先考虑忽略字典序的限制怎么做。设 $dp_{i,j}$ 表示长度为 $i$、首项为 $j$ 的合法排列数，转移有三种情况 第二个元素 $k$ 比 $j$ 大：那么如果 $k$ 不能与...
CF1174E Ehab and the Expected GCD Problem
Codeforces Luogu 分析 根据一些小学奥数知识可以知道第一个数应该是 $2^x3^y$ 的形式，而且 $y\in\{0,1\}$ ，因为 $>3$ 的质因子我们换成 $2^k$ 更优，$3^2$ 换成 $2^3$ 更优。为了方便设 $m=\lfloor\log_2 n\rfloor$。 考虑 DP。设 $dp_{i,x,y}$ 表示前 $i$ 个数，当前的 $\gcd$ ...
CF838D Airplane Arrangements
Codeforces Luogu 分析 我们考虑计算总方案数乘上合法的概率。然而这样子并不好计算，考虑一些转化。 我们加一个位置 $n+1$，然后把飞机看成一个环，问题变为每个人随机一个初始位置和方向，走到第一个空位停下，如果停在 $n+1$ 就不合法。 这样子最后的每种座位情况都是等概率的，那么 $n+1$ 上有人的概率为 $\frac{m}{n+1}$，即合法概率为 $\frac{n+1...