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$。

Goodbye Jihai 公告

2020-01-16 20:33:13 By peehs_moorhsum

再见,己亥!

鼠年来了!老鼠们都非常兴奋,想过一个红红火火的好年!

但是,猫咪们仍然在欺负老鼠,他们的新年晚会被猫咪彻底打搅了。

于是在除夕前一天,小淘气、舒克、米老鼠、杰瑞、皮卡丘找到了他们的跳蚤朋友,来帮助他们举行盛大的新年宴会!

快来参加uoj的比赛来解决他们的难题吧!

我们将于除夕前一天下午 13:00 到 18:00 举办一场盛大的 Goodbye Jihai 赛。

即:1月23日下午 13:00 到 18:00。比赛时间为 5 小时,共 5 道题 ABCDE 来给大家贺岁~

赛制仍然为OI赛制,水题和省选难度题兼有。欢迎所有人包括萌萌哒CSP选手来玩!

出题人:vfleaking,peehs_moorhsum,EntropyIncreaser,zhouyuyang,bulijiojiodibulido & peehs_moorhsum

这场成绩将计入rating。

参加本次比赛将有机会获得 UOJ 抱枕!获奖条件的 SHA256 码是639ada783755345bda2f08c0e2d32af0319812ba746ee2150b2bf3a09d4f339f。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD: 恭喜前五名的选手!

  1. fjzzq2002
  2. Cyanic
  3. Itst
  4. rushcheyo
  5. sgygd2004
import hashlib
s='所有选手中非AC提交次数最多的,如有多个选择排名最高的'
m=hashlib.sha256()
m.update(s.encode('utf-8'))
print(m.hexdigest())

639ada783755345bda2f08c0e2d32af0319812ba746ee2150b2bf3a09d4f339f

恭喜 Marco_L_Tsien 获得 uoj 抱枕!

关于UOJ题目标签

2019-11-13 20:41:05 By peehs_moorhsum

UOJ本来有题目标签功能..在题库页面里,勾上“显示标签”选项即可看到

但我们发现..第一页的标签很全,后面就越来越少了quq

我现在想重拾这个功能..但由于我水平很菜,自己给标签十分困难

所以我想向可爱的UOJ网友们征集!

有任何关于标签的想法,如某题应该加上/删去某标签,都可以在这个博客下回复;我会在一天内修改ww

谢谢大家qaq

任务列表(持续更新)

2019-08-13 15:37:03 By peehs_moorhsum

呜..从英国回来,发现自己成了一条命选手

但好像还没有..认真学过oi呢..

明明有那么多想学的知识,也有不少时间,但都用来颓废了

这实在是不好qaq

于是我决定,开个帖子监督自己

希望大家多多指教!


想在开学前学会的东西:(看起来学不会,把时限放宽一点?)

1.SAM

2.多项式理论

3.拟阵交

4.弦图,prufer序列相关理论

5.平衡树;LCT

6.线性规划

7.计算几何

8.一般图(最大权)匹配

9.高一文化课(先学会化学吧)

10.DDP

11.析合树

12.BM算法

13.类欧几里得算法


进展:

8.13:开始学多项式了!

造了个快一点的NTT板子(交今年LNR d1t3能过那种

手推了多项式求逆、除法的式子,卡过了luogu上的模板题


8.14:文化课好难啊..先学化学吧..

做了一点五三,约占总量的1/40

学会了多项式ln exp 加减乘除 插值求值 达到了入门水平

造了个封装不错的板子,不用问象要了


8.15:早上大概学会了线性规划,还没写板子

化学做了一点必修一五三

下午打nowcoder多校..真刺激

30min抢了ABC一血开始咸鱼

吃了个饭,慢吞吞地把I分块过掉了(据说可以类欧?)

然后干G,大概1h过了样例,交上去喜提WA

拍也拍过了,看着也没问题,疯狂自闭

队友300iq的F也一样..后来F发现锅了,重测就过了

但我干G一直干到结束..交了一堆无差别的代码,愉快-5

晚上看到了G的标程,喜闻乐见地发现它连小数据都不对?被一个出锅鬼题耗掉了一下午,这就是我咕咕咕的原因了


8.16:又学了点化学

下午去浪了,咕咕咕qaq

晚上写了个线性规划,喜提97

加了一堆优化乱搞,结果变成50了?

不知道哪写挂了。。感觉充满了奇怪的bug。。


8.17:继续学化学

下午咕咕咕

晚上打AGC,开始还挺顺

直到开E,写不对循环的高超代码能力才展现出来

开F时彻底成了演员,细节根本没想,根据样例输出调整边界

最后就喜闻乐见地没过样例

由于前面题过的快,苟了个rk8

但是..好不容易有一次AGC可打..就浪没了啊..感觉不可能进final了[哭]


8.18:学了一个多小时的化学,觉得很无聊

就把昨天的F补了一下

飞快改完,一遍过了?

证实了我的演员本质

被杜老师教了一下拟阵交,大概意会了?

晚上打百度之星,看错题被打爆了..感觉我有点垃圾..


8.19:

上午瞎讲了点数论

下午和学长组队打多校

虽然大家都比较咕(bushi),但玩得很开心

同时深刻感到了自己的菜(帮助队伍罚时上天?

晚上太困了,啥也没干

总而言之,又是摸鱼的一天呢qwq

学长们都好可爱啊

杜老师天上第一


8.20:

由于个人原因,无限期咕咕咕


8.21:

处理完个人问题了?

被xtq教了一下sam,感觉很玄乎

咕咕咕


8.22:准备学一哈ddp

把洛谷板子过掉了


8.23:要开学了,有点难受

昨天xtq写bzoj5210被卡了

我今天也写了一哈,过编译直接对了

但跑得比他还慢

于是我把矩阵乘法的有效位置暴力展开了一下,复制了他的读入优化和heap,就卡过去了?


8.24:打了好久的洛谷比赛

学会了MTT的高明写法及线性递推

然而太兴奋以致脚摔伤了..有点狼狈


8.25:看懂了BM

然后又去颓洛谷了

感觉我有点垃圾..明天要把新学的算法写一下

脚还是没好,走路很狼狈

早上翻ZOJ,看到wujiuwu的签名,就把<退役的你>重温了一遍

其中一句是,“你总说退役遥遥无期,转眼就各奔东西”

突然感到很难受

好像..很多事情再也无法重现..很多人再也不会重逢了?

我好想我的学长们啊..QAQ


8.26:写了一下BM算法,重温了拟阵交

晚上打X round..打得很自闭

感觉我好菜啊..为什么总被卡常啊..

我是不是完全不会oi啊..是不是应该趁早退役啊..

呜呜呜


8.27:写了两道拟阵交,调了调都过了

下午学了一下弦图..过了两个模板题

给杜老师编了一下线性求非弦图的无弦圈,觉得很深刻

然后找了半天,发现莫得这题

一天就这样过去了

好像快开学了诶..QAQ


8.28:快把化学必修一学完了?

中午被某学长请了顿意餐..感觉鹅肝挺好吃的?

下午浪了挺久(

感觉自己有点咕咕咕


8.29:上午vp了一场CF,感觉代码水平8太行

好像已经。。啥都写不对了?

由于日期特殊,下午做了些奇怪的事(

晚上开始肝必修二。。真的好难啊。。谁能带带我啊。。


8.30:上午看了看prufer编码

会证广义cayley定理了(只能有x-y+1位原因:需要有叶子)

写了一哈类欧,过了loj模板题

下午独自听着OI的歌,又开始怀念学长

我向许大大倾诉;她安慰我说,总能再见面的

但愿如此吧qaq

入门了析合树,尽管不会板子,但很轻易地用n^6跑过了上上次CF的F

(一点心愿:在下次开学前,见到oscar/595/fpdqwq/miloris/hld67890各一次


8.31:要开学了,很自闭

和杜老师玩了一下午,十分快乐

(具体过程略去

晚上打百度之星..平均1行代码调30s,手速极慢,罚时上天

然而大家好像..更演一点?送了个并列rk1?


9.1:呜呜明天就要上课了

课本全都没了

下午组队打比赛,然而我一直在浪?感觉有点对不起队友QAQ

zzqnb


9.2:第一天上课

啥也不会

但是喜提语文/物理课代表?

我来认真学一段时间,看看能弄懂多少QAQ


9.4:mgwxh杜老师nb


9.6:打算开个新帖

不定期更了

一种特殊DP的奇怪优化方法

2017-03-09 14:19:03 By peehs_moorhsum

大家好!我是一只蒟蒻初二数竞选手

在一次数学课上,老师给我们留了一道题,我做了出来

我发现它可以出成OI题,于是开心地放到了校内UOJ上

直到WC讲课前,我发现这就是Stilwell的讲课内容ULAM游戏

是不是很有趣呀!

以上就是我写这篇博客的背景(其实真实原因是我给UOJ投题被大神退了)


以下是题面:

在ulam游戏中,考虑至多撒谎一次的情况。

告诉你至多撒谎一次的子集大小n, 不能撒谎的子集大小m,求出在两人都足够聪明的情况下,猜测者至少猜几次才能确认想数者所想的数。

数据范围:n, m <= 10^5000


这道题有明显的(nm)^2 dp解法

利用单调性,可以做到n(m^2)或(n^2)m*logm

再搞一搞,也许能搞到n^2

但是数据这么大,除非使用-wangyisong编译这种复杂度是显然过不了的

那么正解是什么呢?


对于一种特殊的二维DP,满足

1.对大小级别为n的x,y,dp[x][y]级别为f(n); 对级别为logn的dp[x][y], 一定有x,y的级别为f(n)

2.对相同的x,dp[x][y]随y上升单调不减

3.对dp[x1][y1], dp[x2][y2], 其能松弛的dp[x][y]中的x仅与x1,x2相关

那么我们令max[a][b]表示使dp[b][q]为a的最大q值,而后用DP方法维护max。于是我们就把复杂度优化到了 原复杂度*(f(n) / n)的级别


在这道题中,可以证明f(n) = logn + loglogn + k (其中abs(k) <= 2), 且满足以上的三条要求

于是我们就把复杂度优化到了n(m^2)logm啦!

是不是很厉害呢?


然而,我们悲伤地发现,上法还没有单调性dp快

考虑如何优化

在上述的特殊DP中,再加上几个条件

1.考虑max[x1][y1]=z1, max[x2][y2]=z2, 若松弛值q = h(z1, z2), 且h满足对a + b >= c + d, a >= b, c >= d, b >= d, 有h(a, b) >= h(c, d) (若干阶导数满足似乎亦可)

那么称h是"Slime"的(其实是一种类似于凸性的东西)

不难发现,原问题中的dp方程满足这一性质

而对于一个"Slime"的转移方程,其所被松弛的项的x下标是确定的

故此,我们可以将复杂度优化到nmlogm

虽然它仍跑不过,但已经很好了

兹兹不兹兹呀


接下来的优化方式,就比较简单了

可以利用数学方法证明,答案的取值范围介于log(n+m) + loglog(n+m) 正负常数(大概是2,3的范围) 的区间里

计算出与答案松弛相关的max坐标,总数的级别为logn

依次枚举每个答案,判断是否可行即可(其实可以不用枚举,但反正是常数,懒得算那么精确)

总复杂度为logn

其中高精度的运算过程并没有什么用,可以全部优化掉

但是...

我懒得优化了QwQ

于是出了log^2的范围


上课时曾和大神讨论过此问题,他告诉我计算熵的方法在至多撒谎一次的判断上是正确的

想了想,发现并不是...比如3,1就是反例

另外,这种dp能推广到撒谎更多次的情形(证明同理),复杂度为2^klogn 或 (2logn)^k

此类方法显然可以用到更多题上...不过由于我不是专业的OI选手,并未看过类似题目


UPD:我做麻烦了QwQ

但这种dp也许是有用的

我好菜呀O(∩_∩)O~

peehs_moorhsum Avatar