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~

卡常赋格

2017-02-14 16:24:52 By peehs_moorhsum

清晨的卡常题我们傍晚调

我们中午早上调我们夜里调

我们调呀调

我们小点得二十看着挺舒服

那出题目的人他造题他HACK

他HACK当渐进等于标程你聪明的出题毒瘤

他HACK交付OJ等待评测

他发通告召回选手

他发通告召来他的OIER调试

他命令我们写代码


清晨的卡常题我们夜里调

我们早上中午调我们傍晚调

我们调呀调

那出题目的人他造题他HACK

他HACK当渐进等于标程你聪明的出题毒瘤

你退役的参赛选手我们小点得二十看着挺舒服


他高叫把运算写得快些你们这伙你们那帮调试

他抓住手中数据他挥舞他衣服是橙的

写得快些你们这伙优化你们那帮继续写代码


清晨的卡常题我们夜里调

我们中午早上调我们傍晚调

我们调呀调

那出题目的人你聪明的出题毒瘤

你退役的参赛选手他HACK


他高叫把常数写得更小些卡常是来自国际的方针

他高叫你们把题写得更慢些你们就一分没拿滚粗

你们就在小点有个二十看着挺舒服


清晨的卡常题我们夜里调

我们中午调卡常是来自国际的方针

我们傍晚早上调我们调呀调

卡常是来自国际的方针他衣服是橙的

他用数据卡你他卡得很准

那出题的人你聪明的出题毒瘤

他放出标程碾压我们许给我们小点的二十

他HACK出题卡常是来自国际的方针


你聪明的出题毒瘤

你退役的参赛选手


UPD:写于若干月前;值此良机,略加修改,公诸博客

一次失败的USACO

2016-12-21 16:39:15 By peehs_moorhsum

蒟蒻peehs_moorhsum来打USACO了! 这是又一篇骗点击率的毫无营养的流水账

首先,花了2h(包括吃饭)水过了Cu, Ag, Au

第二天打Pt

以下是对打Pt过程中优(xin)秀(suan)表现的描绘

0 - 1h

点开T1, 发现是UR 16 的 C 题……

但没看懂题解,好慌啊

于是写了一发压位卡常,过掉了样例,剩下的全RE

看下一道

1 - 2h

发现是一道水的dp

写写写,交上去WA了?

不开心,重读了一遍题

发现有一处排序把n和m打反了

改完A了

再改T1

意识到会爆int

改成了unsigned int, A了

2 - 3h

看T3,认为是一道水题

打了个贪心,WA了样例

查了查,发现贪心是错的……

想了一个$O(nk) $的dijstra 算法, 但松弛要优化?

3 - 4h

乱搞松弛,认为能水(pian)过(fen)

最后没过样例…… 写了个特判, 交上去, 竟然没T?

但几乎全WA……

调了调,好像调出来了!

此刻离结束还剩三秒

提交

系统显示:

THE CONTEST HAS ENDED!

THE CONTEST HAS ENDED!

THE CONTEST HAS ENDED!

于是愉快崩盘

此次比赛,得到重要教训

不要在比赛过程中吃东西,做作业,等写完再去(⊙﹏⊙)

UPDATE:

结束之后发现不AC也能拿部分分……

为什么没上交T3啊

说到底还是实力问题,没能早些写完

我还是太弱了(>_<)

关于胡搞的一道基础数据结构练习题

2016-09-02 20:38:14 By peehs_moorhsum

QS_Studio

先Orz诸位大神为敬Orz

大家好,我是peehs_moorhsum(moorhsum)

我的同学是一个热爱学习的孩子,今天他想要学习数据结构技巧。

在看了一些博客学了一些姿势、A了UOJ上的基础数据结构练习题后,他想要再找一些题来练练手。于是我给他出了一道题。


内存:256MB | 时间限制:2s

  • 题面

 给定 $m$ 次整系数多项式函数 $f(x)$,支持以下操作:

 操作 $1$:将 $a[l]$ 至 $a[r]$ 变为 $f(a[l])$ 至 $f(a[r])$

 操作 $2$:询问区间 $a[L]$ 至 $a[R]$ 中所有元素之和

 由于答案可能很大,只需输出模 $2016$ 的结果即可。

阅读更多……

共 8 篇博客