标签
暂无

NFLSPC #2 题解合集

2019-11-29 17:01:03 By wzy

NFLSPC #2 Game 题解

2019-11-29 16:51:32 By wzy

引理:两人若都采取最优操作方案,那么 Alice 的胜率等价于所有格子等概率随机颜色后,左边和右边连通的概率。

证明:

如果 Alice 在一个回合前知道 Bob 将会走哪个格子,那么假设他当前的策略也选这个格子,这样至少能够达到引理中胜利的概率,即所有格子颜色随机上下连通的概率。

同理,对于 Bob 来说也能够使用此策略达到“所有格子颜色随机左右连通的概率”的胜率。

因此考虑令 $x$ 为最终的期望得分,从 Alice 来看,$x \ge E($格子随机分配$)$,从 Bob 来看,$x \le E($格子随机分配$)$,因此 $x=E($格子随机分配$)$。

因此只需要计算所有格子颜色随机时,上下连通和左右连通的概率,插头 dp 即可。

NFLSPC #2 Magic 题解

2019-11-29 16:44:15 By wzy

先转曼哈顿,如果所有点的 $y=0$ 的话,那么任意一个匹配必然都经过 $x$ 的中位数(最大值的充要条件)。

取 $x$ 坐标的中位数 $a$ 和 $y$ 坐标的中位数 $b$ 得到点 $(a,b)$,然后以这个点为中心划分成一个十字,左上和右下匹配,左下和右上匹配即可。

假设 $n=2k$ 为偶数,那么左半边和右半边都有 $k$ 个,上半边和下半边也都有 $k$ 个。设左上有 $p$ 个,则右下有 $k-(k-p)=p$ 个,可以进行一一匹配;同理,左下也可以和右上进行一一匹配。

$n$ 为奇数时就记一下两维的前缀和,暴力计算出最优解应该删掉哪个点即可。复杂度瓶颈在 sort 上,$O(n \log n)$。

NFLSPC #2 LinQin 题解

2019-11-29 16:36:45 By wzy

$type=0$ 是给莫队的,$m \le 10^5$ 是给按序列分块的(不过好像没卡掉)

做法 1

把区间排序,最后的答案必然在相邻两项中产生。不妨考虑值域分块,即按照值所在的范围把原序列划分为若干个子序列。

不妨令块大小为 $B$,经过这样的划分之后,一次询问必然能分成 $\frac{n}{B}$ 个区间,每个区间在对应的值域块内。

对于每个值域块,用区间 dp 预处理出答案,复杂度 $O(nB)$;对于跨块的情况,不难发现只需要计算某个区间最大值和最小值,st 表即可。

因此总复杂度 $O(nB+\frac{nm}{B})$,$B=\sqrt {nm}$ 最优,复杂度 $O(n\sqrt m)$。

做法 2

考虑从前向后扫统计以当前位置结尾,每个位置作为开头的答案。不妨假设大的元素必然是靠后的那个,考虑找到当前前缀中最大的、且比当前位置小的数字,它能够产生一个前缀的贡献;再找到最大数字到当前数字这个区间中最大的、且小于当前的数字……一个一个更新计算贡献即可,贡献大概是个区间 set,可以用线段树维护。

这样的做法会被卡到 $O(n^2logn)$,因此可以思考一下性质。假设当前元素为 $x$,找到的最大值为 $a$,$a$ 右边找到的最大值为 $b(b < a < x)$。如果 $b$ 和 $x$ 计算了贡献,那么 $b$ 必须满足 $a \ge \frac{x+b}{2}$ 才能进行更新,否则 $a,b$ 会产生更优的贡献。

因此总共只需要更新 $O(\log 10^9)$ 个元素,强制在线可以用主席树维护区间 set,总复杂度 $O(n\log n\log 10^9)$。

NFLSPC #2 Matrix 题解

2019-11-29 16:20:19 By wzy

不难发现合法矩阵的充要条件是每条从右上到左下的斜线上,没有相邻两个颜色相同的格子。

(应该很好证,就不说了)

于是答案就是 $k^{n+m-1}(k-1)^{(n-1)(m-1)}$,快速幂即可。

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

NFLSPC #2 风 题解

2019-11-28 23:02:04 By wzy

我们先考虑另一个相似的问题:如果问的是每行第一个数的和的最大值该如何处理?

这是一个经典做法 考虑枚举平移次数模2^4*3^2*5^2*7的余数 然后要确定每行第一个数只需要知道平移次数模至多一种质数的幂的余数了 于是把数按对应的质数分组 每组是独立的 组内枚举即可 组之间的合并是直接加

回到这道题 这个做法问题出在了哪呢?

合并的时候需要fwt 导致要做很多很多次fwt 严重超时

我们注意到

1 外层枚举的次数不能太大

2 内层枚举的次数只要不比一次fwt慢太多都行

于是我们有了一个改进版的做法

我们先进行一些不影响答案的操作以便于叙述

1 如果n小于50 将n扩大为50 新的位置全部填0

2 我们对前25行依次做如下操作:

对第i行第j列的数x 我们将第2i行第j列和第2i行第i+j列的数异或x 然后把第i行第j列的数变成0

现在我们面对的是恰好50行数 前25行是0不用考虑

考虑第29 31 37 41 43 47行这六行数 发现这行数哪个在第一个不影响其他任何一行 所有我们最后单独考虑再合并即可

我们枚举平移次数模6的余数 然后把剩下的数字分成两组

第一组:27 28 30 32 33 35 36 40 42 44 45 48 49 50

第二组:26 34 38 39 46

注意到第一组的数因子都属于2 3 5 7 11而第二组的数在知道模6余数后只要再知道模某个唯一的质数的余数即可知道模它的余数

而且在知道平移次数模6的余数的情况下 第一二组数的异或和是独立的

对第一组数 我们枚举平移次数模2^5*3^3*5^2*7^2*11的余数(事实上只有2^4*3^2*5^2*7^2*11种) 就可以知道所有第一组数第一个数的异或和的所有可能值

对第二组数 为了减少fwt合并的次数 我们直接一起考虑 枚举平移次数模2*3*13*17*19*23的余数(事实上只有13*17*19*23种) 就可以知道所有第二组数第一个数的异或和的所有可能值

然后我们我们并第一组数和第二组数的所有可能值

我们把枚举的6种大情况的所有可能值再用fwt合并 然后和外面的第29 31 37 41 43 47行这六行数合并(可以fwt或者直接dp)

这道题大体已经做完了 但是还有几个注意点

1 fwt里每个值记录的是每个数作为异或和的方案数 不做处理肯定爆long long 怎么处理呢?

追求正确性的做法:每次fwt合并完都逆fwt 然后把所有非0数变成1 依然不改变每个数是否可能成为异或和 缺点是每次都要逆fwt 比较慢

追求效率的做法:考率模一个数 比如1000000007 这样不用每次逆fwt了 会快得多但是有概率出错(就是某个异或和出现次数是模数若干倍时)在模数是1000000000数量级时出错率在0.001左右

2 如果我们在枚举平移次数模2^5*3^3*5^2*7^2*11的余数的循环内部一一查看这14行第一个数是多少 将会很慢

考虑先枚举模2^5*3^3*5^2*7^2的余数 然后查看已经确定的12行第一个数是多少 然后再枚举模2^5*3^3*5^2*7^2*11的余数(只有11种情况) 再看第33和44行第一个数是多少 这样可以快很多

其实n到60也可以在1s内完成(大循环枚举模12的余数) 但是有点卡常 所有就只放了n=50

$by\ \text{skyline}$

NFLSPC #2 Polynomial 题解

2019-11-28 22:58:41 By wzy

考虑第一次操作是 $(x+c)^k$,那么可以把最终的多项式表示成一个和 $x+c$ 有关的多项式,即计算:

$$g(x+c)=f(x),g(x)=f(x-c)$$

$$g(x)=\sum_{i=0}^{n-1}(x-c)^ia_{i}=\sum_{i=0}^{n-1}a_i\sum_{j=0}^ix^j(-c)^{i-j}\binom{i}{j}$$

交换求和顺序之后是一个卷积的形式,可以多项式乘法求出。

考虑如何计算 $c$,不难发现只需要考虑最高项和次高项的系数即可列方程解得 $c$,由于 $k>1$,因此每次非零系数的数量至少减半,可以压在一起处理。

总复杂度 $T(n)=T(n/2)+O(nlogn)=O(nlogn)$。

NFLSPC #2 火 题解

2019-11-28 22:51:14 By wzy

把第i行第j列的格子拆成aij个点(i,j,1),...,(i,j,aij) (i,j,k)表示第i行第j列的格子被已经烧了k秒的状态

考虑bfs

(i,j,k)向(i,j,k+1)连一条边(k < aij)

(i,j,aij)向四周连边((i-1,j,1)(i+1,j,1)(i,j-1,1)(i,j+1,1)如果目标点不存在不用连)

把所有初始被点燃的点一起放入队列bfs 最后一个被bfs到的点的时间就是答案(如果认为初始点时间是1) 时间复杂度o(n^2*a)

当然 因为时限很松 常数不大的dijkstra也可以通过此题

$by\ \text{skyline}$

NFLSPC #2 键 题解

2019-11-28 22:49:32 By wzy

题目名字起坏了 偏离了我的风格= =

首先有一个在5*n^2次操作内将一个n*(n-1)的长方形填入自己想要的数字的方法

我们以填好前n-1列为例

首先按从上到下 从左到右的顺序填前n-1行n-1列的数:

我们要填在第i行第j列的数字在第x行第y列 这么移呢?

1 i=x

把这两个数字都沿列移到第n行 平移第n行使数字从第y列移动到第j列 然后把两列按列推回原位即可

2 其他情况

把这两个数字都沿行推到第n列 平移第n列使数字从第x行移动到第i行 然后把第i行沿行推回原位即可

注意到这两种操作都没有改变已经填的数字

然后填第n行

我们从左到右填

1 这个数字现在在第n行

把这个数字移到第n列 把第n列上移一格 把现在的格子移到第n列 把第n列下移一格 把第n行移回原位即可

2 这个数字现在不在第n行

把现在的格子移到第n列 把数沿列移动道第n行 把第n行移回原位即可

但是 怎么处理原问题呢?

注意到 每行的key至多n/3下取整个 把这个数字乘上n 和key三个字母的最小出现次数取较小值就是key出现次数的理论最大值

我们将给出一种达到最大值的构造

我们将key从上到下 从左到右的依次画在我们的目标方格表中 剩下的随便填

观察目标方格表 有两种情况

1 第n行没有key

我们只要将前n-1行用上面介绍的方法填上目标方格表里希望的数字即可

最后一行没有key 长什么样无所谓

2 第n行有key

那么第一列一定全是k

我们只要将后n-1列用上面介绍的方法填上目标方格表里希望的数字即可

第一列全是k 所以是什么顺序也无所谓

所有情况都给出了达到理论最大值的构造 并且不会超过5*n^2次平移

注:上移x格和左移x格在输出时应分别改写为下移n-x格和右移n-x格

$by\ \text{skyline}$

共 14 篇博客