这场比较平凡吧 .
省流：
http://zhengruioi.com/contest/1087
目录
目录
A. Gene
题面
题解
算法一（正解）
算法二
B. Fight
题面
题解
算法一（正解）
算法二
算法三
C. Pastry
题面
题解
算法一（SoyTony）
关于 \(f\) 的一些研究
D. Conference
题面
题解
算法一（SoyTony）
时间复杂度瞎算的 .
A. Gene
题面
俩字符串 \(s,t\)，在 \(s\) 中加点字符，使 \(t\) 是 \(s\) 的子串 .
插字符 \(ch\) 有代价 \(c_{ch}\) .
字符集 \(\{\texttt A,\texttt C,\texttt G,\texttt T\}\) .
题解
算法一（正解）
考虑 dp，令 \(dp_{i,j}\) 表示 \(s\) 以 \(i\) 结尾的后缀与 \(t\) 相等的最小代价 .
转移考虑丢掉（换一个）或接续即可 .
时间复杂度 \(O(|S||T|)\)，可以滚动数组 .
算法二
扫一遍 \(s\)，暴力匹配 \(t\)，如果失配了就加字符 .
是不是非常简单，和那个 dp 时间复杂度一模一样 .
时间复杂度 \(O(|S||T|)\) .
B. Fight
题面
为了争夺金坷垃， \(n\) 个人要打 \(m\) 场架，第 \(i\) 场是第 \(a_i\) 个人和第 \(b_i\) 个人打。
主办方突然想把这些人分成日日阵营和非非阵营（每个人都属于某一个阵营），使得只有阵营间的人会打架。但是安排已经决定，要更改安排需要时间。
你需要求出在最优的阵营划分方案中，出现两个相同阵营的人的战斗最晚是在哪一场。（数据保证一定会出现这种情况）
题解
算法一（正解）
种类并查集，非常容易 .
时间复杂度 \(O(n\alpha(m))\) .
算法二
考虑二分答案，于是问题变成判定是否可以划分阵营 .
等价于二分图判定，黑白染色即可 .
时间复杂度 \(O((n+m)\log m)\) .
算法三
依然二分答案 .
然后可以 2-SAT 做，有个老哥这么干 \(80pts\) 超时了（悲） .
时间复杂度 \(O((n+m)\log m)\) .
C. Pastry
题面
\(n\) 个宽度相同的块相邻摆放 .
将第 \(i\) 个块 \(a_i\) 等分，问有多少个本质不同的分界点 .
题解
算法一（SoyTony）
令 \(m =\max\{a_i\}\)
拆一下 .
考虑 \(f(x)\) 表示 \(x\) 与 \(x\) 的所有约数的分界点不同的个数 .
然后可以枚举因子 \(O(m\log m)\) 递推 .
然后对于每个 \(a_i\) 把她和她的约数（去重）的 \(f\) 全加起来就好了 .
这一步枚举因子是 \(O(m\log m)\) .
总时间复杂度 \(O(m\log m)\) .
关于 \(f\) 的一些研究
这个 \(f\) 的表达式是
\[f(n)=\begin{cases}0&i=1\\n-1+\sum_{d\mid n, d\neq n}f(d)\end{cases}
\]
通过打表得到 \(f(n)=\varphi(n)-[n=1]\)，回代也发现成立
过程
众所周知 \(\displaystyle \sum_{d\mid n}\varphi(n)=n\) .
于是带入，得
\[\varphi(n)-[n=1]=n-1+\sum_{d\mid n, d\neq n}(\varphi(n)-[n=1])
\]
这个 \(\sum\) 有两个非常鬼畜的东西，一个是 \(d\neq n\)，一个是 \([n=1]\) .
把 \(1,n\) 单独处理得
\[\begin{aligned}\varphi(n)-[n=1]&=n-1-(n-\varphi(n)-[n=1])\\&=\varphi(n)-1+[n=1]\\&=\varphi(n)-[n=1]\end{aligned}
\]
恒成立 .
能否从递推式直接得到通项还是未解之谜 .
破案了，从 Dirichlet 卷积的角度看 .
FZ 神仙的做法
令 \(g(x) = f(x)-[n=1]\) .
于是
\[g(n)=n-\sum_{d\mid n,d\neq n}g(d)
\]
即
\[\sum_{d\mid n}g(d) = n
\]
即 \(g*I=\mathrm{id}\)，显然 \(g=\varphi\) .
从而 \(f(x)=\varphi(x)-[n=1]\) .
wangrx 神仙的做法
直接写成 Dirichlet 卷积形式，
\[f = \mathrm{id}-I-(I*f-f)
\]
化简得
\[I*f=\mathrm{id}-I
\]
因为 \(I^{-1}=\mu\)，于是
\[\begin{aligned}f&=I^{-1}(\mathrm{id}-I)\\&=\mu* \mathrm{id}-I^{-1}*I\\&=\varphi - \varepsilon\end{aligned}
\]
即 \(f(x)=\varphi(x)-[x=1]\) .
其他
《贝尔级数》
《狄利克雷生成函数》
于是似乎就可以线性筛了（？）然而复杂度不变 qwq .
大概这种含 \(\displaystyle\sum_{d\mid n}\) 的东西就向 Dirichlet 卷积靠吧 .
D. Conference
题面
给一个序列 \(\{a_n\}\) .
对于每个 \(1\le s\le n\) 回答询问：
最小的使得序列 \(\left\{\left\lfloor \dfrac{a_i}k\right\rfloor\right\}\) 存在 \(s\) 个重复元素（最多）的 \(k\)（若不存在输出 -1）
题解
算法一（SoyTony）
众所周知 \(\left\lfloor \dfrac nk\right\rfloor\) 只有 \(O(\sqrt n)\) 个取值 .
然后整除分块出每个 \(a_i\) 的取值块左端点并丢到一个 std::set 里 .
然后遍历那个 std::set 算一下情况下有多少个相同元素就完了 .
时间复杂度 \(O(玄学_1\sqrt{玄学_2}\log 玄学_3)\) .
