NOIp 2017

结论题?再见

Posted by Ghastlcon on November 12, 2017
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 NOIp 2017

$\text{NOIp }2017$

初三玩 $\text{TG}$,暂时 $\text{AFO.}$

感觉跟去年的画风完全不同。

时间分配极度不均匀。

想看 $\text{Solution}$ 的直接翻 $\text{Catalog}$ 。

$\text{Day }[-11,-1)$

区间内共有 $9$ 天,于是我们就做了 $\text{NOIp 9}$ 连测。

$9$ 连测

借用 $\text{GDKOI 2017 Day2}$ 的密码,$\texttt{With-no-REGRET}$。

时间非常紧就对了。

$10.30$,不请自来地滚来了微格室,见到了 $\text{Dalao}$ 们。下午又搞 $\text{SMOJ}$ 的模拟赛,水到 $230$ 。

后来比赛也是时高时低,自以为码力很稳的我有次还连炸 $2$ 题(贪心与分块)。

在微格室整天 $\%\%\%\text{ KsCla}$,抬头看见 $\text{KsCla}$ 在看屏幕,对视几秒,然后又同时低头画题。

(我还不知道我要求的前缀加等差数列前缀最小值怎么搞)

$\text{Day }\mathrm{-1}$

整天的模板题:

模板集合

考试前 $1$ 天,我突然发现自己还不会树链剖分,然而按照惯例不考,就敲了下树套树的模板。虽然因为 $2$ 分而成了 $\log^3$,然而还是 $\text{A}$ 了($\log^2$ 被卡 $\text{QAQ}$)。最后还手动 $\text{YY}$ 出了高斯消元……

感谢我刷的平衡树模板,最后关头帮我多拿 $30\%$ 。

我就不应该玩这么多的 $\text{ExGCD}$ 。

$\text{Day }0$

被 $\text{Ufowoqqqo}$ 在机房捕捉

到达之后发现 $\text{LGJ}$ 居然在用 $\mathrm O(n!)$ 的方法来枚举最优的入住方案。

然后和 $\text{Ufowoqqqo}$ 同房,晚上跟 $\text{Monad,Ufowoqqqo,aspe}$ 滚出去随便吃了点东西。

在 $\text{sc}$ 的机器上玩了几个比较容易写错的算法。

本来还想跟 $\text{KsCla}$ 再玩玩 $\text{ExGCD}$ 。

没什么好说的。早早睡了。睡前看了下数论,图论和数据结构绝对不虚。

$\text{Day }1$

$\text{P1}$ 的 $60\%$ 很可做,先玩个暴力动态规划。

题意找 $k(ax+by)=k$?不过要求 $x,y\geq 0$ 很烦人。估计是个 $\text{ExGCD}$ 。

手玩 $\text{ExGCD}$ 用了 $1\texttt{h}$,最终结论是找最大的 $k$ 使得:

向下取整很烦人。发现自己推不出来,弃。


$\text{P2}$ 纯净模拟。改了几下就过大数据了(sscanf 大法好)。


$\text{P3}$ 貌似很可做,求出最短路然后 $\text{SPFA}$ 转移。

(按照距离排序然后动态规划拿 $70\%$ 啊!没有 $0$ 的情况下不可能走回头的)

发现自己过不了大数据。但是拍不出错。

很虚。思考要不要改成 $\text{Heap}+\text{Dijkstra}$ 。然而最终也没打。


当我听到 $\text{P1}$ 答案是 $ab-a-b$ 的时候心情无法形容。

周围的并没有准确的证明。“感性”的倒是有。

反思下,平时比赛不会做就打表找,为什么现在却忘记了?

发挥不出来又有什么鬼用。


晚上玩。

在电视上用遥控器写代码并成功 $\text{A}$ 过 $\text{PJ P1}$ 。

去问 $\text{KsCla}$ 能不能补 $\text{ExGCD}$ 的做法,然而 $\text{KsCla}$ 并不在房间里。

结果发现煎堆用 $\text{ExGCD}$ 推了 $2.5\texttt{h}$ 过掉了这题。

$\%\%\%$

$\text{Day }2$

起来的时候想着今天要是不能 $\text{AK}$ 的话就没有 $500$ 了……

欢声笑语中打出 $\text{GG}$ 。

$\text{P4}$ 无脑 $\text{BFS}$ 。没忘记 unsigned long long


$\text{P5}$ 疑似状态压缩。

但是我发现我不能压边。

偏偏价格又跟深度(边)有关。

只能上错误的状态压缩。居然还过了 $2$ 个小数据。


$\text{P6}$ 看起来很无脑。

似乎删掉某个点只会对后面的造成影响。

以为直接跳就行了,结果发现跳的区间内可能还会有修改。

不能保证时间复杂度。

$\text{YY}$ 之后发现无果,貌似纯暴力有 $30\%$ 。

然而另外的 $q\leq 500,n\leq 50000$,只能说明很多的 $x$ 坐标没有出现过。

对于 $x=1$ 的点,暴力上 $\text{Splay}$ 维护序列即可(再次感谢刷的模板)。

调对已经是 $11:20$ 了,拍不出错。


似乎都在 $\text{P5}$ 写了贪心……

起码今天不像昨天那样留下 $60\%$ 的遗憾吧。

$\text{Memory}$

原地爆炸。

现在打着这篇玩泥巴记。

明天就要滚回去继续上文化课了。

想起这仅仅 $2$ 周的停课,回头看看 $8$ 小时前 $\text{NOIp}$ 离场的那短暂的 $1$ 刻,忽然发现有点不舍。

胜利即送命

$\text{OI}$ 之路不再是阻且长了,看着高二的指导们逐步走向退役,不知道自己是什么感受。

只剩下最后 $2$ 年了,自己好好珍惜。

但是这是不可能的事呢

$\text{Solution}$

$\text{P1}$

$30\%$

从大到小枚举答案,逐个验证。

虽然在考场上是不知道时间复杂度的,但是从 $100\%$ 做法可以得知是 $\mathrm O((ab)^2)$ 的。

$60\%$

$f[i]$ 表示能否组成价格为 $i$

最后从大到小找到首个为 $\text{false}$ 的 $f[i]$,$i$ 即为答案。

时间复杂度 $\mathrm O(ab)$ 。

$100\%$

题目要求找最大的 $k$,使得不存在整数对 $(x,y)$,满足


注意到题目规定 $\gcd(a,b)=1$,所以肯定有整数对 $(x,y)$,满足

把 $k$ 乘进以上,得

所以在不要求 $(x,y\geq 0)$ 的情况下(就相当于可以找零),能够支付任意的价格 $k$ 。

题目保证有无法支付的,所以 $x,y$ 中,必然有 $1$ 个 $<0$,另 $1$ 个 $>0$ 。

假设 $x<0,y>0$(否则可以交换 $(a,b),(x,y)$)

下面的 $x,y$ 都已经做了赋值操作:x *= k, y *= k 。不难发现乘上 $k$ 之后仍然有 $x<0,y>0$ 。

这意味着我们可以每次给 $x$ 加上 $b$,给 $y$ 减去 $a$ 而保持等式 $ax+by=k$ 的平衡。

现在 $x<0$,那么我们希望加上越多的 $b$ 越好,而最多可以加上 $\left \lfloor \frac{y}{a} \right \rfloor$ 个 $b$ 。

加到最后,如果仍然不是合法的,这就意味着有 $x<0,0\leq y<a$ 。

我们现在要让 $k$ 最大,而 $k=ax+by$,即 $x,y$ 均尽量大。

$x<0,0\leq y<a$,因此取得 $x=-1,y=a-1$ 。

代入,得 $k=ax+by=a(-1)+b(a-1)=ab-a-b$ 。

时间复杂度没什么好说了吧……常数级别 $\mathrm O(1)$ 。

math.cpp


用另外的方法证明答案是 $ab-a-b$ 。

反证法。假设 $ab-a-b$ 能够被表示成 $ax+by=k\; \; (x,y\geq 0)$ 的形式

同时 $x+1,b$ 均为整数,所以 $\frac{b(y+1)}{a}$ 是整数,即

题目规定有 $\gcd(a,b)=1$,所以最终得到

同理得

那么设 $y+1=pa,x+1=qb$,代入 $a(x+1)+b(y+1)=ab$

最终得到了 $p+q=1$ 。然而按照题目规定与及我们的定义

得到了矛盾的结果。因此原命题得证,$ab-a-b$ 不能表示成 $ax+by=k\; \; (x,y\geq 0)$ 的形式。


我们现在还需要证明比 $ab-a-b$ 大的所有数 $k$ 都能表示成 $ax+by=k\; \; (x,y\geq 0)$ 。

先把 $k$ 拆开,即表示成 $k=ab-a-b+s\; \; (s>0)$ 。

找到最小的 $t$,满足 $tb\equiv k\equiv s-a\text{ (mod }a)$ 。由于 $\gcd(a,b)=1$,所以肯定存在这样的 $t$ 。

此时 $t<a$,否则可以不断将 $t$ 减去 $a$,且保持原模等式成立

根据找的 $t$ 的定义,得

综上,$k$ 可以表示成 $k=a\frac{k-bt}{a}+bt$ 。

$\text{P2}$

$100\%$

模拟,没有什么可说的。

$\text{ERR}$ 的情况直接用栈模拟就可以了。

复杂度线性 $\mathrm O(l)$ 。

complexity.cpp

$\text{P3}$

$\text{Day }1$ 里唯 $1$ 有营养的题。

$30\%$

直接统计最短路数量。

由于没有 $0$ 边,所以非常简单。

$60\%$

没有 $0$ 边。

把 $1$ 号点到点 $x$ 的最短距离算出来,记为 $f[x]$ 。

那么到达某个点 $x$ 的距离是不能够超过 $f[x]+k$ 的。

拆点,把点 $x$ 拆成 $k+1$ 个点 $x(0),x(1),..,x(k)$ 。$x(y)$ 代表到达了 $x$ 点,且现在已经走的距离是 $f[x]+y$ 。

再次强调没有 $0$ 边。这意味着没有后效性:从点 $u$ 走到了点 $v$,那么点 $v$ 再走回来肯定不优。

把拆出来的 $n(k+1)$ 个点 $x(y)$ 按照 $f[x]+y$ 从小到大排序:然后扫过去,对于点 $x(y)$,枚举 $x$ 的所有出边,尝试累加答案。

时间复杂度 $\mathrm O(m\log n+nk\log(nk))$ 。最短路 $\text{Heap}+\text{Dijkstra}$ 保平安。

这样子会 $\text{TLE}$ 最后 $30\%$ 的数据,顺带 $\text{WA}$ 第 $6$ 个点。

写挂了,白白丢了 $50\%$ 的分数。

$70\%$

时间主要浪费在排序上:$\mathrm O(nk\log(nk))$ 已经是难以承受的了。

我们可以不拆点:单纯对于所有点按照 $f[x]$ 从小到大排序。

转移的时候,我们先枚举 $y$ 再枚举 $x$:如果先枚举附加的长度 $y$,那么从 $x$ 走到它可以到达的任意点 $k$,到达 $k$ 的距离肯定不小于 $f[k]+y$ 。

时间复杂度 $\mathrm O(m\log n+n\log n)=o((m+n)\log n)$ 。

$100\%$

如果想到了 $70\%$,那么 $100\%$ 就很轻松了。

现在的问题是 $0$ 边 $2$ 端的点的顺序不能确定:$a\overset{0}{\rightarrow}b\overset{0}{\rightarrow}c$ 内,$f[a]=f[b]=f[c]$,此时应该按照 $a,b,c$ 的顺序去更新,然而排序的时候是根本不知道在 $f[x]+y$ 相同的时候应该怎么处理。

所以我们还需要拓扑序:把原图中非 $0$ 边删去,建立新图,跑拓扑排序得到拓扑序。

那么排序的时候按照 $f[x]+y$ 作为首关键字,$x$ 在拓扑序中的位置作为次关键字从小到大排序就可以了。


考虑有无数条合法路径的情况。

即相当于在某条从 $1$ 到 $n$ 的长度不超过 $f[n]+k$ 的路径上,有着 $1$ 个 $0$

记点 $x$ 到点 $n$ 的最短距离为 $g[x]$ 。

对于同 $1$ 个 $0$ 环上的任意 $2$ 个点 $u,v$,都必然有 $f[u]=f[v],g[u]=g[v]$ 。

知道了这个就很好办了:对于新图(即只留下 $0$ 边的图)缩点,遍历所有点数不少于 $2$ 的强连通分量。

对于这个强连通分量中的随便 $1$ 个点 $x$,如果有 $f[x]+g[x]\leq f[n]+k$,就意味着可以有长度不超过 $f[n]+k$ 的路径经过这个环。所以此时最接输出 $-1$ 就可以了。

拓扑序和缩点均为线性,时间复杂度仍为 $\mathrm O((m+n)\log n)$ 。

和其他的题解不同,这种做法非常好写。

请注意常数因子带来的程序效率上的影响。

park.cpp

$\text{P4}$

$100\%$

无脑 $\text{BFS}$,别忘记在求距离的时候用 unsigned long long

cheese.cpp

$\text{P5}$

$20\%$

输入的图是树,直接 $\mathrm O(n^2)$ 枚举根统计答案。

$40\%$

所有的 $v$ 值相等。

枚举根,$\text{BFS}$ 计算答案。$\mathrm O(n^2)$ 。

$70\%$

$n\leq 8$,据出题人所说是暴力 $\text{DFS}$ 。

反正我是没时间打这部分的暴力。

$100\%$

首先如果你的 $\text{DFS}$ 剪枝足够优秀说不定可以跑过去……

然后注意 $n\leq 12$,这在提示我们状态压缩。

在最外层循环先枚举根结点 $r$ 。

如果直接用 $f[i]$ 表示选中了集合为 $i$ 的点的最小价值,明显是不行的:加入新的点 $x$ 之后,不知道 $x$ 的深度(即到 $r$ 的距离)到底是多少。

所以还需要记录深度,按转移:$f[i][j]$ 表示选中了集合为 $i$ 的点,当前已经放了 $j$ 层(即 $i$ 中所有点到达 $r$ 的距离最多为 $j$),需要的最少花费。

记 $g[i][j]$ 为使得集合 $i$ 和集合 $j$ 的点相连需要的最小边权和(需满足 $i\cap j=\varnothing$),则枚举恰好在第 $j$ 层的点集 $t$(即枚举 $i$ 的子集)转移

注意,当 $t$ 中的结点和 $i\setminus t$ 中的结点相连时,$t$ 中结点可能会有深度不达到 $j$ 层的(因为不保证和 $t$ 相连的每个点都在第 $j-1$ 层),但是这并不会影响正确性:正确的转移显然是不会被遗漏的,错误的转移也只会把它的花费算多(比第 $j-1$ 层要浅,然而强制当成是第 $j-1$ 层)而不会算少。

根结点为 $r$ 时,边界 $f[{r}][0]=0$,其它的 $\infty$ 。答案为 $\forall i\in [0,n],\min(f[{0,1,..,n-1}][i])$ 。

至于 $g$ 数组,也可以用状态压缩预处理。利用最小表示法(如果不理解,请看 $\text{NOIp 2016 TG P6}$ 的题解)随便找出元素 $t\in j$,然后枚举和 $t$ 连接的结点 $p\in i$

其中 $l[t][p]$ 表示边 $t\leftrightarrow p$ 的长度。边界 $f[i][\varnothing]=0$ 。

计算 $f$ 由于是子集转移,并且还要枚举根 $r$,所以是 $\mathrm O(n^23^n)$ 的。计算 $g$ 时,由于枚举的 $j$ 要求 $i\cap j=\varnothing$,所以相当于是在 $i$ 的补集中枚举子集,因此 $\mathrm O(n3^n)$ 。

总时间复杂度 $\mathrm O(n^23^n)$ 。

请注意常数因子带来的程序效率上的影响。


写 $1$ 遍就会发现没有必要枚举 $r$ 。

边界变成了 $\forall i\in [0,n),f[{i}][0]=0$,其它的 $\infty$ 。

最终答案仍然是 $\forall i\in [0,n],\min(f[{0,1,..,n-1}][i])$ 。

总时间复杂度 $\mathrm O(n3^n)$ 。

treasure.cpp

$\text{P6}$

$30\%$

直接上 $\mathrm O(qnm)$ 暴力模拟。

$50\%$

$n,q$ 差距非常大:$n,m\leq 5\cdot 10^4,q\leq 500$ 。

在暴力的基础上,注意到修改 $(x,y)$ 只会影响到第 $x$ 行和第 $m$ 列。

所以离线,记录下询问里出现过的 $x$ 坐标,用链表维护;同时链表维护第 $m$ 列。

时间复杂度 $\mathrm O(qm)$ 。

$80\%$

观察所有 $x=1$ 的点。

相当于是在链上操作:询问某个元素的值,然后将其删除并且放在最后。

可以上 $\mathrm O(q\log^2m)$ 的 $2$ 分套树状数组,也可以无脑 $\mathrm O(q\log m)$ 玩 $\text{Splay}$ 。

$100\%$

先试试暴力维护 $n+1$ 个 $\text{Splay}$(每行的第 $m$ 个元素单独用 $1$ 个 $\text{Splay}$ 维护)。

时间复杂度 $\mathrm O(q\log m)$,然而空间复杂度 $\mathrm V(nm)$ 。

注意到 $n,m,q\leq 3\cdot 10^5$ 。

$n,q$ 是同阶的,意味着在 $\text{Splay}$ 里面有很多的元素是从来就没有被移动过的,并且这些元素的值都可以用“区间开头的值 + 偏移”来表示。

所以建立 $\text{Splay}$ 的时候,每个 $\text{Splay}$ 里都只有 $1$ 个结点代表区间 $[1,m)$ 。

询问 $(x,y)$ 的时候,在第 $x$ 行的 $\text{Splay}$ 上找到第 $y$ 个元素,顺序做 $\text{Split,Delete,Insert}$ 即可。

注意不能够 $\text{Merge}$,因为区间并不是连续的,“区间开头的值 + 偏移”会失效。

时间复杂度 $\mathrm O(q\log m)$,空间复杂度 $\mathrm V(q+n)$ 。

请注意常数因子带来的程序效率上的影响。

phalanx.cpp