NFLSPC #2 Experienced Hacker 题解

2019-11-29 16:17:16 By wzy

这题出了一些锅深感抱歉……(如果想要补请重新下载下发文件)

Problem 1

签到题,当 $a=19260817$ 的时候答案不对。

Problem 2

忘记判一个点是否被多次从优先队列取出的 $\text{Dijkstra}$。显然只要让某个点不断被加入优先队列之后又取出即可,在没有重边的情况下可以卡成 $O(n^2logn)$。

Problem 3

树哈希,哈希值为所有点关于子树 $size$ 的某个函数之积,显然只要构造两棵树,并且他们拥有相同的 $size$ 集合即可。

在 $n=6$ 时可以给出一个构造。两棵树分别为:

$(1,2)(1,3)(2,4)(2,5)(3,6)$

$(1,2)(1,3)(2,4)(4,5)(1,6)$

显然不同构但是 $size$ 集合相同。这个点分值低因为很容易就能对拍出来……

Problem 4

对于 JOI 某题的乱搞,钦定 $a_i,a_j,a_k$ 中至少有 $2$ 个在前 $1000$ 大的当中。

很容易卡,$10^9,1,\cdots,10001,19999,19998,\cdots,10001$ ,并且钦定中间的 $10001$ 恰好在正中即可。

Problem 5

CF 某题的随机化做法,现场有神仙(例如 $\text{PinkRabbit}$)用它 A 了。

大概就是让正确答案出现的概率尽量低,下面是一种构造方案:

32768
1 16384
1 16385
...
1 49151

不难发现答案必然是 $65536k+49152$ 的形式,也就是说概率为 $\frac{1}{65536}$,可以卡掉这个做法。

Problem 6

用 $dp$ 计算路径条数来判断是否存在割点。

我们先考虑生成出路径条数在模意义下为 $0$ 但是有合法路径存在的矩阵,利用生日悖论思想来构造哈希冲突。考虑把随机出的任意两个矩阵一个放在右上角,一个放在左下角让他们互不连通,在最外围留一圈路径,剩余部分填满障碍。那么这个大矩阵的方案数实际上是原来两个矩阵的方案数之和。

因此我们期望随机 $O(\sqrt {mod})$ 次,就可以找到这样一个大矩阵。

考虑如何用路径条数模意义为 $0$ 的矩形构造大矩形,使得其割点判断错误。如下图的构造,中间的点会被误判为割点,但整张图并没有割点。

QAejkn.md.png

其中图上两个画圈的部分代表刚刚构造的模意义下路径条数为 $0$ 的矩形。

Problem 7

来自 $\text{skyline}$ 的乱搞法最短路(虽然好像没啥用(雾))。

第一个 dfs 实际上是把邻接表按照最短路排序,双向松弛并按照最短路图进行搜索。首先可以考虑构造从 $1$ 到 $n$ 的一条链,链上每条边的长度都是 $2$ 并且钦定这条链为最短路径。

为了避免 sort 过快地更新到这条路径,我们可以连接 $(1,p)$ 边权为 $1$,$(p,p+1)$ 边权为 $10^5$,$(p+1,n)$ 边权为 $1$,这样显然第一个 dfs 会优先走这条路径到 $n$,再从 $n$ 返回更新到 $1$。

同时,为了避免第二个 dfs 随机化时走到第一条路径上,我们可以增加多条 $(1,x)(x,n)$ 边权均为 $50001$,由于每次第一遍 dfs 只能把第一条链的进度向前推进一格,而 random_shuffle 很难恰好选择到第一条链上,因此这个构造就需要 $O(链长)$ 次 dfs 才能计算出正确答案。

Problem 8

(以前网络流都是这么写的还跑得贼快……)

不难发现 dfs 时若当前剩余流量为 $0$,它还会多向后跳一条边才返回,导致当前边可能没有流完。因此它的复杂度可以被卡到 $O(增广次数 \times m)=O(m^2n)$,即单路增广 EK 的复杂度。

QAm96U.jpg

上图是一种卡满 EK 增广次数的图,中间的点是一个 $k$ 个点的满二分图,容量都为 1,所有点到二分图、二分图到所有点之间边的容量都是 $k$,剩余边(一条链)的容量都是 $+\infty$。

不难发现第一次 $bfs$ 后会产生 $O(k^2)$ 次单路增广,第二次会走左边第 $3$ 个点到二分图,并且把流退回去走到右边的第三个点,第三次走左边第 $5$ 个点重新经过二分图走到右边第 $5$ 个点,隔着一个点的原因是为了保证到 $t$ 的最短路递增。

这样的图可以把增广次数卡到 $O(k^2\cdot\frac{n-2k}{2})=O(mn)$,求导或者调参可以取到最优。

卡这题错的 $dinic$ 只需要在上图(假的)汇点后面连一大堆边权为 $\inf$ 的重边到点 $p$(把 $m$ 的限制卡满),从点 $p$ 再连一条 $\infty$ 到真正的汇点即可。由于每次增广 $1$ 的流量后都会把最后一条 $\infty$ 的边跳过,所以总复杂度就是 $O(m^2n)$ 的。

Problem 9

只要想起来能对拍就有这个点的分……

其实不需要写出正解(平衡树维护 dp),只需要把乱搞的 $2E7$ 改大一点再对拍就行了,只不过这样会很慢……

注意到其实负数出现概率大时乱搞的出错率高,因此在这样的条件下多开几个进程对拍,几分钟就出来了(真·良心送分。

Problem 10

简单数数题……

考虑集合划分容斥,记 $g_k=\sum_{i=1}^{10^9}i^k$,那么最终的答案就是如下的算式:

$$n!\sum_{\sum_{i=1}^m a_i=n}\frac{\prod g_{a_i}(-1)^{a_i-1}(a_i-1)!}{m!\prod a_i!}$$

显然是一个多项式 exp 的形式,直接计算即可,$g$ 可以求逆出伯努利数之后卷积,跟 pro10 的数组比较一下即可。

$by\ \text{wzy}$

评论

avatar
FCBzym
std

发表评论

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