UOJ Logo peehs_moorhsum的博客

博客

GoodBye Jihai 题解

2020-01-23 19:21:22 By peehs_moorhsum

新年的促销

from vfleaking

远离 OI 多年的 vfk 老当益壮,又来出送分题辣 ~\(≧▽≦)/~

题意是说 $n$ 个物品的01背包,但是有买 $a$ 赠一和买 $b$ 赠一的白给活动,是不是很喜闻乐见呢?

算法一

对于前两个点,$n \le 10$。所以我们只需要枚举所有可能的购买方案,然后按题意模拟就好啦。

时间复杂度 $O(n \cdot 2^n)$,期望得分 20 分。

算法二

对于前六个点,$O(n^3 m)$ 的复杂度应该是跑得动的。

我们可以考虑 DP,暴力把所有东西记下来。用 $f[i, u, q, j]$ 表示前 $i$ 袋米,购买了 $u$ 袋,白拿了 $q$ 袋,共花了 $j$ 块钱的情况下总重量的最大值。

DP 方程易得:

\begin{equation} f[i,~u,~q,~j] = \min\begin{cases} f[i - 1,~u,~q,~j] & \quad \text{不购买,不白拿} \\ f[i - 1,~u - 1,~q,~j - p_i] + w_i & \quad \text{买!} \\ f[i - 1,~u,~q - 1,~j] + w_i & \quad \text{拿!} \end{cases} \end{equation}

判一判边界情况,然后 DP 结束后取出那些 $q \le \lfloor u / a \rfloor + \lfloor u / b \rfloor$ 的状态更新下答案就可以拿到 60 分咯。

算法三

对于第 7, 8 号点,需要在 $O(n^2 m)$ 的时间内解决,但有个特殊条件是 $a = b$。

重新考虑考虑算法二,就会发现这种情况下在 DP 结束之后只需要判断 $q \le 2\lfloor u / a \rfloor$,也就是 $u - a\lceil q/2 \rceil \ge 0$。所以我们在 DP 的时候可以把 $u,q$ 这两维换成 $u - a\lceil q/2 \rceil \in [-n, n]$ 和 $q$ 的奇偶性,这样 DP 的复杂度就降为 $O(n^2 m)$ 了。

结合算法二,期望得分 80 分。

算法四

对于所有数据,需要在 $O(n^2 m)$ 的时间内解决,且没有特殊条件。

让我们来考虑一下这样一个判定性问题:如果已知自己要购买或者白拿的所有米袋,怎么判断手上的 $k$ 块钱是否够用?

显然,我们可以把这些米袋按价格排序,然后按价格从低到高依次买,买到不能买的时候判断下剩下的米袋是否可以全部白拿走。

所以 DP 的时候也可以这样做:先把所有物品按价格排序,即 $p_1 \le p_2 \le \cdots \le p_n$,然后依次决定买还是不买,拿还是不拿。

由前面的判定性问题可知,在最优方案里肯定存在一个 $I$ 使得对于 $i \le I$ 的米我们要么买要么不买,一定不会白拿;对于 $i > I$ 的米,我们要么白拿要么不白拿,一定不会买。

所以我们可以使用普通的背包 DP 求出 $f[i, u, j]$,表示前 $i$ 袋米,购买了 $u$ 袋,共花了 $j$ 块钱的情况下总重量的最大值。再用普通的 DP 求出 $g[i, q]$ 表示后 $n - i$ 袋米,白拿了 $q$ 袋的情况下总重量的最大值(其实这里排个序贪心就好了)。然后枚举 $I$ 的值,就可以轻松 $O(n^2m)$ 啦。

期望得分 100 分。

道理我都懂,但为什么我 80 分?

因为你可能算 $g[i, \lfloor u / a \rfloor + \lfloor u / b \rfloor]$ 的时候没有判断 $\lfloor u / a \rfloor + \lfloor u / b \rfloor > n - i$ 的情况导致了某种越界。

新年的新航线

from peehs_moorhsum

zhouyuyang哥哥帮忙看了题,并且造数据卡掉了乱搞

gamegame是此题一血

算法一

我会枚举生成树!

时间复杂度 $\Theta(2^{2n-3} )$,可以通过第一个subtask,预计得分 $20$。

算法二

这道题大概有许多种乱搞..

比如随机一个删点序列,满足每次删掉一个最外围的点;删掉的时候随机将它相连的两条边之一取出来,最后三个点随机选两条边,这样一定是生成树

然后按照序列顺序一轮轮看,看每轮连的边换成另一条之后二度点的个数是否减少,减少则交换

长时间没有更新则改变序列重来

时间复杂度 $\Theta(玄学)$,经测试可以通过前两个subtask;写得优美可能通过subtask 5。 预计得分 $40\sim 50$。

算法四

考虑将三角形作为顶点构建生成树;然后对每棵子树,和边界上多边形顶点的度数/连通性进行DP

可以做到线性。但由于实现复杂度较高、时空常数较大,这里不再展开。

算法五

事实上,如果$n \not= 3$ 则一定有解。

明确这一点之后,考虑一个最外层的点;则它的用处是:将相邻两点之一度数加一。

设它相邻的点为$u$, $v$,点本身为$i$,考虑删去$i$,并在$u$到$v$的边上标上$i$,表示$u$, $v$中要恰有一个点和$i$连边。

于是我们面对这一个,边界上的每条边可能有标数的凸多边形。

如果顶点数不超过$4$,可以暴力搜索。

否则仍然考虑一个最外层的点$i$,以及其相邻点$u$,$v$.

如果$(i, u)$,$(i, v)$均无标数,如前文所述删掉即可。

如果$(i, u)$,$(i, v)$均有标数,将所标的数都连向$i$,并抹去标数,可以转化成均无标数的情况。

如果$(i, u)$,$(i, v)$一个有标数、一个没有,不妨$(i, u)$有标数$s$

则连接$(i, u)$, $(s, u)$,删去点$i$即可。此时边$(u, v)$不需要标数。

一直删点,直到点数不超过$4$,而后搜索。

对每个点记一下有标号相连的点的数组,容易做到线性。

时间复杂度 $\Theta(n)$,预计得分 $100$。

新年的复读机

from EntropyIncreaserzhouyuyang

算法一

考虑进行区间 DP,则有 $f(l, r) = \min_{k = l}^{r - 1} f(l, k) + f(k + 1, r) + g(l, k) + g(k + 1, r)$。

其中 $g(l, r) = \gcd \{ a_l, a_{l+1}, \dots, a_r\}$。

时间复杂度 $\Theta(n^3)$,预计得分 $5\sim 20$。

算法二

事实上这一过程有一个非常强的性质:必然存在某个最优解中有一个数,每次都是这个数和相邻的进行合并。

我们考虑将合并过程看做一颗二叉树,假设存在某个节点的左右子都有孩子且任意一种 rotate 后的情况都不优,不妨这四个孩子为 $gaxr_1, gacxyr_2, gbcxyr_3, gbyr_4$,其中这些数的取法为:先将四个数的 $\gcd$ 取为 $g$,并将整体除以 $g$,然后取 $x = \gcd(a_1, a_2, a_3)$,将这三者除以 $x$……以此类推。这样我们就可以根据两种旋转都不优推出两个式子:

$$ax + by < ax + x, ax + by < by + y$$

两式相加得到 $ax + by < x + y$,而 $a, b \ge 1$,因此矛盾。

故最优解树上可以不存在同层的 $4$ 个节点,这样一个方案必然是某个数一直和相邻的数合并得到的。

因此区间 DP 可以直接改为 $f(l, r) = \max (a_l + g(l + 1, r) + f(l + 1, r), a_r + g(l, r - 1) + f(l, r - 1))$。

取决于 $g$ 的不同计算方法,时间复杂度为 $\Theta(n^2) \sim \Theta(n^2\log a)$。预计得分 $20\sim 35$。

算法三

接下来的叙述需要用到以下引理:

引理 1

给 $k$ 个数求 $\gcd$,直接递推调用欧几里得算法,时间复杂度为 $\Theta(k + \log a)$。

注意到欧几里得算法执行 $(a, b)$ 的过程与 $(\frac a{\gcd(a, b)}, \frac b{\gcd(a, b)})$ 相同,所以我们可以得到一个复杂度的表示 $\Theta(\log \frac{a}{\gcd(a, b)}) = \Theta(\log a - \log \gcd(a, b))$。

我们进行递推的时候,复杂度裂项相消就得到了 $\Theta(k + \log a)$。

引理 2

对于一个数列 $n$,前缀 $\gcd$ 的连续段有最多 $\lfloor\log_2 a\rfloor + 1$ 个。

由于前缀 $\gcd$ 如果有变化则至少除以 $2$,得证。

那么接下来我们考虑对每个数为起点进行 DP,注意到我们的过程一定是这个数向一个方向合并直至 $\gcd$ 发生变化,而两个方向都最多改变 $\log$ 次,那么我们在这个简化的状态上进行 DP 即可,状态数为 $\Theta(\log^2 a)$,通过正确的求 $\gcd$ 方法可以使得转移的复杂度总共也是 $\Theta(\log^2 a)$,因此本算法的复杂度为 $\Theta(n\log^2 a)$。

预计得分 $65$。

算法四

本来标算是上面的做法,但是 zhouyuyang 进一步加强了此做法。

我们考虑变换视角,当我们当前合并的一整段为 $[l, r]$ 时,记 $R(l, k)$ 表示左端点为 $l$,下一步行动为向右合并,目前的 $\gcd$ 为从 $l$ 开始的 $\gcd$ 连续段的第 $k$ 段出发,接下来的最小代价。类似的我们可以定义 $L(r, k)$。通过离线基数排序我们可以在 $\Theta(n\log a)$ 时间内计算出 DP 的转移图。时间复杂度为 $\Theta(n\log a)$。

预计得分 $100$。

新年的追逐战

from EntropyIncreaser

算法一

对于 $n = 1$ 的情况,就是要计算出所有无向简单图的连通块数量的求和。

记无向简单图的 EGF 为 $\large G(x) = \sum_{n\ge 0} \frac{2^{\binom n 2} x^n}{n!}$,则联通图的 EGF 为 $C = \ln G$。不难得到连通块数量的 EGF 由枚举连通块如何插入一个图得到,即为 $G\ln G$。

预计得分 $20$。

算法二

我们考虑给我们一组 $G_k$ 的序列之后如何计算连通块数量。

首先考虑在每个图中选一个点,如果某个选的点数的度数为 $0$(我们称其为“孤立点”),则这个点序列在 $H$ 上对应的点是孤立点。

否则我们考虑每个图中选择一个大小 $>1$ 的连通块。考虑这些连通块的乘积得到的连通块有多少。注意到现在每个点都有邻边,且是无向图,因此我们可以在一条边上反复走。两个点序列之间的可达性可以简化为路径长度的奇偶性。

如果两个点在一个存在奇环的图中,那么显然奇数长度和偶数长度的路径都有。

如果两个点在一个二分图中,那么这和他们是否在同一部中有关。

因此我们可以得到:如果选的这 $n$ 个连通块中有 $k$ 个不存在奇环,那么这些连通块的乘积将会给答案贡献 $2^{\max(k - 1, 0)}$ 个连通块。

因此我们只需要知道全体大小为 $m_k$ 的图可以有多少个孤立点,多少个无奇环的连通块,多少个连通块,则可以由此算出答案。

我们考虑染色二分图的 EGF:$B = \sum_{n\ge 0} \sum_{m\ge 0} \frac{\binom{n+m}{n}2^{nm}x^{n+m}}{(n+m)!}$,则无奇环的连通块显然恰有 2 种方法染色,可以得到 EGF 为 $\frac{\ln B}2$,无奇环连通块数量可以通过 $\frac{G\ln B}2$ 表示。

然而 $B$ 的 EGF 这里要 $\Theta(n^2)$ 计算,预计得分 $50$。

算法三

我们考虑如何快速计算 $B$。

我们考虑在一开始生成两部的时候将两部内部的边去掉,也就是乘以 $2^{-\binom n 2}$,可以得到

$$ B = \sum_{n\ge 0} \sum_{m\ge 0} 2^\binom{n + m}2 \frac{2^{-\binom n 2}x^n}{n!} \frac{2^{-\binom m 2}x^m}{m!} $$

可以看到只需要先计算 $\sum_{n\ge 0} \frac{2^{-\binom n 2}x^n}{n!}$ 即可。

这种转换也有另一个名字,叫做 z 变换。

时间复杂度 $\Theta(n\log n)$,预计得分 $100$。

新年的邀请函

idea 来自 bulijiojiodibulido

peehs_moorhsum造了标程/数据,并和提供idea的哥哥一起想了标算;

whzzt哥哥验了题,并提供了另一种标算

fjzzq2002是此题一血,也是全场唯一通过的人

算法一

我会枚举素数,用欧拉判别法判二次剩余!

时间复杂度 $\Theta(m )$,预计得分 $10$。

算法二

由于生成的数在$10^9$范围内,容易发现,会有约$400$个数的素因子只含有前$30$个素数。

利用高斯消元和二次剩余的积性,可以求出来前$30$个素数是否是二次剩余。(在随机的情形下,可以解出所有)

基于二次互反律,我们在枚举$p$模$4$的余数之后,可以知道$p$模前$30$个素数中的每个是否是二次剩余。

我们考虑前$k$个素数的乘积$s$,则$p$模$s$的余数只有约$s/2^k$种(事实上,由于素数$2$以及余数不能为$0$,会更小一些)

取 $k = 10$ 并枚举所有模$s$合法的素数$p$,用欧拉判别法判断。

时间复杂度 $\Theta(s + m / 2^k * log(m) )$。 可以通过前四个点,预计得分$40$。

算法三

在算法二的基础上略加改进。

判断时,我们先判断$p$模前$30$个素数中剩下的那些是否满足;如果不满足直接返回false,否则再用欧拉判别法对每个$t_i$依次判断。

这样单次判断的期望复杂度减到$\Theta(1)$

时间复杂度 $\Theta(s + m / 2^k )$。 可以通过前六个点,预计得分$60$。

算法四

每个素数均可以写成 $ a * s + b $的形式;其中$b$的合法取值只有约$s/2^k$种

对每个$a$,用一个bitset记录每个合法的$b$在当前是否被筛掉。

而后考虑第$k+1$到第$k+u$个素数;用每个素数去筛掉那些模该素数不合法的。

这一步只需要对 $a = 0, 1, ..., $p-1$ $

求$p$个bitset $r_0$, $r_1$, ..., $r_{p-1}$,

表示对应哪些$b$不行

然后对每个$a$,将$a$对应的bitset与$r_{a mod p}$ 的反取交即可。

最后对没有筛掉的所有数进行判断。这样数的个数只有约$m/2^{k+u}$

时间复杂度 $\Theta(s + m/2^{k+u} + u * s / 2 ^ k * p_{k+u} + m / 2^k / w * u)$。

实践中取$k = 8$, $u = 10$最快,可以在400ms内通过最大的测试数据,预计得分$100$。

算法五

考虑模前$10$个素数乘积$r$的余数$u$和模第$11$到$15$个素数乘积$t$的余数$v$。

利用中国剩余定理合并;知模$rt$的余数为$u + s * r * (v - u)$, 其中 $s * r$ 模 $t$ 余$1$。

上式可写为$(u - s * r * u) + s * r * v$,前者只与$u$有关,后者只与$v$有关。

可以Meet in Middle求出所有1e12以内的余数,而后像之前一样检验。

预计得分$100$。

评论

VictorYuan
前排兹瓷
Define
前排兹瓷
luositing
前排
EntropyIncreaser
绝对不鸽
godfatcat
前排,Orz Itst
YuHaoXiang
中排滋磁
star_magic_young
中排滋磁
QuartZ_Z
中排资瓷
duyi
djqtsdy!
hs_black
资瓷资瓷
negiizhao
应该是 chrip Z-transform,是 Z-transform 在有限个点上的值
pink_rabbit
EI 出了可爱的题目!
Itst
所以为什么B题算法五一定可以得到一组合法解啊QAQ
nealchen2003
@matthew99 myy的C题是啥做法啊。
iot
EI 出了可怕的题目!

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。