「ACM-ICPC2019」上海网络赛 - 部分题解

又是一场疯狂罚时的ACM

link

A

[线段树]

树上某个点的最远点一定是直径的某个端点

很老的套路，线段树动态维护直径，再用一个树状数组动态维护链长度信息即可

B

直接差分

C

[FFT]

补集转化，不合法方案就是$A_i + B_j< C_k$，或$A_i + C_k < B_j$，或$B_j + C_k < A_i$

显然这三个条件最多只能满足一个，于是可以直接FFT计算

这道题还卡常，$n\le 1000$的时候必须跑暴力才能过

D

可以直接爆搜打表

或者考虑一个更优秀一些的搜索：显然确定了$>1$的数的填数方案后，$1$的个数是可以算出来的

所以只需要搜填$2$以上的数，随便剪下枝就跑得飞快

E

[生成函数] [多项式]

和珍珠几乎一模一样

设$m_0$表示$1$至$m$中偶数的个数，$m_1$表示奇数个数，那么题目就是要求

$\begin{aligned} &n![x^n]\Big(\frac{e^x + e^{-x}}{2}\Big)^{m_0} \cdot (e^x)^{m_1}\\ =&\frac{n!}{2^{m_0}}[x^n]\sum_{i=0}^{m_0}\binom{m_0}{i}(e^x)^i(e^{-x})^{m_0 - i}\cdot (e^x)^{m_1}\\ =&\frac{n!}{2^{m_0}}[x^n]\sum_{i=0}^{m_0}\binom{m_0}{i}\cdot (e^{x})^{2i-m_0 + m_1}\\ =&\frac{n!}{2^{m_0}}\sum_{i=0}^{m_0}\binom{m_0}{i}\cdot \frac{(2i-m_0 + m_1)^{n}}{n!}\\ =&\frac{1}{2^{m_0}}\sum_{i=0}^{m_0}\binom{m_0}{i}(2i-m_0 + m_1)^{n} \end{aligned}$

直接算就行

F

[动态规划]

$dp[i][j]$表示当前填到$i$，前$i$位总共用了$j$种字符，后面所有方案的方案数

贪心从小到大考虑每一位填什么，类似于二分往左右走的过程

G

[分块] [字符串]

对询问串长度分块

预处理长度$\le K$的答案；$>K$就暴力（$K$实测可能只能开到$5$左右。。。）

暴力Hash就是类似于一个滑动窗口在字符串上面跑

因为这里的Hash是无序Hash，所以每次移动滑动窗口时直接加加减减，很方便动态维护Hash值

$P.S.$空间卡得很紧，具体实现可以把询问离线，空间就不用开那么多了

H

[栈]

昨天才考了一个这样的套路

用两个栈模拟队列，push就压入栈A，pop就弹栈B。pop时若栈B为空，则把栈A的元素依次取出，压入栈B

复杂度显然是对的，每个元素最多被考虑3次：push、从A转移到B、pop

这样就只用加入和回溯，而不需要删除了

I

Description

长为 $n$ 的序列里有一个 bug ，你每次可以用 $b$ 的代价插一个板，或者用 $a$ 的代价确认 bug 在被已有板隔出的哪一个区间内，问最坏情况下最小代价

$n, a, b\le 10^{18}$

Solution

确认的次数显然不会超过$O(\log n)$，所以可以直接枚举。对于固定的确认次数来说，若第$j$次确认时隔出来$k_j$个区域，那么要保证$\displaystyle \lceil \frac{n}{\prod k_j}\rceil \le 1$

这里要用到一个结论：$\displaystyle \lceil \frac{n}{ab}\rceil = \lceil\frac{\lceil\frac{n}{a}\rceil}{b}\rceil$

xz会证，我只会感性理解

因为和一定差小积大，所以$k_j$要尽量接近

最优解一定形如：$k_{1\cdots p} =\lfloor \sqrt[i]{n}\rfloor, k_{p+1\cdots i} =\lfloor \sqrt[i]{n}\rfloor+1$，暴力找到最小的$p$即可

J

[动态规划]

要求$(\sum A) - \max\{A\} \le \sum (S - A) \le \sum A$的$A$集合个数

把集合排序，从小到大考虑，动态维护$f[i]$表示和为$i$的方案

因为从小到大考虑，所以当前的数一定是$\max$，直接算即可

K

[计算几何]

先枚举其中一个点，圆上的整点只有$\sqrt n$个，方法在这里

求出来后，由于三条边长度已知，可以求出其夹角，进而通过旋转求出另外一点坐标

L

数位dp模板题