peehs_moorhsum的博客

博客

标签

原创数据结构蹭热度

UOJ Round #19 题解

2020-04-04 22:14:20 By peehs_moorhsum

谢罪环节

组题的zhouyuyang本来是想拿这场给UR的难度退退烧，特意给三道题都放了较多的部分分。

结果C出题人matthew99和验题人zhouyuyang一直不知道这道题曾经在清华集训2012中出过类似的题，同时也将部分分放得过于宽松，造成了巨大的放送事故。

因此带来的问题zhouyuyang代表本场的管理员向大家谢罪。

本场难度比以往的UR简单许多，大家可以把这场UR当成UER来做。

清扫银河

from hdmmblz，数据 by peehs_moorhsum，标程、题解 by zhouyuyang。

一血是 Iittle_waxberry。

算法1

我会暴力!

枚举所有可行的操作大力出奇迹。

时间复杂度$O(??)$

期望得分:$0 \sim 40$。

算法2

我会优化暴力!

找出原图的生成森林。则对于每条非树边均形成了一个环。

不难证明所有的简单环均可以通过若干次非树边形成的环进行异或得到。

同时对于操作2我们可以拆成若干次单点操作，如果一条边的两个端点均被操作或均为操作则颜色不变，否则颜色改变。

因此有用的操作种数至多为$m+1$，直接跑一次高斯消元解异或方程组，判断是否有解即可。

时间复杂度$O(\frac{Tm^3}{w})$。

期望得分:$70$。

算法3

我会找性质！

性质:我们称所有颜色为1的边形成的子图为目标子图，对于一张图，若目标子图种所有节点度数均为偶数，则总可以通过$m-n+1$次操作得到一组解。

证明:设所有简单环通过异或操作得到的线性空间为环空间。考虑所有$m-n+1$条边代表的简单环。显然这些简单环为环空间的一组基。因此环空间的维数为$m-n+1$。

同时，所有节点度数为偶数的图均在环空间内，因此总可以通过不超过$m-n+1$次操作将所有边变为白色。

因此我们可以将异或方程组的方程个数和未知量个数减少至$n$。异或方程组的限制是关于节点度数的限制。

由于多次操作2总可以合并至一次进行，因此至多进行一次操作2，总操作次数为$m-n+2 \le m+1$。

时间复杂度$O(\frac{Tn^3}{w})$。

期望得分:$100$。

通用测评号

from ridiculos，数据、标程、题解 by zhouyuyang。

一血是 supy。

算法1

我会暴力！

将每种数字出现的次数压入状态。

不难发现状态个数至多为$\binom{2n}{n}$。

时间复杂度$O(\binom{2n}{n}n)$。

期望得分$20$。

算法2

首先注意到答案和操作次数没有关系所以可以认为每次随机选择一个框子放球，而忽略掉只选择没放满的框子的限制。

枚举满了的框子数量 $d(1 \leq d \leq n - 1)$, 我们只需要计算搞到 $d$ 个满框的概率。

令 $S(z)$ 为 $\sum \limits_{i=0}^{z}{\frac{x^{i}}{i!}}$.

我们把每次放球的框子的编号写成一个序列，并写出合法序列方案数的生成函数。

我们强制一个框子为最后一个变成半满的，再强制确定所有的满框子。设最终共有$d$个满的框子，则关于序列长度的生成函数可以表达为:

$$[e^{x} - S(a - 1)]^{d} \times [S(a - 1) - S(b - 1)]^{n-d-1} \times \frac{x^{b-1}}{(b-1)!}$$

将$[e^{x} - S(a - 1)]^{d}$部分二项式展开，得到:

$$(\sum \limits_{i=0}^{d} \binom{i}{d} \times e^{ix} \times [-S(a - 1)]^{d-i}) \times [S(a - 1) - S(b - 1)]^{n-d-1} \times \frac{x^{b-1}}{(b-1)!}$$

$[S(a - 1) - S(b - 1)]^{n-d-1}$ 和 $[S(a - 1)]^{d}$ 可以通过NTT来快速计算。

现在问题转化为若干个$a_{i} \times x^{i} \times e^{jx}$的求和问题,其贡献为:

$\begin{align} & x^{i} \times e^{jx} \\=&\sum \limits_{k=0}{\frac{(k+i)! \times j^{k}}{k! \times n^{k+i+1}}} \\=&\frac{i! \times n^{-i} \times (\frac{n}{n-j})^{i}}{n - j} \\=&\frac{i!}{(n-j)^{i+1}} \end{align}$

这里出现$n^{k+i+1}$的原因是:因为我们计算的是方案数关于长度的生成函数，因此要将概率删去，而计算时没有统计的最后一个元素也要计入。

对于每个 $d$ 别忘了乘上 $\binom{d}{n} \times (n - d) \times d$，这代表着钦定最后一个半满框子和所有满框子位置的方案数。

总复杂度$O(n^{3} \times k \times log(nk))$. 除去NTT部分之外常数很小。

期望得分:$50$。

算法3

from matthew99。

在验题时matthew99给出了一个比上面优秀的算法。

考虑每个框子在全部半满之前被填满的概率，方便起见这里我们计算的是$1$号框满的概率，最终只需要将答案乘以$n$即可。

考虑枚举在$1$号框满的时候没有半满的集合$S$。

显然在确定半满集合时我们只关心$S$和$1$中球排列的相对顺序。因此可以进行简单的DP。

设$f_{i,j}$表示前$i$个元素，总共填了$j$个球的合法操作序列数，可以进行简单转移。

则可计算出$|S|=i$时在所有框之前填满的概率$=\sum \frac{f_{i,j}}{(i+1)^{j+1}}$。

最后进行一次简单的容斥问题即可。

若使用$FFT$优化复杂度可优化至$O(n^3 \log n)$

期望得分:$70 \sim 100$。

Bonus:本题存在$O(n^3)$做法，选手可以自己思考一下。

前进四

from matthew99，数据、标程、题解 by zhouyuyang。

算法1

我会暴力！

直接模拟题目大意。

时间复杂度$O(n^2)$。

期望得分:$10 \sim 25$。

算法2

我会分块！

将数组分为$\frac{n}{S}$块，每块大小为$S$。

维护每个块内的所有不同的后缀最小值。

询问时由于最终被选中的后缀最小值显然为当前块后缀最小值的某一个前缀，因此可以通过二分快速计数。

时间复杂度$O(n \sqrt{n \log n})$。

期望得分:$50 \sim 70$。

算法3

我会线段树！

采用线段树维护一段区间内的所有不同的后缀最小值。

在两段区间合并时后缀最小值序列可以看成是左儿子序列的前缀和右儿子序列拼接起来的结果。

这提示我们可以采用可持久化的数据结构来维护后缀最小值序列。

由于需要支持可持久化的分裂和合并操作，因此可以使用fhq_treap或者可持久化线段树维护。

时间复杂度$O(n\log^2n)$。

期望得分:$50 \sim 70$

算法4

算法三的序列维护部分占用的大量空间。

实际上算法三并不需要维护这个序列。

我们可以在合并过程中通过后缀min来更新每个节点是否可能作为后缀min节点。

因此只需要支持线段树区间加，区间询问最小值个数即可。

空间复杂度可优化至$O(n)$。

期望得分:$70 \sim 85$

算法5

考虑按照数组下标扫描线，维护关于时间的后缀min的线段树。

需要维护以下两种操作：

区间求min。
单点询问这个值被取min了多少次。

采用Segment tree beats维护即可。

因为没有区间加操作因此使用Segment tree beats的时间复杂度为严格$O(n \log n)$。

期望得分:$85 \sim 100$。

seg beats入门

下面简单介绍下 segment tree beats。

如果我们只需要求出一个节点的min，只需要线段树维护区间min即可。

但是如果我们需要求一个节点被取min了多少次，这个问题变得很难维护。

我们对于每个节点维护区间最大值和最小值，修改时一直在线段树上递归到权值最小值比取min的值要大的节点。这样子就可以支持取min次统计了。

很可惜的时，这样子复杂度仍然是$O(nq)$的。

但是我们考虑一下一种特殊情况，如果一个区间内除了最大值，其余所有值均比取min的值要小的情况下，类似的我们可以维护一个最大值被取min了多少次的标记。

当在线段树上递归到如是节点时，只修改最大值和最大值的标记即可。

乍一看复杂度非常不正确，但是可以证明复杂度是$O(n\log n)$的。

这是因为考虑所有权值大于$min$的点。每出现了一次次大值超过min的情况，就会导致权值连续段个数减少$1$。同时一次操作至多增加两个断点。势能分析一波即可。

如果对此有兴趣的同学可以参阅WC2016中吉如一和罗哲正的营员交流，那里有更加详细的描述。

阅读全文

UOJ Round #19

2020-04-01 11:34:17 By peehs_moorhsum

UOJ Round #19将于 4 月 4 日星期六晚上 19：00 举行！比赛将进行 3 个小时，共三道题。

这是UOJ第十九场UOJ Round。UOJ Round还是一如既往的省选及以上难度，欢迎大家来玩owo

1581年4月4日，法兰西斯·德雷克完成环球航行，成为全世界第一个完成环球航行的船长，并被英格兰女王伊丽莎白一世加封骑士头衔。

2020年，跳蚤国决定启动环银河系航行的宏大计划，但是由于跳蚤国的老航天沉迷于工质发动机的研发，跳蚤国的航天科技一直没有大突破。

现在一位叫章北蚤的军人找到了你，他现在迫切需要你的帮助来重启环银河系航行计划！

出题人：hdmmblz, ridiculos, matthew99。

这场成绩将计入rating。

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

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

UPD:比赛结束了。

获奖条件为:

import hashlib
s='得分与其余选手均不同的选手中得分最低的选手，如果不存在这样的选手则为排行榜上第一名的选手。'
m=hashlib.sha256()
m.update(s.encode('utf-8'))
print(m.hexdigest())

9a4e9af313c5a53673cc050fa1e68e10e12c5a042955ec4d6b89229a0d8d90ad

恭喜liji获得抱枕！

阅读全文

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 EntropyIncreaser，zhouyuyang

算法一

考虑进行区间 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: 恭喜前五名的选手！

fjzzq2002
Cyanic
Itst
rushcheyo
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!

于是愉快崩盘

此次比赛，得到重要教训

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

UPDATE:

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

为什么没上交T3啊

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

我还是太弱了(>_<)

阅读全文

共 21 篇博客